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