mfbt/tests/TestDoublyLinkedList.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/DoublyLinkedList.h"
   9
  10 using mozilla::DoublyLinkedList;
  11 using mozilla::DoublyLinkedListElement;
  12
  13 struct SomeClass : public DoublyLinkedListElement<SomeClass> {
  14   unsigned int mValue;
  15   explicit SomeClass(int aValue) : mValue(aValue) {}
  16   void incr() { ++mValue; }
  17   bool operator==(const SomeClass& other) const {
  18     return mValue == other.mValue;
  19   }
  20 };
  21
  22 template <typename ListType, size_t N>
  23 static void CheckListValues(ListType& list, unsigned int (&values)[N]) {
  24   size_t count = 0;
  25   for (auto& x : list) {
  26     MOZ_RELEASE_ASSERT(x.mValue == values[count]);
  27     ++count;
  28   }
  29   MOZ_RELEASE_ASSERT(count == N);
  30 }
  31
  32 static void TestDoublyLinkedList() {
  33   DoublyLinkedList<SomeClass> list;
  34
  35   SomeClass one(1), two(2), three(3);
  36
  37   MOZ_RELEASE_ASSERT(list.isEmpty());
  38   MOZ_RELEASE_ASSERT(!list.begin());
  39   MOZ_RELEASE_ASSERT(!list.end());
  40
  41   for (SomeClass& x : list) {
  42     MOZ_RELEASE_ASSERT(x.mValue);
  43     MOZ_RELEASE_ASSERT(false);
  44   }
  45
  46   list.pushFront(&one);
  47   {
  48     unsigned int check[]{1};
  49     CheckListValues(list, check);
  50   }
  51
  52   MOZ_RELEASE_ASSERT(list.contains(one));
  53   MOZ_RELEASE_ASSERT(!list.contains(two));
  54   MOZ_RELEASE_ASSERT(!list.contains(three));
  55
  56   MOZ_RELEASE_ASSERT(!list.isEmpty());
  57   MOZ_RELEASE_ASSERT(list.begin()->mValue == 1);
  58   MOZ_RELEASE_ASSERT(!list.end());
  59
  60   list.pushFront(&two);
  61   {
  62     unsigned int check[]{2, 1};
  63     CheckListValues(list, check);
  64   }
  65
  66   MOZ_RELEASE_ASSERT(list.begin()->mValue == 2);
  67   MOZ_RELEASE_ASSERT(!list.end());
  68   MOZ_RELEASE_ASSERT(!list.contains(three));
  69
  70   list.pushBack(&three);
  71   {
  72     unsigned int check[]{2, 1, 3};
  73     CheckListValues(list, check);
  74   }
  75
  76   MOZ_RELEASE_ASSERT(list.begin()->mValue == 2);
  77   MOZ_RELEASE_ASSERT(!list.end());
  78
  79   list.remove(&one);
  80   {
  81     unsigned int check[]{2, 3};
  82     CheckListValues(list, check);
  83   }
  84
  85   list.insertBefore(list.find(three), &one);
  86   {
  87     unsigned int check[]{2, 1, 3};
  88     CheckListValues(list, check);
  89   }
  90
  91   list.remove(&three);
  92   {
  93     unsigned int check[]{2, 1};
  94     CheckListValues(list, check);
  95   }
  96
  97   list.insertBefore(list.find(two), &three);
  98   {
  99     unsigned int check[]{3, 2, 1};
 100     CheckListValues(list, check);
 101   }
 102
 103   list.remove(&three);
 104   {
 105     unsigned int check[]{2, 1};
 106     CheckListValues(list, check);
 107   }
 108
 109   list.insertBefore(++list.find(two), &three);
 110   {
 111     unsigned int check[]{2, 3, 1};
 112     CheckListValues(list, check);
 113   }
 114
 115   list.remove(&one);
 116   {
 117     unsigned int check[]{2, 3};
 118     CheckListValues(list, check);
 119   }
 120
 121   list.remove(&two);
 122   {
 123     unsigned int check[]{3};
 124     CheckListValues(list, check);
 125   }
 126
 127   list.insertBefore(list.find(three), &two);
 128   {
 129     unsigned int check[]{2, 3};
 130     CheckListValues(list, check);
 131   }
 132
 133   list.remove(&three);
 134   {
 135     unsigned int check[]{2};
 136     CheckListValues(list, check);
 137   }
 138
 139   list.remove(&two);
 140   MOZ_RELEASE_ASSERT(list.isEmpty());
 141
 142   list.pushBack(&three);
 143   {
 144     unsigned int check[]{3};
 145     CheckListValues(list, check);
 146   }
 147
 148   list.pushFront(&two);
 149   {
 150     unsigned int check[]{2, 3};
 151     CheckListValues(list, check);
 152   }
 153
 154   // This should modify the values of |two| and |three| as pointers to them are
 155   // stored in the list, not copies.
 156   for (SomeClass& x : list) {
 157     x.incr();
 158   }
 159
 160   MOZ_RELEASE_ASSERT(*list.begin() == two);
 161   MOZ_RELEASE_ASSERT(*++list.begin() == three);
 162
 163   SomeClass four(4);
 164   MOZ_RELEASE_ASSERT(++list.begin() == list.find(four));
 165 }
 166
 167 struct InTwoLists {
 168   explicit InTwoLists(unsigned int aValue) : mValue(aValue) {}
 169   DoublyLinkedListElement<InTwoLists> mListOne;
 170   DoublyLinkedListElement<InTwoLists> mListTwo;
 171   unsigned int mValue;
 172
 173   struct GetListOneTrait {
 174     static DoublyLinkedListElement<InTwoLists>& Get(InTwoLists* aThis) {
 175       return aThis->mListOne;
 176     }
 177   };
 178 };
 179
 180 namespace mozilla {
 181
 182 template <>
 183 struct GetDoublyLinkedListElement<InTwoLists> {
 184   static DoublyLinkedListElement<InTwoLists>& Get(InTwoLists* aThis) {
 185     return aThis->mListTwo;
 186   }
 187 };
 188
 189 }  // namespace mozilla
 190
 191 static void TestCustomAccessor() {
 192   DoublyLinkedList<InTwoLists, InTwoLists::GetListOneTrait> listOne;
 193   DoublyLinkedList<InTwoLists> listTwo;
 194
 195   InTwoLists one(1);
 196   InTwoLists two(2);
 197
 198   listOne.pushBack(&one);
 199   listOne.pushBack(&two);
 200   {
 201     unsigned int check[]{1, 2};
 202     CheckListValues(listOne, check);
 203   }
 204
 205   listTwo.pushBack(&one);
 206   listTwo.pushBack(&two);
 207   {
 208     unsigned int check[]{1, 2};
 209     CheckListValues(listOne, check);
 210   }
 211   {
 212     unsigned int check[]{1, 2};
 213     CheckListValues(listTwo, check);
 214   }
 215
 216   (void)listTwo.popBack();
 217   {
 218     unsigned int check[]{1, 2};
 219     CheckListValues(listOne, check);
 220   }
 221   {
 222     unsigned int check[]{1};
 223     CheckListValues(listTwo, check);
 224   }
 225
 226   (void)listOne.popBack();
 227   {
 228     unsigned int check[]{1};
 229     CheckListValues(listOne, check);
 230   }
 231   {
 232     unsigned int check[]{1};
 233     CheckListValues(listTwo, check);
 234   }
 235 }
 236
 237 static void TestSafeDoubleLinkedList() {
 238   mozilla::SafeDoublyLinkedList<SomeClass> list;
 239   auto* elt1 = new SomeClass(0);
 240   auto* elt2 = new SomeClass(0);
 241   auto* elt3 = new SomeClass(0);
 242   auto* elt4 = new SomeClass(0);
 243   list.pushBack(elt1);
 244   list.pushBack(elt2);
 245   list.pushBack(elt3);
 246   auto iter = list.begin();
 247
 248   // basic tests for iterator validity
 249   MOZ_RELEASE_ASSERT(
 250       &*iter == elt1,
 251       "iterator returned by begin() must point to the first element!");
 252   MOZ_RELEASE_ASSERT(
 253       &*(iter.next()) == elt2,
 254       "iterator returned by begin() must have the second element as 'next'!");
 255   list.remove(elt2);
 256   MOZ_RELEASE_ASSERT(
 257       &*(iter.next()) == elt3,
 258       "After removal of the 2nd element 'next' must point to the 3rd element!");
 259   ++iter;
 260   MOZ_RELEASE_ASSERT(
 261       &*iter == elt3,
 262       "After advancing one step the current element must be the 3rd one!");
 263   MOZ_RELEASE_ASSERT(!iter.next(), "This is the last element of the list!");
 264   list.pushBack(elt4);
 265   MOZ_RELEASE_ASSERT(&*(iter.next()) == elt4,
 266                      "After adding an element at the end of the list the "
 267                      "iterator must be updated!");
 268
 269   // advance to last element, then remove last element
 270   ++iter;
 271   list.popBack();
 272   MOZ_RELEASE_ASSERT(bool(iter) == false,
 273                      "After removing the last element, the iterator pointing "
 274                      "to the last element must be empty!");
 275
 276   // iterate the whole remaining list, increment values
 277   for (auto& el : list) {
 278     el.incr();
 279   }
 280   MOZ_RELEASE_ASSERT(elt1->mValue == 1);
 281   MOZ_RELEASE_ASSERT(elt2->mValue == 0);
 282   MOZ_RELEASE_ASSERT(elt3->mValue == 1);
 283   MOZ_RELEASE_ASSERT(elt4->mValue == 0);
 284
 285   // Removing the first element of the list while iterating must empty the
 286   // iterator
 287   for (auto it = list.begin(); it != list.end(); ++it) {
 288     MOZ_RELEASE_ASSERT(bool(it) == true, "The iterator must contain a value!");
 289     list.popFront();
 290     MOZ_RELEASE_ASSERT(
 291         bool(it) == false,
 292         "After removing the first element, the iterator must be empty!");
 293   }
 294
 295   delete elt1;
 296   delete elt2;
 297   delete elt3;
 298   delete elt4;
 299 }
 300
 301 int main() {
 302   TestDoublyLinkedList();
 303   TestCustomAccessor();
 304   TestSafeDoubleLinkedList();
 305   return 0;
 306 }