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>
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>
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 
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 
128 TEST(ScudoListTest, LinkedListCommon) {
129   testListCommon<SLList>();
130   testListCommon<DLList>();
131 }
132 
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, Z);
165   setList(&L2, A, B, C);
166   L1.append_back(&L2);
167   checkList(&L1, X, Y, Z, A, B, C);
168   EXPECT_TRUE(L2.empty());
169 
170   L1.clear();
171   L2.clear();
172   L1.push_back(X);
173   L1.append_back(&L2);
174   EXPECT_EQ(L1.back(), X);
175   EXPECT_EQ(L1.front(), X);
176   EXPECT_EQ(L1.size(), 1U);
177 }
178 
179 TEST(ScudoListTest, DoublyLinkedList) {
180   DLList L;
181   L.clear();
182 
183   L.push_back(X);
184   L.push_back(Y);
185   L.push_back(Z);
186   L.remove(Y);
187   EXPECT_EQ(L.size(), 2U);
188   EXPECT_EQ(L.front(), X);
189   EXPECT_EQ(L.back(), Z);
190   L.checkConsistency();
191   L.remove(Z);
192   EXPECT_EQ(L.size(), 1U);
193   EXPECT_EQ(L.front(), X);
194   EXPECT_EQ(L.back(), X);
195   L.checkConsistency();
196   L.pop_front();
197   EXPECT_TRUE(L.empty());
198 
199   L.push_back(X);
200   L.insert(Y, X);
201   EXPECT_EQ(L.size(), 2U);
202   EXPECT_EQ(L.front(), Y);
203   EXPECT_EQ(L.back(), X);
204   L.checkConsistency();
205   L.remove(Y);
206   EXPECT_EQ(L.size(), 1U);
207   EXPECT_EQ(L.front(), X);
208   EXPECT_EQ(L.back(), X);
209   L.checkConsistency();
210   L.pop_front();
211   EXPECT_TRUE(L.empty());
212 }
213