1 //===-- sanitizer_list_test.cpp -------------------------------------------===//
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 // This file is a part of ThreadSanitizer/AddressSanitizer runtime.
10 //
11 //===----------------------------------------------------------------------===//
12 #include "sanitizer_common/sanitizer_list.h"
13 #include "gtest/gtest.h"
14
15 namespace __sanitizer {
16
17 struct ListItem {
18 ListItem *next;
19 };
20
21 typedef IntrusiveList<ListItem> List;
22
23 static List static_list;
24
SetList(List * l,ListItem * x=0,ListItem * y=0,ListItem * z=0)25 static void SetList(List *l, ListItem *x = 0,
26 ListItem *y = 0, ListItem *z = 0) {
27 l->clear();
28 if (x) l->push_back(x);
29 if (y) l->push_back(y);
30 if (z) l->push_back(z);
31 }
32
CheckList(List * l,ListItem * i1,ListItem * i2=0,ListItem * i3=0,ListItem * i4=0,ListItem * i5=0,ListItem * i6=0)33 static void CheckList(List *l, ListItem *i1, ListItem *i2 = 0, ListItem *i3 = 0,
34 ListItem *i4 = 0, ListItem *i5 = 0, ListItem *i6 = 0) {
35 if (i1) {
36 CHECK_EQ(l->front(), i1);
37 l->pop_front();
38 }
39 if (i2) {
40 CHECK_EQ(l->front(), i2);
41 l->pop_front();
42 }
43 if (i3) {
44 CHECK_EQ(l->front(), i3);
45 l->pop_front();
46 }
47 if (i4) {
48 CHECK_EQ(l->front(), i4);
49 l->pop_front();
50 }
51 if (i5) {
52 CHECK_EQ(l->front(), i5);
53 l->pop_front();
54 }
55 if (i6) {
56 CHECK_EQ(l->front(), i6);
57 l->pop_front();
58 }
59 CHECK(l->empty());
60 }
61
TEST(SanitizerCommon,IntrusiveList)62 TEST(SanitizerCommon, IntrusiveList) {
63 ListItem items[6];
64 CHECK_EQ(static_list.size(), 0);
65
66 List l;
67 l.clear();
68
69 ListItem *x = &items[0];
70 ListItem *y = &items[1];
71 ListItem *z = &items[2];
72 ListItem *a = &items[3];
73 ListItem *b = &items[4];
74 ListItem *c = &items[5];
75
76 CHECK_EQ(l.size(), 0);
77 l.push_back(x);
78 CHECK_EQ(l.size(), 1);
79 CHECK_EQ(l.back(), x);
80 CHECK_EQ(l.front(), x);
81 l.pop_front();
82 CHECK(l.empty());
83 l.CheckConsistency();
84
85 l.push_front(x);
86 CHECK_EQ(l.size(), 1);
87 CHECK_EQ(l.back(), x);
88 CHECK_EQ(l.front(), x);
89 l.pop_front();
90 CHECK(l.empty());
91 l.CheckConsistency();
92
93 l.push_front(x);
94 l.push_front(y);
95 l.push_front(z);
96 CHECK_EQ(l.size(), 3);
97 CHECK_EQ(l.front(), z);
98 CHECK_EQ(l.back(), x);
99 l.CheckConsistency();
100
101 l.pop_front();
102 CHECK_EQ(l.size(), 2);
103 CHECK_EQ(l.front(), y);
104 CHECK_EQ(l.back(), x);
105 l.pop_front();
106 l.pop_front();
107 CHECK(l.empty());
108 l.CheckConsistency();
109
110 l.push_back(x);
111 l.push_back(y);
112 l.push_back(z);
113 CHECK_EQ(l.size(), 3);
114 CHECK_EQ(l.front(), x);
115 CHECK_EQ(l.back(), z);
116 l.CheckConsistency();
117
118 l.pop_front();
119 CHECK_EQ(l.size(), 2);
120 CHECK_EQ(l.front(), y);
121 CHECK_EQ(l.back(), z);
122 l.pop_front();
123 l.pop_front();
124 CHECK(l.empty());
125 l.CheckConsistency();
126
127 l.push_back(x);
128 l.push_back(y);
129 l.push_back(z);
130 l.extract(x, y);
131 CHECK_EQ(l.size(), 2);
132 CHECK_EQ(l.front(), x);
133 CHECK_EQ(l.back(), z);
134 l.CheckConsistency();
135 l.extract(x, z);
136 CHECK_EQ(l.size(), 1);
137 CHECK_EQ(l.front(), x);
138 CHECK_EQ(l.back(), x);
139 l.CheckConsistency();
140 l.pop_front();
141 CHECK(l.empty());
142
143 List l1, l2;
144 l1.clear();
145 l2.clear();
146
147 l1.append_front(&l2);
148 CHECK(l1.empty());
149 CHECK(l2.empty());
150
151 l1.append_back(&l2);
152 CHECK(l1.empty());
153 CHECK(l2.empty());
154
155 SetList(&l1, x);
156 CheckList(&l1, x);
157
158 SetList(&l1, x, y, z);
159 SetList(&l2, a, b, c);
160 l1.append_back(&l2);
161 CheckList(&l1, x, y, z, a, b, c);
162 CHECK(l2.empty());
163
164 SetList(&l1, x, y);
165 SetList(&l2);
166 l1.append_front(&l2);
167 CheckList(&l1, x, y);
168 CHECK(l2.empty());
169 }
170
TEST(SanitizerCommon,IntrusiveListAppendEmpty)171 TEST(SanitizerCommon, IntrusiveListAppendEmpty) {
172 ListItem i;
173 List l;
174 l.clear();
175 l.push_back(&i);
176 List l2;
177 l2.clear();
178 l.append_back(&l2);
179 CHECK_EQ(l.back(), &i);
180 CHECK_EQ(l.front(), &i);
181 CHECK_EQ(l.size(), 1);
182 l.append_front(&l2);
183 CHECK_EQ(l.back(), &i);
184 CHECK_EQ(l.front(), &i);
185 CHECK_EQ(l.size(), 1);
186 }
187
188 } // namespace __sanitizer
189