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