1 //===- llvm/unittest/ADT/SmallPtrSetTest.cpp ------------------------------===//
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 // SmallPtrSet unit tests.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "llvm/ADT/SmallPtrSet.h"
15 #include "llvm/ADT/PointerIntPair.h"
16 #include "llvm/Support/PointerLikeTypeTraits.h"
17 #include "gtest/gtest.h"
18
19 using namespace llvm;
20
TEST(SmallPtrSetTest,Assignment)21 TEST(SmallPtrSetTest, Assignment) {
22 int buf[8];
23 for (int i = 0; i < 8; ++i)
24 buf[i] = 0;
25
26 SmallPtrSet<int *, 4> s1 = {&buf[0], &buf[1]};
27 SmallPtrSet<int *, 4> s2;
28 (s2 = s1).insert(&buf[2]);
29
30 // Self assign as well.
31 (s2 = static_cast<SmallPtrSet<int *, 4> &>(s2)).insert(&buf[3]);
32
33 s1 = s2;
34 EXPECT_EQ(4U, s1.size());
35 for (int i = 0; i < 8; ++i)
36 if (i < 4)
37 EXPECT_TRUE(s1.count(&buf[i]));
38 else
39 EXPECT_FALSE(s1.count(&buf[i]));
40
41 // Assign and insert with initializer lists, and ones that contain both
42 // duplicates and out-of-order elements.
43 (s2 = {&buf[6], &buf[7], &buf[6]}).insert({&buf[5], &buf[4]});
44 for (int i = 0; i < 8; ++i)
45 if (i < 4)
46 EXPECT_FALSE(s2.count(&buf[i]));
47 else
48 EXPECT_TRUE(s2.count(&buf[i]));
49 }
50
TEST(SmallPtrSetTest,GrowthTest)51 TEST(SmallPtrSetTest, GrowthTest) {
52 int i;
53 int buf[8];
54 for(i=0; i<8; ++i) buf[i]=0;
55
56
57 SmallPtrSet<int *, 4> s;
58 typedef SmallPtrSet<int *, 4>::iterator iter;
59
60 s.insert(&buf[0]);
61 s.insert(&buf[1]);
62 s.insert(&buf[2]);
63 s.insert(&buf[3]);
64 EXPECT_EQ(4U, s.size());
65
66 i = 0;
67 for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i)
68 (**I)++;
69 EXPECT_EQ(4, i);
70 for(i=0; i<8; ++i)
71 EXPECT_EQ(i<4?1:0,buf[i]);
72
73 s.insert(&buf[4]);
74 s.insert(&buf[5]);
75 s.insert(&buf[6]);
76 s.insert(&buf[7]);
77
78 i = 0;
79 for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i)
80 (**I)++;
81 EXPECT_EQ(8, i);
82 s.erase(&buf[4]);
83 s.erase(&buf[5]);
84 s.erase(&buf[6]);
85 s.erase(&buf[7]);
86 EXPECT_EQ(4U, s.size());
87
88 i = 0;
89 for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i)
90 (**I)++;
91 EXPECT_EQ(4, i);
92 for(i=0; i<8; ++i)
93 EXPECT_EQ(i<4?3:1,buf[i]);
94
95 s.clear();
96 for(i=0; i<8; ++i) buf[i]=0;
97 for(i=0; i<128; ++i) s.insert(&buf[i%8]); // test repeated entires
98 EXPECT_EQ(8U, s.size());
99 for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i)
100 (**I)++;
101 for(i=0; i<8; ++i)
102 EXPECT_EQ(1,buf[i]);
103 }
104
TEST(SmallPtrSetTest,CopyAndMoveTest)105 TEST(SmallPtrSetTest, CopyAndMoveTest) {
106 int buf[8];
107 for (int i = 0; i < 8; ++i)
108 buf[i] = 0;
109
110 SmallPtrSet<int *, 4> s1;
111 s1.insert(&buf[0]);
112 s1.insert(&buf[1]);
113 s1.insert(&buf[2]);
114 s1.insert(&buf[3]);
115 EXPECT_EQ(4U, s1.size());
116 for (int i = 0; i < 8; ++i)
117 if (i < 4)
118 EXPECT_TRUE(s1.count(&buf[i]));
119 else
120 EXPECT_FALSE(s1.count(&buf[i]));
121
122 SmallPtrSet<int *, 4> s2(s1);
123 EXPECT_EQ(4U, s2.size());
124 for (int i = 0; i < 8; ++i)
125 if (i < 4)
126 EXPECT_TRUE(s2.count(&buf[i]));
127 else
128 EXPECT_FALSE(s2.count(&buf[i]));
129
130 s1 = s2;
131 EXPECT_EQ(4U, s1.size());
132 EXPECT_EQ(4U, s2.size());
133 for (int i = 0; i < 8; ++i)
134 if (i < 4)
135 EXPECT_TRUE(s1.count(&buf[i]));
136 else
137 EXPECT_FALSE(s1.count(&buf[i]));
138
139 SmallPtrSet<int *, 4> s3(std::move(s1));
140 EXPECT_EQ(4U, s3.size());
141 EXPECT_TRUE(s1.empty());
142 for (int i = 0; i < 8; ++i)
143 if (i < 4)
144 EXPECT_TRUE(s3.count(&buf[i]));
145 else
146 EXPECT_FALSE(s3.count(&buf[i]));
147
148 // Move assign into the moved-from object. Also test move of a non-small
149 // container.
150 s3.insert(&buf[4]);
151 s3.insert(&buf[5]);
152 s3.insert(&buf[6]);
153 s3.insert(&buf[7]);
154 s1 = std::move(s3);
155 EXPECT_EQ(8U, s1.size());
156 EXPECT_TRUE(s3.empty());
157 for (int i = 0; i < 8; ++i)
158 EXPECT_TRUE(s1.count(&buf[i]));
159
160 // Copy assign into a moved-from object.
161 s3 = s1;
162 EXPECT_EQ(8U, s3.size());
163 EXPECT_EQ(8U, s1.size());
164 for (int i = 0; i < 8; ++i)
165 EXPECT_TRUE(s3.count(&buf[i]));
166 }
167
TEST(SmallPtrSetTest,SwapTest)168 TEST(SmallPtrSetTest, SwapTest) {
169 int buf[10];
170
171 SmallPtrSet<int *, 2> a;
172 SmallPtrSet<int *, 2> b;
173
174 a.insert(&buf[0]);
175 a.insert(&buf[1]);
176 b.insert(&buf[2]);
177
178 EXPECT_EQ(2U, a.size());
179 EXPECT_EQ(1U, b.size());
180 EXPECT_TRUE(a.count(&buf[0]));
181 EXPECT_TRUE(a.count(&buf[1]));
182 EXPECT_FALSE(a.count(&buf[2]));
183 EXPECT_FALSE(a.count(&buf[3]));
184 EXPECT_FALSE(b.count(&buf[0]));
185 EXPECT_FALSE(b.count(&buf[1]));
186 EXPECT_TRUE(b.count(&buf[2]));
187 EXPECT_FALSE(b.count(&buf[3]));
188
189 std::swap(a, b);
190
191 EXPECT_EQ(1U, a.size());
192 EXPECT_EQ(2U, b.size());
193 EXPECT_FALSE(a.count(&buf[0]));
194 EXPECT_FALSE(a.count(&buf[1]));
195 EXPECT_TRUE(a.count(&buf[2]));
196 EXPECT_FALSE(a.count(&buf[3]));
197 EXPECT_TRUE(b.count(&buf[0]));
198 EXPECT_TRUE(b.count(&buf[1]));
199 EXPECT_FALSE(b.count(&buf[2]));
200 EXPECT_FALSE(b.count(&buf[3]));
201
202 b.insert(&buf[3]);
203 std::swap(a, b);
204
205 EXPECT_EQ(3U, a.size());
206 EXPECT_EQ(1U, b.size());
207 EXPECT_TRUE(a.count(&buf[0]));
208 EXPECT_TRUE(a.count(&buf[1]));
209 EXPECT_FALSE(a.count(&buf[2]));
210 EXPECT_TRUE(a.count(&buf[3]));
211 EXPECT_FALSE(b.count(&buf[0]));
212 EXPECT_FALSE(b.count(&buf[1]));
213 EXPECT_TRUE(b.count(&buf[2]));
214 EXPECT_FALSE(b.count(&buf[3]));
215
216 std::swap(a, b);
217
218 EXPECT_EQ(1U, a.size());
219 EXPECT_EQ(3U, b.size());
220 EXPECT_FALSE(a.count(&buf[0]));
221 EXPECT_FALSE(a.count(&buf[1]));
222 EXPECT_TRUE(a.count(&buf[2]));
223 EXPECT_FALSE(a.count(&buf[3]));
224 EXPECT_TRUE(b.count(&buf[0]));
225 EXPECT_TRUE(b.count(&buf[1]));
226 EXPECT_FALSE(b.count(&buf[2]));
227 EXPECT_TRUE(b.count(&buf[3]));
228
229 a.insert(&buf[4]);
230 a.insert(&buf[5]);
231 a.insert(&buf[6]);
232
233 std::swap(b, a);
234
235 EXPECT_EQ(3U, a.size());
236 EXPECT_EQ(4U, b.size());
237 EXPECT_TRUE(b.count(&buf[2]));
238 EXPECT_TRUE(b.count(&buf[4]));
239 EXPECT_TRUE(b.count(&buf[5]));
240 EXPECT_TRUE(b.count(&buf[6]));
241 EXPECT_TRUE(a.count(&buf[0]));
242 EXPECT_TRUE(a.count(&buf[1]));
243 EXPECT_TRUE(a.count(&buf[3]));
244 }
245
checkEraseAndIterators(SmallPtrSetImpl<int * > & S)246 void checkEraseAndIterators(SmallPtrSetImpl<int*> &S) {
247 int buf[3];
248
249 S.insert(&buf[0]);
250 S.insert(&buf[1]);
251 S.insert(&buf[2]);
252
253 // Iterators must still be valid after erase() calls;
254 auto B = S.begin();
255 auto M = std::next(B);
256 auto E = S.end();
257 EXPECT_TRUE(*B == &buf[0] || *B == &buf[1] || *B == &buf[2]);
258 EXPECT_TRUE(*M == &buf[0] || *M == &buf[1] || *M == &buf[2]);
259 EXPECT_TRUE(*B != *M);
260 int *Removable = *std::next(M);
261 // No iterator points to Removable now.
262 EXPECT_TRUE(Removable == &buf[0] || Removable == &buf[1] ||
263 Removable == &buf[2]);
264 EXPECT_TRUE(Removable != *B && Removable != *M);
265
266 S.erase(Removable);
267
268 // B,M,E iterators should still be valid
269 EXPECT_EQ(B, S.begin());
270 EXPECT_EQ(M, std::next(B));
271 EXPECT_EQ(E, S.end());
272 EXPECT_EQ(std::next(M), E);
273 }
274
TEST(SmallPtrSetTest,EraseTest)275 TEST(SmallPtrSetTest, EraseTest) {
276 // Test when set stays small.
277 SmallPtrSet<int *, 8> B;
278 checkEraseAndIterators(B);
279
280 // Test when set grows big.
281 SmallPtrSet<int *, 2> A;
282 checkEraseAndIterators(A);
283 }
284
285 // Verify that dereferencing and iteration work.
TEST(SmallPtrSetTest,dereferenceAndIterate)286 TEST(SmallPtrSetTest, dereferenceAndIterate) {
287 int Ints[] = {0, 1, 2, 3, 4, 5, 6, 7};
288 SmallPtrSet<const int *, 4> S;
289 for (int &I : Ints) {
290 EXPECT_EQ(&I, *S.insert(&I).first);
291 EXPECT_EQ(&I, *S.find(&I));
292 }
293
294 // Iterate from each and count how many times each element is found.
295 int Found[sizeof(Ints)/sizeof(int)] = {0};
296 for (int &I : Ints)
297 for (auto F = S.find(&I), E = S.end(); F != E; ++F)
298 ++Found[*F - Ints];
299
300 // Sort. We should hit the first element just once and the final element N
301 // times.
302 llvm::sort(std::begin(Found), std::end(Found));
303 for (auto F = std::begin(Found), E = std::end(Found); F != E; ++F)
304 EXPECT_EQ(F - Found + 1, *F);
305 }
306
307 // Verify that const pointers work for count and find even when the underlying
308 // SmallPtrSet is not for a const pointer type.
TEST(SmallPtrSetTest,ConstTest)309 TEST(SmallPtrSetTest, ConstTest) {
310 SmallPtrSet<int *, 8> IntSet;
311 int A;
312 int *B = &A;
313 const int *C = &A;
314 IntSet.insert(B);
315 EXPECT_EQ(IntSet.count(B), 1u);
316 EXPECT_EQ(IntSet.count(C), 1u);
317 EXPECT_NE(IntSet.find(B), IntSet.end());
318 EXPECT_NE(IntSet.find(C), IntSet.end());
319 }
320
321 // Verify that we automatically get the const version of PointerLikeTypeTraits
322 // filled in for us, even for a non-pointer type
323 using TestPair = PointerIntPair<int *, 1>;
324
TEST(SmallPtrSetTest,ConstNonPtrTest)325 TEST(SmallPtrSetTest, ConstNonPtrTest) {
326 SmallPtrSet<TestPair, 8> IntSet;
327 int A[1];
328 TestPair Pair(&A[0], 1);
329 IntSet.insert(Pair);
330 EXPECT_EQ(IntSet.count(Pair), 1u);
331 EXPECT_NE(IntSet.find(Pair), IntSet.end());
332 }
333