mfbt/tests/TestLinkedList.cpp

   1
   2 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   3 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   4 /* This Source Code Form is subject to the terms of the Mozilla Public
   5  * License, v. 2.0. If a copy of the MPL was not distributed with this file,
   6  * You can obtain one at http://mozilla.org/MPL/2.0/. */
   7
   8 #include "mozilla/Assertions.h"
   9 #include "mozilla/LinkedList.h"
  10
  11 using mozilla::AutoCleanLinkedList;
  12 using mozilla::LinkedList;
  13 using mozilla::LinkedListElement;
  14
  15 struct SomeClass : public LinkedListElement<SomeClass> {
  16   unsigned int mValue;
  17   explicit SomeClass(int aValue = 0) : mValue(aValue) {}
  18   SomeClass(SomeClass&&) = default;
  19   SomeClass& operator=(SomeClass&&) = default;
  20   void incr() { ++mValue; }
  21 };
  22
  23 template <size_t N>
  24 static void CheckListValues(LinkedList<SomeClass>& list,
  25                             unsigned int (&values)[N]) {
  26   size_t count = 0;
  27   for (SomeClass* x : list) {
  28     MOZ_RELEASE_ASSERT(x->mValue == values[count]);
  29     ++count;
  30   }
  31   MOZ_RELEASE_ASSERT(count == N);
  32 }
  33
  34 static void TestList() {
  35   LinkedList<SomeClass> list;
  36
  37   SomeClass one(1), two(2), three(3);
  38
  39   MOZ_RELEASE_ASSERT(list.isEmpty());
  40   MOZ_RELEASE_ASSERT(list.length() == 0);
  41   MOZ_RELEASE_ASSERT(!list.getFirst());
  42   MOZ_RELEASE_ASSERT(!list.getLast());
  43   MOZ_RELEASE_ASSERT(!list.popFirst());
  44   MOZ_RELEASE_ASSERT(!list.popLast());
  45
  46   for (SomeClass* x : list) {
  47     MOZ_RELEASE_ASSERT(x);
  48     MOZ_RELEASE_ASSERT(false);
  49   }
  50
  51   list.insertFront(&one);
  52   {
  53     unsigned int check[]{1};
  54     CheckListValues(list, check);
  55   }
  56
  57   MOZ_RELEASE_ASSERT(one.isInList());
  58   MOZ_RELEASE_ASSERT(!two.isInList());
  59   MOZ_RELEASE_ASSERT(!three.isInList());
  60
  61   MOZ_RELEASE_ASSERT(list.contains(&one));
  62   MOZ_RELEASE_ASSERT(!list.contains(&two));
  63   MOZ_RELEASE_ASSERT(!list.contains(&three));
  64
  65   MOZ_RELEASE_ASSERT(!list.isEmpty());
  66   MOZ_RELEASE_ASSERT(list.length() == 1);
  67   MOZ_RELEASE_ASSERT(list.getFirst()->mValue == 1);
  68   MOZ_RELEASE_ASSERT(list.getLast()->mValue == 1);
  69
  70   list.insertFront(&two);
  71   {
  72     unsigned int check[]{2, 1};
  73     CheckListValues(list, check);
  74   }
  75
  76   MOZ_RELEASE_ASSERT(list.length() == 2);
  77   MOZ_RELEASE_ASSERT(list.getFirst()->mValue == 2);
  78   MOZ_RELEASE_ASSERT(list.getLast()->mValue == 1);
  79
  80   list.insertBack(&three);
  81   {
  82     unsigned int check[]{2, 1, 3};
  83     CheckListValues(list, check);
  84   }
  85
  86   MOZ_RELEASE_ASSERT(list.length() == 3);
  87   MOZ_RELEASE_ASSERT(list.getFirst()->mValue == 2);
  88   MOZ_RELEASE_ASSERT(list.getLast()->mValue == 3);
  89
  90   one.removeFrom(list);
  91   {
  92     unsigned int check[]{2, 3};
  93     CheckListValues(list, check);
  94   }
  95
  96   three.setPrevious(&one);
  97   {
  98     unsigned int check[]{2, 1, 3};
  99     CheckListValues(list, check);
 100   }
 101
 102   three.removeFrom(list);
 103   {
 104     unsigned int check[]{2, 1};
 105     CheckListValues(list, check);
 106   }
 107
 108   two.setPrevious(&three);
 109   {
 110     unsigned int check[]{3, 2, 1};
 111     CheckListValues(list, check);
 112   }
 113
 114   three.removeFrom(list);
 115   {
 116     unsigned int check[]{2, 1};
 117     CheckListValues(list, check);
 118   }
 119
 120   two.setNext(&three);
 121   {
 122     unsigned int check[]{2, 3, 1};
 123     CheckListValues(list, check);
 124   }
 125
 126   one.remove();
 127   {
 128     unsigned int check[]{2, 3};
 129     CheckListValues(list, check);
 130   }
 131
 132   two.remove();
 133   {
 134     unsigned int check[]{3};
 135     CheckListValues(list, check);
 136   }
 137
 138   three.setPrevious(&two);
 139   {
 140     unsigned int check[]{2, 3};
 141     CheckListValues(list, check);
 142   }
 143
 144   three.remove();
 145   {
 146     unsigned int check[]{2};
 147     CheckListValues(list, check);
 148   }
 149
 150   two.remove();
 151
 152   list.insertBack(&three);
 153   {
 154     unsigned int check[]{3};
 155     CheckListValues(list, check);
 156   }
 157
 158   list.insertFront(&two);
 159   {
 160     unsigned int check[]{2, 3};
 161     CheckListValues(list, check);
 162   }
 163
 164   for (SomeClass* x : list) {
 165     x->incr();
 166   }
 167
 168   MOZ_RELEASE_ASSERT(list.length() == 2);
 169   MOZ_RELEASE_ASSERT(list.getFirst() == &two);
 170   MOZ_RELEASE_ASSERT(list.getLast() == &three);
 171   MOZ_RELEASE_ASSERT(list.getFirst()->mValue == 3);
 172   MOZ_RELEASE_ASSERT(list.getLast()->mValue == 4);
 173
 174   const LinkedList<SomeClass>& constList = list;
 175   for (const SomeClass* x : constList) {
 176     MOZ_RELEASE_ASSERT(x);
 177   }
 178 }
 179
 180 static void TestExtendLists() {
 181   AutoCleanLinkedList<SomeClass> list1, list2;
 182
 183   constexpr unsigned int N = 5;
 184   for (unsigned int i = 0; i < N; ++i) {
 185     list1.insertBack(new SomeClass(static_cast<int>(i)));
 186
 187     AutoCleanLinkedList<SomeClass> singleItemList;
 188     singleItemList.insertFront(new SomeClass(static_cast<int>(i + N)));
 189     list2.extendBack(std::move(singleItemList));
 190   }
 191   // list1 = { 0, 1, 2, 3, 4 }
 192   // list2 = { 5, 6, 7, 8, 9 }
 193
 194   list1.extendBack(AutoCleanLinkedList<SomeClass>());
 195   list1.extendBack(std::move(list2));
 196
 197   // Make sure the line above has properly emptied |list2|.
 198   MOZ_RELEASE_ASSERT(list2.isEmpty());  // NOLINT(bugprone-use-after-move)
 199
 200   size_t i = 0;
 201   for (SomeClass* x : list1) {
 202     MOZ_RELEASE_ASSERT(x->mValue == i++);
 203   }
 204   MOZ_RELEASE_ASSERT(i == N * 2);
 205 }
 206
 207 void TestSplice() {
 208   AutoCleanLinkedList<SomeClass> list1, list2;
 209   for (unsigned int i = 1; i <= 5; ++i) {
 210     list1.insertBack(new SomeClass(static_cast<int>(i)));
 211
 212     AutoCleanLinkedList<SomeClass> singleItemList;
 213     singleItemList.insertFront(new SomeClass(static_cast<int>(i * 10)));
 214     list2.extendBack(std::move(singleItemList));
 215   }
 216   // list1 = { 1, 2, 3, 4, 5 }
 217   // list2 = { 10, 20, 30, 40, 50 }
 218
 219   list1.splice(2, list2, 0, 5);
 220
 221   MOZ_RELEASE_ASSERT(list2.isEmpty());
 222   unsigned int kExpected1[]{1, 2, 10, 20, 30, 40, 50, 3, 4, 5};
 223   CheckListValues(list1, kExpected1);
 224
 225   // Since aSourceLen=100 exceeds list1's end, the function transfers
 226   // three items [3, 4, 5].
 227   list2.splice(0, list1, 7, 100);
 228
 229   unsigned int kExpected2[]{1, 2, 10, 20, 30, 40, 50};
 230   unsigned int kExpected3[]{3, 4, 5};
 231   CheckListValues(list1, kExpected2);
 232   CheckListValues(list2, kExpected3);
 233
 234   // Since aDestinationPos=100 exceeds list2's end, the function transfers
 235   // items to list2's end.
 236   list2.splice(100, list1, 1, 1);
 237
 238   unsigned int kExpected4[]{1, 10, 20, 30, 40, 50};
 239   unsigned int kExpected5[]{3, 4, 5, 2};
 240   CheckListValues(list1, kExpected4);
 241   CheckListValues(list2, kExpected5);
 242 }
 243
 244 static void TestMove() {
 245   auto MakeSomeClass = [](unsigned int aValue) -> SomeClass {
 246     return SomeClass(aValue);
 247   };
 248
 249   LinkedList<SomeClass> list1;
 250
 251   // Test move constructor for LinkedListElement.
 252   SomeClass c1(MakeSomeClass(1));
 253   list1.insertBack(&c1);
 254
 255   // Test move assignment for LinkedListElement from an element not in a
 256   // list.
 257   SomeClass c2;
 258   c2 = MakeSomeClass(2);
 259   list1.insertBack(&c2);
 260
 261   // Test move assignment of LinkedListElement from an element already in a
 262   // list.
 263   SomeClass c3;
 264   c3 = std::move(c2);
 265   MOZ_RELEASE_ASSERT(!c2.isInList());
 266   MOZ_RELEASE_ASSERT(c3.isInList());
 267
 268   // Test move constructor for LinkedList.
 269   LinkedList<SomeClass> list2(std::move(list1));
 270   {
 271     unsigned int check[]{1, 2};
 272     CheckListValues(list2, check);
 273   }
 274   MOZ_RELEASE_ASSERT(list1.isEmpty());
 275
 276   // Test move assignment for LinkedList.
 277   LinkedList<SomeClass> list3;
 278   list3 = std::move(list2);
 279   {
 280     unsigned int check[]{1, 2};
 281     CheckListValues(list3, check);
 282   }
 283   MOZ_RELEASE_ASSERT(list2.isEmpty());
 284
 285   list3.clear();
 286 }
 287
 288 static void TestRemoveAndGet() {
 289   LinkedList<SomeClass> list;
 290
 291   SomeClass one(1), two(2), three(3);
 292   list.insertBack(&one);
 293   list.insertBack(&two);
 294   list.insertBack(&three);
 295   {
 296     unsigned int check[]{1, 2, 3};
 297     CheckListValues(list, check);
 298   }
 299
 300   MOZ_RELEASE_ASSERT(two.removeAndGetNext() == &three);
 301   {
 302     unsigned int check[]{1, 3};
 303     CheckListValues(list, check);
 304   }
 305
 306   MOZ_RELEASE_ASSERT(three.removeAndGetPrevious() == &one);
 307   {
 308     unsigned int check[]{1};
 309     CheckListValues(list, check);
 310   }
 311 }
 312
 313 struct PrivateClass : private LinkedListElement<PrivateClass> {
 314   friend class mozilla::LinkedList<PrivateClass>;
 315   friend class mozilla::LinkedListElement<PrivateClass>;
 316 };
 317
 318 static void TestPrivate() {
 319   LinkedList<PrivateClass> list;
 320   PrivateClass one, two;
 321   list.insertBack(&one);
 322   list.insertBack(&two);
 323
 324   size_t count = 0;
 325   for (PrivateClass* p : list) {
 326     MOZ_RELEASE_ASSERT(p, "cannot have null elements in list");
 327     count++;
 328   }
 329   MOZ_RELEASE_ASSERT(count == 2);
 330 }
 331
 332 struct CountedClass : public LinkedListElement<RefPtr<CountedClass>> {
 333   int mCount;
 334   void AddRef() { mCount++; }
 335   void Release() { mCount--; }
 336
 337   CountedClass() : mCount(0) {}
 338   ~CountedClass() { MOZ_RELEASE_ASSERT(mCount == 0); }
 339 };
 340
 341 static void TestRefPtrList() {
 342   LinkedList<RefPtr<CountedClass>> list;
 343   CountedClass* elt1 = new CountedClass;
 344   CountedClass* elt2 = new CountedClass;
 345
 346   list.insertBack(elt1);
 347   list.insertBack(elt2);
 348
 349   MOZ_RELEASE_ASSERT(elt1->mCount == 1);
 350   MOZ_RELEASE_ASSERT(elt2->mCount == 1);
 351
 352   for (RefPtr<CountedClass> p : list) {
 353     MOZ_RELEASE_ASSERT(p->mCount == 2);
 354   }
 355
 356   RefPtr<CountedClass> ptr = list.getFirst();
 357   while (ptr) {
 358     MOZ_RELEASE_ASSERT(ptr->mCount == 2);
 359     RefPtr<CountedClass> next = ptr->getNext();
 360     ptr->remove();
 361     ptr = std::move(next);
 362   }
 363   ptr = nullptr;
 364
 365   MOZ_RELEASE_ASSERT(elt1->mCount == 0);
 366   MOZ_RELEASE_ASSERT(elt2->mCount == 0);
 367
 368   list.insertBack(elt1);
 369   elt1->setNext(elt2);
 370
 371   MOZ_RELEASE_ASSERT(elt1->mCount == 1);
 372   MOZ_RELEASE_ASSERT(elt2->mCount == 1);
 373
 374   RefPtr<CountedClass> first = list.popFirst();
 375
 376   MOZ_RELEASE_ASSERT(elt1->mCount == 1);
 377   MOZ_RELEASE_ASSERT(elt2->mCount == 1);
 378
 379   RefPtr<CountedClass> second = list.popFirst();
 380
 381   MOZ_RELEASE_ASSERT(elt1->mCount == 1);
 382   MOZ_RELEASE_ASSERT(elt2->mCount == 1);
 383
 384   first = second = nullptr;
 385
 386   delete elt1;
 387   delete elt2;
 388 }
 389
 390 int main() {
 391   TestList();
 392   TestExtendLists();
 393   TestSplice();
 394   TestPrivate();
 395   TestMove();
 396   TestRemoveAndGet();
 397   TestRefPtrList();
 398   return 0;
 399 }