Add skeleton circular queue file.

base/containers/circular_deque_unittest.cc

+// Copyright 2017 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "base/containers/circular_deque.h"
+
+#include "base/test/copy_only_int.h"
+#include "base/test/move_only_int.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+using base::internal::VectorBuffer;
+
+namespace base {
+
+namespace {
+
+circular_deque<int> MakeSequence(size_t max) {
+  circular_deque<int> ret;
+  for (size_t i = 0; i < max; i++)
+    ret.push_back(i);
+  return ret;
+}
+
+// Cycles through the queue, popping items from the back and pushing items
+// at the front to validate behavior across different configurations of the
+// queue in relation to the underlying buffer. The tester closure is run for
+// each cycle.
+template <class QueueT, class Tester>
+void CycleTest(circular_deque<QueueT>& queue, const Tester& tester) {
+  size_t steps = queue.size() * 2;
+  for (size_t i = 0; i < steps; i++) {
+    tester(queue, i);
+    queue.pop_back();
+    queue.push_front(QueueT());
+  }
+}
+
+}  // namespace
+
+TEST(CircularDeque, FillConstructor) {
+  constexpr size_t num_elts = 9;
+
+  std::vector<int> foo(15);
+  EXPECT_EQ(15u, foo.size());
+
+  // Fill with default constructor.
+  {
+    circular_deque<int> buf(num_elts);
+
+    EXPECT_EQ(num_elts, buf.size());
+    EXPECT_EQ(num_elts, static_cast<size_t>(buf.end() - buf.begin()));
+
+    for (size_t i = 0; i < num_elts; i++)
+      EXPECT_EQ(0, buf[i]);
+  }
+
+  // Fill with explicit value.
+  {
+    int value = 199;
+    circular_deque<int> buf(num_elts, value);
+
+    EXPECT_EQ(num_elts, buf.size());
+    EXPECT_EQ(num_elts, static_cast<size_t>(buf.end() - buf.begin()));
+
+    for (size_t i = 0; i < num_elts; i++)
+      EXPECT_EQ(value, buf[i]);
+  }
+}
+
+TEST(CircularDeque, CopyAndRangeConstructor) {
+  int values[] = {1, 2, 3, 4, 5, 6};
+  circular_deque<CopyOnlyInt> first(std::begin(values), std::end(values));
+
+  circular_deque<CopyOnlyInt> second(first);
+  EXPECT_EQ(6u, second.size());
+  for (int i = 0; i < 6; i++)
+    EXPECT_EQ(i + 1, second[i].data());
+}
+
+TEST(CircularDeque, MoveConstructor) {
+  int values[] = {1, 2, 3, 4, 5, 6};
+  circular_deque<MoveOnlyInt> first(std::begin(values), std::end(values));
+
+  circular_deque<MoveOnlyInt> second(std::move(first));
+  EXPECT_TRUE(first.empty());
+  EXPECT_EQ(6u, second.size());
+  for (int i = 0; i < 6; i++)
+    EXPECT_EQ(i + 1, second[i].data());
+}
+
+TEST(CircularDeque, InitializerListConstructor) {
+  circular_deque<int> empty({});
+  ASSERT_TRUE(empty.empty());
+
+  circular_deque<int> first({1, 2, 3, 4, 5, 6});
+  EXPECT_EQ(6u, first.size());
+  for (int i = 0; i < 6; i++)
+    EXPECT_EQ(i + 1, first[i]);
+}
+
+TEST(CircularDeque, EqualsCopy) {
+  circular_deque<int> first = {1, 2, 3, 4, 5, 6};
+  circular_deque<int> copy;
+  EXPECT_TRUE(copy.empty());
+  copy = first;
+  EXPECT_EQ(6u, copy.size());
+  for (int i = 0; i < 6; i++) {
+    EXPECT_EQ(i + 1, first[i]);
+    EXPECT_EQ(i + 1, copy[i]);
+    EXPECT_NE(&first[i], &copy[i]);
+  }
+}
+
+TEST(CircularDeque, EqualsMove) {
+  circular_deque<int> first = {1, 2, 3, 4, 5, 6};
+  circular_deque<int> move;
+  EXPECT_TRUE(move.empty());
+  move = std::move(first);
+  EXPECT_TRUE(first.empty());
+  EXPECT_EQ(6u, move.size());
+  for (int i = 0; i < 6; i++)
+    EXPECT_EQ(i + 1, move[i]);
+}
+
+TEST(CircularDeque, EqualsInitializerList) {
+  circular_deque<int> q;
+  EXPECT_TRUE(q.empty());
+  q = {1, 2, 3, 4, 5, 6};
+  EXPECT_EQ(6u, q.size());
+  for (int i = 0; i < 6; i++)
+    EXPECT_EQ(i + 1, q[i]);
+}
+
+TEST(CircularDeque, AssignCountValue) {
+  circular_deque<int> empty;
+  empty.assign(0, 52);
+  EXPECT_EQ(0u, empty.size());
+
+  circular_deque<int> full;
+  size_t count = 13;
+  int value = 12345;
+  full.assign(count, value);
+  EXPECT_EQ(count, full.size());
+
+  for (size_t i = 0; i < count; i++)
+    EXPECT_EQ(value, full[i]);
+}
+
+TEST(CircularDeque, AssignIterator) {
+  int range[8] = {11, 12, 13, 14, 15, 16, 17, 18};
+
+  circular_deque<int> empty;
+  empty.assign(std::begin(range), std::begin(range));
+  EXPECT_TRUE(empty.empty());
+
+  circular_deque<int> full;
+  full.assign(std::begin(range), std::end(range));
+  EXPECT_EQ(8u, full.size());
+  for (size_t i = 0; i < 8; i++)
+    EXPECT_EQ(range[i], full[i]);
+}
+
+TEST(CircularDeque, AssignInitializerList) {
+  circular_deque<int> empty;
+  empty.assign({});
+  EXPECT_TRUE(empty.empty());
+
+  circular_deque<int> full;
+  full.assign({11, 12, 13, 14, 15, 16, 17, 18});
+  EXPECT_EQ(8u, full.size());
+  for (int i = 0; i < 8; i++)
+    EXPECT_EQ(11 + i, full[i]);
+}
+
+// Tests [] and .at().
+TEST(CircularDeque, At) {
+  circular_deque<int> q = MakeSequence(10);
+  CycleTest(q, [](const circular_deque<int>& q, size_t cycle) {
+    size_t expected_size = 10;
+    EXPECT_EQ(expected_size, q.size());
+
+    // A sequence of 0's.
+    size_t index = 0;
+    size_t num_zeros = std::min(expected_size, cycle);
+    for (size_t i = 0; i < num_zeros; i++, index++) {
+      EXPECT_EQ(0, q[index]);
+      EXPECT_EQ(0, q.at(index));
+    }
+
+    // Followed by a sequence of increasing ints.
+    size_t num_ints = expected_size - num_zeros;
+    for (int i = 0; i < static_cast<int>(num_ints); i++, index++) {
+      EXPECT_EQ(i, q[index]);
+      EXPECT_EQ(i, q.at(index));
+    }
+  });
+}
+
+// This also tests the copy constructor with lots of different types of
+// input configurations.
+TEST(CircularDeque, FrontBackPushPop) {
+  circular_deque<int> q = MakeSequence(10);
+
+  int expected_front = 0;
+  int expected_back = 9;
+
+  // Go in one direction.
+  for (int i = 0; i < 100; i++) {
+    const circular_deque<int> const_q(q);
+
+    EXPECT_EQ(expected_front, q.front());
+    EXPECT_EQ(expected_back, q.back());
+    EXPECT_EQ(expected_front, const_q.front());
+    EXPECT_EQ(expected_back, const_q.back());
+
+    expected_front++;
+    expected_back++;
+
+    q.pop_front();
+    q.push_back(expected_back);
+  }
+
+  // Go back in reverse.
+  for (int i = 0; i < 100; i++) {
+    const circular_deque<int> const_q(q);
+
+    EXPECT_EQ(expected_front, q.front());
+    EXPECT_EQ(expected_back, q.back());
+    EXPECT_EQ(expected_front, const_q.front());
+    EXPECT_EQ(expected_back, const_q.back());
+
+    expected_front--;
+    expected_back--;
+
+    q.pop_back();
+    q.push_front(expected_front);
+  }
+}
+
+TEST(CircularDeque, ReallocateWithSplitBuffer) {
+  // Tests reallocating a deque with an internal buffer that looks like this:
+  //   4   5   x   x   0   1   2   3
+  //       end-^       ^-begin
+  circular_deque<int> q;
+  q.reserve(7);  // Internal buffer is always 1 larger than requested.
+  q.push_back(-1);
+  q.push_back(-1);
+  q.push_back(-1);
+  q.push_back(-1);
+  q.push_back(0);
+  q.pop_front();
+  q.pop_front();
+  q.pop_front();
+  q.pop_front();
+  q.push_back(1);
+  q.push_back(2);
+  q.push_back(3);
+  q.push_back(4);
+  q.push_back(5);
+
+  q.shrink_to_fit();
+  EXPECT_EQ(6u, q.size());
+
+  EXPECT_EQ(0, q[0]);
+  EXPECT_EQ(1, q[1]);
+  EXPECT_EQ(2, q[2]);
+  EXPECT_EQ(3, q[3]);
+  EXPECT_EQ(4, q[4]);
+  EXPECT_EQ(5, q[5]);
+}
+
+TEST(CircularDeque, Swap) {
+  circular_deque<int> a = MakeSequence(10);
+  circular_deque<int> b = MakeSequence(100);
+
+  a.swap(b);
+  EXPECT_EQ(100u, a.size());
+  for (int i = 0; i < 100; i++)
+    EXPECT_EQ(i, a[i]);
+
+  EXPECT_EQ(10u, b.size());
+  for (int i = 0; i < 10; i++)
+    EXPECT_EQ(i, b[i]);
+}
+
+TEST(CircularDeque, Iteration) {
+  circular_deque<int> q = MakeSequence(10);
+
+  int expected_front = 0;
+  int expected_back = 9;
+
+  // This loop causes various combinations of begin and end to be tested.
+  for (int i = 0; i < 30; i++) {
+    // Range-based for loop going forward.
+    int current_expected = expected_front;
+    for (int cur : q) {
+      EXPECT_EQ(current_expected, cur);
+      current_expected++;
+    }
+
+    // Manually test reverse iterators.
+    current_expected = expected_back;
+    for (auto cur = q.crbegin(); cur < q.crend(); cur++) {
+      EXPECT_EQ(current_expected, *cur);
+      current_expected--;
+    }
+
+    expected_front++;
+    expected_back++;
+
+    q.pop_front();
+    q.push_back(expected_back);
+  }
+
+  // Go back in reverse.
+  for (int i = 0; i < 100; i++) {
+    const circular_deque<int> const_q(q);
+
+    EXPECT_EQ(expected_front, q.front());
+    EXPECT_EQ(expected_back, q.back());
+    EXPECT_EQ(expected_front, const_q.front());
+    EXPECT_EQ(expected_back, const_q.back());
+
+    expected_front--;
+    expected_back--;
+
+    q.pop_back();
+    q.push_front(expected_front);
+  }
+}
+
+TEST(CircularDeque, IteratorComparisons) {
+  circular_deque<int> q = MakeSequence(10);
+
+  // This loop causes various combinations of begin and end to be tested.
+  for (int i = 0; i < 30; i++) {
+    EXPECT_LT(q.begin(), q.end());
+    EXPECT_LE(q.begin(), q.end());
+    EXPECT_LE(q.begin(), q.begin());
+
+    EXPECT_GT(q.end(), q.begin());
+    EXPECT_GE(q.end(), q.begin());
+    EXPECT_GE(q.end(), q.end());
+
+    EXPECT_EQ(q.begin(), q.begin());
+    EXPECT_NE(q.begin(), q.end());
+
+    q.push_front(10);
+    q.pop_back();
+  }
+}
+
+TEST(CircularDeque, IteratorIntegerOps) {
+  circular_deque<int> q = MakeSequence(10);
+
+  int expected_front = 0;
+  int expected_back = 9;
+
+  for (int i = 0; i < 30; i++) {
+    EXPECT_EQ(0, q.begin() - q.begin());
+    EXPECT_EQ(0, q.end() - q.end());
+    EXPECT_EQ(q.size(), static_cast<size_t>(q.end() - q.begin()));
+
+    // +=
+    circular_deque<int>::iterator eight = q.begin();
+    eight += 8;
+    EXPECT_EQ(8, eight - q.begin());
+    EXPECT_EQ(expected_front + 8, *eight);
+
+    // -=
+    eight -= 8;
+    EXPECT_EQ(q.begin(), eight);
+
+    // +
+    eight = eight + 8;
+    EXPECT_EQ(8, eight - q.begin());
+
+    // -
+    eight = eight - 8;
+    EXPECT_EQ(q.begin(), eight);
+
+    expected_front++;
+    expected_back++;
+
+    q.pop_front();
+    q.push_back(expected_back);
+  }
+}
+
+TEST(CircularDeque, CapacityReserveShrink) {
+  circular_deque<int> q;
+
+  // A default constructed queue should have no capacity since it should waste
+  // no space.
+  EXPECT_TRUE(q.empty());
+  EXPECT_EQ(0u, q.size());
+  EXPECT_EQ(0u, q.capacity());
+
+  size_t new_capacity = 100;
+  q.reserve(new_capacity);
+  EXPECT_EQ(new_capacity, q.capacity());
+
+  // Adding that many items should not cause a resize.
+  for (size_t i = 0; i < new_capacity; i++)
+    q.push_back(i);
+  EXPECT_EQ(new_capacity, q.size());
+  EXPECT_EQ(new_capacity, q.capacity());
+
+  // Shrinking doesn't resize capacity.
+  size_t capacity_2 = new_capacity / 2;
+  q.resize(capacity_2);
+  EXPECT_EQ(capacity_2, q.size());
+  EXPECT_EQ(new_capacity, q.capacity());
+
+  // Shrink to fit to that size.
+  q.shrink_to_fit();
+  EXPECT_EQ(capacity_2, q.size());
+  EXPECT_EQ(capacity_2, q.capacity());
+
+  // Shrink to 0, should have the same capacity.
+  q.resize(0);
+  EXPECT_EQ(0u, q.size());
+  EXPECT_EQ(capacity_2, q.capacity());
+
+  // Shrinking to fit should give 0 capacity.
+  q.shrink_to_fit();
+  EXPECT_EQ(0u, q.size());
+  EXPECT_EQ(0u, q.capacity());
+}
+
+TEST(CircularDeque, ClearAndEmpty) {
+  circular_deque<int> q;
+  EXPECT_TRUE(q.empty());
+
+  q.resize(10);
+  EXPECT_EQ(10u, q.size());
+  EXPECT_FALSE(q.empty());
+
+  q.clear();
+  EXPECT_EQ(0u, q.size());
+  EXPECT_TRUE(q.empty());
+}
+
+TEST(CircularDeque, Resize) {
+  circular_deque<int> q;
+
+  // Resize with default constructor.
+  size_t first_size = 10;
+  q.resize(first_size);
+  EXPECT_EQ(first_size, q.size());
+  for (size_t i = 0; i < first_size; i++)
+    EXPECT_EQ(0, q[i]);
+
+  // Resize with different value.
+  size_t second_expand = 10;
+  q.resize(first_size + second_expand, 3);
+  EXPECT_EQ(first_size + second_expand, q.size());
+  for (size_t i = 0; i < first_size; i++)
+    EXPECT_EQ(0, q[i]);
+  for (size_t i = 0; i < second_expand; i++)
+    EXPECT_EQ(3, q[i + first_size]);
+
+  // Erase from the end and add to the beginning so resize is forced to cross
+  // a circular buffer wrap boundary.
+  q.shrink_to_fit();
+  for (int i = 0; i < 5; i++) {
+    q.pop_back();
+    q.push_front(6);
+  }
+  q.resize(10);
+
+  EXPECT_EQ(6, q[0]);
+  EXPECT_EQ(6, q[1]);
+  EXPECT_EQ(6, q[2]);
+  EXPECT_EQ(6, q[3]);
+  EXPECT_EQ(6, q[4]);
+  EXPECT_EQ(0, q[5]);
+  EXPECT_EQ(0, q[6]);
+  EXPECT_EQ(0, q[7]);
+  EXPECT_EQ(0, q[8]);
+  EXPECT_EQ(0, q[9]);
+}
+
+/*
+This test should assert in a debug build. It tries to dereference an iterator
+after mutating the container. Uncomment to double-check that this works.
+TEST(CircularDeque, UseIteratorAfterMutate) {
+  circular_deque<int> q;
+  q.push_back(0);
+
+  auto old_begin = q.begin();
+  EXPECT_EQ(0, *old_begin);
+
+  q.push_back(1);
+  EXPECT_EQ(0, *old_begin);  // Should DCHECK.
+}
+*/
+
+}  // namespace base