1/* 2 * Copyright 2012 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8#include "SkRandom.h" 9#include "SkTInternalLList.h" 10#include "SkTLList.h" 11#include "Test.h" 12 13class ListElement { 14public: 15 ListElement(int id) : fID(id) { 16 } 17 bool operator== (const ListElement& other) { return fID == other.fID; } 18 19 int fID; 20 21private: 22 23 SK_DECLARE_INTERNAL_LLIST_INTERFACE(ListElement); 24}; 25 26static void check_list(const SkTInternalLList<ListElement>& list, 27 skiatest::Reporter* reporter, 28 bool empty, 29 int numElements, 30 bool in0, bool in1, bool in2, bool in3, 31 ListElement elements[4]) { 32 33 REPORTER_ASSERT(reporter, empty == list.isEmpty()); 34#ifdef SK_DEBUG 35 list.validate(); 36 REPORTER_ASSERT(reporter, numElements == list.countEntries()); 37 REPORTER_ASSERT(reporter, in0 == list.isInList(&elements[0])); 38 REPORTER_ASSERT(reporter, in1 == list.isInList(&elements[1])); 39 REPORTER_ASSERT(reporter, in2 == list.isInList(&elements[2])); 40 REPORTER_ASSERT(reporter, in3 == list.isInList(&elements[3])); 41#endif 42} 43 44static void test_tinternallist(skiatest::Reporter* reporter) { 45 SkTInternalLList<ListElement> list; 46 ListElement elements[4] = { 47 ListElement(0), 48 ListElement(1), 49 ListElement(2), 50 ListElement(3), 51 }; 52 53 // list should be empty to start with 54 check_list(list, reporter, true, 0, false, false, false, false, elements); 55 56 list.addToHead(&elements[0]); 57 58 check_list(list, reporter, false, 1, true, false, false, false, elements); 59 60 list.addToHead(&elements[1]); 61 list.addToHead(&elements[2]); 62 list.addToHead(&elements[3]); 63 64 check_list(list, reporter, false, 4, true, true, true, true, elements); 65 66 // test out iterators 67 typedef SkTInternalLList<ListElement>::Iter Iter; 68 Iter iter; 69 70 ListElement* cur = iter.init(list, Iter::kHead_IterStart); 71 for (int i = 0; cur; ++i, cur = iter.next()) { 72 REPORTER_ASSERT(reporter, cur->fID == 3-i); 73 } 74 75 cur = iter.init(list, Iter::kTail_IterStart); 76 for (int i = 0; cur; ++i, cur = iter.prev()) { 77 REPORTER_ASSERT(reporter, cur->fID == i); 78 } 79 80 // remove middle, frontmost then backmost 81 list.remove(&elements[1]); 82 list.remove(&elements[3]); 83 list.remove(&elements[0]); 84 85 check_list(list, reporter, false, 1, false, false, true, false, elements); 86 87 // remove last element 88 list.remove(&elements[2]); 89 90 // list should be empty again 91 check_list(list, reporter, true, 0, false, false, false, false, elements); 92 93 // test out methods that add to the middle of the list. 94 list.addAfter(&elements[1], nullptr); 95 check_list(list, reporter, false, 1, false, true, false, false, elements); 96 97 list.remove(&elements[1]); 98 99 list.addBefore(&elements[1], nullptr); 100 check_list(list, reporter, false, 1, false, true, false, false, elements); 101 102 list.addBefore(&elements[0], &elements[1]); 103 check_list(list, reporter, false, 2, true, true, false, false, elements); 104 105 list.addAfter(&elements[3], &elements[1]); 106 check_list(list, reporter, false, 3, true, true, false, true, elements); 107 108 list.addBefore(&elements[2], &elements[3]); 109 check_list(list, reporter, false, 4, true, true, true, true, elements); 110 111 cur = iter.init(list, Iter::kHead_IterStart); 112 for (int i = 0; cur; ++i, cur = iter.next()) { 113 REPORTER_ASSERT(reporter, cur->fID == i); 114 } 115 while (!list.isEmpty()) { 116 list.remove(list.tail()); 117 } 118 119 // test concat. 120 SkTInternalLList<ListElement> listA, listB; 121 listA.concat(std::move(listB)); 122 check_list(listA, reporter, true, 0, false, false, false, false, elements); 123 check_list(listB, reporter, true, 0, false, false, false, false, elements); 124 125 listB.addToTail(&elements[0]); 126 listA.concat(std::move(listB)); 127 check_list(listA, reporter, false, 1, true, false, false, false, elements); 128 check_list(listB, reporter, true, 0, false, false, false, false, elements); 129 130 listB.addToTail(&elements[1]); 131 listA.concat(std::move(listB)); 132 check_list(listA, reporter, false, 2, true, true, false, false, elements); 133 check_list(listB, reporter, true, 0, false, false, false, false, elements); 134 135 listA.concat(std::move(listB)); 136 check_list(listA, reporter, false, 2, true, true, false, false, elements); 137 check_list(listB, reporter, true, 0, false, false, false, false, elements); 138 139 listB.addToTail(&elements[2]); 140 listB.addToTail(&elements[3]); 141 listA.concat(std::move(listB)); 142 check_list(listA, reporter, false, 4, true, true, true, true, elements); 143 check_list(listB, reporter, true, 0, false, false, false, false, elements); 144 145 cur = iter.init(listA, Iter::kHead_IterStart); 146 for (int i = 0; cur; ++i, cur = iter.next()) { 147 REPORTER_ASSERT(reporter, cur->fID == i); 148 } 149} 150 151template <unsigned int N> static void test_tllist(skiatest::Reporter* reporter) { 152 typedef SkTLList<ListElement, N> ElList; 153 typedef typename ElList::Iter Iter; 154 SkRandom random; 155 156 ElList list1; 157 ElList list2; 158 Iter iter1; 159 Iter iter2; 160 Iter iter3; 161 Iter iter4; 162 163 REPORTER_ASSERT(reporter, list1.isEmpty()); 164 REPORTER_ASSERT(reporter, nullptr == iter1.init(list1, Iter::kHead_IterStart)); 165 REPORTER_ASSERT(reporter, nullptr == iter1.init(list1, Iter::kTail_IterStart)); 166 // Try popping an empty list 167 list1.popHead(); 168 list1.popTail(); 169 REPORTER_ASSERT(reporter, list1.isEmpty()); 170 REPORTER_ASSERT(reporter, list1 == list2); 171 172 // Create two identical lists, one by appending to head and the other to the tail. 173 list1.addToHead(ListElement(1)); 174 list2.addToTail(ListElement(1)); 175 iter1.init(list1, Iter::kHead_IterStart); 176 iter2.init(list1, Iter::kTail_IterStart); 177 REPORTER_ASSERT(reporter, iter1.get()->fID == iter2.get()->fID); 178 iter3.init(list2, Iter::kHead_IterStart); 179 iter4.init(list2, Iter::kTail_IterStart); 180 REPORTER_ASSERT(reporter, iter3.get()->fID == iter1.get()->fID); 181 REPORTER_ASSERT(reporter, iter4.get()->fID == iter1.get()->fID); 182 REPORTER_ASSERT(reporter, list1 == list2); 183 184 list2.reset(); 185 186 // use both before/after in-place construction on an empty list 187 list2.addBefore(list2.headIter(), 1); 188 REPORTER_ASSERT(reporter, list2 == list1); 189 list2.reset(); 190 191 list2.addAfter(list2.tailIter(), 1); 192 REPORTER_ASSERT(reporter, list2 == list1); 193 194 // add an element to the second list, check that iters are still valid 195 iter3.init(list2, Iter::kHead_IterStart); 196 iter4.init(list2, Iter::kTail_IterStart); 197 list2.addToHead(ListElement(2)); 198 199 REPORTER_ASSERT(reporter, iter3.get()->fID == iter1.get()->fID); 200 REPORTER_ASSERT(reporter, iter4.get()->fID == iter1.get()->fID); 201 REPORTER_ASSERT(reporter, 1 == Iter(list2, Iter::kTail_IterStart).get()->fID); 202 REPORTER_ASSERT(reporter, 2 == Iter(list2, Iter::kHead_IterStart).get()->fID); 203 REPORTER_ASSERT(reporter, list1 != list2); 204 list1.addToHead(ListElement(2)); 205 REPORTER_ASSERT(reporter, list1 == list2); 206 REPORTER_ASSERT(reporter, !list1.isEmpty()); 207 208 list1.reset(); 209 list2.reset(); 210 REPORTER_ASSERT(reporter, list1.isEmpty() && list2.isEmpty()); 211 212 // randomly perform insertions and deletions on a list and perform tests 213 int count = 0; 214 for (int j = 0; j < 100; ++j) { 215 if (list1.isEmpty() || random.nextBiasedBool(3 * SK_Scalar1 / 4)) { 216 int id = j; 217 // Choose one of three ways to insert a new element: at the head, at the tail, 218 // before a random element, after a random element 219 int numValidMethods = 0 == count ? 2 : 4; 220 int insertionMethod = random.nextULessThan(numValidMethods); 221 switch (insertionMethod) { 222 case 0: 223 list1.addToHead(ListElement(id)); 224 break; 225 case 1: 226 list1.addToTail(ListElement(id)); 227 break; 228 case 2: // fallthru to share code that picks random element. 229 case 3: { 230 int n = random.nextULessThan(list1.count()); 231 Iter iter = list1.headIter(); 232 // remember the elements before/after the insertion point. 233 while (n--) { 234 iter.next(); 235 } 236 Iter prev(iter); 237 Iter next(iter); 238 next.next(); 239 prev.prev(); 240 241 SkASSERT(iter.get()); 242 // insert either before or after the iterator, then check that the 243 // surrounding sequence is correct. 244 if (2 == insertionMethod) { 245 list1.addBefore(iter, id); 246 Iter newItem(iter); 247 newItem.prev(); 248 REPORTER_ASSERT(reporter, newItem.get()->fID == id); 249 250 if (next.get()) { 251 REPORTER_ASSERT(reporter, next.prev()->fID == iter.get()->fID); 252 } 253 if (prev.get()) { 254 REPORTER_ASSERT(reporter, prev.next()->fID == id); 255 } 256 } else { 257 list1.addAfter(iter, id); 258 Iter newItem(iter); 259 newItem.next(); 260 REPORTER_ASSERT(reporter, newItem.get()->fID == id); 261 262 if (next.get()) { 263 REPORTER_ASSERT(reporter, next.prev()->fID == id); 264 } 265 if (prev.get()) { 266 REPORTER_ASSERT(reporter, prev.next()->fID == iter.get()->fID); 267 } 268 } 269 } 270 } 271 ++count; 272 } else { 273 // walk to a random place either forward or backwards and remove. 274 int n = random.nextULessThan(list1.count()); 275 typename Iter::IterStart start; 276 ListElement* (Iter::*incrFunc)(); 277 278 if (random.nextBool()) { 279 start = Iter::kHead_IterStart; 280 incrFunc = &Iter::next; 281 } else { 282 start = Iter::kTail_IterStart; 283 incrFunc = &Iter::prev; 284 } 285 286 // find the element 287 Iter iter(list1, start); 288 while (n--) { 289 REPORTER_ASSERT(reporter, iter.get()); 290 (iter.*incrFunc)(); 291 } 292 REPORTER_ASSERT(reporter, iter.get()); 293 294 // remember the prev and next elements from the element to be removed 295 Iter prev = iter; 296 Iter next = iter; 297 prev.prev(); 298 next.next(); 299 list1.remove(iter.get()); 300 301 // make sure the remembered next/prev iters still work 302 Iter pn = prev; pn.next(); 303 Iter np = next; np.prev(); 304 // pn should match next unless the target node was the head, in which case prev 305 // walked off the list. 306 REPORTER_ASSERT(reporter, pn.get() == next.get() || nullptr == prev.get()); 307 // Similarly, np should match prev unless next originally walked off the tail. 308 REPORTER_ASSERT(reporter, np.get() == prev.get() || nullptr == next.get()); 309 --count; 310 } 311 REPORTER_ASSERT(reporter, count == list1.count()); 312 } 313} 314 315DEF_TEST(LList, reporter) { 316 test_tinternallist(reporter); 317 test_tllist<1>(reporter); 318 test_tllist<3>(reporter); 319 test_tllist<8>(reporter); 320 test_tllist<10>(reporter); 321 test_tllist<16>(reporter); 322} 323