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