1 //===- llvm/unittest/ADT/SmallPtrSetTest.cpp ------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // SmallPtrSet unit tests.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/ADT/SmallPtrSet.h"
15 #include "llvm/ADT/PointerIntPair.h"
16 #include "llvm/Support/PointerLikeTypeTraits.h"
17 #include "gtest/gtest.h"
21 TEST(SmallPtrSetTest, Assignment) {
23 for (int i = 0; i < 8; ++i)
26 SmallPtrSet<int *, 4> s1 = {&buf[0], &buf[1]};
27 SmallPtrSet<int *, 4> s2;
28 (s2 = s1).insert(&buf[2]);
30 // Self assign as well.
31 (s2 = s2).insert(&buf[3]);
34 EXPECT_EQ(4U, s1.size());
35 for (int i = 0; i < 8; ++i)
37 EXPECT_TRUE(s1.count(&buf[i]));
39 EXPECT_FALSE(s1.count(&buf[i]));
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)
46 EXPECT_FALSE(s2.count(&buf[i]));
48 EXPECT_TRUE(s2.count(&buf[i]));
51 TEST(SmallPtrSetTest, GrowthTest) {
54 for(i=0; i<8; ++i) buf[i]=0;
57 SmallPtrSet<int *, 4> s;
58 typedef SmallPtrSet<int *, 4>::iterator iter;
64 EXPECT_EQ(4U, s.size());
67 for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i)
71 EXPECT_EQ(i<4?1:0,buf[i]);
79 for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i)
86 EXPECT_EQ(4U, s.size());
89 for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i)
93 EXPECT_EQ(i<4?3:1,buf[i]);
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)
105 TEST(SmallPtrSetTest, CopyAndMoveTest) {
107 for (int i = 0; i < 8; ++i)
110 SmallPtrSet<int *, 4> s1;
115 EXPECT_EQ(4U, s1.size());
116 for (int i = 0; i < 8; ++i)
118 EXPECT_TRUE(s1.count(&buf[i]));
120 EXPECT_FALSE(s1.count(&buf[i]));
122 SmallPtrSet<int *, 4> s2(s1);
123 EXPECT_EQ(4U, s2.size());
124 for (int i = 0; i < 8; ++i)
126 EXPECT_TRUE(s2.count(&buf[i]));
128 EXPECT_FALSE(s2.count(&buf[i]));
131 EXPECT_EQ(4U, s1.size());
132 EXPECT_EQ(4U, s2.size());
133 for (int i = 0; i < 8; ++i)
135 EXPECT_TRUE(s1.count(&buf[i]));
137 EXPECT_FALSE(s1.count(&buf[i]));
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)
144 EXPECT_TRUE(s3.count(&buf[i]));
146 EXPECT_FALSE(s3.count(&buf[i]));
148 // Move assign into the moved-from object. Also test move of a non-small
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]));
160 // Copy assign into a moved-from object.
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]));
168 TEST(SmallPtrSetTest, SwapTest) {
171 SmallPtrSet<int *, 2> a;
172 SmallPtrSet<int *, 2> b;
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]));
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]));
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]));
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]));
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]));
246 void checkEraseAndIterators(SmallPtrSetImpl<int*> &S) {
253 // Iterators must still be valid after erase() calls;
255 auto M = std::next(B);
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);
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);
275 TEST(SmallPtrSetTest, EraseTest) {
276 // Test when set stays small.
277 SmallPtrSet<int *, 8> B;
278 checkEraseAndIterators(B);
280 // Test when set grows big.
281 SmallPtrSet<int *, 2> A;
282 checkEraseAndIterators(A);
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));
294 // Iterate from each and count how many times each element is found.
295 int Found[sizeof(Ints)/sizeof(int)] = {0};
297 for (auto F = S.find(&I), E = S.end(); F != E; ++F)
300 // Sort. We should hit the first element just once and the final element N
302 std::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);
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;
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());
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>;
325 TEST(SmallPtrSetTest, ConstNonPtrTest) {
326 SmallPtrSet<TestPair, 8> IntSet;
328 TestPair Pair(&A[0], 1);
330 EXPECT_EQ(IntSet.count(Pair), 1u);
331 EXPECT_NE(IntSet.find(Pair), IntSet.end());