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