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