// 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 "base/stl_util.h"
#include "testing/gtest/include/gtest/gtest.h"

namespace cc {
namespace {

// Element class having derived classes.
class DerivedElement {
 public:
  virtual ~DerivedElement() = default;

 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);
const size_t kLargestDerivedElementAlign = alignof(DerivedElement3);

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.");
static_assert(alignof(DerivedElement1) <= kLargestDerivedElementSize,
              "Largest Derived Element align needs update. DerivedElement1 is "
              "currently largest.");
static_assert(alignof(DerivedElement2) <= kLargestDerivedElementSize,
              "Largest Derived Element align needs update. DerivedElement2 is "
              "currently largest.");

// Element class having no derived classes.
class NonDerivedElement {
 public:
  NonDerivedElement() = default;
  ~NonDerivedElement() = default;

  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 = default;
  void set_value(int val) { value = val; }
  int get_value() { return value; }

 private:
  int value;
};

class SimpleDerivedElementConstructMagicNumberOne
    : public SimpleDerivedElement {
 public:
  SimpleDerivedElementConstructMagicNumberOne() {
    set_value(kMagicNumberToUseForSimpleDerivedElementOne);
  }
  ~SimpleDerivedElementConstructMagicNumberOne() override = default;
};

class SimpleDerivedElementConstructMagicNumberTwo
    : public SimpleDerivedElement {
 public:
  SimpleDerivedElementConstructMagicNumberTwo() {
    set_value(kMagicNumberToUseForSimpleDerivedElementTwo);
  }
  ~SimpleDerivedElementConstructMagicNumberTwo() override = default;
};

class SimpleDerivedElementConstructMagicNumberThree
    : public SimpleDerivedElement {
 public:
  SimpleDerivedElementConstructMagicNumberThree() {
    set_value(kMagicNumberToUseForSimpleDerivedElementThree);
  }
  ~SimpleDerivedElementConstructMagicNumberThree() override = default;
};

// This class' instances are moved by ListContainer via memcpy(). This behavior
// is not supported by gmock's FunctionMocker, so this class must roll its own
// mocking code.
class MockDerivedElement : public SimpleDerivedElementConstructMagicNumberOne {
 public:
  ~MockDerivedElement() override {
    DestructorCalled();
    CheckDestructExpectation();
  }

  void SetExpectedDestructorCalls(size_t expected_calls) {
    expected_destructor_calls_ = expected_calls;
    has_expected_destructor_calls_ = true;
  }

 private:
  void DestructorCalled() { ++destructor_calls_; }

  void CheckDestructExpectation() {
    if (!has_expected_destructor_calls_)
      return;
    EXPECT_EQ(expected_destructor_calls_, destructor_calls_)
        << "element destructor called the wrong number of times";
  }

