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 | 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 | } |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 115 | } |
| 116 | |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame^] | 117 | template <unsigned int N> static void test_tllist(skiatest::Reporter* reporter) { |
| 118 | typedef SkTLList<ListElement, N> ElList; |
| 119 | typedef typename ElList::Iter Iter; |
commit-bot@chromium.org | e0e7cfe | 2013-09-09 20:09:12 +0000 | [diff] [blame] | 120 | SkRandom random; |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 121 | |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame^] | 122 | ElList list1; |
| 123 | ElList list2; |
| 124 | Iter iter1; |
| 125 | Iter iter2; |
| 126 | Iter iter3; |
| 127 | Iter iter4; |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 128 | |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame^] | 129 | REPORTER_ASSERT(reporter, list1.isEmpty()); |
| 130 | REPORTER_ASSERT(reporter, nullptr == iter1.init(list1, Iter::kHead_IterStart)); |
| 131 | REPORTER_ASSERT(reporter, nullptr == iter1.init(list1, Iter::kTail_IterStart)); |
| 132 | // Try popping an empty list |
| 133 | list1.popHead(); |
| 134 | list1.popTail(); |
| 135 | REPORTER_ASSERT(reporter, list1.isEmpty()); |
| 136 | REPORTER_ASSERT(reporter, list1 == list2); |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 137 | |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame^] | 138 | // Create two identical lists, one by appending to head and the other to the tail. |
| 139 | list1.addToHead(ListElement(1)); |
| 140 | list2.addToTail(ListElement(1)); |
| 141 | iter1.init(list1, Iter::kHead_IterStart); |
| 142 | iter2.init(list1, Iter::kTail_IterStart); |
| 143 | REPORTER_ASSERT(reporter, iter1.get()->fID == iter2.get()->fID); |
| 144 | iter3.init(list2, Iter::kHead_IterStart); |
| 145 | iter4.init(list2, Iter::kTail_IterStart); |
| 146 | REPORTER_ASSERT(reporter, iter3.get()->fID == iter1.get()->fID); |
| 147 | REPORTER_ASSERT(reporter, iter4.get()->fID == iter1.get()->fID); |
| 148 | REPORTER_ASSERT(reporter, list1 == list2); |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 149 | |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame^] | 150 | list2.reset(); |
skia.committer@gmail.com | e659c2e | 2012-12-04 02:01:25 +0000 | [diff] [blame] | 151 | |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame^] | 152 | // use both before/after in-place construction on an empty list |
| 153 | list2.addBefore(list2.headIter(), 1); |
| 154 | REPORTER_ASSERT(reporter, list2 == list1); |
| 155 | list2.reset(); |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 156 | |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame^] | 157 | list2.addAfter(list2.tailIter(), 1); |
| 158 | REPORTER_ASSERT(reporter, list2 == list1); |
skia.committer@gmail.com | e659c2e | 2012-12-04 02:01:25 +0000 | [diff] [blame] | 159 | |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame^] | 160 | // add an element to the second list, check that iters are still valid |
| 161 | iter3.init(list2, Iter::kHead_IterStart); |
| 162 | iter4.init(list2, Iter::kTail_IterStart); |
| 163 | list2.addToHead(ListElement(2)); |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 164 | |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame^] | 165 | REPORTER_ASSERT(reporter, iter3.get()->fID == iter1.get()->fID); |
| 166 | REPORTER_ASSERT(reporter, iter4.get()->fID == iter1.get()->fID); |
| 167 | REPORTER_ASSERT(reporter, 1 == Iter(list2, Iter::kTail_IterStart).get()->fID); |
| 168 | REPORTER_ASSERT(reporter, 2 == Iter(list2, Iter::kHead_IterStart).get()->fID); |
| 169 | REPORTER_ASSERT(reporter, list1 != list2); |
| 170 | list1.addToHead(ListElement(2)); |
| 171 | REPORTER_ASSERT(reporter, list1 == list2); |
| 172 | REPORTER_ASSERT(reporter, !list1.isEmpty()); |
bsalomon@google.com | ebce030 | 2012-12-04 14:48:57 +0000 | [diff] [blame] | 173 | |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame^] | 174 | list1.reset(); |
| 175 | list2.reset(); |
| 176 | REPORTER_ASSERT(reporter, list1.isEmpty() && list2.isEmpty()); |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 177 | |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame^] | 178 | // randomly perform insertions and deletions on a list and perform tests |
| 179 | int count = 0; |
| 180 | for (int j = 0; j < 100; ++j) { |
| 181 | if (list1.isEmpty() || random.nextBiasedBool(3 * SK_Scalar1 / 4)) { |
| 182 | int id = j; |
| 183 | // Choose one of three ways to insert a new element: at the head, at the tail, |
| 184 | // before a random element, after a random element |
| 185 | int numValidMethods = 0 == count ? 2 : 4; |
| 186 | int insertionMethod = random.nextULessThan(numValidMethods); |
| 187 | switch (insertionMethod) { |
| 188 | case 0: |
| 189 | list1.addToHead(ListElement(id)); |
| 190 | break; |
| 191 | case 1: |
| 192 | list1.addToTail(ListElement(id)); |
| 193 | break; |
| 194 | case 2: // fallthru to share code that picks random element. |
| 195 | case 3: { |
| 196 | int n = random.nextULessThan(list1.count()); |
| 197 | Iter iter = list1.headIter(); |
| 198 | // remember the elements before/after the insertion point. |
| 199 | while (n--) { |
| 200 | iter.next(); |
| 201 | } |
| 202 | Iter prev(iter); |
| 203 | Iter next(iter); |
| 204 | next.next(); |
| 205 | prev.prev(); |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 206 | |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame^] | 207 | SkASSERT(iter.get()); |
| 208 | // insert either before or after the iterator, then check that the |
| 209 | // surrounding sequence is correct. |
| 210 | if (2 == insertionMethod) { |
| 211 | list1.addBefore(iter, id); |
| 212 | Iter newItem(iter); |
| 213 | newItem.prev(); |
| 214 | REPORTER_ASSERT(reporter, newItem.get()->fID == id); |
| 215 | |
| 216 | if (next.get()) { |
| 217 | REPORTER_ASSERT(reporter, next.prev()->fID == iter.get()->fID); |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 218 | } |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame^] | 219 | if (prev.get()) { |
| 220 | REPORTER_ASSERT(reporter, prev.next()->fID == id); |
| 221 | } |
| 222 | } else { |
| 223 | list1.addAfter(iter, id); |
| 224 | Iter newItem(iter); |
| 225 | newItem.next(); |
| 226 | REPORTER_ASSERT(reporter, newItem.get()->fID == id); |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 227 | |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame^] | 228 | if (next.get()) { |
| 229 | REPORTER_ASSERT(reporter, next.prev()->fID == id); |
| 230 | } |
| 231 | if (prev.get()) { |
| 232 | REPORTER_ASSERT(reporter, prev.next()->fID == iter.get()->fID); |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 233 | } |
skia.committer@gmail.com | e659c2e | 2012-12-04 02:01:25 +0000 | [diff] [blame] | 234 | } |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 235 | } |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 236 | } |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame^] | 237 | ++count; |
| 238 | } else { |
| 239 | // walk to a random place either forward or backwards and remove. |
| 240 | int n = random.nextULessThan(list1.count()); |
| 241 | typename Iter::IterStart start; |
| 242 | ListElement* (Iter::*incrFunc)(); |
| 243 | |
| 244 | if (random.nextBool()) { |
| 245 | start = Iter::kHead_IterStart; |
| 246 | incrFunc = &Iter::next; |
| 247 | } else { |
| 248 | start = Iter::kTail_IterStart; |
| 249 | incrFunc = &Iter::prev; |
| 250 | } |
| 251 | |
| 252 | // find the element |
| 253 | Iter iter(list1, start); |
| 254 | while (n--) { |
| 255 | REPORTER_ASSERT(reporter, iter.get()); |
| 256 | (iter.*incrFunc)(); |
| 257 | } |
| 258 | REPORTER_ASSERT(reporter, iter.get()); |
| 259 | |
| 260 | // remember the prev and next elements from the element to be removed |
| 261 | Iter prev = iter; |
| 262 | Iter next = iter; |
| 263 | prev.prev(); |
| 264 | next.next(); |
| 265 | list1.remove(iter.get()); |
| 266 | |
| 267 | // make sure the remembered next/prev iters still work |
| 268 | Iter pn = prev; pn.next(); |
| 269 | Iter np = next; np.prev(); |
| 270 | // pn should match next unless the target node was the head, in which case prev |
| 271 | // walked off the list. |
| 272 | REPORTER_ASSERT(reporter, pn.get() == next.get() || nullptr == prev.get()); |
| 273 | // Similarly, np should match prev unless next originally walked off the tail. |
| 274 | REPORTER_ASSERT(reporter, np.get() == prev.get() || nullptr == next.get()); |
| 275 | --count; |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 276 | } |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame^] | 277 | REPORTER_ASSERT(reporter, count == list1.count()); |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 278 | } |
| 279 | } |
| 280 | |
tfarina@chromium.org | e4fafb1 | 2013-12-12 21:11:12 +0000 | [diff] [blame] | 281 | DEF_TEST(LList, reporter) { |
bsalomon | f045d60 | 2015-11-18 19:01:12 -0800 | [diff] [blame^] | 282 | test_tinternallist(reporter); |
| 283 | test_tllist<1>(reporter); |
| 284 | test_tllist<3>(reporter); |
| 285 | test_tllist<8>(reporter); |
| 286 | test_tllist<10>(reporter); |
| 287 | test_tllist<16>(reporter); |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 288 | } |