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