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, SimpleIterationAndManipulation) {
 661   ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
 662   std::vector<SimpleDerivedElement*> sde_list;
 663   size_t size = 10;
 664   for (size_t i = 0; i < size; ++i) {
 665     SimpleDerivedElement* simple_dq =
 666         list.AllocateAndConstruct<SimpleDerivedElement>();
 667     sde_list.push_back(simple_dq);
 668   }
 669   EXPECT_EQ(size, list.size());
 670
 671   ListContainer<DerivedElement>::Iterator iter = list.begin();
 672   for (int i = 0; i < 10; ++i) {
 673     static_cast<SimpleDerivedElement*>(*iter)->set_value(i);
 674     ++iter;
 675   }
 676
 677   int i = 0;
 678   for (std::vector<SimpleDerivedElement*>::const_iterator sde_iter =
 679            sde_list.begin();
 680        sde_iter < sde_list.end(); ++sde_iter) {
 681     EXPECT_EQ(i, (*sde_iter)->get_value());
 682     ++i;
 683   }
 684 }
 685
 686 TEST(ListContainerTest, SimpleManipulationWithIndexSimpleDerivedElement) {
 687   ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
 688   std::vector<SimpleDerivedElement*> de_list;
 689   int size = 10;
 690   for (int i = 0; i < size; ++i) {
 691     de_list.push_back(list.AllocateAndConstruct<SimpleDerivedElement>());
 692   }
 693   EXPECT_EQ(static_cast<size_t>(size), list.size());
 694
 695   for (int i = 0; i < size; ++i) {
 696     static_cast<SimpleDerivedElement*>(list.ElementAt(i))->set_value(i);
 697   }
 698
 699   int i = 0;
 700   for (std::vector<SimpleDerivedElement*>::const_iterator
 701            de_iter = de_list.begin();
 702        de_iter != de_list.end(); ++de_iter, ++i) {
 703     EXPECT_EQ(i, (*de_iter)->get_value());
 704   }
 705 }
 706
 707 TEST(ListContainerTest,
 708      SimpleManipulationWithIndexMoreThanOneAllocationSimpleDerivedElement) {
 709   ListContainer<DerivedElement> list(LargestDerivedElementSize(), 2);
 710   std::vector<SimpleDerivedElement*> de_list;
 711   int size = 10;
 712   for (int i = 0; i < size; ++i) {
 713     de_list.push_back(list.AllocateAndConstruct<SimpleDerivedElement>());
 714   }
 715   EXPECT_EQ(static_cast<size_t>(size), list.size());
 716
 717   for (int i = 0; i < size; ++i) {
 718     static_cast<SimpleDerivedElement*>(list.ElementAt(i))->set_value(i);
 719   }
 720
 721   int i = 0;
 722   for (std::vector<SimpleDerivedElement*>::const_iterator
 723            de_iter = de_list.begin();
 724        de_iter != de_list.end(); ++de_iter, ++i) {
 725     EXPECT_EQ(i, (*de_iter)->get_value());
 726   }
 727 }
 728
 729 TEST(ListContainerTest,
 730      SimpleIterationAndReverseIterationWithIndexNonDerivedElement) {
 731   ListContainer<NonDerivedElement> list;
 732   std::vector<NonDerivedElement*> nde_list;
 733   size_t size = 10;
 734   for (size_t i = 0; i < size; ++i) {
 735     nde_list.push_back(list.AllocateAndConstruct<NonDerivedElement>());
 736   }
 737   EXPECT_EQ(size, list.size());
 738
 739   size_t i = 0;
 740   for (ListContainer<NonDerivedElement>::Iterator iter = list.begin();
 741        iter != list.end(); ++iter) {
 742     EXPECT_EQ(i, iter.index());
 743     ++i;
 744   }
 745
 746   i = 0;
 747   for (ListContainer<NonDerivedElement>::ReverseIterator iter = list.rbegin();
 748        iter != list.rend(); ++iter) {
 749     EXPECT_EQ(i, iter.index());
 750     ++i;
 751   }
 752 }
 753
 754 // Increments an int when constructed (or the counter pointer is supplied) and
 755 // decrements when destructed.
 756 class InstanceCounter {
 757  public:
 758   InstanceCounter() : counter_(nullptr) {}
 759   explicit InstanceCounter(int* counter) { SetCounter(counter); }
 760   ~InstanceCounter() {
 761     if (counter_)
 762       --*counter_;
 763   }
 764   void SetCounter(int* counter) {
 765     counter_ = counter;
 766     ++*counter_;
 767   }
 768
 769  private:
 770   int* counter_;
 771 };
 772
 773 TEST(ListContainerTest, RemoveLastDestruction) {
 774   // We keep an explicit instance count to make sure that the destructors are
 775   // indeed getting called.
 776   int counter = 0;
 777   ListContainer<InstanceCounter> list(sizeof(InstanceCounter), 1);
 778   EXPECT_EQ(0, counter);
 779   EXPECT_EQ(0u, list.size());
 780
 781   // We should be okay to add one and then go back to zero.
 782   list.AllocateAndConstruct<InstanceCounter>()->SetCounter(&counter);
 783   EXPECT_EQ(1, counter);
 784   EXPECT_EQ(1u, list.size());
 785   list.RemoveLast();
 786   EXPECT_EQ(0, counter);
 787   EXPECT_EQ(0u, list.size());
 788
 789   // We should also be okay to remove the last multiple times, as long as there
 790   // are enough elements in the first place.
 791   list.AllocateAndConstruct<InstanceCounter>()->SetCounter(&counter);
 792   list.AllocateAndConstruct<InstanceCounter>()->SetCounter(&counter);
 793   list.AllocateAndConstruct<InstanceCounter>()->SetCounter(&counter);
 794   list.AllocateAndConstruct<InstanceCounter>()->SetCounter(&counter);
 795   list.AllocateAndConstruct<InstanceCounter>()->SetCounter(&counter);
 796   list.AllocateAndConstruct<InstanceCounter>()->SetCounter(&counter);
 797   list.RemoveLast();
 798   list.RemoveLast();
 799   EXPECT_EQ(4, counter);  // Leaves one in the last list.
 800   EXPECT_EQ(4u, list.size());
 801   list.RemoveLast();
 802   EXPECT_EQ(3, counter);  // Removes an inner list from before.
 803   EXPECT_EQ(3u, list.size());
 804 }
 805
 806 // TODO(jbroman): std::equal would work if ListContainer iterators satisfied the
 807 // usual STL iterator constraints. We should fix that.
 808 template <typename It1, typename It2>
 809 bool Equal(It1 it1, const It1& end1, It2 it2) {
 810   for (; it1 != end1; ++it1, ++it2) {
 811     if (!(*it1 == *it2))
 812       return false;
 813   }
 814   return true;
 815 }
 816
 817 TEST(ListContainerTest, RemoveLastIteration) {
 818   struct SmallStruct {
 819     char dummy[16];
 820   };
 821   ListContainer<SmallStruct> list(sizeof(SmallStruct), 1);
 822   std::vector<SmallStruct*> pointers;
 823
 824   // Utilities which keep these two lists in sync and check that their iteration
 825   // order matches.
 826   auto push = [&list, &pointers]() {
 827     pointers.push_back(list.AllocateAndConstruct<SmallStruct>());
 828   };
 829   auto pop = [&list, &pointers]() {
 830     pointers.pop_back();
 831     list.RemoveLast();
 832   };
 833   auto check_equal = [&list, &pointers]() {
 834     // They should be of the same size, and compare equal with all four kinds of
 835     // iteration.
 836     // Apparently Mac doesn't have vector::cbegin and vector::crbegin?
 837     const auto& const_pointers = pointers;
 838     ASSERT_EQ(list.size(), pointers.size());
 839     ASSERT_TRUE(Equal(list.begin(), list.end(), pointers.begin()));
 840     ASSERT_TRUE(Equal(list.cbegin(), list.cend(), const_pointers.begin()));
 841     ASSERT_TRUE(Equal(list.rbegin(), list.rend(), pointers.rbegin()));
 842     ASSERT_TRUE(Equal(list.crbegin(), list.crend(), const_pointers.rbegin()));
 843   };
 844
 845   check_equal();  // Initially empty.
 846   push();
 847   check_equal();  // One full inner list.
 848   push();
 849   check_equal();  // One full, one partially full.
 850   push();
 851   push();
 852   check_equal();  // Two full, one partially full.
 853   pop();
 854   check_equal();  // Two full, one empty.
 855   pop();
 856   check_equal();  // One full, one partially full, one empty.
 857   pop();
 858   check_equal();  // One full, one empty.
 859   push();
 860   pop();
 861   pop();
 862   ASSERT_TRUE(list.empty());
 863   check_equal();  // Empty.
 864 }
 865
 866 TEST(ListContainerTest, AppendByMovingSameList) {
 867   ListContainer<SimpleDerivedElement> list(kCurrentLargestDerivedElementSize);
 868   list.AllocateAndConstruct<SimpleDerivedElementConstructMagicNumberOne>();
 869
 870   list.AppendByMoving(list.front());
 871   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
 872             list.back()->get_value());
 873   EXPECT_EQ(2u, list.size());
 874
 875   list.front()->set_value(kMagicNumberToUseForSimpleDerivedElementTwo);
 876   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementTwo,
 877             list.front()->get_value());
 878   list.AppendByMoving(list.front());
 879   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementTwo,
 880             list.back()->get_value());
 881   EXPECT_EQ(3u, list.size());
 882 }
 883
 884 TEST(ListContainerTest, AppendByMovingDoesNotDestruct) {
 885   ListContainer<DerivedElement> list_1(kCurrentLargestDerivedElementSize);
 886   ListContainer<DerivedElement> list_2(kCurrentLargestDerivedElementSize);
 887   MockDerivedElement* mde_1 = list_1.AllocateAndConstruct<MockDerivedElement>();
 888
 889   // Make sure destructor isn't called during AppendByMoving.
 890   list_2.AppendByMoving(mde_1);
 891   EXPECT_CALL(*mde_1, Destruct()).Times(0);
 892   testing::Mock::VerifyAndClearExpectations(mde_1);
 893   mde_1 = static_cast<MockDerivedElement*>(list_2.back());
 894   EXPECT_CALL(*mde_1, Destruct());
 895 }
 896
 897 TEST(ListContainerTest, AppendByMovingReturnsMovedPointer) {
 898   ListContainer<SimpleDerivedElement> list_1(kCurrentLargestDerivedElementSize);
 899   ListContainer<SimpleDerivedElement> list_2(kCurrentLargestDerivedElementSize);
 900   SimpleDerivedElement* simple_element =
 901       list_1.AllocateAndConstruct<SimpleDerivedElement>();
 902
 903   SimpleDerivedElement* moved_1 = list_2.AppendByMoving(simple_element);
 904   EXPECT_EQ(list_2.back(), moved_1);
 905
 906   SimpleDerivedElement* moved_2 = list_1.AppendByMoving(moved_1);
 907   EXPECT_EQ(list_1.back(), moved_2);
 908   EXPECT_NE(moved_1, moved_2);
 909 }
 910
 911 TEST(ListContainerTest, AppendByMovingReplacesSourceWithNewDerivedElement) {
 912   ListContainer<SimpleDerivedElementConstructMagicNumberOne> list_1(
 913       kCurrentLargestDerivedElementSize);
 914   ListContainer<SimpleDerivedElementConstructMagicNumberTwo> list_2(
 915       kCurrentLargestDerivedElementSize);
 916
 917   list_1.AllocateAndConstruct<SimpleDerivedElementConstructMagicNumberOne>();
 918   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
 919             list_1.front()->get_value());
 920
 921   list_2.AppendByMoving(list_1.front());
 922   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
 923             list_1.front()->get_value());
 924   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
 925             list_2.front()->get_value());
 926
 927   // Change the value of list_2.front() to ensure the value is actually moved.
 928   list_2.back()->set_value(kMagicNumberToUseForSimpleDerivedElementThree);
 929
 930   list_1.AppendByMoving(list_2.back());
 931   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
 932             list_1.front()->get_value());
 933   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementThree,
 934             list_1.back()->get_value());
 935   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementTwo,
 936             list_2.back()->get_value());
 937
 938   // AppendByMoving replaces the source element with a new derived element so
 939   // we do not expect sizes to shrink after AppendByMoving is called.
 940   EXPECT_EQ(2u, list_1.size());  // One direct allocation, one AppendByMoving.
 941   EXPECT_EQ(1u, list_2.size());  // One AppendByMoving.
 942 }
 943
 944 const size_t kLongCountForLongSimpleDerivedElement = 5;
 945
 946 class LongSimpleDerivedElement : public SimpleDerivedElement {
 947  public:
 948   ~LongSimpleDerivedElement() override {}
 949   void SetAllValues(unsigned long value) {
 950     for (size_t i = 0; i < kLongCountForLongSimpleDerivedElement; i++)
 951       values[i] = value;
 952   }
 953   bool AreAllValuesEqualTo(size_t value) const {
 954     for (size_t i = 1; i < kLongCountForLongSimpleDerivedElement; i++) {
 955       if (values[i] != values[0])
 956         return false;
 957     }
 958     return true;
 959   }
 960
 961  private:
 962   unsigned long values[kLongCountForLongSimpleDerivedElement];
 963 };
 964
 965 const unsigned long kMagicNumberToUseForLongSimpleDerivedElement = 2718ul;
 966
 967 class LongSimpleDerivedElementConstructMagicNumber
 968     : public LongSimpleDerivedElement {
 969  public:
 970   LongSimpleDerivedElementConstructMagicNumber() {
 971     SetAllValues(kMagicNumberToUseForLongSimpleDerivedElement);
 972   }
 973 };
 974
 975 TEST(ListContainerTest, AppendByMovingLongAndSimpleDerivedElements) {
 976   static_assert(sizeof(LongSimpleDerivedElement) > sizeof(SimpleDerivedElement),
 977                 "LongSimpleDerivedElement should be larger than "
 978                 "SimpleDerivedElement's size.");
 979   static_assert(sizeof(LongSimpleDerivedElement) <= kLargestDerivedElementSize,
 980                 "LongSimpleDerivedElement should be smaller than the maximum "
 981                 "DerivedElement size.");
 982
 983   ListContainer<SimpleDerivedElement> list(kCurrentLargestDerivedElementSize);
 984   list.AllocateAndConstruct<LongSimpleDerivedElementConstructMagicNumber>();
 985   list.AllocateAndConstruct<SimpleDerivedElementConstructMagicNumberOne>();
 986
 987   EXPECT_TRUE(
 988       static_cast<LongSimpleDerivedElement*>(list.front())
 989           ->AreAllValuesEqualTo(kMagicNumberToUseForLongSimpleDerivedElement));
 990   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
 991             list.back()->get_value());
 992
 993   // Test that moving a simple derived element actually moves enough data so
 994   // that the LongSimpleDerivedElement at this location is entirely moved.
 995   SimpleDerivedElement* simple_element = list.back();
 996   list.AppendByMoving(list.front());
 997   EXPECT_TRUE(
 998       static_cast<LongSimpleDerivedElement*>(list.back())
 999           ->AreAllValuesEqualTo(kMagicNumberToUseForLongSimpleDerivedElement));
