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
8 #include "SkInstCnt.h"
9 #include "SkRandom.h"
10 #include "SkTInternalLList.h"
11 #include "SkTLList.h"
12 #include "Test.h"
13
14 class ListElement {
15 public:
ListElement(int id)16 ListElement(int id) : fID(id) {
17 }
operator ==(const ListElement & other)18 bool operator== (const ListElement& other) { return fID == other.fID; }
19
20 #if SK_ENABLE_INST_COUNT
21 // Make the instance count available publicly.
InstanceCount()22 static int InstanceCount() { return GetInstanceCount(); }
23 #endif
24
25 int fID;
26
27 private:
28 SK_DECLARE_INST_COUNT(ListElement);
29 SK_DECLARE_INTERNAL_LLIST_INTERFACE(ListElement);
30 };
31
check_list(const SkTInternalLList<ListElement> & list,skiatest::Reporter * reporter,bool empty,int numElements,bool in0,bool in1,bool in2,bool in3,ListElement elements[4])32 static void check_list(const SkTInternalLList<ListElement>& list,
33 skiatest::Reporter* reporter,
34 bool empty,
35 int numElements,
36 bool in0, bool in1, bool in2, bool in3,
37 ListElement elements[4]) {
38
39 REPORTER_ASSERT(reporter, empty == list.isEmpty());
40 #ifdef SK_DEBUG
41 list.validate();
42 REPORTER_ASSERT(reporter, numElements == list.countEntries());
43 REPORTER_ASSERT(reporter, in0 == list.isInList(&elements[0]));
44 REPORTER_ASSERT(reporter, in1 == list.isInList(&elements[1]));
45 REPORTER_ASSERT(reporter, in2 == list.isInList(&elements[2]));
46 REPORTER_ASSERT(reporter, in3 == list.isInList(&elements[3]));
47 #endif
48 }
49
TestTInternalLList(skiatest::Reporter * reporter)50 static void TestTInternalLList(skiatest::Reporter* reporter) {
51 SkTInternalLList<ListElement> list;
52 ListElement elements[4] = {
53 ListElement(0),
54 ListElement(1),
55 ListElement(2),
56 ListElement(3),
57 };
58
59 // list should be empty to start with
60 check_list(list, reporter, true, 0, false, false, false, false, elements);
61
62 list.addToHead(&elements[0]);
63
64 check_list(list, reporter, false, 1, true, false, false, false, elements);
65
66 list.addToHead(&elements[1]);
67 list.addToHead(&elements[2]);
68 list.addToHead(&elements[3]);
69
70 check_list(list, reporter, false, 4, true, true, true, true, elements);
71
72 // test out iterators
73 typedef SkTInternalLList<ListElement>::Iter Iter;
74 Iter iter;
75
76 ListElement* cur = iter.init(list, Iter::kHead_IterStart);
77 for (int i = 0; cur; ++i, cur = iter.next()) {
78 REPORTER_ASSERT(reporter, cur->fID == 3-i);
79 }
80
81 cur = iter.init(list, Iter::kTail_IterStart);
82 for (int i = 0; cur; ++i, cur = iter.prev()) {
83 REPORTER_ASSERT(reporter, cur->fID == i);
84 }
85
86 // remove middle, frontmost then backmost
87 list.remove(&elements[1]);
88 list.remove(&elements[3]);
89 list.remove(&elements[0]);
90
91 check_list(list, reporter, false, 1, false, false, true, false, elements);
92
93 // remove last element
94 list.remove(&elements[2]);
95
96 // list should be empty again
97 check_list(list, reporter, true, 0, false, false, false, false, elements);
98
99 // test out methods that add to the middle of the list.
100 list.addAfter(&elements[1], NULL);
101 check_list(list, reporter, false, 1, false, true, false, false, elements);
102
103 list.remove(&elements[1]);
104
105 list.addBefore(&elements[1], NULL);
106 check_list(list, reporter, false, 1, false, true, false, false, elements);
107
108 list.addBefore(&elements[0], &elements[1]);
109 check_list(list, reporter, false, 2, true, true, false, false, elements);
110
111 list.addAfter(&elements[3], &elements[1]);
112 check_list(list, reporter, false, 3, true, true, false, true, elements);
113
114 list.addBefore(&elements[2], &elements[3]);
115 check_list(list, reporter, false, 4, true, true, true, true, elements);
116
117 cur = iter.init(list, Iter::kHead_IterStart);
118 for (int i = 0; cur; ++i, cur = iter.next()) {
119 REPORTER_ASSERT(reporter, cur->fID == i);
120 }
121 }
122
TestTLList(skiatest::Reporter * reporter)123 static void TestTLList(skiatest::Reporter* reporter) {
124 typedef SkTLList<ListElement> ElList;
125 typedef ElList::Iter Iter;
126 SkRandom random;
127
128 for (int i = 1; i <= 16; i *= 2) {
129
130 ElList list1(i);
131 ElList list2(i);
132 Iter iter1;
133 Iter iter2;
134 Iter iter3;
135 Iter iter4;
136
137 #if SK_ENABLE_INST_COUNT
138 SkASSERT(0 == ListElement::InstanceCount());
139 #endif
140
141 REPORTER_ASSERT(reporter, list1.isEmpty());
142 REPORTER_ASSERT(reporter, NULL == iter1.init(list1, Iter::kHead_IterStart));
143 REPORTER_ASSERT(reporter, NULL == iter1.init(list1, Iter::kTail_IterStart));
144 // Try popping an empty list
145 list1.popHead();
146 list1.popTail();
147 REPORTER_ASSERT(reporter, list1.isEmpty());
148 REPORTER_ASSERT(reporter, list1 == list2);
149
150 // Create two identical lists, one by appending to head and the other to the tail.
151 list1.addToHead(ListElement(1));
152 list2.addToTail(ListElement(1));
153 #if SK_ENABLE_INST_COUNT
154 SkASSERT(2 == ListElement::InstanceCount());
155 #endif
156 iter1.init(list1, Iter::kHead_IterStart);
157 iter2.init(list1, Iter::kTail_IterStart);
158 REPORTER_ASSERT(reporter, iter1.get()->fID == iter2.get()->fID);
159 iter3.init(list2, Iter::kHead_IterStart);
160 iter4.init(list2, Iter::kTail_IterStart);
161 REPORTER_ASSERT(reporter, iter3.get()->fID == iter1.get()->fID);
162 REPORTER_ASSERT(reporter, iter4.get()->fID == iter1.get()->fID);
163 REPORTER_ASSERT(reporter, list1 == list2);
164
165 list2.reset();
166
167 // use both before/after in-place construction on an empty list
168 SkNEW_INSERT_IN_LLIST_BEFORE(&list2, list2.headIter(), ListElement, (1));
169 REPORTER_ASSERT(reporter, list2 == list1);
170 list2.reset();
171
172 SkNEW_INSERT_IN_LLIST_AFTER(&list2, list2.tailIter(), ListElement, (1));
173 REPORTER_ASSERT(reporter, list2 == list1);
174
175 // add an element to the second list, check that iters are still valid
176 iter3.init(list2, Iter::kHead_IterStart);
177 iter4.init(list2, Iter::kTail_IterStart);
178 list2.addToHead(ListElement(2));
179
180 #if SK_ENABLE_INST_COUNT
181 SkASSERT(3 == ListElement::InstanceCount());
182 #endif
183
184 REPORTER_ASSERT(reporter, iter3.get()->fID == iter1.get()->fID);
185 REPORTER_ASSERT(reporter, iter4.get()->fID == iter1.get()->fID);
186 REPORTER_ASSERT(reporter, 1 == Iter(list2, Iter::kTail_IterStart).get()->fID);
187 REPORTER_ASSERT(reporter, 2 == Iter(list2, Iter::kHead_IterStart).get()->fID);
188 REPORTER_ASSERT(reporter, list1 != list2);
189 list1.addToHead(ListElement(2));
190 REPORTER_ASSERT(reporter, list1 == list2);
191 #if SK_ENABLE_INST_COUNT
192 SkASSERT(4 == ListElement::InstanceCount());
193 #endif
194 REPORTER_ASSERT(reporter, !list1.isEmpty());
195
196 list1.reset();
197 list2.reset();
198 #if SK_ENABLE_INST_COUNT
199 SkASSERT(0 == ListElement::InstanceCount());
200 #endif
201 REPORTER_ASSERT(reporter, list1.isEmpty() && list2.isEmpty());
202
203 // randomly perform insertions and deletions on a list and perform tests
204 int count = 0;
205 for (int j = 0; j < 100; ++j) {
206 if (list1.isEmpty() || random.nextBiasedBool(3 * SK_Scalar1 / 4)) {
207 int id = j;
208 // 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
210 int numValidMethods = 0 == count ? 2 : 4;
211 int insertionMethod = random.nextULessThan(numValidMethods);
212 switch (insertionMethod) {
213 case 0:
214 list1.addToHead(ListElement(id));
215 break;
216 case 1:
217 list1.addToTail(ListElement(id));
218 break;
219 case 2: // fallthru to share code that picks random element.
220 case 3: {
221 int n = random.nextULessThan(list1.count());
222 Iter iter = list1.headIter();
223 // remember the elements before/after the insertion point.
224 while (n--) {
225 iter.next();
226 }
227 Iter prev(iter);
228 Iter next(iter);
229 next.next();
230 prev.prev();
231
232 SkASSERT(iter.get());
233 // insert either before or after the iterator, then check that the
234 // surrounding sequence is correct.
235 if (2 == insertionMethod) {
236 SkNEW_INSERT_IN_LLIST_BEFORE(&list1, iter, ListElement, (id));
237 Iter newItem(iter);
238 newItem.prev();
239 REPORTER_ASSERT(reporter, newItem.get()->fID == id);
240
241 if (next.get()) {
242 REPORTER_ASSERT(reporter, next.prev()->fID == iter.get()->fID);
243 }
244 if (prev.get()) {
245 REPORTER_ASSERT(reporter, prev.next()->fID == id);
246 }
247 } else {
248 SkNEW_INSERT_IN_LLIST_AFTER(&list1, iter, ListElement, (id));
249 Iter newItem(iter);
250 newItem.next();
251 REPORTER_ASSERT(reporter, newItem.get()->fID == id);
252
253 if (next.get()) {
254 REPORTER_ASSERT(reporter, next.prev()->fID == id);
255 }
256 if (prev.get()) {
257 REPORTER_ASSERT(reporter, prev.next()->fID == iter.get()->fID);
258 }
259 }
260 }
261 }
262 ++count;
263 } else {
264 // walk to a random place either forward or backwards and remove.
265 int n = random.nextULessThan(list1.count());
266 Iter::IterStart start;
267 ListElement* (Iter::*incrFunc)();
268
269 if (random.nextBool()) {
270 start = Iter::kHead_IterStart;
271 incrFunc = &Iter::next;
272 } else {
273 start = Iter::kTail_IterStart;
274 incrFunc = &Iter::prev;
275 }
276
277 // find the element
278 Iter iter(list1, start);
279 while (n--) {
280 REPORTER_ASSERT(reporter, iter.get());
281 (iter.*incrFunc)();
282 }
283 REPORTER_ASSERT(reporter, iter.get());
284
285 // remember the prev and next elements from the element to be removed
286 Iter prev = iter;
287 Iter next = iter;
288 prev.prev();
289 next.next();
290 list1.remove(iter.get());
291
292 // make sure the remembered next/prev iters still work
293 Iter pn = prev; pn.next();
294 Iter np = next; np.prev();
295 // pn should match next unless the target node was the head, in which case prev
296 // walked off the list.
297 REPORTER_ASSERT(reporter, pn.get() == next.get() || NULL == prev.get());
298 // Similarly, np should match prev unless next originally walked off the tail.
299 REPORTER_ASSERT(reporter, np.get() == prev.get() || NULL == next.get());
300 --count;
301 }
302 REPORTER_ASSERT(reporter, count == list1.count());
303 #if SK_ENABLE_INST_COUNT
304 SkASSERT(count == ListElement::InstanceCount());
305 #endif
306 }
307 list1.reset();
308 #if SK_ENABLE_INST_COUNT
309 SkASSERT(0 == ListElement::InstanceCount());
310 #endif
311 }
312 }
313
DEF_TEST(LList,reporter)314 DEF_TEST(LList, reporter) {
315 TestTInternalLList(reporter);
316 TestTLList(reporter);
317 }
318