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 struct ListItem {
14 ListItem *Next;
15 ListItem *Prev;
16 };
17
18 static ListItem Items[6];
19 static ListItem *X = &Items[0];
20 static ListItem *Y = &Items[1];
21 static ListItem *Z = &Items[2];
22 static ListItem *A = &Items[3];
23 static ListItem *B = &Items[4];
24 static ListItem *C = &Items[5];
25
26 typedef scudo::SinglyLinkedList<ListItem> SLList;
27 typedef scudo::DoublyLinkedList<ListItem> DLList;
28
29 template <typename ListT>
setList(ListT * L,ListItem * I1=nullptr,ListItem * I2=nullptr,ListItem * I3=nullptr)30 static void setList(ListT *L, ListItem *I1 = nullptr, ListItem *I2 = nullptr,
31 ListItem *I3 = nullptr) {
32 L->clear();
33 if (I1)
34 L->push_back(I1);
35 if (I2)
36 L->push_back(I2);
37 if (I3)
38 L->push_back(I3);
39 }
40
41 template <typename ListT>
checkList(ListT * L,ListItem * I1,ListItem * I2=nullptr,ListItem * I3=nullptr,ListItem * I4=nullptr,ListItem * I5=nullptr,ListItem * I6=nullptr)42 static void checkList(ListT *L, ListItem *I1, ListItem *I2 = nullptr,
43 ListItem *I3 = nullptr, ListItem *I4 = nullptr,
44 ListItem *I5 = nullptr, ListItem *I6 = nullptr) {
45 if (I1) {
46 EXPECT_EQ(L->front(), I1);
47 L->pop_front();
48 }
49 if (I2) {
50 EXPECT_EQ(L->front(), I2);
51 L->pop_front();
52 }
53 if (I3) {
54 EXPECT_EQ(L->front(), I3);
55 L->pop_front();
56 }
57 if (I4) {
58 EXPECT_EQ(L->front(), I4);
59 L->pop_front();
60 }
61 if (I5) {
62 EXPECT_EQ(L->front(), I5);
63 L->pop_front();
64 }
65 if (I6) {
66 EXPECT_EQ(L->front(), I6);
67 L->pop_front();
68 }
69 EXPECT_TRUE(L->empty());
70 }
71
testListCommon(void)72 template <typename ListT> static void testListCommon(void) {
73 ListT L;
74 L.clear();
75
76 EXPECT_EQ(L.size(), 0U);
77 L.push_back(X);
78 EXPECT_EQ(L.size(), 1U);
79 EXPECT_EQ(L.back(), X);
80 EXPECT_EQ(L.front(), X);
81 L.pop_front();
82 EXPECT_TRUE(L.empty());
83 L.checkConsistency();
84
85 L.push_front(X);
86 EXPECT_EQ(L.size(), 1U);
87 EXPECT_EQ(L.back(), X);
88 EXPECT_EQ(L.front(), X);
89 L.pop_front();
90 EXPECT_TRUE(L.empty());
91 L.checkConsistency();
92
93 L.push_front(X);
94 L.push_front(Y);
95 L.push_front(Z);
96 EXPECT_EQ(L.size(), 3U);
97 EXPECT_EQ(L.front(), Z);
98 EXPECT_EQ(L.back(), X);
99 L.checkConsistency();
100
101 L.pop_front();
102 EXPECT_EQ(L.size(), 2U);
103 EXPECT_EQ(L.front(), Y);
104 EXPECT_EQ(L.back(), X);
105 L.pop_front();
106 L.pop_front();
107 EXPECT_TRUE(L.empty());
108 L.checkConsistency();
109
110 L.push_back(X);
111 L.push_back(Y);
112 L.push_back(Z);
113 EXPECT_EQ(L.size(), 3U);
114 EXPECT_EQ(L.front(), X);
115 EXPECT_EQ(L.back(), Z);
116 L.checkConsistency();
117
118 L.pop_front();
119 EXPECT_EQ(L.size(), 2U);
120 EXPECT_EQ(L.front(), Y);
121 EXPECT_EQ(L.back(), Z);
122 L.pop_front();
123 L.pop_front();
124 EXPECT_TRUE(L.empty());
125 L.checkConsistency();
126 }
127
TEST(ScudoListTest,LinkedListCommon)128 TEST(ScudoListTest, LinkedListCommon) {
129 testListCommon<SLList>();
130 testListCommon<DLList>();
131 }
132
TEST(ScudoListTest,SinglyLinkedList)133 TEST(ScudoListTest, SinglyLinkedList) {
134 SLList L;
135 L.clear();
136
137 L.push_back(X);
138 L.push_back(Y);
139 L.push_back(Z);
140 L.extract(X, Y);
141 EXPECT_EQ(L.size(), 2U);
142 EXPECT_EQ(L.front(), X);
143 EXPECT_EQ(L.back(), Z);
144 L.checkConsistency();
145 L.extract(X, Z);
146 EXPECT_EQ(L.size(), 1U);
147 EXPECT_EQ(L.front(), X);
148 EXPECT_EQ(L.back(), X);
149 L.checkConsistency();
150 L.pop_front();
151 EXPECT_TRUE(L.empty());
152
153 SLList L1, L2;
154 L1.clear();
155 L2.clear();
156
157 L1.append_back(&L2);
158 EXPECT_TRUE(L1.empty());
159 EXPECT_TRUE(L2.empty());
160
161 setList(&L1, X);
162 checkList(&L1, X);
163
164 setList(&L1, X, Y);
165 L1.insert(X, Z);
166 checkList(&L1, X, Z, Y);
167
168 setList(&L1, X, Y, Z);
169 setList(&L2, A, B, C);
170 L1.append_back(&L2);
171 checkList(&L1, X, Y, Z, A, B, C);
172 EXPECT_TRUE(L2.empty());
173
174 L1.clear();
175 L2.clear();
176 L1.push_back(X);
177 L1.append_back(&L2);
178 EXPECT_EQ(L1.back(), X);
179 EXPECT_EQ(L1.front(), X);
180 EXPECT_EQ(L1.size(), 1U);
181 }
182
TEST(ScudoListTest,DoublyLinkedList)183 TEST(ScudoListTest, DoublyLinkedList) {
184 DLList L;
185 L.clear();
186
187 L.push_back(X);
188 L.push_back(Y);
189 L.push_back(Z);
190 L.remove(Y);
191 EXPECT_EQ(L.size(), 2U);
192 EXPECT_EQ(L.front(), X);
193 EXPECT_EQ(L.back(), Z);
194 L.checkConsistency();
195 L.remove(Z);
196 EXPECT_EQ(L.size(), 1U);
197 EXPECT_EQ(L.front(), X);
198 EXPECT_EQ(L.back(), X);
199 L.checkConsistency();
200 L.pop_front();
201 EXPECT_TRUE(L.empty());
202
203 L.push_back(X);
204 L.insert(Y, X);
205 EXPECT_EQ(L.size(), 2U);
206 EXPECT_EQ(L.front(), Y);
207 EXPECT_EQ(L.back(), X);
208 L.checkConsistency();
209 L.remove(Y);
210 EXPECT_EQ(L.size(), 1U);
211 EXPECT_EQ(L.front(), X);
212 EXPECT_EQ(L.back(), X);
213 L.checkConsistency();
214 L.pop_front();
215 EXPECT_TRUE(L.empty());
216 }
217