testSinglyLinkedList.cpp (5233B)
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 */ 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 6 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ 7 8 #include "ds/SinglyLinkedList.h" 9 #include "jsapi-tests/tests.h" 10 11 using namespace js; 12 13 struct IntSinglyLinkedElement { 14 int value; 15 IntSinglyLinkedElement* next = nullptr; 16 17 explicit IntSinglyLinkedElement(int v) : value(v) {} 18 }; 19 using TestList = SinglyLinkedList<IntSinglyLinkedElement>; 20 21 BEGIN_TEST(testSinglyLinkedList) { 22 // Test empty lists. 23 24 TestList list; 25 CHECK(list.isEmpty()); 26 CHECK(!list.getFirst()); 27 CHECK(!list.getLast()); 28 CHECK(CountList(list) == 0); 29 30 // Test list pushBack and first/last accessors. 31 32 list.pushBack(MakeElement(1)); 33 CHECK(!list.isEmpty()); 34 CHECK(list.getFirst()->value == 1); 35 CHECK(list.getLast()->value == 1); 36 CHECK(CheckList<1>(list)); 37 38 list.pushBack(MakeElement(2)); 39 list.pushBack(MakeElement(3)); 40 CHECK(!list.isEmpty()); 41 CHECK(list.getFirst()->value == 1); 42 CHECK(list.getLast()->value == 3); 43 CHECK((CheckList<1, 2, 3>(list))); 44 45 // Test popFront. 46 47 IntSinglyLinkedElement* e = list.popFront(); 48 CHECK(e->value == 1); 49 js_delete(e); 50 CHECK(list.getFirst()->value == 2); 51 CHECK((CheckList<2, 3>(list))); 52 53 e = list.popFront(); 54 CHECK(e->value == 2); 55 js_delete(e); 56 CHECK(list.getFirst()->value == 3); 57 58 // Test pushFront. 59 60 list.pushFront(MakeElement(2)); 61 CHECK(list.getFirst()->value == 2); 62 CHECK((CheckList<2, 3>(list))); 63 64 list.pushFront(MakeElement(1)); 65 CHECK(list.getFirst()->value == 1); 66 CHECK((CheckList<1, 2, 3>(list))); 67 68 // Test moveFrontToBack. 69 70 list.moveFrontToBack(); 71 CHECK(list.getFirst()->value == 2); 72 CHECK(list.getLast()->value == 1); 73 CHECK((CheckList<2, 3, 1>(list))); 74 list.moveFrontToBack(); 75 list.moveFrontToBack(); 76 CHECK((CheckList<1, 2, 3>(list))); 77 78 // Test move constructor and assignment. 79 80 TestList list2(std::move(list)); 81 CHECK(list.isEmpty()); 82 CHECK((CheckList<1, 2, 3>(list2))); 83 84 list = std::move(list2); 85 CHECK(list2.isEmpty()); 86 CHECK((CheckList<1, 2, 3>(list))); 87 88 // Test release. 89 90 IntSinglyLinkedElement* head = list.release(); 91 CHECK(list.isEmpty()); 92 CHECK(head->value == 1); 93 CHECK(head->next->value == 2); 94 CHECK(head->next->next->value == 3); 95 CHECK(!head->next->next->next); 96 97 // Test construct from linked list. 98 99 list = TestList(head, head->next->next); 100 CHECK((CheckList<1, 2, 3>(list))); 101 102 // Test append. 103 104 CHECK(list2.isEmpty()); 105 list.append(std::move(list2)); 106 CHECK((CheckList<1, 2, 3>(list))); 107 CHECK(list2.isEmpty()); 108 109 TestList list3; 110 list3.pushBack(MakeElement(4)); 111 list3.pushBack(MakeElement(5)); 112 list3.pushBack(MakeElement(6)); 113 list2.append(std::move(list3)); 114 CHECK((CheckList<4, 5, 6>(list2))); 115 CHECK(list3.isEmpty()); 116 117 list.append(std::move(list2)); 118 CHECK((CheckList<1, 2, 3, 4, 5, 6>(list))); 119 CHECK(list2.isEmpty()); 120 121 // Test prepend. 122 123 CHECK(list2.isEmpty()); 124 list.prepend(std::move(list2)); 125 CHECK((CheckList<1, 2, 3, 4, 5, 6>(list))); 126 CHECK(list2.isEmpty()); 127 128 CHECK(list3.isEmpty()); 129 list3.pushBack(MakeElement(7)); 130 list3.pushBack(MakeElement(8)); 131 list3.pushBack(MakeElement(9)); 132 list2.prepend(std::move(list3)); 133 CHECK((CheckList<7, 8, 9>(list2))); 134 CHECK(list3.isEmpty()); 135 136 list.prepend(std::move(list2)); 137 CHECK((CheckList<7, 8, 9, 1, 2, 3, 4, 5, 6>(list))); 138 CHECK(list2.isEmpty()); 139 140 // Test iterators. 141 142 TestList::Iterator iter; 143 CHECK(iter.done()); 144 145 iter = list.iter(); 146 CHECK(!iter.done()); 147 CHECK(iter.get() == list.getFirst()); 148 149 iter = list.iterFrom(list.getLast()); 150 CHECK(!iter.done()); 151 CHECK(iter.get() == list.getLast()); 152 153 // Test removeRange. 154 155 e = FindElement(list, 3); 156 CHECK(e); 157 list.removeRange(e, list.getLast()); 158 CHECK((CheckList<7, 8, 9, 1, 2, 3>(list))); 159 160 e = FindElement(list, 8); 161 CHECK(e); 162 IntSinglyLinkedElement* f = FindElement(list, 2); 163 CHECK(f); 164 list.removeRange(e, f); 165 CHECK((CheckList<7, 8, 3>(list))); 166 167 // Cleanup. 168 169 while (!list.isEmpty()) { 170 js_delete(list.popFront()); 171 } 172 CHECK(list.isEmpty()); 173 CHECK(!list.getFirst()); 174 CHECK(!list.getLast()); 175 CHECK(CountList(list) == 0); 176 177 return true; 178 } 179 180 IntSinglyLinkedElement* MakeElement(int value) { 181 IntSinglyLinkedElement* element = js_new<IntSinglyLinkedElement>(value); 182 MOZ_RELEASE_ASSERT(element); 183 return element; 184 } 185 186 size_t CountList(const TestList& list) { 187 size_t i = 0; 188 for (auto iter = list.iter(); !iter.done(); iter.next()) { 189 i++; 190 } 191 return i; 192 } 193 194 IntSinglyLinkedElement* FindElement(const TestList& list, int value) { 195 for (auto iter = list.iter(); !iter.done(); iter.next()) { 196 if (iter->value == value) { 197 return iter.get(); 198 } 199 } 200 201 return nullptr; 202 } 203 204 template <int... Values> 205 bool CheckList(const TestList& list) { 206 int expected[] = {Values...}; 207 constexpr size_t N = std::size(expected); 208 209 size_t i = 0; 210 for (auto iter = list.iter(); !iter.done(); iter.next()) { 211 CHECK(i < N); 212 CHECK(iter->value == expected[i]); 213 i++; 214 } 215 216 CHECK(i == N); 217 218 return true; 219 } 220 221 END_TEST(testSinglyLinkedList)