third_party/pigweed/repo/pw_containers/intrusive_list_test.cc

   1 // Copyright 2020 The Pigweed Authors
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
   4 // use this file except in compliance with the License. You may obtain a copy of
   5 // the License at
   6 //
   7 //     https://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
  11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
  12 // License for the specific language governing permissions and limitations under
  13 // the License.
  14
  15 #include "pw_containers/intrusive_list.h"
  16
  17 #include <array>
  18 #include <cstddef>
  19 #include <cstdint>
  20
  21 #include "gtest/gtest.h"
  22 #include "pw_preprocessor/util.h"
  23
  24 namespace pw {
  25 namespace {
  26
  27 class TestItem : public IntrusiveList<TestItem>::Item {
  28  public:
  29   TestItem() : number_(0) {}
  30   TestItem(int number) : number_(number) {}
  31
  32   int GetNumber() const { return number_; }
  33   void SetNumber(int num) { number_ = num; }
  34
  35   // Add equality comparison to ensure comparisons are done by identity rather
  36   // than equality for the remove function.
  37   bool operator==(const TestItem& other) const {
  38     return number_ == other.number_;
  39   }
  40
  41  private:
  42   int number_;
  43 };
  44
  45 TEST(IntrusiveList, Construct_InitializerList_Empty) {
  46   IntrusiveList<TestItem> list({});
  47   EXPECT_TRUE(list.empty());
  48 }
  49
  50 TEST(IntrusiveList, Construct_InitializerList_One) {
  51   TestItem one(1);
  52   IntrusiveList<TestItem> list({&one});
  53
  54   EXPECT_EQ(&one, &list.front());
  55 }
  56
  57 TEST(IntrusiveList, Construct_InitializerList_Multiple) {
  58   TestItem one(1);
  59   TestItem two(2);
  60   TestItem thr(3);
  61
  62   IntrusiveList<TestItem> list({&one, &two, &thr});
  63   auto it = list.begin();
  64   EXPECT_EQ(&one, &(*it++));
  65   EXPECT_EQ(&two, &(*it++));
  66   EXPECT_EQ(&thr, &(*it++));
  67   EXPECT_EQ(list.end(), it);
  68 }
  69
  70 TEST(IntrusiveList, Construct_ObjectIterator_Empty) {
  71   std::array<TestItem, 0> array;
  72   IntrusiveList<TestItem> list(array.begin(), array.end());
  73
  74   EXPECT_TRUE(list.empty());
  75 }
  76
  77 TEST(IntrusiveList, Construct_ObjectIterator_One) {
  78   std::array<TestItem, 1> array{{{1}}};
  79   IntrusiveList<TestItem> list(array.begin(), array.end());
  80
  81   EXPECT_EQ(&array.front(), &list.front());
  82 }
  83
  84 TEST(IntrusiveList, Construct_ObjectIterator_Multiple) {
  85   std::array<TestItem, 3> array{{{1}, {2}, {3}}};
  86
  87   IntrusiveList<TestItem> list(array.begin(), array.end());
  88   auto it = list.begin();
  89   EXPECT_EQ(&array[0], &(*it++));
  90   EXPECT_EQ(&array[1], &(*it++));
  91   EXPECT_EQ(&array[2], &(*it++));
  92   EXPECT_EQ(list.end(), it);
  93 }
  94
  95 TEST(IntrusiveList, Construct_PointerIterator_Empty) {
  96   std::array<TestItem*, 0> array;
  97   IntrusiveList<TestItem> list(array.begin(), array.end());
  98
  99   EXPECT_TRUE(list.empty());
 100 }
 101
 102 TEST(IntrusiveList, Construct_PointerIterator_One) {
 103   std::array<TestItem, 1> array{{{1}}};
 104   std::array<TestItem*, 1> ptrs{{&array[0]}};
 105
 106   IntrusiveList<TestItem> list(ptrs.begin(), ptrs.end());
 107
 108   EXPECT_EQ(ptrs[0], &list.front());
 109 }
 110
 111 TEST(IntrusiveList, Construct_PointerIterator_Multiple) {
 112   std::array<TestItem, 3> array{{{1}, {2}, {3}}};
 113   std::array<TestItem*, 3> ptrs{{&array[0], &array[1], &array[2]}};
 114
 115   IntrusiveList<TestItem> list(ptrs.begin(), ptrs.end());
 116   auto it = list.begin();
 117   EXPECT_EQ(ptrs[0], &(*it++));
 118   EXPECT_EQ(ptrs[1], &(*it++));
 119   EXPECT_EQ(ptrs[2], &(*it++));
 120   EXPECT_EQ(list.end(), it);
 121 }
 122
 123 TEST(IntrusiveList, Assign_ReplacesPriorContents) {
 124   std::array<TestItem, 3> array{{{0}, {100}, {200}}};
 125   IntrusiveList<TestItem> list(array.begin(), array.end());
 126
 127   list.assign(array.begin() + 1, array.begin() + 2);
 128
 129   auto it = list.begin();
 130   EXPECT_EQ(&array[1], &(*it++));
 131   EXPECT_EQ(list.end(), it);
 132 }
 133
 134 TEST(IntrusiveList, Assign_EmptyRange) {
 135   std::array<TestItem, 3> array{{{0}, {100}, {200}}};
 136   IntrusiveList<TestItem> list(array.begin(), array.end());
 137
 138   list.assign(array.begin() + 1, array.begin() + 1);
 139
 140   EXPECT_TRUE(list.empty());
 141 }
 142
 143 TEST(IntrusiveList, PushOne) {
 144   constexpr int kMagicValue = 31;
 145   TestItem item1(kMagicValue);
 146   IntrusiveList<TestItem> list;
 147   list.push_back(item1);
 148   EXPECT_FALSE(list.empty());
 149   EXPECT_EQ(list.front().GetNumber(), kMagicValue);
 150 }
 151
 152 TEST(IntrusiveList, PushThree) {
 153   TestItem item1(1);
 154   TestItem item2(2);
 155   TestItem item3(3);
 156
 157   IntrusiveList<TestItem> list;
 158   list.push_back(item1);
 159   list.push_back(item2);
 160   list.push_back(item3);
 161
 162   int loop_count = 0;
 163   for (auto& test_item : list) {
 164     loop_count++;
 165     EXPECT_EQ(loop_count, test_item.GetNumber());
 166   }
 167   EXPECT_EQ(loop_count, 3);
 168 }
 169
 170 TEST(IntrusiveList, IsEmpty) {
 171   TestItem item1(1);
 172
 173   IntrusiveList<TestItem> list;
 174   EXPECT_TRUE(list.empty());
 175
 176   list.push_back(item1);
 177   EXPECT_FALSE(list.empty());
 178 }
 179
 180 TEST(IntrusiveList, InsertAfter) {
 181   // Create a test item to insert midway through the list.
 182   constexpr int kMagicValue = 42;
 183   TestItem inserted_item(kMagicValue);
 184
 185   // Create initial values to fill in the start/end.
 186   TestItem item_array[20];
 187
 188   IntrusiveList<TestItem> list;
 189   // Fill the list with TestItem objects that have a value of zero.
 190   for (size_t i = 0; i < PW_ARRAY_SIZE(item_array); ++i) {
 191     item_array[i].SetNumber(0);
 192     list.push_back(item_array[i]);
 193   }
 194
 195   // Move an iterator to the middle of the list, and then insert the magic item.
 196   auto it = list.begin();
 197   size_t expected_index = 1;  // Expected index is iterator index + 1.
 198   for (size_t i = 0; i < PW_ARRAY_SIZE(item_array) / 2; ++i) {
 199     it++;
 200     expected_index++;
 201   }
 202   it = list.insert_after(it, inserted_item);
 203
 204   // Ensure the returned iterator from insert_after is the newly inserted
 205   // element.
 206   EXPECT_EQ(it->GetNumber(), kMagicValue);
 207
 208   // Ensure the value is in the expected location (index of the iterator + 1).
 209   size_t i = 0;
 210   for (TestItem& item : list) {
 211     if (item.GetNumber() == kMagicValue) {
 212       EXPECT_EQ(i, expected_index);
 213     } else {
 214       EXPECT_EQ(item.GetNumber(), 0);
 215     }
 216     i++;
 217   }
 218
 219   // Ensure the list didn't break and change sizes.
 220   EXPECT_EQ(i, PW_ARRAY_SIZE(item_array) + 1);
 221 }
 222
 223 TEST(IntrusiveList, PushFront) {
 224   constexpr int kMagicValue = 42;
 225   TestItem pushed_item(kMagicValue);
 226
 227   TestItem item_array[20];
 228   IntrusiveList<TestItem> list;
 229   // Fill the list with TestItem objects that have a value of zero.
 230   for (size_t i = 0; i < PW_ARRAY_SIZE(item_array); ++i) {
 231     item_array[i].SetNumber(0);
 232     list.push_back(item_array[i]);
 233   }
 234
 235   // Create a test item to push to the front of the list.
 236   list.push_front(pushed_item);
 237   EXPECT_EQ(list.front().GetNumber(), kMagicValue);
 238 }
 239
 240 TEST(IntrusiveList, Clear_Empty) {
 241   IntrusiveList<TestItem> list;
 242   EXPECT_TRUE(list.empty());
 243   list.clear();
 244   EXPECT_TRUE(list.empty());
 245 }
 246
 247 TEST(IntrusiveList, Clear_OneItem) {
 248   TestItem item(42);
 249   IntrusiveList<TestItem> list;
 250   list.push_back(item);
 251   EXPECT_FALSE(list.empty());
 252   list.clear();
 253   EXPECT_TRUE(list.empty());
 254 }
 255
 256 TEST(IntrusiveList, Clear_TwoItems) {
 257   TestItem item1(42);
 258   TestItem item2(42);
 259   IntrusiveList<TestItem> list;
 260   list.push_back(item1);
 261   list.push_back(item2);
 262   EXPECT_FALSE(list.empty());
 263   list.clear();
 264   EXPECT_TRUE(list.empty());
 265 }
 266
 267 TEST(IntrusiveList, Clear_ReinsertClearedItems) {
 268   std::array<TestItem, 20> item_array;
 269   IntrusiveList<TestItem> list;
 270   EXPECT_TRUE(list.empty());
 271   list.clear();
 272   EXPECT_TRUE(list.empty());
 273
 274   // Fill the list with TestItem objects.
 275   for (size_t i = 0; i < item_array.size(); ++i) {
 276     item_array[i].SetNumber(0);
 277     list.push_back(item_array[i]);
 278   }
 279
 280   // Remove everything.
 281   list.clear();
 282   EXPECT_TRUE(list.empty());
 283
 284   // Ensure all the removed elements can still be added back to a list.
 285   for (size_t i = 0; i < item_array.size(); ++i) {
 286     item_array[i].SetNumber(0);
 287     list.push_back(item_array[i]);
 288   }
 289 }
 290
 291 TEST(IntrusiveList, PopFront) {
 292   constexpr int kValue1 = 32;
 293   constexpr int kValue2 = 4083;
 294
 295   TestItem item1(kValue1);
 296   TestItem item2(kValue2);
 297
 298   IntrusiveList<TestItem> list;
 299   EXPECT_TRUE(list.empty());
 300
 301   list.push_front(item2);
 302   list.push_front(item1);
 303   list.pop_front();
 304   EXPECT_EQ(list.front().GetNumber(), kValue2);
 305   EXPECT_FALSE(list.empty());
 306   list.pop_front();
 307   EXPECT_TRUE(list.empty());
 308 }
 309
 310 TEST(IntrusiveList, PopFrontAndReinsert) {
 311   constexpr int kValue1 = 32;
 312   constexpr int kValue2 = 4083;
 313
 314   TestItem item1(kValue1);
 315   TestItem item2(kValue2);
 316
 317   IntrusiveList<TestItem> list;
 318   EXPECT_TRUE(list.empty());
 319
 320   list.push_front(item2);
 321   list.push_front(item1);
 322   list.pop_front();
 323   list.push_front(item1);
 324   EXPECT_EQ(list.front().GetNumber(), kValue1);
 325 }
 326
 327 TEST(IntrusiveList, ListFront) {
 328   TestItem item1(1);
 329   TestItem item2(0);
 330   TestItem item3(0xffff);
 331
 332   IntrusiveList<TestItem> list;
 333   list.push_back(item1);
 334   list.push_back(item2);
 335   list.push_back(item3);
 336
 337   EXPECT_EQ(&item1, &list.front());
 338   EXPECT_EQ(&item1, &(*list.begin()));
 339 }
 340
 341 TEST(IntrusiveList, IteratorIncrement) {
 342   TestItem item_array[20];
 343   IntrusiveList<TestItem> list;
 344   for (size_t i = 0; i < PW_ARRAY_SIZE(item_array); ++i) {
 345     item_array[i].SetNumber(i);
 346     list.push_back(item_array[i]);
 347   }
 348
 349   auto it = list.begin();
 350   int i = 0;
 351   while (it != list.end()) {
 352     if (i == 0) {
 353       // Test pre-incrementing on the first element.
 354       EXPECT_EQ((++it)->GetNumber(), item_array[++i].GetNumber());
 355     } else {
 356       EXPECT_EQ((it++)->GetNumber(), item_array[i++].GetNumber());
 357     }
 358   }
 359 }
 360
 361 TEST(IntrusiveList, ConstIteratorRead) {
 362   // For this test, items are checked to be non-zero.
 363   TestItem item1(1);
 364   TestItem item2(99);
 365   IntrusiveList<TestItem> list;
 366
 367   const IntrusiveList<TestItem>* const_list = &list;
 368
 369   list.push_back(item1);
 370   list.push_back(item2);
 371
 372   auto it = const_list->begin();
 373   while (it != const_list->end()) {
 374     EXPECT_NE(it->GetNumber(), 0);
 375     it++;
 376   }
 377 }
 378
 379 // TODO(pwbug/47): These tests should fail to compile, enable when no-compile
 380 // tests are set up in Pigweed.
 381 #define NO_COMPILE_TESTS 0
 382 #if NO_COMPILE_TESTS
 383 TEST(IntrusiveList, ConstIteratorModify) {
 384   TestItem item1(1);
 385   TestItem item2(99);
 386   IntrusiveList<TestItem> list;
 387
 388   const IntrusiveList<TestItem>* const_list = &list;
 389
 390   list.push_back(item1);
 391   list.push_back(item2);
 392
 393   auto it = const_list->begin();
 394   while (it != const_list->end()) {
 395     it->SetNumber(0);
 396     it++;
 397   }
 398 }
 399 #endif  // NO_COMPILE_TESTS
 400
 401 // TODO(pwbug/88): These tests should trigger a CHECK failure. This requires
 402 // using a testing version of pw_assert.
 403 #define TESTING_CHECK_FAILURES_IS_SUPPORTED 0
 404 #if TESTING_CHECK_FAILURES_IS_SUPPORTED
 405 TEST(IntrusiveList, Construct_DuplicateItems) {
 406   TestItem item(1);
 407   IntrusiveList<TestItem> list({&item, &item});
 408 }
 409
 410 TEST(IntrusiveList, InsertAfter_SameItem) {
 411   TestItem item(1);
 412   IntrusiveList<TestItem> list({&item});
 413
 414   list.insert_after(list.begin(), item);
 415 }
 416
 417 TEST(IntrusiveList, InsertAfter_SameItemAfterEnd) {
 418   TestItem item(1);
 419   IntrusiveList<TestItem> list({&item});
 420
 421   list.insert_after(list.end(), item);
 422 }
 423
 424 TEST(IntrusiveList, PushBack_SameItem) {
 425   TestItem item(1);
 426   IntrusiveList<TestItem> list({&item});
 427
 428   list.push_back(item);
 429 }
 430
 431 TEST(IntrusiveList, PushFront_SameItem) {
 432   TestItem item(1);
 433   IntrusiveList<TestItem> list({&item});
 434
 435   list.push_front(item);
 436 }
 437 #endif  // TESTING_CHECK_FAILURES_IS_SUPPORTED
 438
 439 TEST(IntrusiveList, EraseAfter_FirstItem) {
 440   std::array<TestItem, 3> items{{{0}, {1}, {2}}};
 441   IntrusiveList<TestItem> list(items.begin(), items.end());
 442
 443   auto it = list.erase_after(list.before_begin());
 444   EXPECT_EQ(list.begin(), it);
 445   EXPECT_EQ(&items[1], &list.front());
 446 }
 447
 448 TEST(IntrusiveList, EraseAfter_LastItem) {
 449   std::array<TestItem, 3> items{{{0}, {1}, {2}}};
 450   IntrusiveList<TestItem> list(items.begin(), items.end());
 451
 452   auto it = list.begin();
 453   ++it;
 454
 455   it = list.erase_after(it);
 456   EXPECT_EQ(list.end(), it);
 457
 458   it = list.begin();
 459   ++it;
 460
 461   EXPECT_EQ(&items[1], &(*it));
 462 }
 463
 464 TEST(IntrusiveList, EraseAfter_AllItems) {
 465   std::array<TestItem, 3> items{{{0}, {1}, {2}}};
 466   IntrusiveList<TestItem> list(items.begin(), items.end());
 467
 468   list.erase_after(list.begin());
 469   list.erase_after(list.begin());
 470   auto it = list.erase_after(list.before_begin());
 471
 472   EXPECT_EQ(list.end(), it);
 473   EXPECT_TRUE(list.empty());
 474 }
 475
 476 TEST(IntrusiveList, Remove_EmptyList) {
 477   std::array<TestItem, 1> items{{{3}}};
 478   IntrusiveList<TestItem> list(items.begin(), items.begin());  // Add nothing!
 479
 480   EXPECT_TRUE(list.empty());
 481   EXPECT_FALSE(list.remove(items[0]));
 482 }
 483
 484 TEST(IntrusiveList, Remove_SingleItem_NotPresent) {
 485   std::array<TestItem, 1> items{{{1}}};
 486   IntrusiveList<TestItem> list(items.begin(), items.end());
 487
 488   EXPECT_FALSE(list.remove(TestItem(1)));
 489   EXPECT_EQ(&items.front(), &list.front());
 490 }
 491
 492 TEST(IntrusiveList, Remove_SingleItem_Removed) {
 493   std::array<TestItem, 1> items{{{1}}};
 494   IntrusiveList<TestItem> list(items.begin(), items.end());
 495
 496   EXPECT_TRUE(list.remove(items[0]));
 497   EXPECT_TRUE(list.empty());
 498 }
 499
 500 TEST(IntrusiveList, Remove_MultipleItems_NotPresent) {
 501   std::array<TestItem, 5> items{{{1}, {1}, {2}, {3}, {4}}};
 502   IntrusiveList<TestItem> list(items.begin(), items.end());
 503
 504   EXPECT_FALSE(list.remove(TestItem(1)));
 505 }
 506
 507 TEST(IntrusiveList, Remove_MultipleItems_RemoveAndPushBack) {
 508   std::array<TestItem, 5> items{{{1}, {1}, {2}, {3}, {4}}};
 509   IntrusiveList<TestItem> list(items.begin(), items.end());
 510
 511   EXPECT_TRUE(list.remove(items[0]));
 512   EXPECT_TRUE(list.remove(items[3]));
 513   list.push_back(items[0]);  // Make sure can add the item after removing it.
 514
 515   auto it = list.begin();
 516   EXPECT_EQ(&items[1], &(*it++));
 517   EXPECT_EQ(&items[2], &(*it++));
 518   EXPECT_EQ(&items[4], &(*it++));
 519   EXPECT_EQ(&items[0], &(*it++));
 520   EXPECT_EQ(list.end(), it);
 521 }
 522
 523 TEST(IntrusiveList, ItemsRemoveThemselvesFromListsWhenDestructed) {
 524   // Create a list with some items it.
 525   TestItem a, b, c, d;
 526   IntrusiveList<TestItem> list;
 527   list.push_back(a);
 528   list.push_back(b);
 529   list.push_back(c);
 530   list.push_back(d);
 531
 532   // Insert items that will be destructed before the list.
 533   {
 534     TestItem x, y, z, w;
 535     list.push_back(x);
 536     list.push_back(z);
 537     list.push_front(y);
 538     list.push_front(w);
 539
 540     auto it = list.begin();
 541     EXPECT_EQ(&w, &(*it++));
 542     EXPECT_EQ(&y, &(*it++));
 543     EXPECT_EQ(&a, &(*it++));
 544     EXPECT_EQ(&b, &(*it++));
 545     EXPECT_EQ(&c, &(*it++));
 546     EXPECT_EQ(&d, &(*it++));
 547     EXPECT_EQ(&x, &(*it++));
 548     EXPECT_EQ(&z, &(*it++));
 549     EXPECT_EQ(list.end(), it);
 550
 551     // Here, x, y, z, w are removed from the list for the destructor.
 552   }
 553
 554   // Ensure we get back our original list.
 555   auto it = list.begin();
 556   EXPECT_EQ(&a, &(*it++));
 557   EXPECT_EQ(&b, &(*it++));
 558   EXPECT_EQ(&c, &(*it++));
 559   EXPECT_EQ(&d, &(*it++));
 560   EXPECT_EQ(list.end(), it);
 561 }
 562
 563 TEST(IntrusiveList, SizeBasic) {
 564   IntrusiveList<TestItem> list;
 565   EXPECT_EQ(list.size(), 0u);
 566
 567   TestItem one(55);
 568   list.push_front(one);
 569   EXPECT_EQ(list.size(), static_cast<size_t>(1));
 570
 571   TestItem two(66);
 572   list.push_back(two);
 573   EXPECT_EQ(list.size(), static_cast<size_t>(2));
 574
 575   TestItem thr(77);
 576   list.push_back(thr);
 577   EXPECT_EQ(list.size(), static_cast<size_t>(3));
 578 }
 579
 580 TEST(IntrusiveList, SizeScoped) {
 581   IntrusiveList<TestItem> list;
 582   EXPECT_EQ(list.size(), 0u);
 583
 584   // Add elements in new scopes; verify size on the way in and on the way out.
 585   {
 586     TestItem one(55);
 587     list.push_back(one);
 588     EXPECT_EQ(list.size(), static_cast<size_t>(1));
 589
 590     {
 591       TestItem two(66);
 592       list.push_back(two);
 593       EXPECT_EQ(list.size(), static_cast<size_t>(2));
 594       {
 595         TestItem thr(77);
 596         list.push_back(thr);
 597         EXPECT_EQ(list.size(), static_cast<size_t>(3));
 598       }
 599       EXPECT_EQ(list.size(), static_cast<size_t>(2));
 600     }
 601     EXPECT_EQ(list.size(), static_cast<size_t>(1));
 602   }
 603   EXPECT_EQ(list.size(), static_cast<size_t>(0));
 604 }
 605
 606 }  // namespace
 607 }  // namespace pw