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 | |
Mike Klein | c0bd9f9 | 2019-04-23 12:05:21 -0500 | [diff] [blame] | 8 | #include "include/utils/SkRandom.h" |
Ben Wagner | 729a23f | 2019-05-17 16:29:34 -0400 | [diff] [blame] | 9 | #include "src/core/SkTInternalLList.h" |
Mike Klein | c0bd9f9 | 2019-04-23 12:05:21 -0500 | [diff] [blame] | 10 | #include "src/core/SkTLList.h" |
| 11 | #include "tests/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 | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 19 | int fID; |
| 20 | |
| 21 | private: |
mtklein | 2766c00 | 2015-06-26 11:45:03 -0700 | [diff] [blame] | 22 | |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 23 | SK_DECLARE_INTERNAL_LLIST_INTERFACE(ListElement); |
| 24 | }; |
| 25 | |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 26 | static 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()); |
commit-bot@chromium.org | 515dcd3 | 2013-08-28 14:17:03 +0000 | [diff] [blame] | 34 | #ifdef SK_DEBUG |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 35 | list.validate(); |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 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 | |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame] | 44 | static void test_tinternallist(skiatest::Reporter* reporter) { |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 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); |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 71 | for (int i = 0; cur; ++i, cur = iter.next()) { |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 72 | REPORTER_ASSERT(reporter, cur->fID == 3-i); |
| 73 | } |
| 74 | |
| 75 | cur = iter.init(list, Iter::kTail_IterStart); |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 76 | for (int i = 0; cur; ++i, cur = iter.prev()) { |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 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); |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 92 | |
| 93 | // test out methods that add to the middle of the list. |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 94 | list.addAfter(&elements[1], nullptr); |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 95 | check_list(list, reporter, false, 1, false, true, false, false, elements); |
| 96 | |
| 97 | list.remove(&elements[1]); |
| 98 | |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 99 | list.addBefore(&elements[1], nullptr); |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 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); |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 112 | for (int i = 0; cur; ++i, cur = iter.next()) { |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 113 | REPORTER_ASSERT(reporter, cur->fID == i); |
| 114 | } |
Chris Dalton | 832bd2b | 2017-06-21 12:33:39 -0700 | [diff] [blame] | 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); |
Mike Klein | 1688507 | 2018-12-11 09:54:31 -0500 | [diff] [blame] | 123 | // NOLINTNEXTLINE(bugprone-use-after-move) |
Chris Dalton | 832bd2b | 2017-06-21 12:33:39 -0700 | [diff] [blame] | 124 | check_list(listB, reporter, true, 0, false, false, false, false, elements); |
| 125 | |
| 126 | listB.addToTail(&elements[0]); |
| 127 | listA.concat(std::move(listB)); |
| 128 | check_list(listA, reporter, false, 1, true, false, false, false, elements); |
Mike Klein | 1688507 | 2018-12-11 09:54:31 -0500 | [diff] [blame] | 129 | // NOLINTNEXTLINE(bugprone-use-after-move) |
Chris Dalton | 832bd2b | 2017-06-21 12:33:39 -0700 | [diff] [blame] | 130 | check_list(listB, reporter, true, 0, false, false, false, false, elements); |
| 131 | |
| 132 | listB.addToTail(&elements[1]); |
| 133 | listA.concat(std::move(listB)); |
| 134 | check_list(listA, reporter, false, 2, true, true, false, false, elements); |
Mike Klein | 1688507 | 2018-12-11 09:54:31 -0500 | [diff] [blame] | 135 | // NOLINTNEXTLINE(bugprone-use-after-move) |
Chris Dalton | 832bd2b | 2017-06-21 12:33:39 -0700 | [diff] [blame] | 136 | check_list(listB, reporter, true, 0, false, false, false, false, elements); |
| 137 | |
| 138 | listA.concat(std::move(listB)); |
| 139 | check_list(listA, reporter, false, 2, true, true, false, false, elements); |
Mike Klein | 1688507 | 2018-12-11 09:54:31 -0500 | [diff] [blame] | 140 | // NOLINTNEXTLINE(bugprone-use-after-move) |
Chris Dalton | 832bd2b | 2017-06-21 12:33:39 -0700 | [diff] [blame] | 141 | check_list(listB, reporter, true, 0, false, false, false, false, elements); |
| 142 | |
| 143 | listB.addToTail(&elements[2]); |
| 144 | listB.addToTail(&elements[3]); |
| 145 | listA.concat(std::move(listB)); |
| 146 | check_list(listA, reporter, false, 4, true, true, true, true, elements); |
Mike Klein | 1688507 | 2018-12-11 09:54:31 -0500 | [diff] [blame] | 147 | // NOLINTNEXTLINE(bugprone-use-after-move) |
Chris Dalton | 832bd2b | 2017-06-21 12:33:39 -0700 | [diff] [blame] | 148 | check_list(listB, reporter, true, 0, false, false, false, false, elements); |
| 149 | |
| 150 | cur = iter.init(listA, Iter::kHead_IterStart); |
| 151 | for (int i = 0; cur; ++i, cur = iter.next()) { |
| 152 | REPORTER_ASSERT(reporter, cur->fID == i); |
| 153 | } |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 154 | } |
| 155 | |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame] | 156 | template <unsigned int N> static void test_tllist(skiatest::Reporter* reporter) { |
| 157 | typedef SkTLList<ListElement, N> ElList; |
| 158 | typedef typename ElList::Iter Iter; |
commit-bot@chromium.org | e0e7cfe | 2013-09-09 20:09:12 +0000 | [diff] [blame] | 159 | SkRandom random; |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 160 | |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame] | 161 | ElList list1; |
| 162 | ElList list2; |
| 163 | Iter iter1; |
| 164 | Iter iter2; |
| 165 | Iter iter3; |
| 166 | Iter iter4; |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 167 | |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame] | 168 | REPORTER_ASSERT(reporter, list1.isEmpty()); |
| 169 | REPORTER_ASSERT(reporter, nullptr == iter1.init(list1, Iter::kHead_IterStart)); |
| 170 | REPORTER_ASSERT(reporter, nullptr == iter1.init(list1, Iter::kTail_IterStart)); |
| 171 | // Try popping an empty list |
| 172 | list1.popHead(); |
| 173 | list1.popTail(); |
| 174 | REPORTER_ASSERT(reporter, list1.isEmpty()); |
| 175 | REPORTER_ASSERT(reporter, list1 == list2); |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 176 | |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame] | 177 | // Create two identical lists, one by appending to head and the other to the tail. |
| 178 | list1.addToHead(ListElement(1)); |
| 179 | list2.addToTail(ListElement(1)); |
| 180 | iter1.init(list1, Iter::kHead_IterStart); |
| 181 | iter2.init(list1, Iter::kTail_IterStart); |
| 182 | REPORTER_ASSERT(reporter, iter1.get()->fID == iter2.get()->fID); |
| 183 | iter3.init(list2, Iter::kHead_IterStart); |
| 184 | iter4.init(list2, Iter::kTail_IterStart); |
| 185 | REPORTER_ASSERT(reporter, iter3.get()->fID == iter1.get()->fID); |
| 186 | REPORTER_ASSERT(reporter, iter4.get()->fID == iter1.get()->fID); |
| 187 | REPORTER_ASSERT(reporter, list1 == list2); |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 188 | |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame] | 189 | list2.reset(); |
skia.committer@gmail.com | e659c2e | 2012-12-04 02:01:25 +0000 | [diff] [blame] | 190 | |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame] | 191 | // use both before/after in-place construction on an empty list |
| 192 | list2.addBefore(list2.headIter(), 1); |
| 193 | REPORTER_ASSERT(reporter, list2 == list1); |
| 194 | list2.reset(); |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 195 | |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame] | 196 | list2.addAfter(list2.tailIter(), 1); |
| 197 | REPORTER_ASSERT(reporter, list2 == list1); |
skia.committer@gmail.com | e659c2e | 2012-12-04 02:01:25 +0000 | [diff] [blame] | 198 | |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame] | 199 | // add an element to the second list, check that iters are still valid |
| 200 | iter3.init(list2, Iter::kHead_IterStart); |
| 201 | iter4.init(list2, Iter::kTail_IterStart); |
| 202 | list2.addToHead(ListElement(2)); |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 203 | |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame] | 204 | REPORTER_ASSERT(reporter, iter3.get()->fID == iter1.get()->fID); |
| 205 | REPORTER_ASSERT(reporter, iter4.get()->fID == iter1.get()->fID); |
| 206 | REPORTER_ASSERT(reporter, 1 == Iter(list2, Iter::kTail_IterStart).get()->fID); |
| 207 | REPORTER_ASSERT(reporter, 2 == Iter(list2, Iter::kHead_IterStart).get()->fID); |
| 208 | REPORTER_ASSERT(reporter, list1 != list2); |
| 209 | list1.addToHead(ListElement(2)); |
| 210 | REPORTER_ASSERT(reporter, list1 == list2); |
| 211 | REPORTER_ASSERT(reporter, !list1.isEmpty()); |
bsalomon@google.com | ebce030 | 2012-12-04 14:48:57 +0000 | [diff] [blame] | 212 | |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame] | 213 | list1.reset(); |
| 214 | list2.reset(); |
| 215 | REPORTER_ASSERT(reporter, list1.isEmpty() && list2.isEmpty()); |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 216 | |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame] | 217 | // randomly perform insertions and deletions on a list and perform tests |
| 218 | int count = 0; |
| 219 | for (int j = 0; j < 100; ++j) { |
| 220 | if (list1.isEmpty() || random.nextBiasedBool(3 * SK_Scalar1 / 4)) { |
| 221 | int id = j; |
| 222 | // Choose one of three ways to insert a new element: at the head, at the tail, |
| 223 | // before a random element, after a random element |
| 224 | int numValidMethods = 0 == count ? 2 : 4; |
| 225 | int insertionMethod = random.nextULessThan(numValidMethods); |
| 226 | switch (insertionMethod) { |
| 227 | case 0: |
| 228 | list1.addToHead(ListElement(id)); |
| 229 | break; |
| 230 | case 1: |
| 231 | list1.addToTail(ListElement(id)); |
| 232 | break; |
| 233 | case 2: // fallthru to share code that picks random element. |
| 234 | case 3: { |
| 235 | int n = random.nextULessThan(list1.count()); |
| 236 | Iter iter = list1.headIter(); |
| 237 | // remember the elements before/after the insertion point. |
| 238 | while (n--) { |
| 239 | iter.next(); |
| 240 | } |
| 241 | Iter prev(iter); |
| 242 | Iter next(iter); |
| 243 | next.next(); |
| 244 | prev.prev(); |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 245 | |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame] | 246 | SkASSERT(iter.get()); |
| 247 | // insert either before or after the iterator, then check that the |
| 248 | // surrounding sequence is correct. |
| 249 | if (2 == insertionMethod) { |
| 250 | list1.addBefore(iter, id); |
| 251 | Iter newItem(iter); |
| 252 | newItem.prev(); |
| 253 | REPORTER_ASSERT(reporter, newItem.get()->fID == id); |
| 254 | |
| 255 | if (next.get()) { |
| 256 | REPORTER_ASSERT(reporter, next.prev()->fID == iter.get()->fID); |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 257 | } |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame] | 258 | if (prev.get()) { |
| 259 | REPORTER_ASSERT(reporter, prev.next()->fID == id); |
| 260 | } |
| 261 | } else { |
| 262 | list1.addAfter(iter, id); |
| 263 | Iter newItem(iter); |
| 264 | newItem.next(); |
| 265 | REPORTER_ASSERT(reporter, newItem.get()->fID == id); |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 266 | |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame] | 267 | if (next.get()) { |
| 268 | REPORTER_ASSERT(reporter, next.prev()->fID == id); |
| 269 | } |
| 270 | if (prev.get()) { |
| 271 | REPORTER_ASSERT(reporter, prev.next()->fID == iter.get()->fID); |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 272 | } |
skia.committer@gmail.com | e659c2e | 2012-12-04 02:01:25 +0000 | [diff] [blame] | 273 | } |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 274 | } |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 275 | } |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame] | 276 | ++count; |
| 277 | } else { |
| 278 | // walk to a random place either forward or backwards and remove. |
| 279 | int n = random.nextULessThan(list1.count()); |
| 280 | typename Iter::IterStart start; |
| 281 | ListElement* (Iter::*incrFunc)(); |
| 282 | |
| 283 | if (random.nextBool()) { |
| 284 | start = Iter::kHead_IterStart; |
| 285 | incrFunc = &Iter::next; |
| 286 | } else { |
| 287 | start = Iter::kTail_IterStart; |
| 288 | incrFunc = &Iter::prev; |
| 289 | } |
| 290 | |
| 291 | // find the element |
| 292 | Iter iter(list1, start); |
| 293 | while (n--) { |
| 294 | REPORTER_ASSERT(reporter, iter.get()); |
| 295 | (iter.*incrFunc)(); |
| 296 | } |
| 297 | REPORTER_ASSERT(reporter, iter.get()); |
| 298 | |
| 299 | // remember the prev and next elements from the element to be removed |
| 300 | Iter prev = iter; |
| 301 | Iter next = iter; |
| 302 | prev.prev(); |
| 303 | next.next(); |
| 304 | list1.remove(iter.get()); |
| 305 | |
| 306 | // make sure the remembered next/prev iters still work |
| 307 | Iter pn = prev; pn.next(); |
| 308 | Iter np = next; np.prev(); |
| 309 | // pn should match next unless the target node was the head, in which case prev |
| 310 | // walked off the list. |
| 311 | REPORTER_ASSERT(reporter, pn.get() == next.get() || nullptr == prev.get()); |
| 312 | // Similarly, np should match prev unless next originally walked off the tail. |
| 313 | REPORTER_ASSERT(reporter, np.get() == prev.get() || nullptr == next.get()); |
| 314 | --count; |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 315 | } |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame] | 316 | REPORTER_ASSERT(reporter, count == list1.count()); |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 317 | } |
| 318 | } |
| 319 | |
tfarina@chromium.org | e4fafb1 | 2013-12-12 21:11:12 +0000 | [diff] [blame] | 320 | DEF_TEST(LList, reporter) { |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame] | 321 | test_tinternallist(reporter); |
| 322 | test_tllist<1>(reporter); |
| 323 | test_tllist<3>(reporter); |
| 324 | test_tllist<8>(reporter); |
| 325 | test_tllist<10>(reporter); |
| 326 | test_tllist<16>(reporter); |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 327 | } |