Index: base/containers/circular_deque_unittest.cc |
diff --git a/base/containers/circular_deque_unittest.cc b/base/containers/circular_deque_unittest.cc |
new file mode 100644 |
index 0000000000000000000000000000000000000000..5ea320cf1ab2a2e4c6654acde41775ef531bd9ed |
--- /dev/null |
+++ b/base/containers/circular_deque_unittest.cc |
@@ -0,0 +1,499 @@ |
+// 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], ©[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 |