testLinkedList.cpp (5909B)
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 "mozilla/ScopeExit.h" 9 10 #include "ds/SlimLinkedList.h" 11 12 #include "jsapi-tests/tests.h" 13 14 using namespace js; 15 16 struct IntElement : public SlimLinkedListElement<IntElement> { 17 int value; 18 explicit IntElement(int value = 0) : value(value) {} 19 void incr() { ++value; } 20 }; 21 22 BEGIN_TEST(testSlimLinkedList) { 23 CHECK(TestList()); 24 CHECK(TestMove()); 25 CHECK(TestExtendLists()); 26 return true; 27 } 28 29 template <size_t N> 30 [[nodiscard]] bool PushListValues(SlimLinkedList<IntElement>& list, 31 const std::array<int, N>& values) { 32 for (int value : values) { 33 IntElement* element = new IntElement(value); 34 CHECK(element); 35 list.pushBack(element); 36 } 37 38 return true; 39 } 40 41 template <size_t N> 42 [[nodiscard]] bool CheckListValues(const SlimLinkedList<IntElement>& list, 43 const std::array<int, N>& expected) { 44 size_t count = 0; 45 for (const IntElement* x : list) { 46 CHECK(x->value == expected[count]); 47 ++count; 48 } 49 CHECK(count == N); 50 51 return true; 52 } 53 54 bool TestList() { 55 SlimLinkedList<IntElement> list; 56 const SlimLinkedList<IntElement>& constList = list; 57 58 IntElement one(1), two(2), three(3); 59 60 auto guard = mozilla::MakeScopeExit([&list]() { list.clear(); }); 61 62 // Test empty list. 63 CHECK(list.isEmpty()); 64 CHECK(list.length() == 0); 65 CHECK(!list.getFirst()); 66 CHECK(!list.getLast()); 67 CHECK(!list.popFirst()); 68 CHECK(!list.popLast()); 69 CHECK(list.begin() == list.end()); 70 CHECK(constList.begin() == constList.end()); 71 CHECK(CheckListValues(list, std::array<int, 0>{})); 72 73 // Test pushFront. 74 list.pushFront(&one); 75 CHECK(!list.isEmpty()); 76 CHECK(list.length() == 1); 77 CHECK(list.getFirst() == &one); 78 CHECK(list.getLast() == &one); 79 CHECK(*list.begin() == &one); 80 list.pushFront(&two); 81 CHECK(list.length() == 2); 82 CHECK(list.getFirst() == &two); 83 CHECK(list.getLast() == &one); 84 CHECK(*list.begin() == &two); 85 CHECK(CheckListValues(list, std::array{2, 1})); 86 CHECK(list.contains(&one)); 87 CHECK(!list.contains(&three)); 88 89 // Test popFirst. 90 IntElement* element = list.popFirst(); 91 CHECK(element == &two); 92 CHECK(list.length() == 1); 93 element = list.popFirst(); 94 CHECK(element == &one); 95 CHECK(list.isEmpty()); 96 97 // Test pushBack. 98 list.pushBack(&one); 99 CHECK(!list.isEmpty()); 100 CHECK(list.length() == 1); 101 CHECK(list.getFirst() == &one); 102 CHECK(list.getLast() == &one); 103 CHECK(*list.begin() == &one); 104 list.pushBack(&two); 105 CHECK(list.length() == 2); 106 CHECK(list.getFirst() == &one); 107 CHECK(list.getLast() == &two); 108 CHECK(*list.begin() == &one); 109 CHECK(CheckListValues(list, std::array{1, 2})); 110 CHECK(list.contains(&one)); 111 CHECK(!list.contains(&three)); 112 113 // Test popLast. 114 element = list.popLast(); 115 CHECK(element == &two); 116 CHECK(list.length() == 1); 117 element = list.popLast(); 118 CHECK(element == &one); 119 CHECK(list.isEmpty()); 120 121 // Test remove. 122 list.pushBack(&one); 123 list.pushBack(&two); 124 list.pushBack(&three); 125 list.remove(&one); 126 CHECK(CheckListValues(list, std::array{2, 3})); 127 list.pushFront(&one); 128 list.remove(&three); 129 CHECK(CheckListValues(list, std::array{1, 2})); 130 list.pushBack(&three); 131 list.remove(&two); 132 CHECK(CheckListValues(list, std::array{1, 3})); 133 134 // Test eraseIf. 135 list.pushBack(&two); 136 list.eraseIf([](IntElement* element) { return element->value % 2 == 1; }); 137 CHECK(CheckListValues(list, std::array{2})); 138 139 // Test clear. 140 list.clear(); 141 CHECK(list.isEmpty()); 142 list.clear(); 143 CHECK(list.isEmpty()); 144 145 return true; 146 } 147 148 bool TestExtendLists() { 149 SlimLinkedList<IntElement> list1; 150 auto guard = 151 mozilla::MakeScopeExit([&]() { list1.drain([](auto* e) { delete e; }); }); 152 153 CHECK(PushListValues(list1, std::array{0, 1, 2})); 154 CHECK(CheckListValues(list1, std::array{0, 1, 2})); 155 156 // Test extending with empty list. 157 list1.append(SlimLinkedList<IntElement>()); 158 CHECK(CheckListValues(list1, std::array{0, 1, 2})); 159 list1.prepend(SlimLinkedList<IntElement>()); 160 CHECK(CheckListValues(list1, std::array{0, 1, 2})); 161 162 // Test extending empty list. 163 SlimLinkedList<IntElement> list2; 164 list2.append(std::move(list1)); 165 CHECK(list1.isEmpty()); 166 CHECK(CheckListValues(list2, std::array{0, 1, 2})); 167 list1.prepend(std::move(list2)); 168 CHECK(list2.isEmpty()); 169 CHECK(CheckListValues(list1, std::array{0, 1, 2})); 170 171 // Test append. 172 CHECK(PushListValues(list2, std::array{3, 4, 5})); 173 CHECK(CheckListValues(list2, std::array{3, 4, 5})); 174 list1.append(std::move(list2)); 175 CHECK(CheckListValues(list1, std::array{0, 1, 2, 3, 4, 5})); 176 CHECK(list2.isEmpty()); 177 178 // Test prepend. 179 CHECK(PushListValues(list2, std::array{6, 7, 8})); 180 CHECK(CheckListValues(list2, std::array{6, 7, 8})); 181 list1.prepend(std::move(list2)); 182 CHECK(CheckListValues(list1, std::array{6, 7, 8, 0, 1, 2, 3, 4, 5})); 183 CHECK(list2.isEmpty()); 184 185 return true; 186 } 187 188 bool TestMove() { 189 // Test move constructor for the element. 190 IntElement c1(IntElement(1)); 191 CHECK(c1.value == 1); 192 193 // Test move assignment from an element not in a list. 194 IntElement c2; 195 c2 = IntElement(2); 196 CHECK(c2.value == 2); 197 198 SlimLinkedList<IntElement> list1; 199 list1.pushBack(&c1); 200 list1.pushBack(&c2); 201 202 // Test move constructor for the list. 203 SlimLinkedList<IntElement> list2(std::move(list1)); 204 CHECK(CheckListValues(list2, std::array{1, 2})); 205 CHECK(list1.isEmpty()); 206 207 // Test move assignment for the list. 208 SlimLinkedList<IntElement> list3; 209 list3 = std::move(list2); 210 CHECK(CheckListValues(list3, std::array{1, 2})); 211 CHECK(list2.isEmpty()); 212 213 list3.clear(); 214 215 return true; 216 } 217 END_TEST(testSlimLinkedList)