tor-browser

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

TestLinkedList.cpp (9709B)

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