blob: 13630252959be10c9d54e230ff53ccc0c2ead1f8 [file] [log] [blame]
// Copyright 2014 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 "cc/base/list_container.h"
#include <stddef.h>
#include <algorithm>
#include <vector>
#include "testing/gmock/include/gmock/gmock.h"
#include "testing/gtest/include/gtest/gtest.h"
namespace cc {
namespace {
// Element class having derived classes.
class DerivedElement {
public:
virtual ~DerivedElement() {}
protected:
bool bool_values[1];
char char_values[1];
int int_values[1];
long long_values[1];
};
class DerivedElement1 : public DerivedElement {
protected:
bool bool_values1[1];
char char_values1[1];
int int_values1[1];
long long_values1[1];
};
class DerivedElement2 : public DerivedElement {
protected:
bool bool_values2[2];
char char_values2[2];
int int_values2[2];
long long_values2[2];
};
class DerivedElement3 : public DerivedElement {
protected:
bool bool_values3[3];
char char_values3[3];
int int_values3[3];
long long_values3[3];
};
const size_t kLargestDerivedElementSize = sizeof(DerivedElement3);
size_t LargestDerivedElementSize() {
static_assert(sizeof(DerivedElement1) <= kLargestDerivedElementSize,
"Largest Derived Element size needs update. DerivedElement1 is "
"currently largest.");
static_assert(sizeof(DerivedElement2) <= kLargestDerivedElementSize,
"Largest Derived Element size needs update. DerivedElement2 is "
"currently largest.");
return kLargestDerivedElementSize;
}
// Element class having no derived classes.
class NonDerivedElement {
public:
NonDerivedElement() {}
~NonDerivedElement() {}
int int_values[1];
};
bool isConstNonDerivedElementPointer(const NonDerivedElement* ptr) {
return true;
}
bool isConstNonDerivedElementPointer(NonDerivedElement* ptr) {
return false;
}
const int kMagicNumberToUseForSimpleDerivedElementOne = 42;
const int kMagicNumberToUseForSimpleDerivedElementTwo = 314;
const int kMagicNumberToUseForSimpleDerivedElementThree = 1618;
class SimpleDerivedElement : public DerivedElement {
public:
~SimpleDerivedElement() override {}
void set_value(int val) { value = val; }
int get_value() { return value; }
private:
int value;
};
class SimpleDerivedElementConstructMagicNumberOne
: public SimpleDerivedElement {
public:
SimpleDerivedElementConstructMagicNumberOne() {
set_value(kMagicNumberToUseForSimpleDerivedElementOne);
}
};
class SimpleDerivedElementConstructMagicNumberTwo
: public SimpleDerivedElement {
public:
SimpleDerivedElementConstructMagicNumberTwo() {
set_value(kMagicNumberToUseForSimpleDerivedElementTwo);
}
};
class SimpleDerivedElementConstructMagicNumberThree
: public SimpleDerivedElement {
public:
SimpleDerivedElementConstructMagicNumberThree() {
set_value(kMagicNumberToUseForSimpleDerivedElementThree);
}
};
class MockDerivedElement : public SimpleDerivedElementConstructMagicNumberOne {
public:
~MockDerivedElement() override { Destruct(); }
MOCK_METHOD0(Destruct, void());
};
class MockDerivedElementSubclass : public MockDerivedElement {
public:
MockDerivedElementSubclass() {
set_value(kMagicNumberToUseForSimpleDerivedElementTwo);
}
};
const size_t kCurrentLargestDerivedElementSize =
std::max(LargestDerivedElementSize(), sizeof(MockDerivedElementSubclass));
TEST(ListContainerTest, ConstructorCalledInAllocateAndConstruct) {
ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
size_t size = 2;
SimpleDerivedElementConstructMagicNumberOne* de_1 =
list.AllocateAndConstruct<SimpleDerivedElementConstructMagicNumberOne>();
SimpleDerivedElementConstructMagicNumberTwo* de_2 =
list.AllocateAndConstruct<SimpleDerivedElementConstructMagicNumberTwo>();
EXPECT_EQ(size, list.size());
EXPECT_EQ(de_1, list.front());
EXPECT_EQ(de_2, list.back());
EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne, de_1->get_value());
EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementTwo, de_2->get_value());
}
TEST(ListContainerTest, DestructorCalled) {
ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
size_t size = 1;
MockDerivedElement* de_1 = list.AllocateAndConstruct<MockDerivedElement>();
EXPECT_CALL(*de_1, Destruct());
EXPECT_EQ(size, list.size());
EXPECT_EQ(de_1, list.front());
}
TEST(ListContainerTest, DestructorCalledOnceWhenClear) {
ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
size_t size = 1;
MockDerivedElement* de_1 = list.AllocateAndConstruct<MockDerivedElement>();
EXPECT_EQ(size, list.size());
EXPECT_EQ(de_1, list.front());
// Make sure destructor is called once during clear, and won't be called
// again.
testing::MockFunction<void()> separator;
{
testing::InSequence s;
EXPECT_CALL(*de_1, Destruct());
EXPECT_CALL(separator, Call());
EXPECT_CALL(*de_1, Destruct()).Times(0);
}
list.clear();
separator.Call();
}
TEST(ListContainerTest, ClearDoesNotMalloc) {
const size_t reserve = 10;
ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize,
reserve);
// Memory from the initial inner list that should be re-used after clear().
std::vector<DerivedElement*> reserved_element_pointers;
for (size_t i = 0; i < reserve; i++) {
DerivedElement* element = list.AllocateAndConstruct<DerivedElement>();
reserved_element_pointers.push_back(element);
}
EXPECT_EQ(0u, list.AvailableSizeWithoutAnotherAllocationForTesting());
// Allocate more than the reserve count, forcing new capacity to be added.
list.AllocateAndConstruct<DerivedElement>();
EXPECT_NE(0u, list.AvailableSizeWithoutAnotherAllocationForTesting());
// Clear should free all memory except the first |reserve| elements.
list.clear();
EXPECT_EQ(reserve, list.AvailableSizeWithoutAnotherAllocationForTesting());
// Verify the first |reserve| elements are re-used after clear().
for (size_t i = 0; i < reserve; i++) {
DerivedElement* element = list.AllocateAndConstruct<DerivedElement>();
EXPECT_EQ(element, reserved_element_pointers[i]);
}
EXPECT_EQ(0u, list.AvailableSizeWithoutAnotherAllocationForTesting());
// Verify that capacity can still grow properly.
list.AllocateAndConstruct<DerivedElement>();
EXPECT_NE(0u, list.AvailableSizeWithoutAnotherAllocationForTesting());
}
TEST(ListContainerTest, ReplaceExistingElement) {
ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
size_t size = 1;
MockDerivedElement* de_1 = list.AllocateAndConstruct<MockDerivedElement>();
EXPECT_EQ(size, list.size());
EXPECT_EQ(de_1, list.front());
// Make sure destructor is called once during clear, and won't be called
// again.
testing::MockFunction<void()> separator;
{
testing::InSequence s;
EXPECT_CALL(*de_1, Destruct());
EXPECT_CALL(separator, Call());
EXPECT_CALL(*de_1, Destruct()).Times(0);
}
list.ReplaceExistingElement<MockDerivedElementSubclass>(list.begin());
EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementTwo, de_1->get_value());
separator.Call();
EXPECT_CALL(*de_1, Destruct());
list.clear();
}
TEST(ListContainerTest, DestructorCalledOnceWhenErase) {
ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
size_t size = 1;
MockDerivedElement* de_1 = list.AllocateAndConstruct<MockDerivedElement>();
EXPECT_EQ(size, list.size());
EXPECT_EQ(de_1, list.front());
// Make sure destructor is called once during clear, and won't be called
// again.
testing::MockFunction<void()> separator;
{
testing::InSequence s;
EXPECT_CALL(*de_1, Destruct());
EXPECT_CALL(separator, Call());
EXPECT_CALL(*de_1, Destruct()).Times(0);
}
list.EraseAndInvalidateAllPointers(list.begin());
separator.Call();
}
TEST(ListContainerTest, SimpleIndexAccessNonDerivedElement) {
ListContainer<NonDerivedElement> list;
size_t size = 3;
NonDerivedElement* nde_1 = list.AllocateAndConstruct<NonDerivedElement>();
NonDerivedElement* nde_2 = list.AllocateAndConstruct<NonDerivedElement>();
NonDerivedElement* nde_3 = list.AllocateAndConstruct<NonDerivedElement>();
EXPECT_EQ(size, list.size());
EXPECT_EQ(nde_1, list.front());
EXPECT_EQ(nde_3, list.back());
EXPECT_EQ(list.front(), list.ElementAt(0));
EXPECT_EQ(nde_2, list.ElementAt(1));
EXPECT_EQ(list.back(), list.ElementAt(2));
}
TEST(ListContainerTest, SimpleInsertionNonDerivedElement) {
ListContainer<NonDerivedElement> list;
size_t size = 3;
NonDerivedElement* nde_1 = list.AllocateAndConstruct<NonDerivedElement>();
list.AllocateAndConstruct<NonDerivedElement>();
NonDerivedElement* nde_3 = list.AllocateAndConstruct<NonDerivedElement>();
EXPECT_EQ(size, list.size());
EXPECT_EQ(nde_1, list.front());
EXPECT_EQ(nde_3, list.back());
}
TEST(ListContainerTest, SimpleInsertionAndClearNonDerivedElement) {
ListContainer<NonDerivedElement> list;
EXPECT_TRUE(list.empty());
EXPECT_EQ(0u, list.size());
size_t size = 3;
NonDerivedElement* nde_1 = list.AllocateAndConstruct<NonDerivedElement>();
list.AllocateAndConstruct<NonDerivedElement>();
NonDerivedElement* nde_3 = list.AllocateAndConstruct<NonDerivedElement>();
EXPECT_EQ(size, list.size());
EXPECT_EQ(nde_1, list.front());
EXPECT_EQ(nde_3, list.back());
EXPECT_FALSE(list.empty());
list.clear();
EXPECT_TRUE(list.empty());
EXPECT_EQ(0u, list.size());
}
TEST(ListContainerTest, SimpleInsertionClearAndInsertAgainNonDerivedElement) {
ListContainer<NonDerivedElement> list;
EXPECT_TRUE(list.empty());
EXPECT_EQ(0u, list.size());
size_t size = 2;
NonDerivedElement* nde_front = list.AllocateAndConstruct<NonDerivedElement>();
NonDerivedElement* nde_back = list.AllocateAndConstruct<NonDerivedElement>();
EXPECT_EQ(size, list.size());
EXPECT_EQ(nde_front, list.front());
EXPECT_EQ(nde_back, list.back());
EXPECT_FALSE(list.empty());
list.clear();
EXPECT_TRUE(list.empty());
EXPECT_EQ(0u, list.size());
size = 3;
nde_front = list.AllocateAndConstruct<NonDerivedElement>();
list.AllocateAndConstruct<NonDerivedElement>();
nde_back = list.AllocateAndConstruct<NonDerivedElement>();
EXPECT_EQ(size, list.size());
EXPECT_EQ(nde_front, list.front());
EXPECT_EQ(nde_back, list.back());
EXPECT_FALSE(list.empty());
}
// This test is used to test when there is more than one allocation needed
// for, ListContainer can still perform like normal vector.
TEST(ListContainerTest,
SimpleInsertionTriggerMoreThanOneAllocationNonDerivedElement) {
ListContainer<NonDerivedElement> list(sizeof(NonDerivedElement), 2);
std::vector<NonDerivedElement*> nde_list;
size_t size = 10;
for (size_t i = 0; i < size; ++i) {
nde_list.push_back(list.AllocateAndConstruct<NonDerivedElement>());
}
EXPECT_EQ(size, list.size());
ListContainer<NonDerivedElement>::Iterator iter = list.begin();
for (std::vector<NonDerivedElement*>::const_iterator nde_iter =
nde_list.begin();
nde_iter != nde_list.end(); ++nde_iter) {
EXPECT_EQ(*nde_iter, *iter);
++iter;
}
}
TEST(ListContainerTest,
CorrectAllocationSizeForMoreThanOneAllocationNonDerivedElement) {
// Constructor sets the allocation size to 2. Every time ListContainer needs
// to allocate again, it doubles allocation size. In this test, 10 elements is
// needed, thus ListContainerShould allocate spaces 2, 4 and 8 elements.
ListContainer<NonDerivedElement> list(sizeof(NonDerivedElement), 2);
std::vector<NonDerivedElement*> nde_list;
size_t size = 10;
for (size_t i = 0; i < size; ++i) {
// Before asking for a new element, space available without another
// allocation follows.
switch (i) {
case 2:
case 6:
EXPECT_EQ(0u, list.AvailableSizeWithoutAnotherAllocationForTesting());
break;
case 1:
case 5:
EXPECT_EQ(1u, list.AvailableSizeWithoutAnotherAllocationForTesting());
break;
case 0:
case 4:
EXPECT_EQ(2u, list.AvailableSizeWithoutAnotherAllocationForTesting());
break;
case 3:
EXPECT_EQ(3u, list.AvailableSizeWithoutAnotherAllocationForTesting());
break;
case 9:
EXPECT_EQ(5u, list.AvailableSizeWithoutAnotherAllocationForTesting());
break;
case 8:
EXPECT_EQ(6u, list.AvailableSizeWithoutAnotherAllocationForTesting());
break;
case 7:
EXPECT_EQ(7u, list.AvailableSizeWithoutAnotherAllocationForTesting());
break;
default:
break;
}
nde_list.push_back(list.AllocateAndConstruct<NonDerivedElement>());
// After asking for a new element, space available without another
// allocation follows.
switch (i) {
case 1:
case 5:
EXPECT_EQ(0u, list.AvailableSizeWithoutAnotherAllocationForTesting());
break;
case 0:
case 4:
EXPECT_EQ(1u, list.AvailableSizeWithoutAnotherAllocationForTesting());
break;
case 3:
EXPECT_EQ(2u, list.AvailableSizeWithoutAnotherAllocationForTesting());
break;
case 2:
EXPECT_EQ(3u, list.AvailableSizeWithoutAnotherAllocationForTesting());
break;
case 9:
EXPECT_EQ(4u, list.AvailableSizeWithoutAnotherAllocationForTesting());
break;
case 8:
EXPECT_EQ(5u, list.AvailableSizeWithoutAnotherAllocationForTesting());
break;
case 7:
EXPECT_EQ(6u, list.AvailableSizeWithoutAnotherAllocationForTesting());
break;
case 6:
EXPECT_EQ(7u, list.AvailableSizeWithoutAnotherAllocationForTesting());
break;
default:
break;
}
}
EXPECT_EQ(size, list.size());
ListContainer<NonDerivedElement>::Iterator iter = list.begin();
for (std::vector<NonDerivedElement*>::const_iterator nde_iter =
nde_list.begin();
nde_iter != nde_list.end(); ++nde_iter) {
EXPECT_EQ(*nde_iter, *iter);
++iter;
}
}
TEST(ListContainerTest, SimpleIterationNonDerivedElement) {
ListContainer<NonDerivedElement> list;
std::vector<NonDerivedElement*> nde_list;
size_t size = 10;
for (size_t i = 0; i < size; ++i) {
nde_list.push_back(list.AllocateAndConstruct<NonDerivedElement>());
}
EXPECT_EQ(size, list.size());
size_t num_iters_in_list = 0;
{
std::vector<NonDerivedElement*>::const_iterator nde_iter = nde_list.begin();
for (ListContainer<NonDerivedElement>::Iterator iter = list.begin();
iter != list.end(); ++iter) {
EXPECT_EQ(*nde_iter, *iter);
++num_iters_in_list;
++nde_iter;
}
}
size_t num_iters_in_vector = 0;
{
ListContainer<NonDerivedElement>::Iterator iter = list.begin();
for (std::vector<NonDerivedElement*>::const_iterator nde_iter =
nde_list.begin();
nde_iter != nde_list.end(); ++nde_iter) {
EXPECT_EQ(*nde_iter, *iter);
++num_iters_in_vector;
++iter;
}
}
EXPECT_EQ(num_iters_in_vector, num_iters_in_list);
}
TEST(ListContainerTest, SimpleConstIteratorIterationNonDerivedElement) {
ListContainer<NonDerivedElement> list;
std::vector<const NonDerivedElement*> nde_list;
size_t size = 10;
for (size_t i = 0; i < size; ++i) {
nde_list.push_back(list.AllocateAndConstruct<NonDerivedElement>());
}
EXPECT_EQ(size, list.size());
{
std::vector<const NonDerivedElement*>::const_iterator nde_iter =
nde_list.begin();
for (ListContainer<NonDerivedElement>::ConstIterator iter = list.begin();
iter != list.end(); ++iter) {
EXPECT_TRUE(isConstNonDerivedElementPointer(*iter));
EXPECT_EQ(*nde_iter, *iter);
++nde_iter;
}
}
{
std::vector<const NonDerivedElement*>::const_iterator nde_iter =
nde_list.begin();
for (ListContainer<NonDerivedElement>::Iterator iter = list.begin();
iter != list.end(); ++iter) {
EXPECT_FALSE(isConstNonDerivedElementPointer(*iter));
EXPECT_EQ(*nde_iter, *iter);
++nde_iter;
}
}
{
ListContainer<NonDerivedElement>::ConstIterator iter = list.begin();
for (std::vector<const NonDerivedElement*>::const_iterator nde_iter =
nde_list.begin();
nde_iter != nde_list.end(); ++nde_iter) {
EXPECT_EQ(*nde_iter, *iter);
++iter;
}
}
}
TEST(ListContainerTest, SimpleReverseInsertionNonDerivedElement) {
ListContainer<NonDerivedElement> list;
std::vector<NonDerivedElement*> nde_list;
size_t size = 10;
for (size_t i = 0; i < size; ++i) {
nde_list.push_back(list.AllocateAndConstruct<NonDerivedElement>());
}
EXPECT_EQ(size, list.size());
{
std::vector<NonDerivedElement*>::const_reverse_iterator nde_iter =
nde_list.rbegin();
for (ListContainer<NonDerivedElement>::ReverseIterator iter = list.rbegin();
iter != list.rend(); ++iter) {
EXPECT_EQ(*nde_iter, *iter);
++nde_iter;
}
}
{
ListContainer<NonDerivedElement>::ReverseIterator iter = list.rbegin();
for (std::vector<NonDerivedElement*>::reverse_iterator nde_iter =
nde_list.rbegin();
nde_iter != nde_list.rend(); ++nde_iter) {
EXPECT_EQ(*nde_iter, *iter);
++iter;
}
}
}
TEST(ListContainerTest, SimpleDeletion) {
ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
std::vector<SimpleDerivedElement*> sde_list;
int size = 10;
for (int i = 0; i < size; ++i) {
sde_list.push_back(list.AllocateAndConstruct<SimpleDerivedElement>());
sde_list.back()->set_value(i);
}
EXPECT_EQ(static_cast<size_t>(size), list.size());
list.EraseAndInvalidateAllPointers(list.begin());
--size;
EXPECT_EQ(static_cast<size_t>(size), list.size());
int i = 1;
for (ListContainer<DerivedElement>::Iterator iter = list.begin();
iter != list.end(); ++iter) {
EXPECT_EQ(i, static_cast<SimpleDerivedElement*>(*iter)->get_value());
++i;
}
}
TEST(ListContainerTest, DeletionAllInAllocation) {
const size_t kReserve = 10;
ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize,
kReserve);
std::vector<SimpleDerivedElement*> sde_list;
// Add enough elements to cause another allocation.
for (size_t i = 0; i < kReserve + 1; ++i) {
sde_list.push_back(list.AllocateAndConstruct<SimpleDerivedElement>());
sde_list.back()->set_value(static_cast<int>(i));
}
EXPECT_EQ(kReserve + 1, list.size());
// Remove everything in the first allocation.
for (size_t i = 0; i < kReserve; ++i)
list.EraseAndInvalidateAllPointers(list.begin());
EXPECT_EQ(1u, list.size());
// The last element is left.
SimpleDerivedElement* de = static_cast<SimpleDerivedElement*>(*list.begin());
EXPECT_EQ(static_cast<int>(kReserve), de->get_value());
// Remove the element from the 2nd allocation.
list.EraseAndInvalidateAllPointers(list.begin());
EXPECT_EQ(0u, list.size());
}
TEST(ListContainerTest, DeletionAllInAllocationReversed) {
const size_t kReserve = 10;
ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize,
kReserve);
std::vector<SimpleDerivedElement*> sde_list;
// Add enough elements to cause another allocation.
for (size_t i = 0; i < kReserve + 1; ++i) {
sde_list.push_back(list.AllocateAndConstruct<SimpleDerivedElement>());
sde_list.back()->set_value(static_cast<int>(i));
}
EXPECT_EQ(kReserve + 1, list.size());
// Remove everything in the 2nd allocation.
auto it = list.begin();
for (size_t i = 0; i < kReserve; ++i)
++it;
list.EraseAndInvalidateAllPointers(it);
// The 2nd-last element is next, and the rest of the elements exist.
size_t i = kReserve - 1;
for (auto it = list.rbegin(); it != list.rend(); ++it) {
SimpleDerivedElement* de = static_cast<SimpleDerivedElement*>(*it);
EXPECT_EQ(static_cast<int>(i), de->get_value());
--i;
}
// Can forward iterate too.
i = 0;
for (auto it = list.begin(); it != list.end(); ++it) {
SimpleDerivedElement* de = static_cast<SimpleDerivedElement*>(*it);
EXPECT_EQ(static_cast<int>(i), de->get_value());
++i;
}
// Remove the last thing from the 1st allocation.
it = list.begin();
for (size_t i = 0; i < kReserve - 1; ++i)
++it;
list.EraseAndInvalidateAllPointers(it);
// The 2nd-last element is next, and the rest of the elements exist.
i = kReserve - 2;
for (auto it = list.rbegin(); it != list.rend(); ++it) {
SimpleDerivedElement* de = static_cast<SimpleDerivedElement*>(*it);
EXPECT_EQ(static_cast<int>(i), de->get_value());
--i;
}
// Can forward iterate too.
i = 0;
for (auto it = list.begin(); it != list.end(); ++it) {
SimpleDerivedElement* de = static_cast<SimpleDerivedElement*>(*it);
EXPECT_EQ(static_cast<int>(i), de->get_value());
++i;
}
}
TEST(ListContainerTest, DeletionWhileIterating) {
ListContainer<SimpleDerivedElement> list(kCurrentLargestDerivedElementSize);
for (int i = 0; i < 4; ++i)
list.AllocateAndConstruct<SimpleDerivedElement>()->set_value(i);
// Delete odd elements.
for (auto it = list.begin(); it != list.end();) {
if ((*it)->get_value() % 2)
it = list.EraseAndInvalidateAllPointers(it);
else
++it;
}
EXPECT_EQ(2u, list.size());
EXPECT_EQ(0, list.front()->get_value());
EXPECT_EQ(2, list.back()->get_value());
// Erase all elements.
for (auto it = list.begin(); it != list.end();)
it = list.EraseAndInvalidateAllPointers(it);
EXPECT_TRUE(list.empty());
}
TEST(ListContainerTest, InsertBeforeBegin) {
ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
std::vector<SimpleDerivedElement*> sde_list;
const int size = 4;
for (int i = 0; i < size; ++i) {
sde_list.push_back(list.AllocateAndConstruct<SimpleDerivedElement>());
sde_list.back()->set_value(i);
}
EXPECT_EQ(static_cast<size_t>(size), list.size());
const int count = 2;
ListContainer<DerivedElement>::Iterator iter =
list.InsertBeforeAndInvalidateAllPointers<SimpleDerivedElement>(
list.begin(), count);
for (int i = 0; i < count; ++i) {
static_cast<SimpleDerivedElement*>(*iter)->set_value(100 + i);
++iter;
}
const int expected_result[] = {100, 101, 0, 1, 2, 3};
int iter_index = 0;
for (iter = list.begin(); iter != list.end(); ++iter) {
EXPECT_EQ(expected_result[iter_index],
static_cast<SimpleDerivedElement*>(*iter)->get_value());
++iter_index;
}
EXPECT_EQ(size + count, iter_index);
}
TEST(ListContainerTest, InsertBeforeEnd) {
ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
std::vector<SimpleDerivedElement*> sde_list;
const int size = 4;
for (int i = 0; i < size; ++i) {
sde_list.push_back(list.AllocateAndConstruct<SimpleDerivedElement>());
sde_list.back()->set_value(i);
}
EXPECT_EQ(static_cast<size_t>(size), list.size());
const int count = 3;
ListContainer<DerivedElement>::Iterator iter =
list.InsertBeforeAndInvalidateAllPointers<SimpleDerivedElement>(
list.end(), count);
for (int i = 0; i < count; ++i) {
static_cast<SimpleDerivedElement*>(*iter)->set_value(100 + i);
++iter;
}
const int expected_result[] = {0, 1, 2, 3, 100, 101, 102};
int iter_index = 0;
for (iter = list.begin(); iter != list.end(); ++iter) {
EXPECT_EQ(expected_result[iter_index],
static_cast<SimpleDerivedElement*>(*iter)->get_value());
++iter_index;
}
EXPECT_EQ(size + count, iter_index);
}
TEST(ListContainerTest, InsertBeforeEmpty) {
ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
const int count = 3;
ListContainer<DerivedElement>::Iterator iter =
list.InsertBeforeAndInvalidateAllPointers<SimpleDerivedElement>(
list.end(), count);
for (int i = 0; i < count; ++i) {
static_cast<SimpleDerivedElement*>(*iter)->set_value(100 + i);
++iter;
}
const int expected_result[] = {100, 101, 102};
int iter_index = 0;
for (iter = list.begin(); iter != list.end(); ++iter) {
EXPECT_EQ(expected_result[iter_index],
static_cast<SimpleDerivedElement*>(*iter)->get_value());
++iter_index;
}
EXPECT_EQ(count, iter_index);
}
TEST(ListContainerTest, InsertBeforeMany) {
ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
std::vector<SimpleDerivedElement*> sde_list;
// Create a partial list of 1,...,99.
int initial_list[] = {
0, 1, 4, 5, 6, 7, 8, 9, 11, 12, 17, 18, 19, 20, 21, 22,
23, 24, 25, 26, 27, 28, 29, 30, 32, 34, 36, 37, 51, 52, 54, 56,
60, 64, 65, 70, 75, 76, 80, 81, 83, 86, 87, 90, 93, 95, 97, 98,
};
const size_t size = sizeof(initial_list) / sizeof(initial_list[0]);
for (size_t i = 0; i < size; ++i) {
sde_list.push_back(list.AllocateAndConstruct<SimpleDerivedElement>());
sde_list.back()->set_value(initial_list[i]);
}
EXPECT_EQ(static_cast<size_t>(size), list.size());
// Insert the missing elements.
ListContainer<DerivedElement>::Iterator iter = list.begin();
while (iter != list.end()) {
ListContainer<DerivedElement>::Iterator iter_next = iter;
++iter_next;
int value = static_cast<SimpleDerivedElement*>(*iter)->get_value();
int value_next =
iter_next != list.end()
? static_cast<SimpleDerivedElement*>(*iter_next)->get_value()
: 100;
int count = value_next - value - 1;
iter = list.InsertBeforeAndInvalidateAllPointers<SimpleDerivedElement>(
iter_next, count);
for (int i = value + 1; i < value_next; ++i) {
static_cast<SimpleDerivedElement*>(*iter)->set_value(i);
++iter;
}
}
int iter_index = 0;
for (iter = list.begin(); iter != list.end(); ++iter) {
EXPECT_EQ(iter_index,
static_cast<SimpleDerivedElement*>(*iter)->get_value());
++iter_index;
}
EXPECT_EQ(100, iter_index);
}
TEST(ListContainerTest, SimpleManipulationWithIndexSimpleDerivedElement) {
ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
std::vector<SimpleDerivedElement*> de_list;
int size = 10;
for (int i = 0; i < size; ++i) {
de_list.push_back(list.AllocateAndConstruct<SimpleDerivedElement>());
}
EXPECT_EQ(static_cast<size_t>(size), list.size());
for (int i = 0; i < size; ++i) {
static_cast<SimpleDerivedElement*>(list.ElementAt(i))->set_value(i);
}
int i = 0;
for (std::vector<SimpleDerivedElement*>::const_iterator
de_iter = de_list.begin();
de_iter != de_list.end(); ++de_iter, ++i) {
EXPECT_EQ(i, (*de_iter)->get_value());
}
}
TEST(ListContainerTest,
SimpleManipulationWithIndexMoreThanOneAllocationSimpleDerivedElement) {
ListContainer<DerivedElement> list(LargestDerivedElementSize(), 2);
std::vector<SimpleDerivedElement*> de_list;
int size = 10;
for (int i = 0; i < size; ++i) {
de_list.push_back(list.AllocateAndConstruct<SimpleDerivedElement>());
}
EXPECT_EQ(static_cast<size_t>(size), list.size());
for (int i = 0; i < size; ++i) {
static_cast<SimpleDerivedElement*>(list.ElementAt(i))->set_value(i);
}
int i = 0;
for (std::vector<SimpleDerivedElement*>::const_iterator
de_iter = de_list.begin();
de_iter != de_list.end(); ++de_iter, ++i) {
EXPECT_EQ(i, (*de_iter)->get_value());
}
}
TEST(ListContainerTest,
SimpleIterationAndReverseIterationWithIndexNonDerivedElement) {
ListContainer<NonDerivedElement> list;
std::vector<NonDerivedElement*> nde_list;
size_t size = 10;
for (size_t i = 0; i < size; ++i) {
nde_list.push_back(list.AllocateAndConstruct<NonDerivedElement>());
}
EXPECT_EQ(size, list.size());
size_t i = 0;
for (ListContainer<NonDerivedElement>::Iterator iter = list.begin();
iter != list.end(); ++iter) {
EXPECT_EQ(i, iter.index());
++i;
}
i = 0;
for (ListContainer<NonDerivedElement>::ReverseIterator iter = list.rbegin();
iter != list.rend(); ++iter) {
EXPECT_EQ(i, iter.index());
++i;
}
}
// Increments an int when constructed (or the counter pointer is supplied) and
// decrements when destructed.
class InstanceCounter {
public:
InstanceCounter() : counter_(nullptr) {}
explicit InstanceCounter(int* counter) { SetCounter(counter); }
~InstanceCounter() {
if (counter_)
--*counter_;
}
void SetCounter(int* counter) {
counter_ = counter;
++*counter_;
}
private:
int* counter_;
};
TEST(ListContainerTest, RemoveLastDestruction) {
// We keep an explicit instance count to make sure that the destructors are
// indeed getting called.
int counter = 0;
ListContainer<InstanceCounter> list(sizeof(InstanceCounter), 1);
EXPECT_EQ(0, counter);
EXPECT_EQ(0u, list.size());
// We should be okay to add one and then go back to zero.
list.AllocateAndConstruct<InstanceCounter>()->SetCounter(&counter);
EXPECT_EQ(1, counter);
EXPECT_EQ(1u, list.size());
list.RemoveLast();
EXPECT_EQ(0, counter);
EXPECT_EQ(0u, list.size());
// We should also be okay to remove the last multiple times, as long as there
// are enough elements in the first place.
list.AllocateAndConstruct<InstanceCounter>()->SetCounter(&counter);
list.AllocateAndConstruct<InstanceCounter>()->SetCounter(&counter);
list.AllocateAndConstruct<InstanceCounter>()->SetCounter(&counter);
list.AllocateAndConstruct<InstanceCounter>()->SetCounter(&counter);
list.AllocateAndConstruct<InstanceCounter>()->SetCounter(&counter);
list.AllocateAndConstruct<InstanceCounter>()->SetCounter(&counter);
list.RemoveLast();
list.RemoveLast();
EXPECT_EQ(4, counter); // Leaves one in the last list.
EXPECT_EQ(4u, list.size());
list.RemoveLast();
EXPECT_EQ(3, counter); // Removes an inner list from before.
EXPECT_EQ(3u, list.size());
}
// TODO(jbroman): std::equal would work if ListContainer iterators satisfied the
// usual STL iterator constraints. We should fix that.
template <typename It1, typename It2>
bool Equal(It1 it1, const It1& end1, It2 it2) {
for (; it1 != end1; ++it1, ++it2) {
if (!(*it1 == *it2))
return false;
}
return true;
}
TEST(ListContainerTest, RemoveLastIteration) {
struct SmallStruct {
char dummy[16];
};
ListContainer<SmallStruct> list(sizeof(SmallStruct), 1);
std::vector<SmallStruct*> pointers;
// Utilities which keep these two lists in sync and check that their iteration
// order matches.
auto push = [&list, &pointers]() {
pointers.push_back(list.AllocateAndConstruct<SmallStruct>());
};
auto pop = [&list, &pointers]() {
pointers.pop_back();
list.RemoveLast();
};
auto check_equal = [&list, &pointers]() {
// They should be of the same size, and compare equal with all four kinds of
// iteration.
// Apparently Mac doesn't have vector::cbegin and vector::crbegin?
const auto& const_pointers = pointers;
ASSERT_EQ(list.size(), pointers.size());
ASSERT_TRUE(Equal(list.begin(), list.end(), pointers.begin()));
ASSERT_TRUE(Equal(list.cbegin(), list.cend(), const_pointers.begin()));
ASSERT_TRUE(Equal(list.rbegin(), list.rend(), pointers.rbegin()));
ASSERT_TRUE(Equal(list.crbegin(), list.crend(), const_pointers.rbegin()));
};
check_equal(); // Initially empty.
push();
check_equal(); // One full inner list.
push();
check_equal(); // One full, one partially full.
push();
push();
check_equal(); // Two full, one partially full.
pop();
check_equal(); // Two full, one empty.
pop();
check_equal(); // One full, one partially full, one empty.
pop();
check_equal(); // One full, one empty.
push();
pop();
pop();
ASSERT_TRUE(list.empty());
check_equal(); // Empty.
}
TEST(ListContainerTest, AppendByMovingSameList) {
ListContainer<SimpleDerivedElement> list(kCurrentLargestDerivedElementSize);
list.AllocateAndConstruct<SimpleDerivedElementConstructMagicNumberOne>();
list.AppendByMoving(list.front());
EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
list.back()->get_value());
EXPECT_EQ(2u, list.size());
list.front()->set_value(kMagicNumberToUseForSimpleDerivedElementTwo);
EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementTwo,
list.front()->get_value());
list.AppendByMoving(list.front());
EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementTwo,
list.back()->get_value());
EXPECT_EQ(3u, list.size());
}
TEST(ListContainerTest, AppendByMovingDoesNotDestruct) {
ListContainer<DerivedElement> list_1(kCurrentLargestDerivedElementSize);
ListContainer<DerivedElement> list_2(kCurrentLargestDerivedElementSize);
MockDerivedElement* mde_1 = list_1.AllocateAndConstruct<MockDerivedElement>();
// Make sure destructor isn't called during AppendByMoving.
list_2.AppendByMoving(mde_1);
EXPECT_CALL(*mde_1, Destruct()).Times(0);
testing::Mock::VerifyAndClearExpectations(mde_1);
mde_1 = static_cast<MockDerivedElement*>(list_2.back());
EXPECT_CALL(*mde_1, Destruct());
}
TEST(ListContainerTest, AppendByMovingReturnsMovedPointer) {
ListContainer<SimpleDerivedElement> list_1(kCurrentLargestDerivedElementSize);
ListContainer<SimpleDerivedElement> list_2(kCurrentLargestDerivedElementSize);
SimpleDerivedElement* simple_element =
list_1.AllocateAndConstruct<SimpleDerivedElement>();
SimpleDerivedElement* moved_1 = list_2.AppendByMoving(simple_element);
EXPECT_EQ(list_2.back(), moved_1);
SimpleDerivedElement* moved_2 = list_1.AppendByMoving(moved_1);
EXPECT_EQ(list_1.back(), moved_2);
EXPECT_NE(moved_1, moved_2);
}
TEST(ListContainerTest, AppendByMovingReplacesSourceWithNewDerivedElement) {
ListContainer<SimpleDerivedElementConstructMagicNumberOne> list_1(
kCurrentLargestDerivedElementSize);
ListContainer<SimpleDerivedElementConstructMagicNumberTwo> list_2(
kCurrentLargestDerivedElementSize);
list_1.AllocateAndConstruct<SimpleDerivedElementConstructMagicNumberOne>();
EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
list_1.front()->get_value());
list_2.AppendByMoving(list_1.front());
EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
list_1.front()->get_value());
EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
list_2.front()->get_value());
// Change the value of list_2.front() to ensure the value is actually moved.
list_2.back()->set_value(kMagicNumberToUseForSimpleDerivedElementThree);
list_1.AppendByMoving(list_2.back());
EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
list_1.front()->get_value());
EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementThree,
list_1.back()->get_value());
EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementTwo,
list_2.back()->get_value());
// AppendByMoving replaces the source element with a new derived element so
// we do not expect sizes to shrink after AppendByMoving is called.
EXPECT_EQ(2u, list_1.size()); // One direct allocation, one AppendByMoving.
EXPECT_EQ(1u, list_2.size()); // One AppendByMoving.
}
const size_t kLongCountForLongSimpleDerivedElement = 5;
class LongSimpleDerivedElement : public SimpleDerivedElement {
public:
~LongSimpleDerivedElement() override {}
void SetAllValues(unsigned long value) {
for (size_t i = 0; i < kLongCountForLongSimpleDerivedElement; i++)
values[i] = value;
}
bool AreAllValuesEqualTo(size_t value) const {
for (size_t i = 1; i < kLongCountForLongSimpleDerivedElement; i++) {
if (values[i] != values[0])
return false;
}
return true;
}
private:
unsigned long values[kLongCountForLongSimpleDerivedElement];
};
const unsigned long kMagicNumberToUseForLongSimpleDerivedElement = 2718ul;
class LongSimpleDerivedElementConstructMagicNumber
: public LongSimpleDerivedElement {
public:
LongSimpleDerivedElementConstructMagicNumber() {
SetAllValues(kMagicNumberToUseForLongSimpleDerivedElement);
}
};
TEST(ListContainerTest, AppendByMovingLongAndSimpleDerivedElements) {
static_assert(sizeof(LongSimpleDerivedElement) > sizeof(SimpleDerivedElement),
"LongSimpleDerivedElement should be larger than "
"SimpleDerivedElement's size.");
static_assert(sizeof(LongSimpleDerivedElement) <= kLargestDerivedElementSize,
"LongSimpleDerivedElement should be smaller than the maximum "
"DerivedElement size.");
ListContainer<SimpleDerivedElement> list(kCurrentLargestDerivedElementSize);
list.AllocateAndConstruct<LongSimpleDerivedElementConstructMagicNumber>();
list.AllocateAndConstruct<SimpleDerivedElementConstructMagicNumberOne>();
EXPECT_TRUE(
static_cast<LongSimpleDerivedElement*>(list.front())
->AreAllValuesEqualTo(kMagicNumberToUseForLongSimpleDerivedElement));
EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
list.back()->get_value());
// Test that moving a simple derived element actually moves enough data so
// that the LongSimpleDerivedElement at this location is entirely moved.
SimpleDerivedElement* simple_element = list.back();
list.AppendByMoving(list.front());
EXPECT_TRUE(
static_cast<LongSimpleDerivedElement*>(list.back())
->AreAllValuesEqualTo(kMagicNumberToUseForLongSimpleDerivedElement));
EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
simple_element->get_value());
LongSimpleDerivedElement* long_element =
static_cast<LongSimpleDerivedElement*>(list.back());
list.AppendByMoving(simple_element);
EXPECT_TRUE(long_element->AreAllValuesEqualTo(
kMagicNumberToUseForLongSimpleDerivedElement));
EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
list.back()->get_value());
}
TEST(ListContainerTest, Swap) {
ListContainer<SimpleDerivedElement> list_1(kCurrentLargestDerivedElementSize);
list_1.AllocateAndConstruct<SimpleDerivedElementConstructMagicNumberOne>();
ListContainer<SimpleDerivedElement> list_2(kCurrentLargestDerivedElementSize);
list_2.AllocateAndConstruct<SimpleDerivedElementConstructMagicNumberTwo>();
list_2.AllocateAndConstruct<SimpleDerivedElementConstructMagicNumberThree>();
SimpleDerivedElement* pre_swap_list_1_front = list_1.front();
EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
list_1.front()->get_value());
EXPECT_EQ(1u, list_1.size());
EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementTwo,
list_2.front()->get_value());
EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementThree,
list_2.back()->get_value());
EXPECT_EQ(2u, list_2.size());
list_2.swap(list_1);
EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementTwo,
list_1.front()->get_value());
EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementThree,
list_1.back()->get_value());
EXPECT_EQ(2u, list_1.size());
EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
list_2.front()->get_value());
EXPECT_EQ(1u, list_2.size());
// Ensure pointers are still valid after swapping.
EXPECT_EQ(pre_swap_list_1_front, list_2.front());
}
TEST(ListContainerTest, GetCapacityInBytes) {
const int iterations = 500;
const size_t initial_capacity = 10;
const size_t upper_bound_on_min_capacity = initial_capacity;
// At time of writing, removing elements from the end can cause up to 7x the
// memory required to be consumed, in the worst case, since we can have up to
// two trailing inner lists that are empty (for 2*size + 4*size in unused
// memory, due to the exponential growth strategy).
const size_t max_waste_factor = 8;
ListContainer<DerivedElement> list(LargestDerivedElementSize(),
initial_capacity);
// The capacity should grow with the list.
for (int i = 0; i < iterations; i++) {
size_t capacity = list.GetCapacityInBytes();
ASSERT_GE(capacity, list.size() * LargestDerivedElementSize());
ASSERT_LE(capacity, std::max(list.size(), upper_bound_on_min_capacity) *
max_waste_factor * LargestDerivedElementSize());
list.AllocateAndConstruct<DerivedElement1>();
}
// The capacity should shrink with the list.
for (int i = 0; i < iterations; i++) {
size_t capacity = list.GetCapacityInBytes();
ASSERT_GE(capacity, list.size() * LargestDerivedElementSize());
ASSERT_LE(capacity, std::max(list.size(), upper_bound_on_min_capacity) *
max_waste_factor * LargestDerivedElementSize());
list.RemoveLast();
}
}
} // namespace
} // namespace cc