blob: 368141e942ecc50bac275b5c23bebf419d3792c5 [file] [log] [blame]
// 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());
}
}
class DestructorCounter {
public:
DestructorCounter(int* counter) : counter_(counter) {}
~DestructorCounter() { ++(*counter_); }
private:
int* counter_;
};
} // 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, Destructor) {
int destruct_count = 0;
// Contiguous buffer.
{
circular_deque<DestructorCounter> q;
q.resize(5, DestructorCounter(&destruct_count));
EXPECT_EQ(1, destruct_count); // The temporary in the call to resize().
destruct_count = 0;
}
EXPECT_EQ(5, destruct_count); // One call for each.
// Force a wraparound buffer.
{
circular_deque<DestructorCounter> q;
q.reserve(7);
q.resize(5, DestructorCounter(&destruct_count));
// Cycle throught some elements in our buffer to force a wraparound.
destruct_count = 0;
for (int i = 0; i < 4; i++) {
q.emplace_back(&destruct_count);
q.pop_front();
}
EXPECT_EQ(4, destruct_count); // One for each cycle.
destruct_count = 0;
}
EXPECT_EQ(5, destruct_count); // One call for each.
}
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, IteratorIncDec) {
circular_deque<int> q = MakeSequence(10);
// Mutable preincrement, predecrement.
{
circular_deque<int>::iterator it = q.begin();
circular_deque<int>::iterator op_result = ++it;
EXPECT_EQ(1, *op_result);
EXPECT_EQ(1, *it);
op_result = --it;
EXPECT_EQ(0, *op_result);
EXPECT_EQ(0, *it);
}
// Const preincrement, predecrement.
{
circular_deque<int>::const_iterator it = q.begin();
circular_deque<int>::const_iterator op_result = ++it;
EXPECT_EQ(1, *op_result);
EXPECT_EQ(1, *it);
op_result = --it;
EXPECT_EQ(0, *op_result);
EXPECT_EQ(0, *it);
}
// Mutable postincrement, postdecrement.
{
circular_deque<int>::iterator it = q.begin();
circular_deque<int>::iterator op_result = it++;
EXPECT_EQ(0, *op_result);
EXPECT_EQ(1, *it);
op_result = it--;
EXPECT_EQ(1, *op_result);
EXPECT_EQ(0, *it);
}
// Const postincrement, postdecrement.
{
circular_deque<int>::const_iterator it = q.begin();
circular_deque<int>::const_iterator op_result = it++;
EXPECT_EQ(0, *op_result);
EXPECT_EQ(1, *it);
op_result = it--;
EXPECT_EQ(1, *op_result);
EXPECT_EQ(0, *it);
}
}
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());
// clear() also should reset the capacity.
EXPECT_EQ(0u, q.capacity());
}
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]);
}
// Tests destructor behavior of resize.
TEST(CircularDeque, ResizeDelete) {
int counter = 0;
circular_deque<DestructorCounter> q;
q.resize(10, DestructorCounter(&counter));
// The one temporary when calling resize() should be deleted, that's it.
EXPECT_EQ(1, counter);
// The loops below assume the capacity will be set by resize().
EXPECT_EQ(10u, q.capacity());
counter = 0;
q.resize(5, DestructorCounter(&counter));
// 5 deleted ones + the one temporary in the resize() call.
EXPECT_EQ(6, counter);
// Cycle through some items so the 5 remaining items will cross the boundary
// in the 11-item buffer (one more than the capacity).
counter = 0;
for (int i = 0; i < 7; i++) {
q.emplace_back(&counter);
q.pop_front();
}
EXPECT_EQ(7, counter); // Loop should have deleted 7 items.
counter = 0;
q.resize(1, DestructorCounter(&counter));
// 4 deleted ones + the one temporary in the resize() call.
EXPECT_EQ(5, counter);
}
/*
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