tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

TestDoublyLinkedList.cpp (7687B)

      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    static const DoublyLinkedListElement<InTwoLists>& Get(
    178        const InTwoLists* aThis) {
    179      return aThis->mListOne;
    180    }
    181  };
    182 };
    183 
    184 namespace mozilla {
    185 
    186 template <>
    187 struct GetDoublyLinkedListElement<InTwoLists> {
    188  static DoublyLinkedListElement<InTwoLists>& Get(InTwoLists* aThis) {
    189    return aThis->mListTwo;
    190  }
    191  static const DoublyLinkedListElement<InTwoLists>& Get(
    192      const InTwoLists* aThis) {
    193    return aThis->mListTwo;
    194  }
    195 };
    196 
    197 }  // namespace mozilla
    198 
    199 static void TestCustomAccessor() {
    200  DoublyLinkedList<InTwoLists, InTwoLists::GetListOneTrait> listOne;
    201  DoublyLinkedList<InTwoLists> listTwo;
    202 
    203  InTwoLists one(1);
    204  InTwoLists two(2);
    205 
    206  listOne.pushBack(&one);
    207  listOne.pushBack(&two);
    208  {
    209    unsigned int check[]{1, 2};
    210    CheckListValues(listOne, check);
    211  }
    212 
    213  listTwo.pushBack(&one);
    214  listTwo.pushBack(&two);
    215  {
    216    unsigned int check[]{1, 2};
    217    CheckListValues(listOne, check);
    218  }
    219  {
    220    unsigned int check[]{1, 2};
    221    CheckListValues(listTwo, check);
    222  }
    223 
    224  (void)listTwo.popBack();
    225  {
    226    unsigned int check[]{1, 2};
    227    CheckListValues(listOne, check);
    228  }
    229  {
    230    unsigned int check[]{1};
    231    CheckListValues(listTwo, check);
    232  }
    233 
    234  (void)listOne.popBack();
    235  {
    236    unsigned int check[]{1};
    237    CheckListValues(listOne, check);
    238  }
    239  {
    240    unsigned int check[]{1};
    241    CheckListValues(listTwo, check);
    242  }
    243 }
    244 
    245 static void TestSafeDoubleLinkedList() {
    246  mozilla::SafeDoublyLinkedList<SomeClass> list;
    247  auto* elt1 = new SomeClass(0);
    248  auto* elt2 = new SomeClass(0);
    249  auto* elt3 = new SomeClass(0);
    250  auto* elt4 = new SomeClass(0);
    251  list.pushBack(elt1);
    252  list.pushBack(elt2);
    253  list.pushBack(elt3);
    254  auto iter = list.begin();
    255 
    256  // basic tests for iterator validity
    257  MOZ_RELEASE_ASSERT(
    258      &*iter == elt1,
    259      "iterator returned by begin() must point to the first element!");
    260  MOZ_RELEASE_ASSERT(
    261      &*(iter.next()) == elt2,
    262      "iterator returned by begin() must have the second element as 'next'!");
    263  list.remove(elt2);
    264  MOZ_RELEASE_ASSERT(
    265      &*(iter.next()) == elt3,
    266      "After removal of the 2nd element 'next' must point to the 3rd element!");
    267  ++iter;
    268  MOZ_RELEASE_ASSERT(
    269      &*iter == elt3,
    270      "After advancing one step the current element must be the 3rd one!");
    271  MOZ_RELEASE_ASSERT(!iter.next(), "This is the last element of the list!");
    272  list.pushBack(elt4);
    273  MOZ_RELEASE_ASSERT(&*(iter.next()) == elt4,
    274                     "After adding an element at the end of the list the "
    275                     "iterator must be updated!");
    276 
    277  // advance to last element, then remove last element
    278  ++iter;
    279  list.popBack();
    280  MOZ_RELEASE_ASSERT(bool(iter) == false,
    281                     "After removing the last element, the iterator pointing "
    282                     "to the last element must be empty!");
    283 
    284  // iterate the whole remaining list, increment values
    285  for (auto& el : list) {
    286    el.incr();
    287  }
    288  MOZ_RELEASE_ASSERT(elt1->mValue == 1);
    289  MOZ_RELEASE_ASSERT(elt2->mValue == 0);
    290  MOZ_RELEASE_ASSERT(elt3->mValue == 1);
    291  MOZ_RELEASE_ASSERT(elt4->mValue == 0);
    292 
    293  // Removing the first element of the list while iterating must empty the
    294  // iterator
    295  for (auto it = list.begin(); it != list.end(); ++it) {
    296    MOZ_RELEASE_ASSERT(bool(it) == true, "The iterator must contain a value!");
    297    list.popFront();
    298    MOZ_RELEASE_ASSERT(
    299        bool(it) == false,
    300        "After removing the first element, the iterator must be empty!");
    301  }
    302 
    303  delete elt1;
    304  delete elt2;
    305  delete elt3;
    306  delete elt4;
    307 }
    308 
    309 int main() {
    310  TestDoublyLinkedList();
    311  TestCustomAccessor();
    312  TestSafeDoubleLinkedList();
    313  return 0;
    314 }