1000   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
1001             simple_element->get_value());
1002
1003   LongSimpleDerivedElement* long_element =
1004       static_cast<LongSimpleDerivedElement*>(list.back());
1005   list.AppendByMoving(simple_element);
1006   EXPECT_TRUE(long_element->AreAllValuesEqualTo(
1007       kMagicNumberToUseForLongSimpleDerivedElement));
1008   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
1009             list.back()->get_value());
1010 }
1011
1012 TEST(ListContainerTest, Swap) {
1013   ListContainer<SimpleDerivedElement> list_1(kCurrentLargestDerivedElementSize);
1014   list_1.AllocateAndConstruct<SimpleDerivedElementConstructMagicNumberOne>();
1015   ListContainer<SimpleDerivedElement> list_2(kCurrentLargestDerivedElementSize);
1016   list_2.AllocateAndConstruct<SimpleDerivedElementConstructMagicNumberTwo>();
1017   list_2.AllocateAndConstruct<SimpleDerivedElementConstructMagicNumberThree>();
1018
1019   SimpleDerivedElement* pre_swap_list_1_front = list_1.front();
1020
1021   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
1022             list_1.front()->get_value());
1023   EXPECT_EQ(1u, list_1.size());
1024
1025   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementTwo,
1026             list_2.front()->get_value());
1027   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementThree,
1028             list_2.back()->get_value());
1029   EXPECT_EQ(2u, list_2.size());
1030
1031   list_2.swap(list_1);
1032
1033   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementTwo,
1034             list_1.front()->get_value());
1035   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementThree,
1036             list_1.back()->get_value());
1037   EXPECT_EQ(2u, list_1.size());
1038
1039   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne,
1040             list_2.front()->get_value());
1041   EXPECT_EQ(1u, list_2.size());
1042
1043   // Ensure pointers are still valid after swapping.
1044   EXPECT_EQ(pre_swap_list_1_front, list_2.front());
1045 }
1046
1047 TEST(ListContainerTest, GetCapacityInBytes) {
1048   const int iterations = 500;
1049   const size_t initial_capacity = 10;
1050   const size_t upper_bound_on_min_capacity = initial_capacity;
1051
1052   // At time of writing, removing elements from the end can cause up to 7x the
1053   // memory required to be consumed, in the worst case, since we can have up to
1054   // two trailing inner lists that are empty (for 2*size + 4*size in unused
1055   // memory, due to the exponential growth strategy).
1056   const size_t max_waste_factor = 8;
1057
1058   ListContainer<DerivedElement> list(LargestDerivedElementSize(),
1059                                      initial_capacity);
1060
1061   // The capacity should grow with the list.
1062   for (int i = 0; i < iterations; i++) {
1063     size_t capacity = list.GetCapacityInBytes();
1064     ASSERT_GE(capacity, list.size() * LargestDerivedElementSize());
1065     ASSERT_LE(capacity, std::max(list.size(), upper_bound_on_min_capacity) *
1066                             max_waste_factor * LargestDerivedElementSize());
1067     list.AllocateAndConstruct<DerivedElement1>();
1068   }
1069
1070   // The capacity should shrink with the list.
1071   for (int i = 0; i < iterations; i++) {
1072     size_t capacity = list.GetCapacityInBytes();
1073     ASSERT_GE(capacity, list.size() * LargestDerivedElementSize());
1074     ASSERT_LE(capacity, std::max(list.size(), upper_bound_on_min_capacity) *
1075                             max_waste_factor * LargestDerivedElementSize());
1076     list.RemoveLast();
1077   }
1078 }
1079
1080 }  // namespace
1081 }  // namespace cc