| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright 2012 Google Inc. | 2 * Copyright 2012 Google Inc. |
| 3 * | 3 * |
| 4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
| 5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
| 6 */ | 6 */ |
| 7 | 7 |
| 8 #include "SkInstCnt.h" | |
| 9 #include "SkRandom.h" | 8 #include "SkRandom.h" |
| 10 #include "SkTInternalLList.h" | 9 #include "SkTInternalLList.h" |
| 11 #include "SkTLList.h" | 10 #include "SkTLList.h" |
| 12 #include "Test.h" | 11 #include "Test.h" |
| 13 | 12 |
| 14 class ListElement { | 13 class ListElement { |
| 15 public: | 14 public: |
| 16 ListElement(int id) : fID(id) { | 15 ListElement(int id) : fID(id) { |
| 17 } | 16 } |
| 18 bool operator== (const ListElement& other) { return fID == other.fID; } | 17 bool operator== (const ListElement& other) { return fID == other.fID; } |
| 19 | 18 |
| 20 #if SK_ENABLE_INST_COUNT | |
| 21 // Make the instance count available publicly. | |
| 22 static int InstanceCount() { return GetInstanceCount(); } | |
| 23 #endif | |
| 24 | |
| 25 int fID; | 19 int fID; |
| 26 | 20 |
| 27 private: | 21 private: |
| 28 SK_DECLARE_INST_COUNT(ListElement); | 22 |
| 29 SK_DECLARE_INTERNAL_LLIST_INTERFACE(ListElement); | 23 SK_DECLARE_INTERNAL_LLIST_INTERFACE(ListElement); |
| 30 }; | 24 }; |
| 31 | 25 |
| 32 static void check_list(const SkTInternalLList<ListElement>& list, | 26 static void check_list(const SkTInternalLList<ListElement>& list, |
| 33 skiatest::Reporter* reporter, | 27 skiatest::Reporter* reporter, |
| 34 bool empty, | 28 bool empty, |
| 35 int numElements, | 29 int numElements, |
| 36 bool in0, bool in1, bool in2, bool in3, | 30 bool in0, bool in1, bool in2, bool in3, |
| 37 ListElement elements[4]) { | 31 ListElement elements[4]) { |
| 38 | 32 |
| (...skipping 88 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 127 | 121 |
| 128 for (int i = 1; i <= 16; i *= 2) { | 122 for (int i = 1; i <= 16; i *= 2) { |
| 129 | 123 |
| 130 ElList list1(i); | 124 ElList list1(i); |
| 131 ElList list2(i); | 125 ElList list2(i); |
| 132 Iter iter1; | 126 Iter iter1; |
| 133 Iter iter2; | 127 Iter iter2; |
| 134 Iter iter3; | 128 Iter iter3; |
| 135 Iter iter4; | 129 Iter iter4; |
| 136 | 130 |
| 137 #if SK_ENABLE_INST_COUNT | |
| 138 SkASSERT(0 == ListElement::InstanceCount()); | |
| 139 #endif | |
| 140 | |
| 141 REPORTER_ASSERT(reporter, list1.isEmpty()); | 131 REPORTER_ASSERT(reporter, list1.isEmpty()); |
| 142 REPORTER_ASSERT(reporter, NULL == iter1.init(list1, Iter::kHead_IterStar
t)); | 132 REPORTER_ASSERT(reporter, NULL == iter1.init(list1, Iter::kHead_IterStar
t)); |
| 143 REPORTER_ASSERT(reporter, NULL == iter1.init(list1, Iter::kTail_IterStar
t)); | 133 REPORTER_ASSERT(reporter, NULL == iter1.init(list1, Iter::kTail_IterStar
t)); |
| 144 // Try popping an empty list | 134 // Try popping an empty list |
| 145 list1.popHead(); | 135 list1.popHead(); |
| 146 list1.popTail(); | 136 list1.popTail(); |
| 147 REPORTER_ASSERT(reporter, list1.isEmpty()); | 137 REPORTER_ASSERT(reporter, list1.isEmpty()); |
| 148 REPORTER_ASSERT(reporter, list1 == list2); | 138 REPORTER_ASSERT(reporter, list1 == list2); |
| 149 | 139 |
| 150 // Create two identical lists, one by appending to head and the other to
the tail. | 140 // Create two identical lists, one by appending to head and the other to
the tail. |
| 151 list1.addToHead(ListElement(1)); | 141 list1.addToHead(ListElement(1)); |
| 152 list2.addToTail(ListElement(1)); | 142 list2.addToTail(ListElement(1)); |
| 153 #if SK_ENABLE_INST_COUNT | |
| 154 SkASSERT(2 == ListElement::InstanceCount()); | |
| 155 #endif | |
| 156 iter1.init(list1, Iter::kHead_IterStart); | 143 iter1.init(list1, Iter::kHead_IterStart); |
| 157 iter2.init(list1, Iter::kTail_IterStart); | 144 iter2.init(list1, Iter::kTail_IterStart); |
| 158 REPORTER_ASSERT(reporter, iter1.get()->fID == iter2.get()->fID); | 145 REPORTER_ASSERT(reporter, iter1.get()->fID == iter2.get()->fID); |
| 159 iter3.init(list2, Iter::kHead_IterStart); | 146 iter3.init(list2, Iter::kHead_IterStart); |
| 160 iter4.init(list2, Iter::kTail_IterStart); | 147 iter4.init(list2, Iter::kTail_IterStart); |
| 161 REPORTER_ASSERT(reporter, iter3.get()->fID == iter1.get()->fID); | 148 REPORTER_ASSERT(reporter, iter3.get()->fID == iter1.get()->fID); |
| 162 REPORTER_ASSERT(reporter, iter4.get()->fID == iter1.get()->fID); | 149 REPORTER_ASSERT(reporter, iter4.get()->fID == iter1.get()->fID); |
| 163 REPORTER_ASSERT(reporter, list1 == list2); | 150 REPORTER_ASSERT(reporter, list1 == list2); |
| 164 | 151 |
| 165 list2.reset(); | 152 list2.reset(); |
| 166 | 153 |
| 167 // use both before/after in-place construction on an empty list | 154 // use both before/after in-place construction on an empty list |
| 168 SkNEW_INSERT_IN_LLIST_BEFORE(&list2, list2.headIter(), ListElement, (1))
; | 155 SkNEW_INSERT_IN_LLIST_BEFORE(&list2, list2.headIter(), ListElement, (1))
; |
| 169 REPORTER_ASSERT(reporter, list2 == list1); | 156 REPORTER_ASSERT(reporter, list2 == list1); |
| 170 list2.reset(); | 157 list2.reset(); |
| 171 | 158 |
| 172 SkNEW_INSERT_IN_LLIST_AFTER(&list2, list2.tailIter(), ListElement, (1)); | 159 SkNEW_INSERT_IN_LLIST_AFTER(&list2, list2.tailIter(), ListElement, (1)); |
| 173 REPORTER_ASSERT(reporter, list2 == list1); | 160 REPORTER_ASSERT(reporter, list2 == list1); |
| 174 | 161 |
| 175 // add an element to the second list, check that iters are still valid | 162 // add an element to the second list, check that iters are still valid |
| 176 iter3.init(list2, Iter::kHead_IterStart); | 163 iter3.init(list2, Iter::kHead_IterStart); |
| 177 iter4.init(list2, Iter::kTail_IterStart); | 164 iter4.init(list2, Iter::kTail_IterStart); |
| 178 list2.addToHead(ListElement(2)); | 165 list2.addToHead(ListElement(2)); |
| 179 | 166 |
| 180 #if SK_ENABLE_INST_COUNT | |
| 181 SkASSERT(3 == ListElement::InstanceCount()); | |
| 182 #endif | |
| 183 | |
| 184 REPORTER_ASSERT(reporter, iter3.get()->fID == iter1.get()->fID); | 167 REPORTER_ASSERT(reporter, iter3.get()->fID == iter1.get()->fID); |
| 185 REPORTER_ASSERT(reporter, iter4.get()->fID == iter1.get()->fID); | 168 REPORTER_ASSERT(reporter, iter4.get()->fID == iter1.get()->fID); |
| 186 REPORTER_ASSERT(reporter, 1 == Iter(list2, Iter::kTail_IterStart).get()-
>fID); | 169 REPORTER_ASSERT(reporter, 1 == Iter(list2, Iter::kTail_IterStart).get()-
>fID); |
| 187 REPORTER_ASSERT(reporter, 2 == Iter(list2, Iter::kHead_IterStart).get()-
>fID); | 170 REPORTER_ASSERT(reporter, 2 == Iter(list2, Iter::kHead_IterStart).get()-
>fID); |
| 188 REPORTER_ASSERT(reporter, list1 != list2); | 171 REPORTER_ASSERT(reporter, list1 != list2); |
| 189 list1.addToHead(ListElement(2)); | 172 list1.addToHead(ListElement(2)); |
| 190 REPORTER_ASSERT(reporter, list1 == list2); | 173 REPORTER_ASSERT(reporter, list1 == list2); |
| 191 #if SK_ENABLE_INST_COUNT | |
| 192 SkASSERT(4 == ListElement::InstanceCount()); | |
| 193 #endif | |
| 194 REPORTER_ASSERT(reporter, !list1.isEmpty()); | 174 REPORTER_ASSERT(reporter, !list1.isEmpty()); |
| 195 | 175 |
| 196 list1.reset(); | 176 list1.reset(); |
| 197 list2.reset(); | 177 list2.reset(); |
| 198 #if SK_ENABLE_INST_COUNT | |
| 199 SkASSERT(0 == ListElement::InstanceCount()); | |
| 200 #endif | |
| 201 REPORTER_ASSERT(reporter, list1.isEmpty() && list2.isEmpty()); | 178 REPORTER_ASSERT(reporter, list1.isEmpty() && list2.isEmpty()); |
| 202 | 179 |
| 203 // randomly perform insertions and deletions on a list and perform tests | 180 // randomly perform insertions and deletions on a list and perform tests |
| 204 int count = 0; | 181 int count = 0; |
| 205 for (int j = 0; j < 100; ++j) { | 182 for (int j = 0; j < 100; ++j) { |
| 206 if (list1.isEmpty() || random.nextBiasedBool(3 * SK_Scalar1 / 4)) { | 183 if (list1.isEmpty() || random.nextBiasedBool(3 * SK_Scalar1 / 4)) { |
| 207 int id = j; | 184 int id = j; |
| 208 // Choose one of three ways to insert a new element: at the head
, at the tail, | 185 // Choose one of three ways to insert a new element: at the head
, at the tail, |
| 209 // before a random element, after a random element | 186 // before a random element, after a random element |
| 210 int numValidMethods = 0 == count ? 2 : 4; | 187 int numValidMethods = 0 == count ? 2 : 4; |
| (...skipping 82 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 293 Iter pn = prev; pn.next(); | 270 Iter pn = prev; pn.next(); |
| 294 Iter np = next; np.prev(); | 271 Iter np = next; np.prev(); |
| 295 // pn should match next unless the target node was the head, in
which case prev | 272 // pn should match next unless the target node was the head, in
which case prev |
| 296 // walked off the list. | 273 // walked off the list. |
| 297 REPORTER_ASSERT(reporter, pn.get() == next.get() || NULL == prev
.get()); | 274 REPORTER_ASSERT(reporter, pn.get() == next.get() || NULL == prev
.get()); |
| 298 // Similarly, np should match prev unless next originally walked
off the tail. | 275 // Similarly, np should match prev unless next originally walked
off the tail. |
| 299 REPORTER_ASSERT(reporter, np.get() == prev.get() || NULL == next
.get()); | 276 REPORTER_ASSERT(reporter, np.get() == prev.get() || NULL == next
.get()); |
| 300 --count; | 277 --count; |
| 301 } | 278 } |
| 302 REPORTER_ASSERT(reporter, count == list1.count()); | 279 REPORTER_ASSERT(reporter, count == list1.count()); |
| 303 #if SK_ENABLE_INST_COUNT | |
| 304 SkASSERT(count == ListElement::InstanceCount()); | |
| 305 #endif | |
| 306 } | 280 } |
| 307 list1.reset(); | 281 list1.reset(); |
| 308 #if SK_ENABLE_INST_COUNT | |
| 309 SkASSERT(0 == ListElement::InstanceCount()); | |
| 310 #endif | |
| 311 } | 282 } |
| 312 } | 283 } |
| 313 | 284 |
| 314 DEF_TEST(LList, reporter) { | 285 DEF_TEST(LList, reporter) { |
| 315 TestTInternalLList(reporter); | 286 TestTInternalLList(reporter); |
| 316 TestTLList(reporter); | 287 TestTLList(reporter); |
| 317 } | 288 } |
| OLD | NEW |