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(&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 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 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 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 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 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. 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(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. 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_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(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(&buf[0]); 342 a.insert(&buf[1]); 343 344 SmallPtrSet<int *, 2> b; 345 b.insert(&buf[1]); 346 b.insert(&buf[0]); 347 348 SmallPtrSet<int *, 3> c; 349 c.insert(&buf[1]); 350 c.insert(&buf[2]); 351 352 SmallPtrSet<int *, 4> d; 353 d.insert(&buf[0]); 354 355 SmallPtrSet<int *, 5> e; 356 e.insert(&buf[0]); 357 e.insert(&buf[1]); 358 e.insert(&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(&buf[0]); 379 Set.insert(&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(&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(&buf[1]); 390 EXPECT_TRUE(Set.contains(&buf[0])); 391 EXPECT_FALSE(Set.contains(&buf[1])); 392 393 Set.insert(&buf[1]); 394 Set.insert(&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