blob: 88fe11dd39a81c40a6a9522632496a2499239166 [file] [log] [blame]
bsalomon@google.combbe52902012-12-03 18:01:45 +00001/*
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
13class ListElement {
14public:
15 ListElement(int id) : fID(id) {
16 }
17 bool operator== (const ListElement& other) { return fID == other.fID; }
18
bsalomon@google.com4e230682013-01-15 20:37:04 +000019#if SK_ENABLE_INST_COUNT
bsalomon@google.combbe52902012-12-03 18:01:45 +000020 // Make the instance count available publicly.
21 static int InstanceCount() { return GetInstanceCount(); }
22#endif
23
24 int fID;
25
26private:
27 SK_DECLARE_INST_COUNT_ROOT(ListElement);
28 SK_DECLARE_INTERNAL_LLIST_INTERFACE(ListElement);
29};
30
31SK_DEFINE_INST_COUNT(ListElement);
32
33static 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());
commit-bot@chromium.org515dcd32013-08-28 14:17:03 +000041#ifdef SK_DEBUG
bsalomon@google.comdd3f7a92012-12-03 19:47:41 +000042 list.validate();
bsalomon@google.combbe52902012-12-03 18:01:45 +000043 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
51static 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);
bsalomon@google.comdd3f7a92012-12-03 19:47:41 +000099
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 }
bsalomon@google.combbe52902012-12-03 18:01:45 +0000122}
123
124static void TestTLList(skiatest::Reporter* reporter) {
125 typedef SkTLList<ListElement> ElList;
126 typedef ElList::Iter Iter;
jvanverth@google.comc490f802013-03-04 13:56:38 +0000127 SkMWCRandom random;
bsalomon@google.combbe52902012-12-03 18:01:45 +0000128
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
bsalomon@google.com4e230682013-01-15 20:37:04 +0000138#if SK_ENABLE_INST_COUNT
bsalomon@google.combbe52902012-12-03 18:01:45 +0000139 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));
bsalomon@google.com4e230682013-01-15 20:37:04 +0000154#if SK_ENABLE_INST_COUNT
bsalomon@google.combbe52902012-12-03 18:01:45 +0000155 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);
skia.committer@gmail.come659c2e2012-12-04 02:01:25 +0000165
bsalomon@google.comdd3f7a92012-12-03 19:47:41 +0000166 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();
skia.committer@gmail.come659c2e2012-12-04 02:01:25 +0000172
bsalomon@google.comdd3f7a92012-12-03 19:47:41 +0000173 SkNEW_INSERT_IN_LLIST_AFTER(&list2, list2.tailIter(), ListElement, (1));
174 REPORTER_ASSERT(reporter, list2 == list1);
175
bsalomon@google.combbe52902012-12-03 18:01:45 +0000176 // add an element to the second list, check that iters are still valid
bsalomon@google.comebce0302012-12-04 14:48:57 +0000177 iter3.init(list2, Iter::kHead_IterStart);
178 iter4.init(list2, Iter::kTail_IterStart);
bsalomon@google.combbe52902012-12-03 18:01:45 +0000179 list2.addToHead(ListElement(2));
bsalomon@google.comebce0302012-12-04 14:48:57 +0000180
bsalomon@google.com4e230682013-01-15 20:37:04 +0000181#if SK_ENABLE_INST_COUNT
bsalomon@google.combbe52902012-12-03 18:01:45 +0000182 SkASSERT(3 == ListElement::InstanceCount());
183#endif
bsalomon@google.comdd3f7a92012-12-03 19:47:41 +0000184
bsalomon@google.combbe52902012-12-03 18:01:45 +0000185 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);
bsalomon@google.com4e230682013-01-15 20:37:04 +0000192#if SK_ENABLE_INST_COUNT
bsalomon@google.combbe52902012-12-03 18:01:45 +0000193 SkASSERT(4 == ListElement::InstanceCount());
194#endif
195 REPORTER_ASSERT(reporter, !list1.isEmpty());
196
197 list1.reset();
198 list2.reset();
bsalomon@google.com4e230682013-01-15 20:37:04 +0000199#if SK_ENABLE_INST_COUNT
bsalomon@google.combbe52902012-12-03 18:01:45 +0000200 SkASSERT(0 == ListElement::InstanceCount());
201#endif
202 REPORTER_ASSERT(reporter, list1.isEmpty() && list2.isEmpty());
203
bsalomon@google.comdd3f7a92012-12-03 19:47:41 +0000204 // randomly perform insertions and deletions on a list and perform tests
bsalomon@google.combbe52902012-12-03 18:01:45 +0000205 int count = 0;
206 for (int j = 0; j < 100; ++j) {
207 if (list1.isEmpty() || random.nextBiasedBool(3 * SK_Scalar1 / 4)) {
bsalomon@google.comdd3f7a92012-12-03 19:47:41 +0000208 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 }
skia.committer@gmail.come659c2e2012-12-04 02:01:25 +0000261 }
bsalomon@google.combbe52902012-12-03 18:01:45 +0000262 }
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)();
skia.committer@gmail.come659c2e2012-12-04 02:01:25 +0000269
bsalomon@google.combbe52902012-12-03 18:01:45 +0000270 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());
bsalomon@google.com4e230682013-01-15 20:37:04 +0000304#if SK_ENABLE_INST_COUNT
bsalomon@google.combbe52902012-12-03 18:01:45 +0000305 SkASSERT(count == ListElement::InstanceCount());
306#endif
307 }
308 list1.reset();
bsalomon@google.com4e230682013-01-15 20:37:04 +0000309#if SK_ENABLE_INST_COUNT
bsalomon@google.combbe52902012-12-03 18:01:45 +0000310 SkASSERT(0 == ListElement::InstanceCount());
311#endif
312 }
313}
314
315static void test_llists(skiatest::Reporter* reporter) {
316 TestTInternalLList(reporter);
317 TestTLList(reporter);
318}
319
320#include "TestClassDef.h"
321DEFINE_TESTCLASS("LList", TestLListClass, test_llists)