mfbt/tests/TestLinkedList.cpp

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