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 "tests/Test.h"
11
12 class ListElement {
13 public:
ListElement(int id)14 ListElement(int id) : fID(id) {
15 }
operator ==(const ListElement & other)16 bool operator== (const ListElement& other) { return fID == other.fID; }
17
18 int fID;
19
20 private:
21
22 SK_DECLARE_INTERNAL_LLIST_INTERFACE(ListElement);
23 };
24
check_list(const SkTInternalLList<ListElement> & list,skiatest::Reporter * reporter,bool empty,int numElements,bool in0,bool in1,bool in2,bool in3,ListElement elements[4])25 static void check_list(const SkTInternalLList<ListElement>& list,
26 skiatest::Reporter* reporter,
27 bool empty,
28 int numElements,
29 bool in0, bool in1, bool in2, bool in3,
30 ListElement elements[4]) {
31
32 REPORTER_ASSERT(reporter, empty == list.isEmpty());
33 #ifdef SK_DEBUG
34 list.validate();
35 REPORTER_ASSERT(reporter, numElements == list.countEntries());
36 REPORTER_ASSERT(reporter, in0 == list.isInList(&elements[0]));
37 REPORTER_ASSERT(reporter, in1 == list.isInList(&elements[1]));
38 REPORTER_ASSERT(reporter, in2 == list.isInList(&elements[2]));
39 REPORTER_ASSERT(reporter, in3 == list.isInList(&elements[3]));
40 #endif
41 }
42
DEF_TEST(InternalLList,reporter)43 DEF_TEST(InternalLList, reporter) {
44 SkTInternalLList<ListElement> list;
45 ListElement elements[4] = {
46 ListElement(0),
47 ListElement(1),
48 ListElement(2),
49 ListElement(3),
50 };
51
52 // list should be empty to start with
53 check_list(list, reporter, true, 0, false, false, false, false, elements);
54
55 list.addToHead(&elements[0]);
56
57 check_list(list, reporter, false, 1, true, false, false, false, elements);
58
59 list.addToHead(&elements[1]);
60 list.addToHead(&elements[2]);
61 list.addToHead(&elements[3]);
62
63 check_list(list, reporter, false, 4, true, true, true, true, elements);
64
65 // test out iterators
66 typedef SkTInternalLList<ListElement>::Iter Iter;
67 Iter iter;
68
69 ListElement* cur = iter.init(list, Iter::kHead_IterStart);
70 for (int i = 0; cur; ++i, cur = iter.next()) {
71 REPORTER_ASSERT(reporter, cur->fID == 3-i);
72 }
73
74 cur = iter.init(list, Iter::kTail_IterStart);
75 for (int i = 0; cur; ++i, cur = iter.prev()) {
76 REPORTER_ASSERT(reporter, cur->fID == i);
77 }
78
79 // remove middle, frontmost then backmost
80 list.remove(&elements[1]);
81 list.remove(&elements[3]);
82 list.remove(&elements[0]);
83
84 check_list(list, reporter, false, 1, false, false, true, false, elements);
85
86 // remove last element
87 list.remove(&elements[2]);
88
89 // list should be empty again
90 check_list(list, reporter, true, 0, false, false, false, false, elements);
91
92 // test out methods that add to the middle of the list.
93 list.addAfter(&elements[1], nullptr);
94 check_list(list, reporter, false, 1, false, true, false, false, elements);
95
96 list.remove(&elements[1]);
97
98 list.addBefore(&elements[1], nullptr);
99 check_list(list, reporter, false, 1, false, true, false, false, elements);
100
101 list.addBefore(&elements[0], &elements[1]);
102 check_list(list, reporter, false, 2, true, true, false, false, elements);
103
104 list.addAfter(&elements[3], &elements[1]);
105 check_list(list, reporter, false, 3, true, true, false, true, elements);
106
107 list.addBefore(&elements[2], &elements[3]);
108 check_list(list, reporter, false, 4, true, true, true, true, elements);
109
110 cur = iter.init(list, Iter::kHead_IterStart);
111 for (int i = 0; cur; ++i, cur = iter.next()) {
112 REPORTER_ASSERT(reporter, cur->fID == i);
113 }
114 while (!list.isEmpty()) {
115 list.remove(list.tail());
116 }
117
118 // test concat.
119 SkTInternalLList<ListElement> listA, listB;
120 listA.concat(std::move(listB));
121 check_list(listA, reporter, true, 0, false, false, false, false, elements);
122 // NOLINTNEXTLINE(bugprone-use-after-move)
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 // NOLINTNEXTLINE(bugprone-use-after-move)
129 check_list(listB, reporter, true, 0, false, false, false, false, elements);
130
131 listB.addToTail(&elements[1]);
132 listA.concat(std::move(listB));
133 check_list(listA, reporter, false, 2, true, true, false, false, elements);
134 // NOLINTNEXTLINE(bugprone-use-after-move)
135 check_list(listB, reporter, true, 0, false, false, false, false, elements);
136
137 listA.concat(std::move(listB));
138 check_list(listA, reporter, false, 2, true, true, false, false, elements);
139 // NOLINTNEXTLINE(bugprone-use-after-move)
140 check_list(listB, reporter, true, 0, false, false, false, false, elements);
141
142 listB.addToTail(&elements[2]);
143 listB.addToTail(&elements[3]);
144 listA.concat(std::move(listB));
145 check_list(listA, reporter, false, 4, true, true, true, true, elements);
146 // NOLINTNEXTLINE(bugprone-use-after-move)
147 check_list(listB, reporter, true, 0, false, false, false, false, elements);
148
149 cur = iter.init(listA, Iter::kHead_IterStart);
150 for (int i = 0; cur; ++i, cur = iter.next()) {
151 REPORTER_ASSERT(reporter, cur->fID == i);
152 }
153 }
154