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
15struct ListItemLinkedWithPtr {
16 ListItemLinkedWithPtr *Next;
17 ListItemLinkedWithPtr *Prev;
18};
19
20struct ListItemLinkedWithIndex {
21 scudo::uptr Next;
22 scudo::uptr Prev;
23 static constexpr scudo::uptr EndOfListVal = 1ULL << 30;
24};
25
26template <typename ListT, typename ListItemTy>
27static 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
38template <typename ListT, typename ListItemTy>
39static 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
69template <template <typename> class ListTy, typename ListItemTy>
70static 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
144TEST(ScudoListTest, LinkedListCommon) {
145 testListCommon<scudo::SinglyLinkedList, ListItemLinkedWithPtr>();
146 testListCommon<scudo::SinglyLinkedList, ListItemLinkedWithIndex>();
147 testListCommon<scudo::DoublyLinkedList, ListItemLinkedWithPtr>();
148 testListCommon<scudo::DoublyLinkedList, ListItemLinkedWithIndex>();
149}
150
151template <template <typename> class ListTy, typename ListItemTy>
152static 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
213TEST(ScudoListTest, SinglyLinkedList) {
214 testSinglyLinkedList<scudo::SinglyLinkedList, ListItemLinkedWithPtr>();
215 testSinglyLinkedList<scudo::SinglyLinkedList, ListItemLinkedWithIndex>();
216}
217
218template <template <typename> class ListTy, typename ListItemTy>
219static 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
260TEST(ScudoListTest, DoublyLinkedList) {
261 testDoublyLinkedList<scudo::DoublyLinkedList, ListItemLinkedWithPtr>();
262 testDoublyLinkedList<scudo::DoublyLinkedList, ListItemLinkedWithIndex>();
263}
264

Provided by KDAB

Privacy Policy
Improve your Profiling and Debugging skills
Find out more

source code of compiler-rt/lib/scudo/standalone/tests/list_test.cpp