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 "SkRandom.h"
9 #include "SkTInternalLList.h"
10 #include "SkTLList.h"
11 #include "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 }
116
test_tllist(skiatest::Reporter * reporter)117 template <unsigned int N> static void test_tllist(skiatest::Reporter* reporter) {
118 typedef SkTLList<ListElement, N> ElList;
119 typedef typename ElList::Iter Iter;
120 SkRandom random;
121
122 ElList list1;
123 ElList list2;
124 Iter iter1;
125 Iter iter2;
126 Iter iter3;
127 Iter iter4;
128
129 REPORTER_ASSERT(reporter, list1.isEmpty());
130 REPORTER_ASSERT(reporter, nullptr == iter1.init(list1, Iter::kHead_IterStart));
131 REPORTER_ASSERT(reporter, nullptr == iter1.init(list1, Iter::kTail_IterStart));
132 // Try popping an empty list
133 list1.popHead();
134 list1.popTail();
135 REPORTER_ASSERT(reporter, list1.isEmpty());
136 REPORTER_ASSERT(reporter, list1 == list2);
137
138 // Create two identical lists, one by appending to head and the other to the tail.
139 list1.addToHead(ListElement(1));
140 list2.addToTail(ListElement(1));
141 iter1.init(list1, Iter::kHead_IterStart);
142 iter2.init(list1, Iter::kTail_IterStart);
143 REPORTER_ASSERT(reporter, iter1.get()->fID == iter2.get()->fID);
144 iter3.init(list2, Iter::kHead_IterStart);
145 iter4.init(list2, Iter::kTail_IterStart);
146 REPORTER_ASSERT(reporter, iter3.get()->fID == iter1.get()->fID);
147 REPORTER_ASSERT(reporter, iter4.get()->fID == iter1.get()->fID);
148 REPORTER_ASSERT(reporter, list1 == list2);
149
150 list2.reset();
151
152 // use both before/after in-place construction on an empty list
153 list2.addBefore(list2.headIter(), 1);
154 REPORTER_ASSERT(reporter, list2 == list1);
155 list2.reset();
156
157 list2.addAfter(list2.tailIter(), 1);
158 REPORTER_ASSERT(reporter, list2 == list1);
159
160 // add an element to the second list, check that iters are still valid
161 iter3.init(list2, Iter::kHead_IterStart);
162 iter4.init(list2, Iter::kTail_IterStart);
163 list2.addToHead(ListElement(2));
164
165 REPORTER_ASSERT(reporter, iter3.get()->fID == iter1.get()->fID);
166 REPORTER_ASSERT(reporter, iter4.get()->fID == iter1.get()->fID);
167 REPORTER_ASSERT(reporter, 1 == Iter(list2, Iter::kTail_IterStart).get()->fID);
168 REPORTER_ASSERT(reporter, 2 == Iter(list2, Iter::kHead_IterStart).get()->fID);
169 REPORTER_ASSERT(reporter, list1 != list2);
170 list1.addToHead(ListElement(2));
171 REPORTER_ASSERT(reporter, list1 == list2);
172 REPORTER_ASSERT(reporter, !list1.isEmpty());
173
174 list1.reset();
175 list2.reset();
176 REPORTER_ASSERT(reporter, list1.isEmpty() && list2.isEmpty());
177
178 // randomly perform insertions and deletions on a list and perform tests
179 int count = 0;
180 for (int j = 0; j < 100; ++j) {
181 if (list1.isEmpty() || random.nextBiasedBool(3 * SK_Scalar1 / 4)) {
182 int id = j;
183 // Choose one of three ways to insert a new element: at the head, at the tail,
184 // before a random element, after a random element
185 int numValidMethods = 0 == count ? 2 : 4;
186 int insertionMethod = random.nextULessThan(numValidMethods);
187 switch (insertionMethod) {
188 case 0:
189 list1.addToHead(ListElement(id));
190 break;
191 case 1:
192 list1.addToTail(ListElement(id));
193 break;
194 case 2: // fallthru to share code that picks random element.
195 case 3: {
196 int n = random.nextULessThan(list1.count());
197 Iter iter = list1.headIter();
198 // remember the elements before/after the insertion point.
199 while (n--) {
200 iter.next();
201 }
202 Iter prev(iter);
203 Iter next(iter);
204 next.next();
205 prev.prev();
206
207 SkASSERT(iter.get());
208 // insert either before or after the iterator, then check that the
209 // surrounding sequence is correct.
210 if (2 == insertionMethod) {
211 list1.addBefore(iter, id);
212 Iter newItem(iter);
213 newItem.prev();
214 REPORTER_ASSERT(reporter, newItem.get()->fID == id);
215
216 if (next.get()) {
217 REPORTER_ASSERT(reporter, next.prev()->fID == iter.get()->fID);
218 }
219 if (prev.get()) {
220 REPORTER_ASSERT(reporter, prev.next()->fID == id);
221 }
222 } else {
223 list1.addAfter(iter, id);
224 Iter newItem(iter);
225 newItem.next();
226 REPORTER_ASSERT(reporter, newItem.get()->fID == id);
227
228 if (next.get()) {
229 REPORTER_ASSERT(reporter, next.prev()->fID == id);
230 }
231 if (prev.get()) {
232 REPORTER_ASSERT(reporter, prev.next()->fID == iter.get()->fID);
233 }
234 }
235 }
236 }
237 ++count;
238 } else {
239 // walk to a random place either forward or backwards and remove.
240 int n = random.nextULessThan(list1.count());
241 typename Iter::IterStart start;
242 ListElement* (Iter::*incrFunc)();
243
244 if (random.nextBool()) {
245 start = Iter::kHead_IterStart;
246 incrFunc = &Iter::next;
247 } else {
248 start = Iter::kTail_IterStart;
249 incrFunc = &Iter::prev;
250 }
251
252 // find the element
253 Iter iter(list1, start);
254 while (n--) {
255 REPORTER_ASSERT(reporter, iter.get());
256 (iter.*incrFunc)();
257 }
258 REPORTER_ASSERT(reporter, iter.get());
259
260 // remember the prev and next elements from the element to be removed
261 Iter prev = iter;
262 Iter next = iter;
263 prev.prev();
264 next.next();
265 list1.remove(iter.get());
266
267 // make sure the remembered next/prev iters still work
268 Iter pn = prev; pn.next();
269 Iter np = next; np.prev();
270 // pn should match next unless the target node was the head, in which case prev
271 // walked off the list.
272 REPORTER_ASSERT(reporter, pn.get() == next.get() || nullptr == prev.get());
273 // Similarly, np should match prev unless next originally walked off the tail.
274 REPORTER_ASSERT(reporter, np.get() == prev.get() || nullptr == next.get());
275 --count;
276 }
277 REPORTER_ASSERT(reporter, count == list1.count());
278 }
279 }
280
DEF_TEST(LList,reporter)281 DEF_TEST(LList, reporter) {
282 test_tinternallist(reporter);
283 test_tllist<1>(reporter);
284 test_tllist<3>(reporter);
285 test_tllist<8>(reporter);
286 test_tllist<10>(reporter);
287 test_tllist<16>(reporter);
288 }
289