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(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
183TEST(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