1 | //===-- list_test.cpp -------------------------------------------*- C++ -*-===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | |
9 | #include "tests/scudo_unit_test.h" |
10 | |
11 | #include "list.h" |
12 | |
13 | #include <array> |
14 | |
15 | struct ListItemLinkedWithPtr { |
16 | ListItemLinkedWithPtr *Next; |
17 | ListItemLinkedWithPtr *Prev; |
18 | }; |
19 | |
20 | struct ListItemLinkedWithIndex { |
21 | scudo::uptr Next; |
22 | scudo::uptr Prev; |
23 | static constexpr scudo::uptr EndOfListVal = 1ULL << 30; |
24 | }; |
25 | |
26 | template <typename ListT, typename ListItemTy> |
27 | static void setList(ListT *L, ListItemTy *I1 = nullptr, |
28 | ListItemTy *I2 = nullptr, ListItemTy *I3 = nullptr) { |
29 | L->clear(); |
30 | if (I1) |
31 | L->push_back(I1); |
32 | if (I2) |
33 | L->push_back(I2); |
34 | if (I3) |
35 | L->push_back(I3); |
36 | } |
37 | |
38 | template <typename ListT, typename ListItemTy> |
39 | static void checkList(ListT *L, ListItemTy *I1, ListItemTy *I2 = nullptr, |
40 | ListItemTy *I3 = nullptr, ListItemTy *I4 = nullptr, |
41 | ListItemTy *I5 = nullptr, ListItemTy *I6 = nullptr) { |
42 | if (I1) { |
43 | EXPECT_EQ(L->front(), I1); |
44 | L->pop_front(); |
45 | } |
46 | if (I2) { |
47 | EXPECT_EQ(L->front(), I2); |
48 | L->pop_front(); |
49 | } |
50 | if (I3) { |
51 | EXPECT_EQ(L->front(), I3); |
52 | L->pop_front(); |
53 | } |
54 | if (I4) { |
55 | EXPECT_EQ(L->front(), I4); |
56 | L->pop_front(); |
57 | } |
58 | if (I5) { |
59 | EXPECT_EQ(L->front(), I5); |
60 | L->pop_front(); |
61 | } |
62 | if (I6) { |
63 | EXPECT_EQ(L->front(), I6); |
64 | L->pop_front(); |
65 | } |
66 | EXPECT_TRUE(L->empty()); |
67 | } |
68 | |
69 | template <template <typename> class ListTy, typename ListItemTy> |
70 | static void testListCommon(void) { |
71 | ListItemTy Items[3]; |
72 | ListItemTy *X = &Items[0]; |
73 | ListItemTy *Y = &Items[1]; |
74 | ListItemTy *Z = &Items[2]; |
75 | |
76 | ListTy<ListItemTy> L; |
77 | L.clear(); |
78 | L.init(Items, sizeof(Items)); |
79 | |
80 | EXPECT_EQ(L.size(), 0U); |
81 | L.push_back(X); |
82 | EXPECT_EQ(L.size(), 1U); |
83 | EXPECT_EQ(L.back(), X); |
84 | EXPECT_EQ(L.front(), X); |
85 | L.pop_front(); |
86 | EXPECT_TRUE(L.empty()); |
87 | L.checkConsistency(); |
88 | |
89 | L.push_front(X); |
90 | EXPECT_EQ(L.size(), 1U); |
91 | EXPECT_EQ(L.back(), X); |
92 | EXPECT_EQ(L.front(), X); |
93 | L.pop_front(); |
94 | EXPECT_TRUE(L.empty()); |
95 | L.checkConsistency(); |
96 | |
97 | L.push_front(X); |
98 | L.push_front(Y); |
99 | L.push_front(Z); |
100 | EXPECT_EQ(L.size(), 3U); |
101 | EXPECT_EQ(L.front(), Z); |
102 | EXPECT_EQ(L.back(), X); |
103 | L.checkConsistency(); |
104 | |
105 | L.pop_front(); |
106 | EXPECT_EQ(L.size(), 2U); |
107 | EXPECT_EQ(L.front(), Y); |
108 | EXPECT_EQ(L.back(), X); |
109 | L.pop_front(); |
110 | L.pop_front(); |
111 | EXPECT_TRUE(L.empty()); |
112 | L.checkConsistency(); |
113 | |
114 | L.push_back(X); |
115 | L.push_back(Y); |
116 | L.push_back(Z); |
117 | EXPECT_EQ(L.size(), 3U); |
118 | EXPECT_EQ(L.front(), X); |
119 | EXPECT_EQ(L.back(), Z); |
120 | L.checkConsistency(); |
121 | |
122 | L.pop_front(); |
123 | EXPECT_EQ(L.size(), 2U); |
124 | EXPECT_EQ(L.front(), Y); |
125 | EXPECT_EQ(L.back(), Z); |
126 | L.pop_front(); |
127 | L.pop_front(); |
128 | EXPECT_TRUE(L.empty()); |
129 | L.checkConsistency(); |
130 | |
131 | L.push_back(X); |
132 | L.push_back(Y); |
133 | L.push_back(Z); |
134 | |
135 | // Verify the iterator |
136 | std::array<ListItemTy *, 3> visitOrder{X, Y, Z}; |
137 | auto Iter = visitOrder.begin(); |
138 | for (const auto &Item : L) { |
139 | EXPECT_EQ(&Item, *Iter); |
140 | ++Iter; |
141 | } |
142 | } |
143 | |
144 | TEST(ScudoListTest, LinkedListCommon) { |
145 | testListCommon<scudo::SinglyLinkedList, ListItemLinkedWithPtr>(); |
146 | testListCommon<scudo::SinglyLinkedList, ListItemLinkedWithIndex>(); |
147 | testListCommon<scudo::DoublyLinkedList, ListItemLinkedWithPtr>(); |
148 | testListCommon<scudo::DoublyLinkedList, ListItemLinkedWithIndex>(); |
149 | } |
150 | |
151 | template <template <typename> class ListTy, typename ListItemTy> |
152 | static void testSinglyLinkedList() { |
153 | ListItemTy Items[6]; |
154 | ListItemTy *X = &Items[0]; |
155 | ListItemTy *Y = &Items[1]; |
156 | ListItemTy *Z = &Items[2]; |
157 | ListItemTy *A = &Items[3]; |
158 | ListItemTy *B = &Items[4]; |
159 | ListItemTy *C = &Items[5]; |
160 | |
161 | ListTy<ListItemTy> L; |
162 | L.clear(); |
163 | L.init(Items, sizeof(Items)); |
164 | |
165 | L.push_back(X); |
166 | L.push_back(Y); |
167 | L.push_back(Z); |
168 | L.extract(X, Y); |
169 | EXPECT_EQ(L.size(), 2U); |
170 | EXPECT_EQ(L.front(), X); |
171 | EXPECT_EQ(L.back(), Z); |
172 | L.checkConsistency(); |
173 | L.extract(X, Z); |
174 | EXPECT_EQ(L.size(), 1U); |
175 | EXPECT_EQ(L.front(), X); |
176 | EXPECT_EQ(L.back(), X); |
177 | L.checkConsistency(); |
178 | L.pop_front(); |
179 | EXPECT_TRUE(L.empty()); |
180 | |
181 | ListTy<ListItemTy> L1, L2; |
182 | L1.clear(); |
183 | L2.clear(); |
184 | L1.init(Items, sizeof(Items)); |
185 | L2.init(Items, sizeof(Items)); |
186 | |
187 | L1.append_back(&L2); |
188 | EXPECT_TRUE(L1.empty()); |
189 | EXPECT_TRUE(L2.empty()); |
190 | |
191 | setList(&L1, X); |
192 | checkList(&L1, X); |
193 | |
194 | setList(&L1, X, Y); |
195 | L1.insert(X, Z); |
196 | checkList(&L1, X, Z, Y); |
197 | |
198 | setList(&L1, X, Y, Z); |
199 | setList(&L2, A, B, C); |
200 | L1.append_back(&L2); |
201 | checkList(&L1, X, Y, Z, A, B, C); |
202 | EXPECT_TRUE(L2.empty()); |
203 | |
204 | L1.clear(); |
205 | L2.clear(); |
206 | L1.push_back(X); |
207 | L1.append_back(&L2); |
208 | EXPECT_EQ(L1.back(), X); |
209 | EXPECT_EQ(L1.front(), X); |
210 | EXPECT_EQ(L1.size(), 1U); |
211 | } |
212 | |
213 | TEST(ScudoListTest, SinglyLinkedList) { |
214 | testSinglyLinkedList<scudo::SinglyLinkedList, ListItemLinkedWithPtr>(); |
215 | testSinglyLinkedList<scudo::SinglyLinkedList, ListItemLinkedWithIndex>(); |
216 | } |
217 | |
218 | template <template <typename> class ListTy, typename ListItemTy> |
219 | static void testDoublyLinkedList() { |
220 | ListItemTy Items[3]; |
221 | ListItemTy *X = &Items[0]; |
222 | ListItemTy *Y = &Items[1]; |
223 | ListItemTy *Z = &Items[2]; |
224 | |
225 | ListTy<ListItemTy> L; |
226 | L.clear(); |
227 | L.init(Items, sizeof(Items)); |
228 | |
229 | L.push_back(X); |
230 | L.push_back(Y); |
231 | L.push_back(Z); |
232 | L.remove(Y); |
233 | EXPECT_EQ(L.size(), 2U); |
234 | EXPECT_EQ(L.front(), X); |
235 | EXPECT_EQ(L.back(), Z); |
236 | L.checkConsistency(); |
237 | L.remove(Z); |
238 | EXPECT_EQ(L.size(), 1U); |
239 | EXPECT_EQ(L.front(), X); |
240 | EXPECT_EQ(L.back(), X); |
241 | L.checkConsistency(); |
242 | L.pop_front(); |
243 | EXPECT_TRUE(L.empty()); |
244 | |
245 | L.push_back(X); |
246 | L.insert(Y, X); |
247 | EXPECT_EQ(L.size(), 2U); |
248 | EXPECT_EQ(L.front(), Y); |
249 | EXPECT_EQ(L.back(), X); |
250 | L.checkConsistency(); |
251 | L.remove(Y); |
252 | EXPECT_EQ(L.size(), 1U); |
253 | EXPECT_EQ(L.front(), X); |
254 | EXPECT_EQ(L.back(), X); |
255 | L.checkConsistency(); |
256 | L.pop_front(); |
257 | EXPECT_TRUE(L.empty()); |
258 | } |
259 | |
260 | TEST(ScudoListTest, DoublyLinkedList) { |
261 | testDoublyLinkedList<scudo::DoublyLinkedList, ListItemLinkedWithPtr>(); |
262 | testDoublyLinkedList<scudo::DoublyLinkedList, ListItemLinkedWithIndex>(); |
263 | } |
264 | |