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 <vector>
   8 #include "testing/gmock/include/gmock/gmock.h"
   9 #include "testing/gtest/include/gtest/gtest.h"
  10
  11 namespace cc {
  12 namespace {
  13
  14 // Element class having derived classes.
  15 class DerivedElement {
  16  public:
  17   virtual ~DerivedElement() {}
  18
  19  protected:
  20   bool bool_values[1];
  21   char char_values[1];
  22   int int_values[1];
  23   long long_values[1];
  24 };
  25
  26 class DerivedElement1 : public DerivedElement {
  27  protected:
  28   bool bool_values1[1];
  29   char char_values1[1];
  30   int int_values1[1];
  31   long long_values1[1];
  32 };
  33
  34 class DerivedElement2 : public DerivedElement {
  35  protected:
  36   bool bool_values2[2];
  37   char char_values2[2];
  38   int int_values2[2];
  39   long long_values2[2];
  40 };
  41
  42 class DerivedElement3 : public DerivedElement {
  43  protected:
  44   bool bool_values3[3];
  45   char char_values3[3];
  46   int int_values3[3];
  47   long long_values3[3];
  48 };
  49
  50 const size_t kLargestDerivedElementSize = sizeof(DerivedElement3);
  51
  52 size_t LargestDerivedElementSize() {
  53   static_assert(sizeof(DerivedElement1) <= kLargestDerivedElementSize,
  54                 "Largest Derived Element size needs update. DerivedElement1 is "
  55                 "currently largest.");
  56   static_assert(sizeof(DerivedElement2) <= kLargestDerivedElementSize,
  57                 "Largest Derived Element size needs update. DerivedElement2 is "
  58                 "currently largest.");
  59
  60   return kLargestDerivedElementSize;
  61 }
  62
  63 // Element class having no derived classes.
  64 class NonDerivedElement {
  65  public:
  66   NonDerivedElement() {}
  67   ~NonDerivedElement() {}
  68
  69   int int_values[1];
  70 };
  71
  72 bool isConstNonDerivedElementPointer(const NonDerivedElement* ptr) {
  73   return true;
  74 }
  75
  76 bool isConstNonDerivedElementPointer(NonDerivedElement* ptr) {
  77   return false;
  78 }
  79
  80 const int kMagicNumberToUseForSimpleDerivedElementOne = 42;
  81 const int kMagicNumberToUseForSimpleDerivedElementTwo = 314;
  82
  83 class SimpleDerivedElement : public DerivedElement {
  84  public:
  85   ~SimpleDerivedElement() override {}
  86   void set_value(int val) { value = val; }
  87   int get_value() { return value; }
  88
  89  private:
  90   int value;
  91 };
  92
  93 class SimpleDerivedElementConstructMagicNumberOne
  94     : public SimpleDerivedElement {
  95  public:
  96   SimpleDerivedElementConstructMagicNumberOne() : SimpleDerivedElement() {
  97     set_value(kMagicNumberToUseForSimpleDerivedElementOne);
  98   }
  99 };
 100
 101 class SimpleDerivedElementConstructMagicNumberTwo
 102     : public SimpleDerivedElement {
 103  public:
 104   SimpleDerivedElementConstructMagicNumberTwo() : SimpleDerivedElement() {
 105     set_value(kMagicNumberToUseForSimpleDerivedElementTwo);
 106   }
 107 };
 108
 109 class MockDerivedElement : public SimpleDerivedElementConstructMagicNumberOne {
 110  public:
 111   ~MockDerivedElement() override { Destruct(); }
 112   MOCK_METHOD0(Destruct, void());
 113 };
 114
 115 class MockDerivedElementSubclass : public MockDerivedElement {
 116  public:
 117   MockDerivedElementSubclass() {
 118     set_value(kMagicNumberToUseForSimpleDerivedElementTwo);
 119   }
 120 };
 121
 122 const size_t kCurrentLargestDerivedElementSize =
 123     std::max(LargestDerivedElementSize(), sizeof(MockDerivedElementSubclass));
 124
 125 TEST(ListContainerTest, ConstructorCalledInAllocateAndConstruct) {
 126   ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
 127
 128   size_t size = 2;
 129   SimpleDerivedElementConstructMagicNumberOne* de_1 =
 130       list.AllocateAndConstruct<SimpleDerivedElementConstructMagicNumberOne>();
 131   SimpleDerivedElementConstructMagicNumberTwo* de_2 =
 132       list.AllocateAndConstruct<SimpleDerivedElementConstructMagicNumberTwo>();
 133
 134   EXPECT_EQ(size, list.size());
 135   EXPECT_EQ(de_1, list.front());
 136   EXPECT_EQ(de_2, list.back());
 137
 138   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementOne, de_1->get_value());
 139   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementTwo, de_2->get_value());
 140 }
 141
 142 TEST(ListContainerTest, DestructorCalled) {
 143   ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
 144
 145   size_t size = 1;
 146   MockDerivedElement* de_1 = list.AllocateAndConstruct<MockDerivedElement>();
 147
 148   EXPECT_CALL(*de_1, Destruct());
 149   EXPECT_EQ(size, list.size());
 150   EXPECT_EQ(de_1, list.front());
 151 }
 152
 153 TEST(ListContainerTest, DestructorCalledOnceWhenClear) {
 154   ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
 155   size_t size = 1;
 156   MockDerivedElement* de_1 = list.AllocateAndConstruct<MockDerivedElement>();
 157
 158   EXPECT_EQ(size, list.size());
 159   EXPECT_EQ(de_1, list.front());
 160
 161   // Make sure destructor is called once during clear, and won't be called
 162   // again.
 163   testing::MockFunction<void()> separator;
 164   {
 165     testing::InSequence s;
 166     EXPECT_CALL(*de_1, Destruct());
 167     EXPECT_CALL(separator, Call());
 168     EXPECT_CALL(*de_1, Destruct()).Times(0);
 169   }
 170
 171   list.clear();
 172   separator.Call();
 173 }
 174
 175 TEST(ListContainerTest, ReplaceExistingElement) {
 176   ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
 177   size_t size = 1;
 178   MockDerivedElement* de_1 = list.AllocateAndConstruct<MockDerivedElement>();
 179
 180   EXPECT_EQ(size, list.size());
 181   EXPECT_EQ(de_1, list.front());
 182
 183   // Make sure destructor is called once during clear, and won't be called
 184   // again.
 185   testing::MockFunction<void()> separator;
 186   {
 187     testing::InSequence s;
 188     EXPECT_CALL(*de_1, Destruct());
 189     EXPECT_CALL(separator, Call());
 190     EXPECT_CALL(*de_1, Destruct()).Times(0);
 191   }
 192
 193   list.ReplaceExistingElement<MockDerivedElementSubclass>(list.begin());
 194   EXPECT_EQ(kMagicNumberToUseForSimpleDerivedElementTwo, de_1->get_value());
 195   separator.Call();
 196
 197   EXPECT_CALL(*de_1, Destruct());
 198   list.clear();
 199 }
 200
 201 TEST(ListContainerTest, DestructorCalledOnceWhenErase) {
 202   ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
 203   size_t size = 1;
 204   MockDerivedElement* de_1 = list.AllocateAndConstruct<MockDerivedElement>();
 205
 206   EXPECT_EQ(size, list.size());
 207   EXPECT_EQ(de_1, list.front());
 208
 209   // Make sure destructor is called once during clear, and won't be called
 210   // again.
 211   testing::MockFunction<void()> separator;
 212   {
 213     testing::InSequence s;
 214     EXPECT_CALL(*de_1, Destruct());
 215     EXPECT_CALL(separator, Call());
 216     EXPECT_CALL(*de_1, Destruct()).Times(0);
 217   }
 218
 219   list.EraseAndInvalidateAllPointers(list.begin());
 220   separator.Call();
 221 }
 222
 223 TEST(ListContainerTest, SimpleIndexAccessNonDerivedElement) {
 224   ListContainer<NonDerivedElement> list;
 225
 226   size_t size = 3;
 227   NonDerivedElement* nde_1 = list.AllocateAndConstruct<NonDerivedElement>();
 228   NonDerivedElement* nde_2 = list.AllocateAndConstruct<NonDerivedElement>();
 229   NonDerivedElement* nde_3 = list.AllocateAndConstruct<NonDerivedElement>();
 230
 231   EXPECT_EQ(size, list.size());
 232   EXPECT_EQ(nde_1, list.front());
 233   EXPECT_EQ(nde_3, list.back());
 234   EXPECT_EQ(list.front(), list.ElementAt(0));
 235   EXPECT_EQ(nde_2, list.ElementAt(1));
 236   EXPECT_EQ(list.back(), list.ElementAt(2));
 237 }
 238
 239 TEST(ListContainerTest, SimpleInsertionNonDerivedElement) {
 240   ListContainer<NonDerivedElement> list;
 241
 242   size_t size = 3;
 243   NonDerivedElement* nde_1 = list.AllocateAndConstruct<NonDerivedElement>();
 244   list.AllocateAndConstruct<NonDerivedElement>();
 245   NonDerivedElement* nde_3 = list.AllocateAndConstruct<NonDerivedElement>();
 246
 247   EXPECT_EQ(size, list.size());
 248   EXPECT_EQ(nde_1, list.front());
 249   EXPECT_EQ(nde_3, list.back());
 250 }
 251
 252 TEST(ListContainerTest, SimpleInsertionAndClearNonDerivedElement) {
 253   ListContainer<NonDerivedElement> list;
 254   EXPECT_TRUE(list.empty());
 255   EXPECT_EQ(0u, list.size());
 256
 257   size_t size = 3;
 258   NonDerivedElement* nde_1 = list.AllocateAndConstruct<NonDerivedElement>();
 259   list.AllocateAndConstruct<NonDerivedElement>();
 260   NonDerivedElement* nde_3 = list.AllocateAndConstruct<NonDerivedElement>();
 261
 262   EXPECT_EQ(size, list.size());
 263   EXPECT_EQ(nde_1, list.front());
 264   EXPECT_EQ(nde_3, list.back());
 265   EXPECT_FALSE(list.empty());
 266
 267   list.clear();
 268   EXPECT_TRUE(list.empty());
 269   EXPECT_EQ(0u, list.size());
 270 }
 271
 272 TEST(ListContainerTest, SimpleInsertionClearAndInsertAgainNonDerivedElement) {
 273   ListContainer<NonDerivedElement> list;
 274   EXPECT_TRUE(list.empty());
 275   EXPECT_EQ(0u, list.size());
 276
 277   size_t size = 2;
 278   NonDerivedElement* nde_front = list.AllocateAndConstruct<NonDerivedElement>();
 279   NonDerivedElement* nde_back = list.AllocateAndConstruct<NonDerivedElement>();
 280
 281   EXPECT_EQ(size, list.size());
 282   EXPECT_EQ(nde_front, list.front());
 283   EXPECT_EQ(nde_back, list.back());
 284   EXPECT_FALSE(list.empty());
 285
 286   list.clear();
 287   EXPECT_TRUE(list.empty());
 288   EXPECT_EQ(0u, list.size());
 289
 290   size = 3;
 291   nde_front = list.AllocateAndConstruct<NonDerivedElement>();
 292   list.AllocateAndConstruct<NonDerivedElement>();
 293   nde_back = list.AllocateAndConstruct<NonDerivedElement>();
 294
 295   EXPECT_EQ(size, list.size());
 296   EXPECT_EQ(nde_front, list.front());
 297   EXPECT_EQ(nde_back, list.back());
 298   EXPECT_FALSE(list.empty());
 299 }
 300
 301 // This test is used to test when there is more than one allocation needed
 302 // for, ListContainer can still perform like normal vector.
 303 TEST(ListContainerTest,
 304      SimpleInsertionTriggerMoreThanOneAllocationNonDerivedElement) {
 305   ListContainer<NonDerivedElement> list(sizeof(NonDerivedElement), 2);
 306   std::vector<NonDerivedElement*> nde_list;
 307   size_t size = 10;
 308   for (size_t i = 0; i < size; ++i) {
 309     nde_list.push_back(list.AllocateAndConstruct<NonDerivedElement>());
 310   }
 311   EXPECT_EQ(size, list.size());
 312
 313   ListContainer<NonDerivedElement>::Iterator iter = list.begin();
 314   for (std::vector<NonDerivedElement*>::const_iterator nde_iter =
 315            nde_list.begin();
 316        nde_iter != nde_list.end(); ++nde_iter) {
 317     EXPECT_EQ(*nde_iter, *iter);
 318     ++iter;
 319   }
 320 }
 321
 322 TEST(ListContainerTest,
 323      CorrectAllocationSizeForMoreThanOneAllocationNonDerivedElement) {
 324   // Constructor sets the allocation size to 2. Every time ListContainer needs
 325   // to allocate again, it doubles allocation size. In this test, 10 elements is
 326   // needed, thus ListContainerShould allocate spaces 2, 4 and 8 elements.
 327   ListContainer<NonDerivedElement> list(sizeof(NonDerivedElement), 2);
 328   std::vector<NonDerivedElement*> nde_list;
 329   size_t size = 10;
 330   for (size_t i = 0; i < size; ++i) {
 331     // Before asking for a new element, space available without another
 332     // allocation follows.
 333     switch (i) {
 334       case 2:
 335       case 6:
 336         EXPECT_EQ(0u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 337         break;
 338       case 1:
 339       case 5:
 340         EXPECT_EQ(1u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 341         break;
 342       case 0:
 343       case 4:
 344         EXPECT_EQ(2u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 345         break;
 346       case 3:
 347         EXPECT_EQ(3u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 348         break;
 349       case 9:
 350         EXPECT_EQ(5u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 351         break;
 352       case 8:
 353         EXPECT_EQ(6u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 354         break;
 355       case 7:
 356         EXPECT_EQ(7u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 357         break;
 358       default:
 359         break;
 360     }
 361     nde_list.push_back(list.AllocateAndConstruct<NonDerivedElement>());
 362     // After asking for a new element, space available without another
 363     // allocation follows.
 364     switch (i) {
 365       case 1:
 366       case 5:
 367         EXPECT_EQ(0u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 368         break;
 369       case 0:
 370       case 4:
 371         EXPECT_EQ(1u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 372         break;
 373       case 3:
 374         EXPECT_EQ(2u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 375         break;
 376       case 2:
 377         EXPECT_EQ(3u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 378         break;
 379       case 9:
 380         EXPECT_EQ(4u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 381         break;
 382       case 8:
 383         EXPECT_EQ(5u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 384         break;
 385       case 7:
 386         EXPECT_EQ(6u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 387         break;
 388       case 6:
 389         EXPECT_EQ(7u, list.AvailableSizeWithoutAnotherAllocationForTesting());
 390         break;
 391       default:
 392         break;
 393     }
 394   }
 395   EXPECT_EQ(size, list.size());
 396
 397   ListContainer<NonDerivedElement>::Iterator iter = list.begin();
 398   for (std::vector<NonDerivedElement*>::const_iterator nde_iter =
 399            nde_list.begin();
 400        nde_iter != nde_list.end(); ++nde_iter) {
 401     EXPECT_EQ(*nde_iter, *iter);
 402     ++iter;
 403   }
 404 }
 405
 406 TEST(ListContainerTest, SimpleIterationNonDerivedElement) {
 407   ListContainer<NonDerivedElement> list;
 408   std::vector<NonDerivedElement*> nde_list;
 409   size_t size = 10;
 410   for (size_t i = 0; i < size; ++i) {
 411     nde_list.push_back(list.AllocateAndConstruct<NonDerivedElement>());
 412   }
 413   EXPECT_EQ(size, list.size());
 414
 415   size_t num_iters_in_list = 0;
 416   {
 417     std::vector<NonDerivedElement*>::const_iterator nde_iter = nde_list.begin();
 418     for (ListContainer<NonDerivedElement>::Iterator iter = list.begin();
 419          iter != list.end(); ++iter) {
 420       EXPECT_EQ(*nde_iter, *iter);
 421       ++num_iters_in_list;
 422       ++nde_iter;
 423     }
 424   }
 425
 426   size_t num_iters_in_vector = 0;
 427   {
 428     ListContainer<NonDerivedElement>::Iterator iter = list.begin();
 429     for (std::vector<NonDerivedElement*>::const_iterator nde_iter =
 430              nde_list.begin();
 431          nde_iter != nde_list.end(); ++nde_iter) {
 432       EXPECT_EQ(*nde_iter, *iter);
 433       ++num_iters_in_vector;
 434       ++iter;
 435     }
 436   }
 437
 438   EXPECT_EQ(num_iters_in_vector, num_iters_in_list);
 439 }
 440
 441 TEST(ListContainerTest, SimpleConstIteratorIterationNonDerivedElement) {
 442   ListContainer<NonDerivedElement> list;
 443   std::vector<const NonDerivedElement*> nde_list;
 444   size_t size = 10;
 445   for (size_t i = 0; i < size; ++i) {
 446     nde_list.push_back(list.AllocateAndConstruct<NonDerivedElement>());
 447   }
 448   EXPECT_EQ(size, list.size());
 449
 450   {
 451     std::vector<const NonDerivedElement*>::const_iterator nde_iter =
 452         nde_list.begin();
 453     for (ListContainer<NonDerivedElement>::ConstIterator iter = list.begin();
 454          iter != list.end(); ++iter) {
 455       EXPECT_TRUE(isConstNonDerivedElementPointer(*iter));
 456       EXPECT_EQ(*nde_iter, *iter);
 457       ++nde_iter;
 458     }
 459   }
 460
 461   {
 462     std::vector<const NonDerivedElement*>::const_iterator nde_iter =
 463         nde_list.begin();
 464     for (ListContainer<NonDerivedElement>::Iterator iter = list.begin();
 465          iter != list.end(); ++iter) {
 466       EXPECT_FALSE(isConstNonDerivedElementPointer(*iter));
 467       EXPECT_EQ(*nde_iter, *iter);
 468       ++nde_iter;
 469     }
 470   }
 471
 472   {
 473     ListContainer<NonDerivedElement>::ConstIterator iter = list.begin();
 474     for (std::vector<const NonDerivedElement*>::const_iterator nde_iter =
 475              nde_list.begin();
 476          nde_iter != nde_list.end(); ++nde_iter) {
 477       EXPECT_EQ(*nde_iter, *iter);
 478       ++iter;
 479     }
 480   }
 481 }
 482
 483 TEST(ListContainerTest, SimpleReverseInsertionNonDerivedElement) {
 484   ListContainer<NonDerivedElement> list;
 485   std::vector<NonDerivedElement*> nde_list;
 486   size_t size = 10;
 487   for (size_t i = 0; i < size; ++i) {
 488     nde_list.push_back(list.AllocateAndConstruct<NonDerivedElement>());
 489   }
 490   EXPECT_EQ(size, list.size());
 491
 492   {
 493     std::vector<NonDerivedElement*>::const_reverse_iterator nde_iter =
 494         nde_list.rbegin();
 495     for (ListContainer<NonDerivedElement>::ReverseIterator iter = list.rbegin();
 496          iter != list.rend(); ++iter) {
 497       EXPECT_EQ(*nde_iter, *iter);
 498       ++nde_iter;
 499     }
 500   }
 501
 502   {
 503     ListContainer<NonDerivedElement>::ReverseIterator iter = list.rbegin();
 504     for (std::vector<NonDerivedElement*>::reverse_iterator nde_iter =
 505              nde_list.rbegin();
 506          nde_iter != nde_list.rend(); ++nde_iter) {
 507       EXPECT_EQ(*nde_iter, *iter);
 508       ++iter;
 509     }
 510   }
 511 }
 512
 513 TEST(ListContainerTest, SimpleDeletion) {
 514   ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
 515   std::vector<SimpleDerivedElement*> sde_list;
 516   int size = 10;
 517   for (int i = 0; i < size; ++i) {
 518     sde_list.push_back(list.AllocateAndConstruct<SimpleDerivedElement>());
 519     sde_list.back()->set_value(i);
 520   }
 521   EXPECT_EQ(static_cast<size_t>(size), list.size());
 522
 523   list.EraseAndInvalidateAllPointers(list.begin());
 524   --size;
 525   EXPECT_EQ(static_cast<size_t>(size), list.size());
 526   int i = 1;
 527   for (ListContainer<DerivedElement>::Iterator iter = list.begin();
 528        iter != list.end(); ++iter) {
 529     EXPECT_EQ(i, static_cast<SimpleDerivedElement*>(*iter)->get_value());
 530     ++i;
 531   }
 532 }
 533
 534 TEST(ListContainerTest, DeletionAllInAllocation) {
 535   const size_t kReserve = 10;
 536   ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize,
 537                                      kReserve);
 538   std::vector<SimpleDerivedElement*> sde_list;
 539   // Add enough elements to cause another allocation.
 540   for (size_t i = 0; i < kReserve + 1; ++i) {
 541     sde_list.push_back(list.AllocateAndConstruct<SimpleDerivedElement>());
 542     sde_list.back()->set_value(static_cast<int>(i));
 543   }
 544   EXPECT_EQ(kReserve + 1, list.size());
 545
 546   // Remove everything in the first allocation.
 547   for (size_t i = 0; i < kReserve; ++i)
 548     list.EraseAndInvalidateAllPointers(list.begin());
 549   EXPECT_EQ(1u, list.size());
 550
 551   // The last element is left.
 552   SimpleDerivedElement* de = static_cast<SimpleDerivedElement*>(*list.begin());
 553   EXPECT_EQ(static_cast<int>(kReserve), de->get_value());
 554
 555   // Remove the element from the 2nd allocation.
 556   list.EraseAndInvalidateAllPointers(list.begin());
 557   EXPECT_EQ(0u, list.size());
 558 }
 559
 560 TEST(ListContainerTest, DeletionAllInAllocationReversed) {
 561   const size_t kReserve = 10;
 562   ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize,
 563                                      kReserve);
 564   std::vector<SimpleDerivedElement*> sde_list;
 565   // Add enough elements to cause another allocation.
 566   for (size_t i = 0; i < kReserve + 1; ++i) {
 567     sde_list.push_back(list.AllocateAndConstruct<SimpleDerivedElement>());
 568     sde_list.back()->set_value(static_cast<int>(i));
 569   }
 570   EXPECT_EQ(kReserve + 1, list.size());
 571
 572   // Remove everything in the 2nd allocation.
 573   auto it = list.begin();
 574   for (size_t i = 0; i < kReserve; ++i)
 575     ++it;
 576   list.EraseAndInvalidateAllPointers(it);
 577
 578   // The 2nd-last element is next, and the rest of the elements exist.
 579   size_t i = kReserve - 1;
 580   for (auto it = list.rbegin(); it != list.rend(); ++it) {
 581     SimpleDerivedElement* de = static_cast<SimpleDerivedElement*>(*it);
 582     EXPECT_EQ(static_cast<int>(i), de->get_value());
 583     --i;
 584   }
 585
 586   // Can forward iterate too.
 587   i = 0;
 588   for (auto it = list.begin(); it != list.end(); ++it) {
 589     SimpleDerivedElement* de = static_cast<SimpleDerivedElement*>(*it);
 590     EXPECT_EQ(static_cast<int>(i), de->get_value());
 591     ++i;
 592   }
 593
 594   // Remove the last thing from the 1st allocation.
 595   it = list.begin();
 596   for (size_t i = 0; i < kReserve - 1; ++i)
 597     ++it;
 598   list.EraseAndInvalidateAllPointers(it);
 599
 600   // The 2nd-last element is next, and the rest of the elements exist.
 601   i = kReserve - 2;
 602   for (auto it = list.rbegin(); it != list.rend(); ++it) {
 603     SimpleDerivedElement* de = static_cast<SimpleDerivedElement*>(*it);
 604     EXPECT_EQ(static_cast<int>(i), de->get_value());
 605     --i;
 606   }
 607
 608   // Can forward iterate too.
 609   i = 0;
 610   for (auto it = list.begin(); it != list.end(); ++it) {
 611     SimpleDerivedElement* de = static_cast<SimpleDerivedElement*>(*it);
 612     EXPECT_EQ(static_cast<int>(i), de->get_value());
 613     ++i;
 614   }
 615 }
 616
 617 TEST(ListContainerTest, SimpleIterationAndManipulation) {
 618   ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
 619   std::vector<SimpleDerivedElement*> sde_list;
 620   size_t size = 10;
 621   for (size_t i = 0; i < size; ++i) {
 622     SimpleDerivedElement* simple_dq =
 623         list.AllocateAndConstruct<SimpleDerivedElement>();
 624     sde_list.push_back(simple_dq);
 625   }
 626   EXPECT_EQ(size, list.size());
 627
 628   ListContainer<DerivedElement>::Iterator iter = list.begin();
 629   for (int i = 0; i < 10; ++i) {
 630     static_cast<SimpleDerivedElement*>(*iter)->set_value(i);
 631     ++iter;
 632   }
 633
 634   int i = 0;
 635   for (std::vector<SimpleDerivedElement*>::const_iterator sde_iter =
 636            sde_list.begin();
 637        sde_iter < sde_list.end(); ++sde_iter) {
 638     EXPECT_EQ(i, (*sde_iter)->get_value());
 639     ++i;
 640   }
 641 }
 642
 643 TEST(ListContainerTest, SimpleManipulationWithIndexSimpleDerivedElement) {
 644   ListContainer<DerivedElement> list(kCurrentLargestDerivedElementSize);
 645   std::vector<SimpleDerivedElement*> de_list;
 646   int size = 10;
 647   for (int i = 0; i < size; ++i) {
 648     de_list.push_back(list.AllocateAndConstruct<SimpleDerivedElement>());
 649   }
 650   EXPECT_EQ(static_cast<size_t>(size), list.size());
 651
 652   for (int i = 0; i < size; ++i) {
 653     static_cast<SimpleDerivedElement*>(list.ElementAt(i))->set_value(i);
 654   }
 655
 656   int i = 0;
 657   for (std::vector<SimpleDerivedElement*>::const_iterator
 658            de_iter = de_list.begin();
 659        de_iter != de_list.end(); ++de_iter, ++i) {
 660     EXPECT_EQ(i, (*de_iter)->get_value());
 661   }
 662 }
 663
 664 TEST(ListContainerTest,
 665      SimpleManipulationWithIndexMoreThanOneAllocationSimpleDerivedElement) {
 666   ListContainer<DerivedElement> list(LargestDerivedElementSize(), 2);
 667   std::vector<SimpleDerivedElement*> de_list;
 668   int size = 10;
 669   for (int i = 0; i < size; ++i) {
 670     de_list.push_back(list.AllocateAndConstruct<SimpleDerivedElement>());
 671   }
 672   EXPECT_EQ(static_cast<size_t>(size), list.size());
 673
 674   for (int i = 0; i < size; ++i) {
 675     static_cast<SimpleDerivedElement*>(list.ElementAt(i))->set_value(i);
 676   }
 677
 678   int i = 0;
 679   for (std::vector<SimpleDerivedElement*>::const_iterator
 680            de_iter = de_list.begin();
 681        de_iter != de_list.end(); ++de_iter, ++i) {
 682     EXPECT_EQ(i, (*de_iter)->get_value());
 683   }
 684 }
 685
 686 TEST(ListContainerTest,
 687      SimpleIterationAndReverseIterationWithIndexNonDerivedElement) {
 688   ListContainer<NonDerivedElement> list;
 689   std::vector<NonDerivedElement*> nde_list;
 690   size_t size = 10;
 691   for (size_t i = 0; i < size; ++i) {
 692     nde_list.push_back(list.AllocateAndConstruct<NonDerivedElement>());
 693   }
 694   EXPECT_EQ(size, list.size());
 695
 696   size_t i = 0;
 697   for (ListContainer<NonDerivedElement>::Iterator iter = list.begin();
 698        iter != list.end(); ++iter) {
 699     EXPECT_EQ(i, iter.index());
 700     ++i;
 701   }
 702
 703   i = 0;
 704   for (ListContainer<NonDerivedElement>::ReverseIterator iter = list.rbegin();
 705        iter != list.rend(); ++iter) {
 706     EXPECT_EQ(i, iter.index());
 707     ++i;
 708   }
 709 }
 710
 711 // Increments an int when constructed (or the counter pointer is supplied) and
 712 // decrements when destructed.
 713 class InstanceCounter {
 714  public:
 715   InstanceCounter() : counter_(nullptr) {}
 716   explicit InstanceCounter(int* counter) { SetCounter(counter); }
 717   ~InstanceCounter() {
 718     if (counter_)
 719       --*counter_;
 720   }
 721   void SetCounter(int* counter) {
 722     counter_ = counter;
 723     ++*counter_;
 724   }
 725
 726  private:
 727   int* counter_;
 728 };
 729
 730 TEST(ListContainerTest, RemoveLastDestruction) {
 731   // We keep an explicit instance count to make sure that the destructors are
 732   // indeed getting called.
 733   int counter = 0;
 734   ListContainer<InstanceCounter> list(sizeof(InstanceCounter), 1);
 735   EXPECT_EQ(0, counter);
 736   EXPECT_EQ(0u, list.size());
 737
 738   // We should be okay to add one and then go back to zero.
 739   list.AllocateAndConstruct<InstanceCounter>()->SetCounter(&counter);
 740   EXPECT_EQ(1, counter);
 741   EXPECT_EQ(1u, list.size());
 742   list.RemoveLast();
 743   EXPECT_EQ(0, counter);
 744   EXPECT_EQ(0u, list.size());
 745
 746   // We should also be okay to remove the last multiple times, as long as there
 747   // are enough elements in the first place.
 748   list.AllocateAndConstruct<InstanceCounter>()->SetCounter(&counter);
 749   list.AllocateAndConstruct<InstanceCounter>()->SetCounter(&counter);
 750   list.AllocateAndConstruct<InstanceCounter>()->SetCounter(&counter);
 751   list.AllocateAndConstruct<InstanceCounter>()->SetCounter(&counter);
 752   list.AllocateAndConstruct<InstanceCounter>()->SetCounter(&counter);
 753   list.AllocateAndConstruct<InstanceCounter>()->SetCounter(&counter);
 754   list.RemoveLast();
 755   list.RemoveLast();
 756   EXPECT_EQ(4, counter);  // Leaves one in the last list.
 757   EXPECT_EQ(4u, list.size());
 758   list.RemoveLast();
 759   EXPECT_EQ(3, counter);  // Removes an inner list from before.
 760   EXPECT_EQ(3u, list.size());
 761 }
 762
 763 // TODO(jbroman): std::equal would work if ListContainer iterators satisfied the
 764 // usual STL iterator constraints. We should fix that.
 765 template <typename It1, typename It2>
 766 bool Equal(It1 it1, const It1& end1, It2 it2) {
 767   for (; it1 != end1; ++it1, ++it2) {
 768     if (!(*it1 == *it2))
 769       return false;
 770   }
 771   return true;
 772 }
 773
 774 TEST(ListContainerTest, RemoveLastIteration) {
 775   struct SmallStruct {
 776     char dummy[16];
 777   };
 778   ListContainer<SmallStruct> list(sizeof(SmallStruct), 1);
 779   std::vector<SmallStruct*> pointers;
 780
 781   // Utilities which keep these two lists in sync and check that their iteration
 782   // order matches.
 783   auto push = [&list, &pointers]() {
 784     pointers.push_back(list.AllocateAndConstruct<SmallStruct>());
 785   };
 786   auto pop = [&list, &pointers]() {
 787     pointers.pop_back();
 788     list.RemoveLast();
 789   };
 790   auto check_equal = [&list, &pointers]() {
 791     // They should be of the same size, and compare equal with all four kinds of
 792     // iteration.
 793     // Apparently Mac doesn't have vector::cbegin and vector::crbegin?
 794     const auto& const_pointers = pointers;
 795     ASSERT_EQ(list.size(), pointers.size());
 796     ASSERT_TRUE(Equal(list.begin(), list.end(), pointers.begin()));
 797     ASSERT_TRUE(Equal(list.cbegin(), list.cend(), const_pointers.begin()));
 798     ASSERT_TRUE(Equal(list.rbegin(), list.rend(), pointers.rbegin()));
 799     ASSERT_TRUE(Equal(list.crbegin(), list.crend(), const_pointers.rbegin()));
 800   };
 801
 802   check_equal();  // Initially empty.
 803   push();
 804   check_equal();  // One full inner list.
 805   push();
 806   check_equal();  // One full, one partially full.
 807   push();
 808   push();
 809   check_equal();  // Two full, one partially full.
 810   pop();
 811   check_equal();  // Two full, one empty.
 812   pop();
 813   check_equal();  // One full, one partially full, one empty.
 814   pop();
 815   check_equal();  // One full, one empty.
 816   push();
 817   pop();
 818   pop();
 819   ASSERT_TRUE(list.empty());
 820   check_equal();  // Empty.
 821 }
 822
 823 }  // namespace
 824 }  // namespace cc