cc/base/list_container_unittest.cc

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "cc/base/list_container.h"
   6
   7 #include <algorithm>
   8 #include <vector>
   9 #include "testing/gmock/include/gmock/gmock.h"
  10 #include "testing/gtest/include/gtest/gtest.h"
  11
  12 namespace cc {
  13 namespace {
  14
  15 // Element class having derived classes.
  16 class DerivedElement {
  17  public:
  18   virtual ~DerivedElement() {}
  19
  20  protected:
  21   bool bool_values[1];
  22   char char_values[1];
  23   int int_values[1];
  24   long long_values[1];
  25 };
  26
  27 class DerivedElement1 : public DerivedElement {
  28  protected:
  29   bool bool_values1[1];
  30   char char_values1[1];
  31   int int_values1[1];
  32   long long_values1[1];
  33 };
  34
  35 class DerivedElement2 : public DerivedElement {
  36  protected:
  37   bool bool_values2[2];
  38   char char_values2[2];
  39   int int_values2[2];
  40   long long_values2[2];
  41 };
  42
  43 class DerivedElement3 : public DerivedElement {
  44  protected:
  45   bool bool_values3[3];
  46   char char_values3[3];
  47   int int_values3[3];
  48   long long_values3[3];
  49 };
  50
  51 const size_t kLargestDerivedElementSize = sizeof(DerivedElement3);
  52
  53 size_t LargestDerivedElementSize() {
  54   static_assert(sizeof(DerivedElement1) <= kLargestDerivedElementSize,
  55                 "Largest Derived Element size needs update. DerivedElement1 is "
  56                 "currently largest.");
  57   static_assert(sizeof(DerivedElement2) <= kLargestDerivedElementSize,
  58                 "Largest Derived Element size needs update. DerivedElement2 is "
  59                 "currently largest.");
  60
  61   return kLargestDerivedElementSize;
  62 }
  63
  64 // Element class having no derived classes.
  65 class NonDerivedElement {
  66  public:
  67   NonDerivedElement() {}
  68   ~NonDerivedElement() {}
  69
  70   int int_values[1];
  71 };
  72
  73 bool isConstNonDerivedElementPointer(const NonDerivedElement* ptr) {
  74   return true;
  75 }
  76
  77 bool isConstNonDerivedElementPointer(NonDerivedElement* ptr) {
  78   return false;
  79 }
  80
  81 const int kMagicNumberToUseForSimpleDerivedElementOne = 42;
  82 const int kMagicNumberToUseForSimpleDerivedElementTwo = 314;
  83 const int kMagicNumberToUseForSimpleDerivedElementThree = 1618;
  84
  85 class SimpleDerivedElement : public DerivedElement {
  86  public:
  87   ~SimpleDerivedElement() override {}
  88   void set_value(int val) { value = val; }
  89   int get_value() { return value; }
  90
  91  private:
  92   int value;
  93 };
  94
  95 class SimpleDerivedElementConstructMagicNumberOne
  96     : public SimpleDerivedElement {
  97  public:
  98   SimpleDerivedElementConstructMagicNumberOne() {
  99     set_value(kMagicNumberToUseForSimpleDerivedElementOne);
 100   }
 101 };
 102
 103 class SimpleDerivedElementConstructMagicNumberTwo
 104     : public SimpleDerivedElement {
 105  public:
 106   SimpleDerivedElementConstructMagicNumberTwo() {
 107     set_value(kMagicNumberToUseForSimpleDerivedElementTwo);
 108   }
 109 };
 110
 111 class SimpleDerivedElementConstructMagicNumberThree
 112     : public SimpleDerivedElement {
 113  public:
 114   SimpleDerivedElementConstructMagicNumberThree() {
 115     set_value(kMagicNumberToUseForSimpleDerivedElementThree);
 116   }
 117 };
 118
 119 class MockDerivedElement : public SimpleDerivedElementConstructMagicNumberOne {
 120  public:
 121   ~MockDerivedElement() override { Destruct(); }
 122   MOCK_METHOD0(Destruct, void());
 123 };
 124
 125 class MockDerivedElementSubclass : public MockDerivedElement {
 126  public:
 127   MockDerivedElementSubclass() {
 128     set_value(kMagicNumberToUseForSimpleDerivedElementTwo);
 129   }
 130 };
 131
 132 const size_t kCurrentLargestDerivedElementSize =
 133     std::max(LargestDerivedElementSize(), sizeof(MockDerivedElementSubclass));
 134
 135 TEST(ListContainerTest, ConstructorCalledInAllocateAndConstruct) {
 136   ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
 137
 138   size_t size = 2;
 139   SimpleDerivedElementConstructMagicNumberOne* de_1 =
 140       list.AllocateAndConstruct<SimpleDerivedElementConstructMagicNumberOne>();
 141   SimpleDerivedElementConstructMagicNumberTwo* de_2 =
 142       list.AllocateAndConstruct<SimpleDerivedElementConstructMagicNumberTwo>();
 143
 144   EXPECT_EQ(size, list.size());
 145   EXPECT_EQ(de_1, list.front());
 146   EXPECT_EQ(de_2, list.back());
 147
 148   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne, de_1->get_value());
 149   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementTwo, de_2->get_value());
 150 }
 151
 152 TEST(ListContainerTest, DestructorCalled) {
 153   ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
 154
 155   size_t size = 1;
 156   MockDerivedElement* de_1 = list.AllocateAndConstruct<MockDerivedElement>();
 157
 158   EXPECT_CALL(*de_1, Destruct());
 159   EXPECT_EQ(size, list.size());
 160   EXPECT_EQ(de_1, list.front());
 161 }
 162
 163 TEST(ListContainerTest, DestructorCalledOnceWhenClear) {
 164   ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
 165   size_t size = 1;
 166   MockDerivedElement* de_1 = list.AllocateAndConstruct<MockDerivedElement>();
 167
 168   EXPECT_EQ(size, list.size());
 169   EXPECT_EQ(de_1, list.front());
 170
 171   // Make sure destructor is called once during clear, and won't be called
 172   // again.
 173   testing::MockFunction<void()> separator;
 174   {
 175     testing::InSequence s;
 176     EXPECT_CALL(*de_1, Destruct());
 177     EXPECT_CALL(separator, Call());
 178     EXPECT_CALL(*de_1, Destruct()).Times(0);
 179   }
 180
 181   list.clear();
 182   separator.Call();
 183 }
 184
 185 TEST(ListContainerTest, ClearDoesNotMalloc) {
 186   const size_t reserve = 10;
 187   ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize,
 188                                      reserve);
 189
 190   // Memory from the initial inner list that should be re-used after clear().
 191   std::vector<DerivedElement*> reserved_element_pointers;
 192   for (size_t i = 0; i < reserve; i++) {
 193     DerivedElement* element = list.AllocateAndConstruct<DerivedElement>();
 194     reserved_element_pointers.push_back(element);
 195   }
 196   EXPECT_EQ(0u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 197
 198   // Allocate more than the reserve count, forcing new capacity to be added.
 199   list.AllocateAndConstruct<DerivedElement>();
 200   EXPECT_NE(0u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 201
 202   // Clear should free all memory except the first |reserve| elements.
 203   list.clear();
 204   EXPECT_EQ(reserve, list.AvailableSizeWithoutAnotherAllocationForTesting());
 205
 206   // Verify the first |reserve| elements are re-used after clear().
 207   for (size_t i = 0; i < reserve; i++) {
 208     DerivedElement* element = list.AllocateAndConstruct<DerivedElement>();
 209     EXPECT_EQ(element, reserved_element_pointers[i]);
 210   }
 211   EXPECT_EQ(0u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 212
 213   // Verify that capacity can still grow properly.
 214   list.AllocateAndConstruct<DerivedElement>();
 215   EXPECT_NE(0u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 216 }
 217
 218 TEST(ListContainerTest, ReplaceExistingElement) {
 219   ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
 220   size_t size = 1;
 221   MockDerivedElement* de_1 = list.AllocateAndConstruct<MockDerivedElement>();
 222
 223   EXPECT_EQ(size, list.size());
 224   EXPECT_EQ(de_1, list.front());
 225
 226   // Make sure destructor is called once during clear, and won't be called
 227   // again.
 228   testing::MockFunction<void()> separator;
 229   {
 230     testing::InSequence s;
 231     EXPECT_CALL(*de_1, Destruct());
 232     EXPECT_CALL(separator, Call());
 233     EXPECT_CALL(*de_1, Destruct()).Times(0);
 234   }
 235
 236   list.ReplaceExistingElement<MockDerivedElementSubclass>(list.begin());
 237   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementTwo, de_1->get_value());
 238   separator.Call();
 239
 240   EXPECT_CALL(*de_1, Destruct());
 241   list.clear();
 242 }
 243
 244 TEST(ListContainerTest, DestructorCalledOnceWhenErase) {
 245   ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
 246   size_t size = 1;
 247   MockDerivedElement* de_1 = list.AllocateAndConstruct<MockDerivedElement>();
 248
 249   EXPECT_EQ(size, list.size());
 250   EXPECT_EQ(de_1, list.front());
 251
 252   // Make sure destructor is called once during clear, and won't be called
 253   // again.
 254   testing::MockFunction<void()> separator;
 255   {
 256     testing::InSequence s;
 257     EXPECT_CALL(*de_1, Destruct());
 258     EXPECT_CALL(separator, Call());
 259     EXPECT_CALL(*de_1, Destruct()).Times(0);
 260   }
 261
 262   list.EraseAndInvalidateAllPointers(list.begin());
 263   separator.Call();
 264 }
 265
 266 TEST(ListContainerTest, SimpleIndexAccessNonDerivedElement) {
 267   ListContainer<NonDerivedElement> list;
 268
 269   size_t size = 3;
 270   NonDerivedElement* nde_1 = list.AllocateAndConstruct<NonDerivedElement>();
 271   NonDerivedElement* nde_2 = list.AllocateAndConstruct<NonDerivedElement>();
 272   NonDerivedElement* nde_3 = list.AllocateAndConstruct<NonDerivedElement>();
 273
 274   EXPECT_EQ(size, list.size());
 275   EXPECT_EQ(nde_1, list.front());
 276   EXPECT_EQ(nde_3, list.back());
 277   EXPECT_EQ(list.front(), list.ElementAt(0));
 278   EXPECT_EQ(nde_2, list.ElementAt(1));
 279   EXPECT_EQ(list.back(), list.ElementAt(2));
 280 }
 281
 282 TEST(ListContainerTest, SimpleInsertionNonDerivedElement) {
 283   ListContainer<NonDerivedElement> list;
 284
 285   size_t size = 3;
 286   NonDerivedElement* nde_1 = list.AllocateAndConstruct<NonDerivedElement>();
 287   list.AllocateAndConstruct<NonDerivedElement>();
 288   NonDerivedElement* nde_3 = list.AllocateAndConstruct<NonDerivedElement>();
 289
 290   EXPECT_EQ(size, list.size());
 291   EXPECT_EQ(nde_1, list.front());
 292   EXPECT_EQ(nde_3, list.back());
 293 }
 294
 295 TEST(ListContainerTest, SimpleInsertionAndClearNonDerivedElement) {
 296   ListContainer<NonDerivedElement> list;
 297   EXPECT_TRUE(list.empty());
 298   EXPECT_EQ(0u, list.size());
 299
 300   size_t size = 3;
 301   NonDerivedElement* nde_1 = list.AllocateAndConstruct<NonDerivedElement>();
 302   list.AllocateAndConstruct<NonDerivedElement>();
 303   NonDerivedElement* nde_3 = list.AllocateAndConstruct<NonDerivedElement>();
 304
 305   EXPECT_EQ(size, list.size());
 306   EXPECT_EQ(nde_1, list.front());
 307   EXPECT_EQ(nde_3, list.back());
 308   EXPECT_FALSE(list.empty());
 309
 310   list.clear();
 311   EXPECT_TRUE(list.empty());
 312   EXPECT_EQ(0u, list.size());
 313 }
 314
 315 TEST(ListContainerTest, SimpleInsertionClearAndInsertAgainNonDerivedElement) {
 316   ListContainer<NonDerivedElement> list;
 317   EXPECT_TRUE(list.empty());
 318   EXPECT_EQ(0u, list.size());
 319
 320   size_t size = 2;
 321   NonDerivedElement* nde_front = list.AllocateAndConstruct<NonDerivedElement>();
 322   NonDerivedElement* nde_back = list.AllocateAndConstruct<NonDerivedElement>();
 323
 324   EXPECT_EQ(size, list.size());
 325   EXPECT_EQ(nde_front, list.front());
 326   EXPECT_EQ(nde_back, list.back());
 327   EXPECT_FALSE(list.empty());
 328
 329   list.clear();
 330   EXPECT_TRUE(list.empty());
 331   EXPECT_EQ(0u, list.size());
 332
 333   size = 3;
 334   nde_front = list.AllocateAndConstruct<NonDerivedElement>();
 335   list.AllocateAndConstruct<NonDerivedElement>();
 336   nde_back = list.AllocateAndConstruct<NonDerivedElement>();
 337
 338   EXPECT_EQ(size, list.size());
 339   EXPECT_EQ(nde_front, list.front());
 340   EXPECT_EQ(nde_back, list.back());
 341   EXPECT_FALSE(list.empty());
 342 }
 343
 344 // This test is used to test when there is more than one allocation needed
 345 // for, ListContainer can still perform like normal vector.
 346 TEST(ListContainerTest,
 347      SimpleInsertionTriggerMoreThanOneAllocationNonDerivedElement) {
 348   ListContainer<NonDerivedElement> list(sizeof(NonDerivedElement), 2);
 349   std::vector<NonDerivedElement*> nde_list;
 350   size_t size = 10;
 351   for (size_t i = 0; i < size; ++i) {
 352     nde_list.push_back(list.AllocateAndConstruct<NonDerivedElement>());
 353   }
 354   EXPECT_EQ(size, list.size());
 355
 356   ListContainer<NonDerivedElement>::Iterator iter = list.begin();
 357   for (std::vector<NonDerivedElement*>::const_iterator nde_iter =
 358            nde_list.begin();
 359        nde_iter != nde_list.end(); ++nde_iter) {
 360     EXPECT_EQ(*nde_iter, *iter);
 361     ++iter;
 362   }
 363 }
 364
 365 TEST(ListContainerTest,
 366      CorrectAllocationSizeForMoreThanOneAllocationNonDerivedElement) {
 367   // Constructor sets the allocation size to 2. Every time ListContainer needs
 368   // to allocate again, it doubles allocation size. In this test, 10 elements is
 369   // needed, thus ListContainerShould allocate spaces 2, 4 and 8 elements.
 370   ListContainer<NonDerivedElement> list(sizeof(NonDerivedElement), 2);
 371   std::vector<NonDerivedElement*> nde_list;
 372   size_t size = 10;
 373   for (size_t i = 0; i < size; ++i) {
 374     // Before asking for a new element, space available without another
 375     // allocation follows.
 376     switch (i) {
 377       case 2:
 378       case 6:
 379         EXPECT_EQ(0u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 380         break;
 381       case 1:
 382       case 5:
 383         EXPECT_EQ(1u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 384         break;
 385       case 0:
 386       case 4:
 387         EXPECT_EQ(2u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 388         break;
 389       case 3:
 390         EXPECT_EQ(3u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 391         break;
 392       case 9:
 393         EXPECT_EQ(5u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 394         break;
 395       case 8:
 396         EXPECT_EQ(6u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 397         break;
 398       case 7:
 399         EXPECT_EQ(7u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 400         break;
 401       default:
 402         break;
 403     }
 404     nde_list.push_back(list.AllocateAndConstruct<NonDerivedElement>());
 405     // After asking for a new element, space available without another
 406     // allocation follows.
 407     switch (i) {
 408       case 1:
 409       case 5:
 410         EXPECT_EQ(0u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 411         break;
 412       case 0:
 413       case 4:
 414         EXPECT_EQ(1u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 415         break;
 416       case 3:
 417         EXPECT_EQ(2u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 418         break;
 419       case 2:
 420         EXPECT_EQ(3u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 421         break;
 422       case 9:
 423         EXPECT_EQ(4u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 424         break;
 425       case 8:
 426         EXPECT_EQ(5u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 427         break;
 428       case 7:
 429         EXPECT_EQ(6u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 430         break;
 431       case 6:
 432         EXPECT_EQ(7u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 433         break;
 434       default:
 435         break;
 436     }
 437   }
 438   EXPECT_EQ(size, list.size());
 439
 440   ListContainer<NonDerivedElement>::Iterator iter = list.begin();
 441   for (std::vector<NonDerivedElement*>::const_iterator nde_iter =
 442            nde_list.begin();
 443        nde_iter != nde_list.end(); ++nde_iter) {
 444     EXPECT_EQ(*nde_iter, *iter);
 445     ++iter;
 446   }
 447 }
 448
 449 TEST(ListContainerTest, SimpleIterationNonDerivedElement) {
 450   ListContainer<NonDerivedElement> list;
 451   std::vector<NonDerivedElement*> nde_list;
 452   size_t size = 10;
 453   for (size_t i = 0; i < size; ++i) {
 454     nde_list.push_back(list.AllocateAndConstruct<NonDerivedElement>());
 455   }
 456   EXPECT_EQ(size, list.size());
 457
 458   size_t num_iters_in_list = 0;
 459   {
 460     std::vector<NonDerivedElement*>::const_iterator nde_iter = nde_list.begin();
 461     for (ListContainer<NonDerivedElement>::Iterator iter = list.begin();
 462          iter != list.end(); ++iter) {
 463       EXPECT_EQ(*nde_iter, *iter);
 464       ++num_iters_in_list;
 465       ++nde_iter;
 466     }
 467   }
 468
 469   size_t num_iters_in_vector = 0;
 470   {
 471     ListContainer<NonDerivedElement>::Iterator iter = list.begin();
 472     for (std::vector<NonDerivedElement*>::const_iterator nde_iter =
 473              nde_list.begin();
 474          nde_iter != nde_list.end(); ++nde_iter) {
 475       EXPECT_EQ(*nde_iter, *iter);
 476       ++num_iters_in_vector;
 477       ++iter;
 478     }
 479   }
 480
 481   EXPECT_EQ(num_iters_in_vector, num_iters_in_list);
 482 }
 483
 484 TEST(ListContainerTest, SimpleConstIteratorIterationNonDerivedElement) {
 485   ListContainer<NonDerivedElement> list;
 486   std::vector<const NonDerivedElement*> nde_list;
 487   size_t size = 10;
 488   for (size_t i = 0; i < size; ++i) {
 489     nde_list.push_back(list.AllocateAndConstruct<NonDerivedElement>());
 490   }
 491   EXPECT_EQ(size, list.size());
 492
 493   {
 494     std::vector<const NonDerivedElement*>::const_iterator nde_iter =
 495         nde_list.begin();
 496     for (ListContainer<NonDerivedElement>::ConstIterator iter = list.begin();
 497          iter != list.end(); ++iter) {
 498       EXPECT_TRUE(isConstNonDerivedElementPointer(*iter));
 499       EXPECT_EQ(*nde_iter, *iter);
 500       ++nde_iter;
 501     }
 502   }
 503
 504   {
 505     std::vector<const NonDerivedElement*>::const_iterator nde_iter =
 506         nde_list.begin();
 507     for (ListContainer<NonDerivedElement>::Iterator iter = list.begin();
 508          iter != list.end(); ++iter) {
 509       EXPECT_FALSE(isConstNonDerivedElementPointer(*iter));
 510       EXPECT_EQ(*nde_iter, *iter);
 511       ++nde_iter;
 512     }
 513   }
 514
 515   {
 516     ListContainer<NonDerivedElement>::ConstIterator iter = list.begin();
 517     for (std::vector<const NonDerivedElement*>::const_iterator nde_iter =
 518              nde_list.begin();
 519          nde_iter != nde_list.end(); ++nde_iter) {
 520       EXPECT_EQ(*nde_iter, *iter);
 521       ++iter;
 522     }
 523   }
 524 }
 525
 526 TEST(ListContainerTest, SimpleReverseInsertionNonDerivedElement) {
 527   ListContainer<NonDerivedElement> list;
 528   std::vector<NonDerivedElement*> nde_list;
 529   size_t size = 10;
 530   for (size_t i = 0; i < size; ++i) {
 531     nde_list.push_back(list.AllocateAndConstruct<NonDerivedElement>());
 532   }
 533   EXPECT_EQ(size, list.size());
 534
 535   {
 536     std::vector<NonDerivedElement*>::const_reverse_iterator nde_iter =
 537         nde_list.rbegin();
 538     for (ListContainer<NonDerivedElement>::ReverseIterator iter = list.rbegin();
 539          iter != list.rend(); ++iter) {
 540       EXPECT_EQ(*nde_iter, *iter);
 541       ++nde_iter;
 542     }
 543   }
 544
 545   {
 546     ListContainer<NonDerivedElement>::ReverseIterator iter = list.rbegin();
 547     for (std::vector<NonDerivedElement*>::reverse_iterator nde_iter =
 548              nde_list.rbegin();
 549          nde_iter != nde_list.rend(); ++nde_iter) {
 550       EXPECT_EQ(*nde_iter, *iter);
 551       ++iter;
 552     }
 553   }
 554 }
 555
 556 TEST(ListContainerTest, SimpleDeletion) {
 557   ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
 558   std::vector<SimpleDerivedElement*> sde_list;
 559   int size = 10;
 560   for (int i = 0; i < size; ++i) {
 561     sde_list.push_back(list.AllocateAndConstruct<SimpleDerivedElement>());
 562     sde_list.back()->set_value(i);
 563   }
 564   EXPECT_EQ(static_cast<size_t>(size), list.size());
 565
 566   list.EraseAndInvalidateAllPointers(list.begin());
 567   --size;
 568   EXPECT_EQ(static_cast<size_t>(size), list.size());
 569   int i = 1;
 570   for (ListContainer<DerivedElement>::Iterator iter = list.begin();
 571        iter != list.end(); ++iter) {
 572     EXPECT_EQ(i, static_cast<SimpleDerivedElement*>(*iter)->get_value());
 573     ++i;
 574   }
 575 }
 576
 577 TEST(ListContainerTest, DeletionAllInAllocation) {
 578   const size_t kReserve = 10;
 579   ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize,
 580                                      kReserve);
 581   std::vector<SimpleDerivedElement*> sde_list;
 582   // Add enough elements to cause another allocation.
 583   for (size_t i = 0; i < kReserve + 1; ++i) {
 584     sde_list.push_back(list.AllocateAndConstruct<SimpleDerivedElement>());
 585     sde_list.back()->set_value(static_cast<int>(i));
 586   }
 587   EXPECT_EQ(kReserve + 1, list.size());
 588
 589   // Remove everything in the first allocation.
 590   for (size_t i = 0; i < kReserve; ++i)
 591     list.EraseAndInvalidateAllPointers(list.begin());
 592   EXPECT_EQ(1u, list.size());
 593
 594   // The last element is left.
 595   SimpleDerivedElement* de = static_cast<SimpleDerivedElement*>(*list.begin());
 596   EXPECT_EQ(static_cast<int>(kReserve), de->get_value());
 597
 598   // Remove the element from the 2nd allocation.
 599   list.EraseAndInvalidateAllPointers(list.begin());
 600   EXPECT_EQ(0u, list.size());
 601 }
 602
 603 TEST(ListContainerTest, DeletionAllInAllocationReversed) {
 604   const size_t kReserve = 10;
 605   ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize,
 606                                      kReserve);
 607   std::vector<SimpleDerivedElement*> sde_list;
 608   // Add enough elements to cause another allocation.
 609   for (size_t i = 0; i < kReserve + 1; ++i) {
 610     sde_list.push_back(list.AllocateAndConstruct<SimpleDerivedElement>());
 611     sde_list.back()->set_value(static_cast<int>(i));
 612   }
 613   EXPECT_EQ(kReserve + 1, list.size());
 614
 615   // Remove everything in the 2nd allocation.
 616   auto it = list.begin();
 617   for (size_t i = 0; i < kReserve; ++i)
 618     ++it;
 619   list.EraseAndInvalidateAllPointers(it);
 620
 621   // The 2nd-last element is next, and the rest of the elements exist.
 622   size_t i = kReserve - 1;
 623   for (auto it = list.rbegin(); it != list.rend(); ++it) {
 624     SimpleDerivedElement* de = static_cast<SimpleDerivedElement*>(*it);
 625     EXPECT_EQ(static_cast<int>(i), de->get_value());
 626     --i;
 627   }
 628
 629   // Can forward iterate too.
 630   i = 0;
 631   for (auto it = list.begin(); it != list.end(); ++it) {
 632     SimpleDerivedElement* de = static_cast<SimpleDerivedElement*>(*it);
 633     EXPECT_EQ(static_cast<int>(i), de->get_value());
 634     ++i;
 635   }
 636
 637   // Remove the last thing from the 1st allocation.
 638   it = list.begin();
 639   for (size_t i = 0; i < kReserve - 1; ++i)
 640     ++it;
 641   list.EraseAndInvalidateAllPointers(it);
 642
 643   // The 2nd-last element is next, and the rest of the elements exist.
 644   i = kReserve - 2;
 645   for (auto it = list.rbegin(); it != list.rend(); ++it) {
 646     SimpleDerivedElement* de = static_cast<SimpleDerivedElement*>(*it);
 647     EXPECT_EQ(static_cast<int>(i), de->get_value());
 648     --i;
 649   }
 650
 651   // Can forward iterate too.
 652   i = 0;
 653   for (auto it = list.begin(); it != list.end(); ++it) {
 654     SimpleDerivedElement* de = static_cast<SimpleDerivedElement*>(*it);
 655     EXPECT_EQ(static_cast<int>(i), de->get_value());
 656     ++i;
 657   }
 658 }
 659
 660 TEST(ListContainerTest, DeletionWhileIterating) {
 661   ListContainer<SimpleDerivedElement> list(kCurrentLargestDerivedElementSize);
 662   for (int i = 0; i < 4; ++i)
 663     list.AllocateAndConstruct<SimpleDerivedElement>()->set_value(i);
 664
 665   // Delete odd elements.
 666   for (auto it = list.begin(); it != list.end();) {
 667     if ((*it)->get_value() % 2)
 668       it = list.EraseAndInvalidateAllPointers(it);
 669     else
 670       ++it;
 671   }
 672
 673   EXPECT_EQ(2u, list.size());
 674   EXPECT_EQ(0, list.front()->get_value());
 675   EXPECT_EQ(2, list.back()->get_value());
 676
 677   // Erase all elements.
 678   for (auto it = list.begin(); it != list.end();)
 679     it = list.EraseAndInvalidateAllPointers(it);
 680
 681   EXPECT_TRUE(list.empty());
 682 }
 683
 684 TEST(ListContainerTest, InsertBeforeBegin) {
 685   ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
 686   std::vector<SimpleDerivedElement*> sde_list;
 687   const int size = 4;
 688   for (int i = 0; i < size; ++i) {
 689     sde_list.push_back(list.AllocateAndConstruct<SimpleDerivedElement>());
 690     sde_list.back()->set_value(i);
 691   }
 692   EXPECT_EQ(static_cast<size_t>(size), list.size());
 693
 694   const int count = 2;
 695   ListContainer<DerivedElement>::Iterator iter =
 696       list.InsertBeforeAndInvalidateAllPointers<SimpleDerivedElement>(
 697           list.begin(), count);
 698   for (int i = 0; i < count; ++i) {
 699     static_cast<SimpleDerivedElement*>(*iter)->set_value(100 + i);
 700     ++iter;
 701   }
 702
 703   const int expected_result[] = {100, 101, 0, 1, 2, 3};
 704   int iter_index = 0;
 705   for (iter = list.begin(); iter != list.end(); ++iter) {
 706     EXPECT_EQ(expected_result[iter_index],
 707               static_cast<SimpleDerivedElement*>(*iter)->get_value());
 708     ++iter_index;
 709   }
 710   EXPECT_EQ(size + count, iter_index);
 711 }
 712
 713 TEST(ListContainerTest, InsertBeforeEnd) {
 714   ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
 715   std::vector<SimpleDerivedElement*> sde_list;
 716   const int size = 4;
 717   for (int i = 0; i < size; ++i) {
 718     sde_list.push_back(list.AllocateAndConstruct<SimpleDerivedElement>());
 719     sde_list.back()->set_value(i);
 720   }
 721   EXPECT_EQ(static_cast<size_t>(size), list.size());
 722
 723   const int count = 3;
 724   ListContainer<DerivedElement>::Iterator iter =
 725       list.InsertBeforeAndInvalidateAllPointers<SimpleDerivedElement>(
 726           list.end(), count);
 727   for (int i = 0; i < count; ++i) {
 728     static_cast<SimpleDerivedElement*>(*iter)->set_value(100 + i);
 729     ++iter;
 730   }
 731
 732   const int expected_result[] = {0, 1, 2, 3, 100, 101, 102};
 733   int iter_index = 0;
 734   for (iter = list.begin(); iter != list.end(); ++iter) {
 735     EXPECT_EQ(expected_result[iter_index],
 736               static_cast<SimpleDerivedElement*>(*iter)->get_value());
 737     ++iter_index;
 738   }
 739   EXPECT_EQ(size + count, iter_index);
 740 }
 741
 742 TEST(ListContainerTest, InsertBeforeEmpty) {
 743   ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
 744
 745   const int count = 3;
 746   ListContainer<DerivedElement>::Iterator iter =
 747       list.InsertBeforeAndInvalidateAllPointers<SimpleDerivedElement>(
 748           list.end(), count);
 749   for (int i = 0; i < count; ++i) {
 750     static_cast<SimpleDerivedElement*>(*iter)->set_value(100 + i);
 751     ++iter;
 752   }
 753
 754   const int expected_result[] = {100, 101, 102};
 755   int iter_index = 0;
 756   for (iter = list.begin(); iter != list.end(); ++iter) {
 757     EXPECT_EQ(expected_result[iter_index],
 758               static_cast<SimpleDerivedElement*>(*iter)->get_value());
 759     ++iter_index;
 760   }
 761   EXPECT_EQ(count, iter_index);
 762 }
 763
 764 TEST(ListContainerTest, InsertBeforeMany) {
 765   ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
 766   std::vector<SimpleDerivedElement*> sde_list;
 767   // Create a partial list of 1,...,99.
 768   int initial_list[] = {
 769       0,  1,  4,  5,  6,  7,  8,  9,  11, 12, 17, 18, 19, 20, 21, 22,
 770       23, 24, 25, 26, 27, 28, 29, 30, 32, 34, 36, 37, 51, 52, 54, 56,
 771       60, 64, 65, 70, 75, 76, 80, 81, 83, 86, 87, 90, 93, 95, 97, 98,
 772   };
 773   const size_t size = sizeof(initial_list) / sizeof(initial_list[0]);
 774   for (size_t i = 0; i < size; ++i) {
 775     sde_list.push_back(list.AllocateAndConstruct<SimpleDerivedElement>());
 776     sde_list.back()->set_value(initial_list[i]);
 777   }
 778   EXPECT_EQ(static_cast<size_t>(size), list.size());
 779
 780   // Insert the missing elements.
 781   ListContainer<DerivedElement>::Iterator iter = list.begin();
 782   while (iter != list.end()) {
 783     ListContainer<DerivedElement>::Iterator iter_next = iter;
 784     ++iter_next;
 785
 786     int value = static_cast<SimpleDerivedElement*>(*iter)->get_value();
 787     int value_next =
 788         iter_next != list.end()
 789             ? static_cast<SimpleDerivedElement*>(*iter_next)->get_value()
 790             : 100;
 791     int count = value_next - value - 1;
 792
 793     iter = list.InsertBeforeAndInvalidateAllPointers<SimpleDerivedElement>(
 794         iter_next, count);
 795     for (int i = value + 1; i < value_next; ++i) {
 796       static_cast<SimpleDerivedElement*>(*iter)->set_value(i);
 797       ++iter;
 798     }
 799   }
 800
 801   int iter_index = 0;
 802   for (iter = list.begin(); iter != list.end(); ++iter) {
 803     EXPECT_EQ(iter_index,
 804               static_cast<SimpleDerivedElement*>(*iter)->get_value());
 805     ++iter_index;
 806   }
 807   EXPECT_EQ(100, iter_index);
 808 }
 809
 810 TEST(ListContainerTest, SimpleManipulationWithIndexSimpleDerivedElement) {
 811   ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
 812   std::vector<SimpleDerivedElement*> de_list;
 813   int size = 10;
 814   for (int i = 0; i < size; ++i) {
 815     de_list.push_back(list.AllocateAndConstruct<SimpleDerivedElement>());
 816   }
 817   EXPECT_EQ(static_cast<size_t>(size), list.size());
 818
 819   for (int i = 0; i < size; ++i) {
 820     static_cast<SimpleDerivedElement*>(list.ElementAt(i))->set_value(i);
 821   }
 822
 823   int i = 0;
 824   for (std::vector<SimpleDerivedElement*>::const_iterator
 825            de_iter = de_list.begin();
 826        de_iter != de_list.end(); ++de_iter, ++i) {
 827     EXPECT_EQ(i, (*de_iter)->get_value());
 828   }
 829 }
 830
 831 TEST(ListContainerTest,
 832      SimpleManipulationWithIndexMoreThanOneAllocationSimpleDerivedElement) {
 833   ListContainer<DerivedElement> list(LargestDerivedElementSize(), 2);
 834   std::vector<SimpleDerivedElement*> de_list;
 835   int size = 10;
 836   for (int i = 0; i < size; ++i) {
 837     de_list.push_back(list.AllocateAndConstruct<SimpleDerivedElement>());
 838   }
 839   EXPECT_EQ(static_cast<size_t>(size), list.size());
 840
 841   for (int i = 0; i < size; ++i) {
 842     static_cast<SimpleDerivedElement*>(list.ElementAt(i))->set_value(i);
 843   }
 844
 845   int i = 0;
 846   for (std::vector<SimpleDerivedElement*>::const_iterator
 847            de_iter = de_list.begin();
 848        de_iter != de_list.end(); ++de_iter, ++i) {
 849     EXPECT_EQ(i, (*de_iter)->get_value());
 850   }
 851 }
 852
 853 TEST(ListContainerTest,
 854      SimpleIterationAndReverseIterationWithIndexNonDerivedElement) {
 855   ListContainer<NonDerivedElement> list;
 856   std::vector<NonDerivedElement*> nde_list;
 857   size_t size = 10;
 858   for (size_t i = 0; i < size; ++i) {
 859     nde_list.push_back(list.AllocateAndConstruct<NonDerivedElement>());
 860   }
 861   EXPECT_EQ(size, list.size());
 862
 863   size_t i = 0;
 864   for (ListContainer<NonDerivedElement>::Iterator iter = list.begin();
 865        iter != list.end(); ++iter) {
 866     EXPECT_EQ(i, iter.index());
 867     ++i;
 868   }
 869
 870   i = 0;
 871   for (ListContainer<NonDerivedElement>::ReverseIterator iter = list.rbegin();
 872        iter != list.rend(); ++iter) {
 873     EXPECT_EQ(i, iter.index());
 874     ++i;
 875   }
 876 }
 877
 878 // Increments an int when constructed (or the counter pointer is supplied) and
 879 // decrements when destructed.
 880 class InstanceCounter {
 881  public:
 882   InstanceCounter() : counter_(nullptr) {}
 883   explicit InstanceCounter(int* counter) { SetCounter(counter); }
 884   ~InstanceCounter() {
 885     if (counter_)
 886       --*counter_;
 887   }
 888   void SetCounter(int* counter) {
 889     counter_ = counter;
 890     ++*counter_;
 891   }
 892
 893  private:
 894   int* counter_;
 895 };
 896
 897 TEST(ListContainerTest, RemoveLastDestruction) {
 898   // We keep an explicit instance count to make sure that the destructors are
 899   // indeed getting called.
 900   int counter = 0;
 901   ListContainer<InstanceCounter> list(sizeof(InstanceCounter), 1);
 902   EXPECT_EQ(0, counter);
 903   EXPECT_EQ(0u, list.size());
 904
 905   // We should be okay to add one and then go back to zero.
 906   list.AllocateAndConstruct<InstanceCounter>()->SetCounter(&counter);
 907   EXPECT_EQ(1, counter);
 908   EXPECT_EQ(1u, list.size());
 909   list.RemoveLast();
 910   EXPECT_EQ(0, counter);
 911   EXPECT_EQ(0u, list.size());
 912
 913   // We should also be okay to remove the last multiple times, as long as there
 914   // are enough elements in the first place.
 915   list.AllocateAndConstruct<InstanceCounter>()->SetCounter(&counter);
 916   list.AllocateAndConstruct<InstanceCounter>()->SetCounter(&counter);
 917   list.AllocateAndConstruct<InstanceCounter>()->SetCounter(&counter);
 918   list.AllocateAndConstruct<InstanceCounter>()->SetCounter(&counter);
 919   list.AllocateAndConstruct<InstanceCounter>()->SetCounter(&counter);
 920   list.AllocateAndConstruct<InstanceCounter>()->SetCounter(&counter);
 921   list.RemoveLast();
 922   list.RemoveLast();
 923   EXPECT_EQ(4, counter);  // Leaves one in the last list.
 924   EXPECT_EQ(4u, list.size());
 925   list.RemoveLast();
 926   EXPECT_EQ(3, counter);  // Removes an inner list from before.
 927   EXPECT_EQ(3u, list.size());
 928 }
 929
 930 // TODO(jbroman): std::equal would work if ListContainer iterators satisfied the
 931 // usual STL iterator constraints. We should fix that.
 932 template <typename It1, typename It2>
 933 bool Equal(It1 it1, const It1& end1, It2 it2) {
 934   for (; it1 != end1; ++it1, ++it2) {
 935     if (!(*it1 == *it2))
 936       return false;
 937   }
 938   return true;
 939 }
 940
 941 TEST(ListContainerTest, RemoveLastIteration) {
 942   struct SmallStruct {
 943     char dummy[16];
 944   };
 945   ListContainer<SmallStruct> list(sizeof(SmallStruct), 1);
 946   std::vector<SmallStruct*> pointers;
 947
 948   // Utilities which keep these two lists in sync and check that their iteration
 949   // order matches.
 950   auto push = [&list, &pointers]() {
 951     pointers.push_back(list.AllocateAndConstruct<SmallStruct>());
 952   };
 953   auto pop = [&list, &pointers]() {
 954     pointers.pop_back();
 955     list.RemoveLast();
 956   };
 957   auto check_equal = [&list, &pointers]() {
 958     // They should be of the same size, and compare equal with all four kinds of
 959     // iteration.
 960     // Apparently Mac doesn't have vector::cbegin and vector::crbegin?
 961     const auto& const_pointers = pointers;
 962     ASSERT_EQ(list.size(), pointers.size());
 963     ASSERT_TRUE(Equal(list.begin(), list.end(), pointers.begin()));
 964     ASSERT_TRUE(Equal(list.cbegin(), list.cend(), const_pointers.begin()));
 965     ASSERT_TRUE(Equal(list.rbegin(), list.rend(), pointers.rbegin()));
 966     ASSERT_TRUE(Equal(list.crbegin(), list.crend(), const_pointers.rbegin()));
 967   };
 968
 969   check_equal();  // Initially empty.
 970   push();
 971   check_equal();  // One full inner list.
 972   push();
 973   check_equal();  // One full, one partially full.
 974   push();
 975   push();
 976   check_equal();  // Two full, one partially full.
 977   pop();
 978   check_equal();  // Two full, one empty.
 979   pop();
 980   check_equal();  // One full, one partially full, one empty.
 981   pop();
 982   check_equal();  // One full, one empty.
 983   push();
 984   pop();
 985   pop();
 986   ASSERT_TRUE(list.empty());
 987   check_equal();  // Empty.
 988 }
 989
 990 TEST(ListContainerTest, AppendByMovingSameList) {
 991   ListContainer<SimpleDerivedElement> list(kCurrentLargestDerivedElementSize);
 992   list.AllocateAndConstruct<SimpleDerivedElementConstructMagicNumberOne>();
 993
 994   list.AppendByMoving(list.front());
 995   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
 996             list.back()->get_value());
 997   EXPECT_EQ(2u, list.size());
 998
 999   list.front()->set_value(kMagicNumberToUseForSimpleDerivedElementTwo);
1000   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementTwo,
1001             list.front()->get_value());
1002   list.AppendByMoving(list.front());
1003   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementTwo,
1004             list.back()->get_value());
1005   EXPECT_EQ(3u, list.size());
1006 }
1007
1008 TEST(ListContainerTest, AppendByMovingDoesNotDestruct) {
1009   ListContainer<DerivedElement> list_1(kCurrentLargestDerivedElementSize);
1010   ListContainer<DerivedElement> list_2(kCurrentLargestDerivedElementSize);
1011   MockDerivedElement* mde_1 = list_1.AllocateAndConstruct<MockDerivedElement>();
1012
1013   // Make sure destructor isn't called during AppendByMoving.
1014   list_2.AppendByMoving(mde_1);
1015   EXPECT_CALL(*mde_1, Destruct()).Times(0);
1016   testing::Mock::VerifyAndClearExpectations(mde_1);
1017   mde_1 = static_cast<MockDerivedElement*>(list_2.back());
1018   EXPECT_CALL(*mde_1, Destruct());
1019 }
1020
1021 TEST(ListContainerTest, AppendByMovingReturnsMovedPointer) {
1022   ListContainer<SimpleDerivedElement> list_1(kCurrentLargestDerivedElementSize);
1023   ListContainer<SimpleDerivedElement> list_2(kCurrentLargestDerivedElementSize);
1024   SimpleDerivedElement* simple_element =
1025       list_1.AllocateAndConstruct<SimpleDerivedElement>();
1026
1027   SimpleDerivedElement* moved_1 = list_2.AppendByMoving(simple_element);
1028   EXPECT_EQ(list_2.back(), moved_1);
1029
1030   SimpleDerivedElement* moved_2 = list_1.AppendByMoving(moved_1);
1031   EXPECT_EQ(list_1.back(), moved_2);
1032   EXPECT_NE(moved_1, moved_2);
1033 }
1034
1035 TEST(ListContainerTest, AppendByMovingReplacesSourceWithNewDerivedElement) {
1036   ListContainer<SimpleDerivedElementConstructMagicNumberOne> list_1(
1037       kCurrentLargestDerivedElementSize);
1038   ListContainer<SimpleDerivedElementConstructMagicNumberTwo> list_2(
1039       kCurrentLargestDerivedElementSize);
1040
1041   list_1.AllocateAndConstruct<SimpleDerivedElementConstructMagicNumberOne>();
1042   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
1043             list_1.front()->get_value());
1044
1045   list_2.AppendByMoving(list_1.front());
1046   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
1047             list_1.front()->get_value());
1048   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
1049             list_2.front()->get_value());
1050
1051   // Change the value of list_2.front() to ensure the value is actually moved.
1052   list_2.back()->set_value(kMagicNumberToUseForSimpleDerivedElementThree);
1053
1054   list_1.AppendByMoving(list_2.back());
1055   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
1056             list_1.front()->get_value());
1057   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementThree,
1058             list_1.back()->get_value());
1059   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementTwo,
1060             list_2.back()->get_value());
1061
1062   // AppendByMoving replaces the source element with a new derived element so
1063   // we do not expect sizes to shrink after AppendByMoving is called.
1064   EXPECT_EQ(2u, list_1.size());  // One direct allocation, one AppendByMoving.
1065   EXPECT_EQ(1u, list_2.size());  // One AppendByMoving.
1066 }
1067
1068 const size_t kLongCountForLongSimpleDerivedElement = 5;
1069
1070 class LongSimpleDerivedElement : public SimpleDerivedElement {
1071  public:
1072   ~LongSimpleDerivedElement() override {}
1073   void SetAllValues(unsigned long value) {
1074     for (size_t i = 0; i < kLongCountForLongSimpleDerivedElement; i++)
1075       values[i] = value;
1076   }
1077   bool AreAllValuesEqualTo(size_t value) const {
1078     for (size_t i = 1; i < kLongCountForLongSimpleDerivedElement; i++) {
1079       if (values[i] != values[0])
1080         return false;
1081     }
1082     return true;
1083   }
1084
1085  private:
1086   unsigned long values[kLongCountForLongSimpleDerivedElement];
1087 };
1088
1089 const unsigned long kMagicNumberToUseForLongSimpleDerivedElement = 2718ul;
1090
1091 class LongSimpleDerivedElementConstructMagicNumber
1092     : public LongSimpleDerivedElement {
1093  public:
1094   LongSimpleDerivedElementConstructMagicNumber() {
1095     SetAllValues(kMagicNumberToUseForLongSimpleDerivedElement);
1096   }
1097 };
1098
1099 TEST(ListContainerTest, AppendByMovingLongAndSimpleDerivedElements) {
1100   static_assert(sizeof(LongSimpleDerivedElement) > sizeof(SimpleDerivedElement),
1101                 "LongSimpleDerivedElement should be larger than "
1102                 "SimpleDerivedElement's size.");
1103   static_assert(sizeof(LongSimpleDerivedElement) <= kLargestDerivedElementSize,
1104                 "LongSimpleDerivedElement should be smaller than the maximum "
1105                 "DerivedElement size.");
1106
1107   ListContainer<SimpleDerivedElement> list(kCurrentLargestDerivedElementSize);
1108   list.AllocateAndConstruct<LongSimpleDerivedElementConstructMagicNumber>();
1109   list.AllocateAndConstruct<SimpleDerivedElementConstructMagicNumberOne>();
1110
1111   EXPECT_TRUE(
1112       static_cast<LongSimpleDerivedElement*>(list.front())
1113           ->AreAllValuesEqualTo(kMagicNumberToUseForLongSimpleDerivedElement));
1114   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
1115             list.back()->get_value());
1116
1117   // Test that moving a simple derived element actually moves enough data so
1118   // that the LongSimpleDerivedElement at this location is entirely moved.
1119   SimpleDerivedElement* simple_element = list.back();
1120   list.AppendByMoving(list.front());
1121   EXPECT_TRUE(
1122       static_cast<LongSimpleDerivedElement*>(list.back())
1123           ->AreAllValuesEqualTo(kMagicNumberToUseForLongSimpleDerivedElement));
1124   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
1125             simple_element->get_value());
1126
1127   LongSimpleDerivedElement* long_element =
1128       static_cast<LongSimpleDerivedElement*>(list.back());
1129   list.AppendByMoving(simple_element);
1130   EXPECT_TRUE(long_element->AreAllValuesEqualTo(
1131       kMagicNumberToUseForLongSimpleDerivedElement));
1132   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
1133             list.back()->get_value());
1134 }
1135
1136 TEST(ListContainerTest, Swap) {
1137   ListContainer<SimpleDerivedElement> list_1(kCurrentLargestDerivedElementSize);
1138   list_1.AllocateAndConstruct<SimpleDerivedElementConstructMagicNumberOne>();
1139   ListContainer<SimpleDerivedElement> list_2(kCurrentLargestDerivedElementSize);
1140   list_2.AllocateAndConstruct<SimpleDerivedElementConstructMagicNumberTwo>();
1141   list_2.AllocateAndConstruct<SimpleDerivedElementConstructMagicNumberThree>();
1142
1143   SimpleDerivedElement* pre_swap_list_1_front = list_1.front();
1144
1145   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
1146             list_1.front()->get_value());
1147   EXPECT_EQ(1u, list_1.size());
1148
1149   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementTwo,
1150             list_2.front()->get_value());
1151   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementThree,
1152             list_2.back()->get_value());
1153   EXPECT_EQ(2u, list_2.size());
1154
1155   list_2.swap(list_1);
1156
1157   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementTwo,
1158             list_1.front()->get_value());
1159   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementThree,
1160             list_1.back()->get_value());
1161   EXPECT_EQ(2u, list_1.size());
1162
1163   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
1164             list_2.front()->get_value());
1165   EXPECT_EQ(1u, list_2.size());
1166
1167   // Ensure pointers are still valid after swapping.
1168   EXPECT_EQ(pre_swap_list_1_front, list_2.front());
1169 }
1170
1171 TEST(ListContainerTest, GetCapacityInBytes) {
1172   const int iterations = 500;
1173   const size_t initial_capacity = 10;
1174   const size_t upper_bound_on_min_capacity = initial_capacity;
1175
1176   // At time of writing, removing elements from the end can cause up to 7x the
1177   // memory required to be consumed, in the worst case, since we can have up to
1178   // two trailing inner lists that are empty (for 2*size + 4*size in unused
1179   // memory, due to the exponential growth strategy).
1180   const size_t max_waste_factor = 8;
1181
1182   ListContainer<DerivedElement> list(LargestDerivedElementSize(),
1183                                      initial_capacity);
1184
1185   // The capacity should grow with the list.
1186   for (int i = 0; i < iterations; i++) {
1187     size_t capacity = list.GetCapacityInBytes();
1188     ASSERT_GE(capacity, list.size() * LargestDerivedElementSize());
1189     ASSERT_LE(capacity, std::max(list.size(), upper_bound_on_min_capacity) *
1190                             max_waste_factor * LargestDerivedElementSize());
1191     list.AllocateAndConstruct<DerivedElement1>();
1192   }
1193
1194   // The capacity should shrink with the list.
1195   for (int i = 0; i < iterations; i++) {
1196     size_t capacity = list.GetCapacityInBytes();
1197     ASSERT_GE(capacity, list.size() * LargestDerivedElementSize());
1198     ASSERT_LE(capacity, std::max(list.size(), upper_bound_on_min_capacity) *
1199                             max_waste_factor * LargestDerivedElementSize());
1200     list.RemoveLast();
1201   }
1202 }
1203
1204 }  // namespace
1205 }  // namespace cc