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
16namespace __sanitizer {
17
18struct ListItem {
19  ListItem *next;
20};
21
22typedef IntrusiveList<ListItem> List;
23
24static List static_list;
25
26static 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
34static 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
63TEST(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
156TEST(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