  // Not using base::Optional<size_t> here in order to get a precise destructor
  // behavior. The tests below need the ability to catch multiple destructor
  // calls, and base::Optional's destructor might make has_value() return false.
  size_t expected_destructor_calls_;
  bool has_expected_destructor_calls_ = false;
  size_t destructor_calls_ = 0;
};

class MockDerivedElementSubclass : public MockDerivedElement {
 public:
  MockDerivedElementSubclass() {
    set_value(kMagicNumberToUseForSimpleDerivedElementTwo);
  }
};

const size_t kCurrentLargestDerivedElementSize =
    std::max(kLargestDerivedElementSize, sizeof(MockDerivedElementSubclass));
const size_t kCurrentLargestDerivedElementAlign =
    std::max(kLargestDerivedElementAlign, alignof(MockDerivedElementSubclass));

TEST(ListContainerTest, ConstructorCalledInAllocateAndConstruct) {
  ListContainer<DerivedElement> list(kCurrentLargestDerivedElementAlign,
                                     kCurrentLargestDerivedElementSize, 0);

  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(kCurrentLargestDerivedElementAlign,
                                     kCurrentLargestDerivedElementSize, 0);

  size_t size = 1;
  MockDerivedElement* de_1 = list.AllocateAndConstruct<MockDerivedElement>();

  de_1->SetExpectedDestructorCalls(1);
  EXPECT_EQ(size, list.size());
  EXPECT_EQ(de_1, list.front());
}

TEST(ListContainerTest, DestructorCalledOnceWhenClear) {
  ListContainer<DerivedElement> list(kCurrentLargestDerivedElementAlign,
                                     kCurrentLargestDerivedElementSize, 0);
  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 exactly once during clear.
  de_1->SetExpectedDestructorCalls(1);

  list.clear();
}

TEST(ListContainerTest, ClearDoesNotMalloc) {
  const size_t reserve = 10;
  ListContainer<DerivedElement> list(kCurrentLargestDerivedElementAlign,
                                     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(kCurrentLargestDerivedElementAlign,
                                     kCurrentLargestDerivedElementSize, 0);
  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 exactly once during clear.
  de_1->SetExpectedDestructorCalls(1);

  list.ReplaceExistingElement<MockDerivedElementSubclass>(list.begin());
  EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementTwo, de_1->get_value());

  list.clear();
}

TEST(ListContainerTest, DestructorCalledOnceWhenErase) {
  ListContainer<DerivedElement> list(kCurrentLargestDerivedElementAlign,
                                     kCurrentLargestDerivedElementSize, 0);
  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 exactly once during clear.
  de_1->SetExpectedDestructorCalls(1);

  list.EraseAndInvalidateAllPointers(list.begin());
}

TEST(ListContainerTest, SimpleIndexAccessNonDerivedElement) {
  ListContainer<NonDerivedElement> list(alignof(NonDerivedElement),
                                        sizeof(NonDerivedElement), 0);

  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(alignof(NonDerivedElement),
                                        sizeof(NonDerivedElement), 0);

  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(alignof(NonDerivedElement),
                                        sizeof(NonDerivedElement), 0);
  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(alignof(NonDerivedElement),
                                        sizeof(NonDerivedElement), 0);
  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(alignof(NonDerivedElement),
                                        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(alignof(NonDerivedElement),
                                        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(alignof(NonDerivedElement),
                                        sizeof(NonDerivedElement), 0);
  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(alignof(NonDerivedElement),
                                        sizeof(NonDerivedElement), 0);
  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(alignof(NonDerivedElement),
                                        sizeof(NonDerivedElement), 0);
  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 (auto nde_iter = nde_list.rbegin(); nde_iter != nde_list.rend();
         ++nde_iter) {
      EXPECT_EQ(*nde_iter, *iter);
      ++iter;
    }
  }
}

TEST(ListContainerTest, SimpleDeletion) {
  ListContainer<DerivedElement> list(kCurrentLargestDerivedElementAlign,
                                     kCurrentLargestDerivedElementSize, 0);
  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(kCurrentLargestDerivedElementAlign,
                                     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(kCurrentLargestDerivedElementAlign,
                                     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(
      kCurrentLargestDerivedElementAlign, kCurrentLargestDerivedElementSize, 0);
  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(kCurrentLargestDerivedElementAlign,
                                     kCurrentLargestDerivedElementSize, 0);
  const int size = 4;
  for (int i = 0; i < size; ++i) {
    SimpleDerivedElement* element =
        list.AllocateAndConstruct<SimpleDerivedElement>();
    element->set_value(i);
  }
  EXPECT_EQ(static_cast<size_t>(size), list.size());

  const int count = 2;
  auto 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(kCurrentLargestDerivedElementAlign,
                                     kCurrentLargestDerivedElementSize, 0);
  const int size = 4;
  for (int i = 0; i < size; ++i) {
    SimpleDerivedElement* element =
        list.AllocateAndConstruct<SimpleDerivedElement>();
    element->set_value(i);
  }
  EXPECT_EQ(static_cast<size_t>(size), list.size());

  const int count = 3;
  auto 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(kCurrentLargestDerivedElementAlign,
                                     kCurrentLargestDerivedElementSize, 0);

  const int count = 3;
  auto 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(kCurrentLargestDerivedElementAlign,
                                     kCurrentLargestDerivedElementSize, 0);
  // 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 = base::size(initial_list);
  for (size_t i = 0; i < size; ++i) {
    SimpleDerivedElement* element =
        list.AllocateAndConstruct<SimpleDerivedElement>();
    element->set_value(initial_list[i]);
  }
  EXPECT_EQ(static_cast<size_t>(size), list.size());

  // Insert the missing elements.
  auto iter = list.begin();
  while (iter != list.end()) {
    auto 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, InsertAfterBegin) {
  ListContainer<DerivedElement> list(kCurrentLargestDerivedElementAlign,
                                     kCurrentLargestDerivedElementSize, 0);
  const int size = 4;
  for (int i = 0; i < size; ++i) {
    SimpleDerivedElement* element =
        list.AllocateAndConstruct<SimpleDerivedElement>();
    element->set_value(i);
  }
  EXPECT_EQ(static_cast<size_t>(size), list.size());

  const int count = 2;
  auto iter = list.InsertAfterAndInvalidateAllPointers<SimpleDerivedElement>(
      list.begin(), count);
  for (int i = 0; i < count; ++i) {
    static_cast<SimpleDerivedElement*>(*iter)->set_value(100 + i);
    ++iter;
  }

  const int expected_result[] = {0, 100, 101, 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, InsertAfterEnd) {
  ListContainer<DerivedElement> list(kCurrentLargestDerivedElementAlign,
                                     kCurrentLargestDerivedElementSize, 0);
  const int size = 4;
  for (int i = 0; i < size; ++i) {
    SimpleDerivedElement* element =
        list.AllocateAndConstruct<SimpleDerivedElement>();
    element->set_value(i);
  }
  EXPECT_EQ(static_cast<size_t>(size), list.size());

  const int count = 3;
  auto iter = list.InsertAfterAndInvalidateAllPointers<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, InsertAfterEmpty) {
  ListContainer<DerivedElement> list(kCurrentLargestDerivedElementAlign,
                                     kCurrentLargestDerivedElementSize, 0);

  const int count = 3;
  auto iter = list.InsertAfterAndInvalidateAllPointers<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, InsertAfterMany) {
  ListContainer<DerivedElement> list(kCurrentLargestDerivedElementAlign,
                                     kCurrentLargestDerivedElementSize, 0);
  // 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 = base::size(initial_list);
  for (size_t i = 0; i < size; ++i) {
    SimpleDerivedElement* element =
        list.AllocateAndConstruct<SimpleDerivedElement>();
    element->set_value(initial_list[i]);
  }
  EXPECT_EQ(static_cast<size_t>(size), list.size());

  // Insert the missing elements.
  auto iter = list.begin();
  while (iter != list.end()) {
    auto 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.InsertAfterAndInvalidateAllPointers<SimpleDerivedElement>(
        iter, 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(kCurrentLargestDerivedElementAlign,
                                     kCurrentLargestDerivedElementSize, 0);
  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(kLargestDerivedElementAlign,
                                     kLargestDerivedElementSize, 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(alignof(NonDerivedElement),
                                        sizeof(NonDerivedElement), 0);
  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(alignof(InstanceCounter),
                                      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(alignof(SmallStruct), 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, Swap) {
  ListContainer<SimpleDerivedElement> list_1(
      kCurrentLargestDerivedElementAlign, kCurrentLargestDerivedElementSize, 0);
  list_1.AllocateAndConstruct<SimpleDerivedElementConstructMagicNumberOne>();
  ListContainer<SimpleDerivedElement> list_2(
      kCurrentLargestDerivedElementAlign, kCurrentLargestDerivedElementSize, 0);
  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(kLargestDerivedElementAlign,
                                     kLargestDerivedElementSize,
                                     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() * kLargestDerivedElementSize);
    ASSERT_LE(capacity, std::max(list.size(), upper_bound_on_min_capacity) *
                            max_waste_factor * kLargestDerivedElementSize);
    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() * kLargestDerivedElementSize);
    ASSERT_LE(capacity, std::max(list.size(), upper_bound_on_min_capacity) *
                            max_waste_factor * kLargestDerivedElementSize);
    list.RemoveLast();
  }
}

}  // namespace
}  // namespace cc