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 };
15 
16 typedef scudo::IntrusiveList<ListItem> List;
17 
18 static List StaticList;
19 
20 static void setList(List *L, ListItem *X = nullptr, ListItem *Y = nullptr,
21                     ListItem *Z = nullptr) {
22   L->clear();
23   if (X)
24     L->push_back(X);
25   if (Y)
26     L->push_back(Y);
27   if (Z)
28     L->push_back(Z);
29 }
30 
31 static void checkList(List *L, ListItem *I1, ListItem *I2 = nullptr,
32                       ListItem *I3 = nullptr, ListItem *I4 = nullptr,
33                       ListItem *I5 = nullptr, ListItem *I6 = nullptr) {
34   if (I1) {
35     EXPECT_EQ(L->front(), I1);
36     L->pop_front();
37   }
38   if (I2) {
39     EXPECT_EQ(L->front(), I2);
40     L->pop_front();
41   }
42   if (I3) {
43     EXPECT_EQ(L->front(), I3);
44     L->pop_front();
45   }
46   if (I4) {
47     EXPECT_EQ(L->front(), I4);
48     L->pop_front();
49   }
50   if (I5) {
51     EXPECT_EQ(L->front(), I5);
52     L->pop_front();
53   }
54   if (I6) {
55     EXPECT_EQ(L->front(), I6);
56     L->pop_front();
57   }
58   EXPECT_TRUE(L->empty());
59 }
60 
61 TEST(ScudoListTest, IntrusiveList) {
62   ListItem Items[6];
63   EXPECT_EQ(StaticList.size(), 0U);
64 
65   List L;
66   L.clear();
67 
68   ListItem *X = &Items[0];
69   ListItem *Y = &Items[1];
70   ListItem *Z = &Items[2];
71   ListItem *A = &Items[3];
72   ListItem *B = &Items[4];
73   ListItem *C = &Items[5];
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   L.push_back(X);
127   L.push_back(Y);
128   L.push_back(Z);
129   L.extract(X, Y);
130   EXPECT_EQ(L.size(), 2U);
131   EXPECT_EQ(L.front(), X);
132   EXPECT_EQ(L.back(), Z);
133   L.checkConsistency();
134   L.extract(X, Z);
135   EXPECT_EQ(L.size(), 1U);
136   EXPECT_EQ(L.front(), X);
137   EXPECT_EQ(L.back(), X);
138   L.checkConsistency();
139   L.pop_front();
140   EXPECT_TRUE(L.empty());
141 
142   List L1, L2;
143   L1.clear();
144   L2.clear();
145 
146   L1.append_front(&L2);
147   EXPECT_TRUE(L1.empty());
148   EXPECT_TRUE(L2.empty());
149 
150   L1.append_back(&L2);
151   EXPECT_TRUE(L1.empty());
152   EXPECT_TRUE(L2.empty());
153 
154   setList(&L1, X);
155   checkList(&L1, X);
156 
157   setList(&L1, X, Y, Z);
158   setList(&L2, A, B, C);
159   L1.append_back(&L2);
160   checkList(&L1, X, Y, Z, A, B, C);
161   EXPECT_TRUE(L2.empty());
162 
163   setList(&L1, X, Y);
164   setList(&L2);
165   L1.append_front(&L2);
166   checkList(&L1, X, Y);
167   EXPECT_TRUE(L2.empty());
168 }
169 
170 TEST(ScudoListTest, IntrusiveListAppendEmpty) {
171   ListItem I;
172   List L;
173   L.clear();
174   L.push_back(&I);
175   List L2;
176   L2.clear();
177   L.append_back(&L2);
178   EXPECT_EQ(L.back(), &I);
179   EXPECT_EQ(L.front(), &I);
180   EXPECT_EQ(L.size(), 1U);
181   L.append_front(&L2);
182   EXPECT_EQ(L.back(), &I);
183   EXPECT_EQ(L.front(), &I);
184   EXPECT_EQ(L.size(), 1U);
185 }
186