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 |