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
15namespace __sanitizer {
16
17struct ListItem {
18 ListItem *next;
19};
20
21typedef IntrusiveList<ListItem> List;
22
23static List static_list;
24
25static 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(x: y);
30 if (z) l->push_back(x: z);
31}
32
33static 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
62TEST(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(x: y);
95 l.push_front(x: 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(x: y);
112 l.push_back(x: 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(x: y);
129 l.push_back(x: z);
130 l.extract(prev: x, 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(prev: x, 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(l: &l2);
148 CHECK(l1.empty());
149 CHECK(l2.empty());
150
151 l1.append_back(l: &l2);
152 CHECK(l1.empty());
153 CHECK(l2.empty());
154
155 SetList(l: &l1, x);
156 CheckList(l: &l1, i1: x);
157
158 SetList(l: &l1, x, y, z);
159 SetList(l: &l2, x: a, y: b, z: c);
160 l1.append_back(l: &l2);
161 CheckList(l: &l1, i1: x, i2: y, i3: z, i4: a, i5: b, i6: c);
162 CHECK(l2.empty());
163
164 SetList(l: &l1, x, y);
165 SetList(l: &l2);
166 l1.append_front(l: &l2);
167 CheckList(l: &l1, i1: x, i2: y);
168 CHECK(l2.empty());
169}
170
171TEST(SanitizerCommon, IntrusiveListAppendEmpty) {
172 ListItem i;
173 List l;
174 l.clear();
175 l.push_back(x: &i);
176 List l2;
177 l2.clear();
178 l.append_back(l: &l2);
179 CHECK_EQ(l.back(), &i);
180 CHECK_EQ(l.front(), &i);
181 CHECK_EQ(l.size(), 1);
182 l.append_front(l: &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

source code of compiler-rt/lib/sanitizer_common/tests/sanitizer_list_test.cpp