bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 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 | |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 8 | #include "SkRandom.h" |
| 9 | #include "SkTInternalLList.h" |
| 10 | #include "SkTLList.h" |
tfarina@chromium.org | 8f6884a | 2014-01-24 20:56:26 +0000 | [diff] [blame] | 11 | #include "Test.h" |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 12 | |
| 13 | class ListElement { |
| 14 | public: |
| 15 | ListElement(int id) : fID(id) { |
| 16 | } |
| 17 | bool operator== (const ListElement& other) { return fID == other.fID; } |
| 18 | |
bsalomon@google.com | 4e23068 | 2013-01-15 20:37:04 +0000 | [diff] [blame] | 19 | #if SK_ENABLE_INST_COUNT |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 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 | |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 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()); |
commit-bot@chromium.org | 515dcd3 | 2013-08-28 14:17:03 +0000 | [diff] [blame] | 39 | #ifdef SK_DEBUG |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 40 | list.validate(); |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 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; NULL != 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; NULL != 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); |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 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; NULL != cur; ++i, cur = iter.next()) { |
| 118 | REPORTER_ASSERT(reporter, cur->fID == i); |
| 119 | } |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 120 | } |
| 121 | |
| 122 | static void TestTLList(skiatest::Reporter* reporter) { |
| 123 | typedef SkTLList<ListElement> ElList; |
| 124 | typedef ElList::Iter Iter; |
commit-bot@chromium.org | e0e7cfe | 2013-09-09 20:09:12 +0000 | [diff] [blame] | 125 | SkRandom random; |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 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 | |
bsalomon@google.com | 4e23068 | 2013-01-15 20:37:04 +0000 | [diff] [blame] | 136 | #if SK_ENABLE_INST_COUNT |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 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)); |
bsalomon@google.com | 4e23068 | 2013-01-15 20:37:04 +0000 | [diff] [blame] | 152 | #if SK_ENABLE_INST_COUNT |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 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); |
skia.committer@gmail.com | e659c2e | 2012-12-04 02:01:25 +0000 | [diff] [blame] | 163 | |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 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(); |
skia.committer@gmail.com | e659c2e | 2012-12-04 02:01:25 +0000 | [diff] [blame] | 170 | |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 171 | SkNEW_INSERT_IN_LLIST_AFTER(&list2, list2.tailIter(), ListElement, (1)); |
| 172 | REPORTER_ASSERT(reporter, list2 == list1); |
| 173 | |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 174 | // add an element to the second list, check that iters are still valid |
bsalomon@google.com | ebce030 | 2012-12-04 14:48:57 +0000 | [diff] [blame] | 175 | iter3.init(list2, Iter::kHead_IterStart); |
| 176 | iter4.init(list2, Iter::kTail_IterStart); |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 177 | list2.addToHead(ListElement(2)); |
bsalomon@google.com | ebce030 | 2012-12-04 14:48:57 +0000 | [diff] [blame] | 178 | |
bsalomon@google.com | 4e23068 | 2013-01-15 20:37:04 +0000 | [diff] [blame] | 179 | #if SK_ENABLE_INST_COUNT |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 180 | SkASSERT(3 == ListElement::InstanceCount()); |
| 181 | #endif |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 182 | |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 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); |
bsalomon@google.com | 4e23068 | 2013-01-15 20:37:04 +0000 | [diff] [blame] | 190 | #if SK_ENABLE_INST_COUNT |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 191 | SkASSERT(4 == ListElement::InstanceCount()); |
| 192 | #endif |
| 193 | REPORTER_ASSERT(reporter, !list1.isEmpty()); |
| 194 | |
| 195 | list1.reset(); |
| 196 | list2.reset(); |
bsalomon@google.com | 4e23068 | 2013-01-15 20:37:04 +0000 | [diff] [blame] | 197 | #if SK_ENABLE_INST_COUNT |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 198 | SkASSERT(0 == ListElement::InstanceCount()); |
| 199 | #endif |
| 200 | REPORTER_ASSERT(reporter, list1.isEmpty() && list2.isEmpty()); |
| 201 | |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 202 | // randomly perform insertions and deletions on a list and perform tests |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 203 | int count = 0; |
| 204 | for (int j = 0; j < 100; ++j) { |
| 205 | if (list1.isEmpty() || random.nextBiasedBool(3 * SK_Scalar1 / 4)) { |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 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(NULL != 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 (NULL != next.get()) { |
| 241 | REPORTER_ASSERT(reporter, next.prev()->fID == iter.get()->fID); |
| 242 | } |
| 243 | if (NULL != 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 (NULL != next.get()) { |
| 253 | REPORTER_ASSERT(reporter, next.prev()->fID == id); |
| 254 | } |
| 255 | if (NULL != prev.get()) { |
| 256 | REPORTER_ASSERT(reporter, prev.next()->fID == iter.get()->fID); |
| 257 | } |
| 258 | } |
skia.committer@gmail.com | e659c2e | 2012-12-04 02:01:25 +0000 | [diff] [blame] | 259 | } |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 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)(); |
skia.committer@gmail.com | e659c2e | 2012-12-04 02:01:25 +0000 | [diff] [blame] | 267 | |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 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, NULL != iter.get()); |
| 280 | (iter.*incrFunc)(); |
| 281 | } |
| 282 | REPORTER_ASSERT(reporter, NULL != 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()); |
bsalomon@google.com | 4e23068 | 2013-01-15 20:37:04 +0000 | [diff] [blame] | 302 | #if SK_ENABLE_INST_COUNT |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 303 | SkASSERT(count == ListElement::InstanceCount()); |
| 304 | #endif |
| 305 | } |
| 306 | list1.reset(); |
bsalomon@google.com | 4e23068 | 2013-01-15 20:37:04 +0000 | [diff] [blame] | 307 | #if SK_ENABLE_INST_COUNT |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 308 | SkASSERT(0 == ListElement::InstanceCount()); |
| 309 | #endif |
| 310 | } |
| 311 | } |
| 312 | |
tfarina@chromium.org | e4fafb1 | 2013-12-12 21:11:12 +0000 | [diff] [blame] | 313 | DEF_TEST(LList, reporter) { |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 314 | TestTInternalLList(reporter); |
| 315 | TestTLList(reporter); |
| 316 | } |