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