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/ADT/STLExtras.h"
16#include "llvm/Support/PointerLikeTypeTraits.h"
17#include "gtest/gtest.h"
18
19using namespace llvm;
20
21TEST(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(Ptr: &buf[2]);
29
30 // Self assign as well.
31 (s2 = static_cast<SmallPtrSet<int *, 4> &>(s2)).insert(Ptr: &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(IL: {&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
51TEST(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(Ptr: &buf[0]);
61 s.insert(Ptr: &buf[1]);
62 s.insert(Ptr: &buf[2]);
63 s.insert(Ptr: &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(Ptr: &buf[4]);
74 s.insert(Ptr: &buf[5]);
75 s.insert(Ptr: &buf[6]);
76 s.insert(Ptr: &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(Ptr: &buf[4]);
83 s.erase(Ptr: &buf[5]);
84 s.erase(Ptr: &buf[6]);
85 s.erase(Ptr: &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(Ptr: &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
105TEST(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(Ptr: &buf[0]);
112 s1.insert(Ptr: &buf[1]);
113 s1.insert(Ptr: &buf[2]);
114 s1.insert(Ptr: &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(Ptr: &buf[4]);
151 s3.insert(Ptr: &buf[5]);
152 s3.insert(Ptr: &buf[6]);
153 s3.insert(Ptr: &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
168TEST(SmallPtrSetTest, SwapTest) {
169 int buf[10];
170
171 SmallPtrSet<int *, 2> a;
172 SmallPtrSet<int *, 2> b;
173
174 a.insert(Ptr: &buf[0]);
175 a.insert(Ptr: &buf[1]);
176 b.insert(Ptr: &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(LHS&: a, RHS&: 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(Ptr: &buf[3]);
203 std::swap(LHS&: a, RHS&: 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(LHS&: a, RHS&: 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(Ptr: &buf[4]);
230 a.insert(Ptr: &buf[5]);
231 a.insert(Ptr: &buf[6]);
232
233 std::swap(LHS&: b, RHS&: 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
246void checkEraseAndIterators(SmallPtrSetImpl<int*> &S) {
247 int buf[3];
248
249 S.insert(Ptr: &buf[0]);
250 S.insert(Ptr: &buf[1]);
251 S.insert(Ptr: &buf[2]);
252
253 // Iterators must still be valid after erase() calls;
254 auto B = S.begin();
255 auto M = std::next(x: 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(x: 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(Ptr: 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
275TEST(SmallPtrSetTest, EraseTest) {
276 // Test when set stays small.
277 SmallPtrSet<int *, 8> B;
278 checkEraseAndIterators(S&: B);
279
280 // Test when set grows big.
281 SmallPtrSet<int *, 2> A;
282 checkEraseAndIterators(S&: A);
283}
284
285// Verify that dereferencing and iteration work.
286TEST(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(Ptr: &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(C&: Found);
303 for (auto F = std::begin(arr&: Found), E = std::end(arr&: 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.
309TEST(SmallPtrSetTest, ConstTest) {
310 SmallPtrSet<int *, 8> IntSet;
311 int A;
312 int *B = &A;
313 const int *C = &A;
314 IntSet.insert(Ptr: B);
315 EXPECT_EQ(IntSet.count(B), 1u);
316 EXPECT_EQ(IntSet.count(C), 1u);
317 EXPECT_TRUE(IntSet.contains(B));
318 EXPECT_TRUE(IntSet.contains(C));
319}
320
321// Verify that we automatically get the const version of PointerLikeTypeTraits
322// filled in for us, even for a non-pointer type
323using TestPair = PointerIntPair<int *, 1>;
324
325TEST(SmallPtrSetTest, ConstNonPtrTest) {
326 SmallPtrSet<TestPair, 8> IntSet;
327 int A[1];
328 TestPair Pair(&A[0], 1);
329 IntSet.insert(Ptr: Pair);
330 EXPECT_EQ(IntSet.count(Pair), 1u);
331 EXPECT_TRUE(IntSet.contains(Pair));
332}
333
334// Test equality comparison.
335TEST(SmallPtrSetTest, EqualityComparison) {
336 int buf[3];
337 for (int i = 0; i < 3; ++i)
338 buf[i] = 0;
339
340 SmallPtrSet<int *, 1> a;
341 a.insert(Ptr: &buf[0]);
342 a.insert(Ptr: &buf[1]);
343
344 SmallPtrSet<int *, 2> b;
345 b.insert(Ptr: &buf[1]);
346 b.insert(Ptr: &buf[0]);
347
348 SmallPtrSet<int *, 3> c;
349 c.insert(Ptr: &buf[1]);
350 c.insert(Ptr: &buf[2]);
351
352 SmallPtrSet<int *, 4> d;
353 d.insert(Ptr: &buf[0]);
354
355 SmallPtrSet<int *, 5> e;
356 e.insert(Ptr: &buf[0]);
357 e.insert(Ptr: &buf[1]);
358 e.insert(Ptr: &buf[2]);
359
360 EXPECT_EQ(a, b);
361 EXPECT_EQ(b, a);
362 EXPECT_NE(b, c);
363 EXPECT_NE(c, a);
364 EXPECT_NE(d, a);
365 EXPECT_NE(a, d);
366 EXPECT_NE(a, e);
367 EXPECT_NE(e, a);
368 EXPECT_NE(c, e);
369 EXPECT_NE(e, d);
370}
371
372TEST(SmallPtrSetTest, Contains) {
373 SmallPtrSet<int *, 2> Set;
374 int buf[4] = {0, 11, 22, 11};
375 EXPECT_FALSE(Set.contains(&buf[0]));
376 EXPECT_FALSE(Set.contains(&buf[1]));
377
378 Set.insert(Ptr: &buf[0]);
379 Set.insert(Ptr: &buf[1]);
380 EXPECT_TRUE(Set.contains(&buf[0]));
381 EXPECT_TRUE(Set.contains(&buf[1]));
382 EXPECT_FALSE(Set.contains(&buf[3]));
383
384 Set.insert(Ptr: &buf[1]);
385 EXPECT_TRUE(Set.contains(&buf[0]));
386 EXPECT_TRUE(Set.contains(&buf[1]));
387 EXPECT_FALSE(Set.contains(&buf[3]));
388
389 Set.erase(Ptr: &buf[1]);
390 EXPECT_TRUE(Set.contains(&buf[0]));
391 EXPECT_FALSE(Set.contains(&buf[1]));
392
393 Set.insert(Ptr: &buf[1]);
394 Set.insert(Ptr: &buf[2]);
395 EXPECT_TRUE(Set.contains(&buf[0]));
396 EXPECT_TRUE(Set.contains(&buf[1]));
397 EXPECT_TRUE(Set.contains(&buf[2]));
398}
399
400TEST(SmallPtrSetTest, InsertIterator) {
401 SmallPtrSet<int *, 5> Set;
402 int Vals[5] = {11, 22, 33, 44, 55};
403 int *Buf[5] = {&Vals[0], &Vals[1], &Vals[2], &Vals[3], &Vals[4]};
404
405 for (int *Ptr : Buf)
406 Set.insert(Set.begin(), Ptr);
407
408 // Ensure that all of the values were copied into the set.
409 for (const auto *Ptr : Buf)
410 EXPECT_TRUE(Set.contains(Ptr));
411}
412

source code of llvm/unittests/ADT/SmallPtrSetTest.cpp