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 | |
19 | using namespace llvm; |
20 | |
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(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 | |
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(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 | |
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(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 | |
168 | TEST(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 | |
246 | void 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 | |
275 | TEST(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. |
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(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. |
309 | TEST(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 |
323 | using TestPair = PointerIntPair<int *, 1>; |
324 | |
325 | TEST(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. |
335 | TEST(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 | |
372 | TEST(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 | |
400 | TEST(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 | |