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
13struct ListItem {
14 ListItem *Next;
15 ListItem *Prev;
16};
17
18static ListItem Items[6];
19static ListItem *X = &Items[0];
20static ListItem *Y = &Items[1];
21static ListItem *Z = &Items[2];
22static ListItem *A = &Items[3];
23static ListItem *B = &Items[4];
24static ListItem *C = &Items[5];
25
26typedef scudo::SinglyLinkedList<ListItem> SLList;
27typedef scudo::DoublyLinkedList<ListItem> DLList;
28
29template <typename ListT>
30static 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
41template <typename ListT>
42static 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
72template <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
128TEST(ScudoListTest, LinkedListCommon) {
129 testListCommon<SLList>();
130 testListCommon<DLList>();
131}
132
133TEST(ScudoListTest, SinglyLinkedList) {
134 SLList L;
135 L.clear();
136
137 L.push_back(X);
138 L.push_back(X: Y);
139 L.push_back(X: Z);
140 L.extract(Prev: X, 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(Prev: X, 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(L: &L2);
158 EXPECT_TRUE(L1.empty());
159 EXPECT_TRUE(L2.empty());
160
161 setList(L: &L1, I1: X);
162 checkList(L: &L1, I1: X);
163
164 setList(L: &L1, I1: X, I2: Y);
165 L1.insert(Prev: X, X: Z);
166 checkList(L: &L1, I1: X, I2: Z, I3: Y);
167
168 setList(L: &L1, I1: X, I2: Y, I3: Z);
169 setList(L: &L2, I1: A, I2: B, I3: C);
170 L1.append_back(L: &L2);
171 checkList(L: &L1, I1: X, I2: Y, I3: Z, I4: A, I5: B, I6: C);
172 EXPECT_TRUE(L2.empty());
173
174 L1.clear();
175 L2.clear();
176 L1.push_back(X);
177 L1.append_back(L: &L2);
178 EXPECT_EQ(L1.back(), X);
179 EXPECT_EQ(L1.front(), X);
180 EXPECT_EQ(L1.size(), 1U);
181}
182
183TEST(ScudoListTest, DoublyLinkedList) {
184 DLList L;
185 L.clear();
186
187 L.push_back(X);
188 L.push_back(X: Y);
189 L.push_back(X: Z);
190 L.remove(X: 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(X: 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(X: Y, 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(X: 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

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