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