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 "gmock/gmock.h" 18 #include "gtest/gtest.h" 19 20 using namespace llvm; 21 using testing::UnorderedElementsAre; 22 23 TEST(SmallPtrSetTest, Assignment) { 24 int buf[8]; 25 for (int i = 0; i < 8; ++i) 26 buf[i] = 0; 27 28 SmallPtrSet<int *, 4> s1 = {&buf[0], &buf[1]}; 29 SmallPtrSet<int *, 4> s2; 30 (s2 = s1).insert(&buf[2]); 31 32 // Self assign as well. 33 (s2 = static_cast<SmallPtrSet<int *, 4> &>(s2)).insert(&buf[3]); 34 35 s1 = s2; 36 EXPECT_EQ(4U, s1.size()); 37 for (int i = 0; i < 8; ++i) 38 if (i < 4) 39 EXPECT_TRUE(s1.count(&buf[i])); 40 else 41 EXPECT_FALSE(s1.count(&buf[i])); 42 43 // Assign and insert with initializer lists, and ones that contain both 44 // duplicates and out-of-order elements. 45 (s2 = {&buf[6], &buf[7], &buf[6]}).insert({&buf[5], &buf[4]}); 46 for (int i = 0; i < 8; ++i) 47 if (i < 4) 48 EXPECT_FALSE(s2.count(&buf[i])); 49 else 50 EXPECT_TRUE(s2.count(&buf[i])); 51 } 52 53 TEST(SmallPtrSetTest, GrowthTest) { 54 int i; 55 int buf[8]; 56 for(i=0; i<8; ++i) buf[i]=0; 57 58 59 SmallPtrSet<int *, 4> s; 60 typedef SmallPtrSet<int *, 4>::iterator iter; 61 62 s.insert(&buf[0]); 63 s.insert(&buf[1]); 64 s.insert(&buf[2]); 65 s.insert(&buf[3]); 66 EXPECT_EQ(4U, s.size()); 67 68 i = 0; 69 for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i) 70 (**I)++; 71 EXPECT_EQ(4, i); 72 for(i=0; i<8; ++i) 73 EXPECT_EQ(i<4?1:0,buf[i]); 74 75 s.insert(&buf[4]); 76 s.insert(&buf[5]); 77 s.insert(&buf[6]); 78 s.insert(&buf[7]); 79 80 i = 0; 81 for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i) 82 (**I)++; 83 EXPECT_EQ(8, i); 84 s.erase(&buf[4]); 85 s.erase(&buf[5]); 86 s.erase(&buf[6]); 87 s.erase(&buf[7]); 88 EXPECT_EQ(4U, s.size()); 89 90 i = 0; 91 for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i) 92 (**I)++; 93 EXPECT_EQ(4, i); 94 for(i=0; i<8; ++i) 95 EXPECT_EQ(i<4?3:1,buf[i]); 96 97 s.clear(); 98 for(i=0; i<8; ++i) buf[i]=0; 99 for(i=0; i<128; ++i) s.insert(&buf[i%8]); // test repeated entires 100 EXPECT_EQ(8U, s.size()); 101 for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i) 102 (**I)++; 103 for(i=0; i<8; ++i) 104 EXPECT_EQ(1,buf[i]); 105 } 106 107 TEST(SmallPtrSetTest, CopyAndMoveTest) { 108 int buf[8]; 109 for (int i = 0; i < 8; ++i) 110 buf[i] = 0; 111 112 SmallPtrSet<int *, 4> s1; 113 s1.insert(&buf[0]); 114 s1.insert(&buf[1]); 115 s1.insert(&buf[2]); 116 s1.insert(&buf[3]); 117 EXPECT_EQ(4U, s1.size()); 118 for (int i = 0; i < 8; ++i) 119 if (i < 4) 120 EXPECT_TRUE(s1.count(&buf[i])); 121 else 122 EXPECT_FALSE(s1.count(&buf[i])); 123 124 SmallPtrSet<int *, 4> s2(s1); 125 EXPECT_EQ(4U, s2.size()); 126 for (int i = 0; i < 8; ++i) 127 if (i < 4) 128 EXPECT_TRUE(s2.count(&buf[i])); 129 else 130 EXPECT_FALSE(s2.count(&buf[i])); 131 132 s1 = s2; 133 EXPECT_EQ(4U, s1.size()); 134 EXPECT_EQ(4U, s2.size()); 135 for (int i = 0; i < 8; ++i) 136 if (i < 4) 137 EXPECT_TRUE(s1.count(&buf[i])); 138 else 139 EXPECT_FALSE(s1.count(&buf[i])); 140 141 SmallPtrSet<int *, 4> s3(std::move(s1)); 142 EXPECT_EQ(4U, s3.size()); 143 EXPECT_TRUE(s1.empty()); 144 for (int i = 0; i < 8; ++i) 145 if (i < 4) 146 EXPECT_TRUE(s3.count(&buf[i])); 147 else 148 EXPECT_FALSE(s3.count(&buf[i])); 149 150 // Move assign into the moved-from object. Also test move of a non-small 151 // container. 152 s3.insert(&buf[4]); 153 s3.insert(&buf[5]); 154 s3.insert(&buf[6]); 155 s3.insert(&buf[7]); 156 s1 = std::move(s3); 157 EXPECT_EQ(8U, s1.size()); 158 EXPECT_TRUE(s3.empty()); 159 for (int i = 0; i < 8; ++i) 160 EXPECT_TRUE(s1.count(&buf[i])); 161 162 // Copy assign into a moved-from object. 163 s3 = s1; 164 EXPECT_EQ(8U, s3.size()); 165 EXPECT_EQ(8U, s1.size()); 166 for (int i = 0; i < 8; ++i) 167 EXPECT_TRUE(s3.count(&buf[i])); 168 } 169 170 TEST(SmallPtrSetTest, SwapTest) { 171 int buf[10]; 172 173 SmallPtrSet<int *, 2> a; 174 SmallPtrSet<int *, 2> b; 175 176 a.insert(&buf[0]); 177 a.insert(&buf[1]); 178 b.insert(&buf[2]); 179 180 EXPECT_EQ(2U, a.size()); 181 EXPECT_EQ(1U, b.size()); 182 EXPECT_TRUE(a.count(&buf[0])); 183 EXPECT_TRUE(a.count(&buf[1])); 184 EXPECT_FALSE(a.count(&buf[2])); 185 EXPECT_FALSE(a.count(&buf[3])); 186 EXPECT_FALSE(b.count(&buf[0])); 187 EXPECT_FALSE(b.count(&buf[1])); 188 EXPECT_TRUE(b.count(&buf[2])); 189 EXPECT_FALSE(b.count(&buf[3])); 190 191 std::swap(a, b); 192 193 EXPECT_EQ(1U, a.size()); 194 EXPECT_EQ(2U, b.size()); 195 EXPECT_FALSE(a.count(&buf[0])); 196 EXPECT_FALSE(a.count(&buf[1])); 197 EXPECT_TRUE(a.count(&buf[2])); 198 EXPECT_FALSE(a.count(&buf[3])); 199 EXPECT_TRUE(b.count(&buf[0])); 200 EXPECT_TRUE(b.count(&buf[1])); 201 EXPECT_FALSE(b.count(&buf[2])); 202 EXPECT_FALSE(b.count(&buf[3])); 203 204 b.insert(&buf[3]); 205 std::swap(a, b); 206 207 EXPECT_EQ(3U, a.size()); 208 EXPECT_EQ(1U, b.size()); 209 EXPECT_TRUE(a.count(&buf[0])); 210 EXPECT_TRUE(a.count(&buf[1])); 211 EXPECT_FALSE(a.count(&buf[2])); 212 EXPECT_TRUE(a.count(&buf[3])); 213 EXPECT_FALSE(b.count(&buf[0])); 214 EXPECT_FALSE(b.count(&buf[1])); 215 EXPECT_TRUE(b.count(&buf[2])); 216 EXPECT_FALSE(b.count(&buf[3])); 217 218 std::swap(a, b); 219 220 EXPECT_EQ(1U, a.size()); 221 EXPECT_EQ(3U, b.size()); 222 EXPECT_FALSE(a.count(&buf[0])); 223 EXPECT_FALSE(a.count(&buf[1])); 224 EXPECT_TRUE(a.count(&buf[2])); 225 EXPECT_FALSE(a.count(&buf[3])); 226 EXPECT_TRUE(b.count(&buf[0])); 227 EXPECT_TRUE(b.count(&buf[1])); 228 EXPECT_FALSE(b.count(&buf[2])); 229 EXPECT_TRUE(b.count(&buf[3])); 230 231 a.insert(&buf[4]); 232 a.insert(&buf[5]); 233 a.insert(&buf[6]); 234 235 std::swap(b, a); 236 237 EXPECT_EQ(3U, a.size()); 238 EXPECT_EQ(4U, b.size()); 239 EXPECT_TRUE(b.count(&buf[2])); 240 EXPECT_TRUE(b.count(&buf[4])); 241 EXPECT_TRUE(b.count(&buf[5])); 242 EXPECT_TRUE(b.count(&buf[6])); 243 EXPECT_TRUE(a.count(&buf[0])); 244 EXPECT_TRUE(a.count(&buf[1])); 245 EXPECT_TRUE(a.count(&buf[3])); 246 } 247 248 // Verify that dereferencing and iteration work. 249 TEST(SmallPtrSetTest, dereferenceAndIterate) { 250 int Ints[] = {0, 1, 2, 3, 4, 5, 6, 7}; 251 SmallPtrSet<const int *, 4> S; 252 for (int &I : Ints) { 253 EXPECT_EQ(&I, *S.insert(&I).first); 254 EXPECT_EQ(&I, *S.find(&I)); 255 } 256 257 // Iterate from each and count how many times each element is found. 258 int Found[sizeof(Ints)/sizeof(int)] = {0}; 259 for (int &I : Ints) 260 for (auto F = S.find(&I), E = S.end(); F != E; ++F) 261 ++Found[*F - Ints]; 262 263 // Sort. We should hit the first element just once and the final element N 264 // times. 265 llvm::sort(Found); 266 for (auto F = std::begin(Found), E = std::end(Found); F != E; ++F) 267 EXPECT_EQ(F - Found + 1, *F); 268 } 269 270 // Verify that const pointers work for count and find even when the underlying 271 // SmallPtrSet is not for a const pointer type. 272 TEST(SmallPtrSetTest, ConstTest) { 273 SmallPtrSet<int *, 8> IntSet; 274 int A; 275 int *B = &A; 276 const int *C = &A; 277 IntSet.insert(B); 278 EXPECT_EQ(IntSet.count(B), 1u); 279 EXPECT_EQ(IntSet.count(C), 1u); 280 EXPECT_TRUE(IntSet.contains(B)); 281 EXPECT_TRUE(IntSet.contains(C)); 282 } 283 284 // Verify that we automatically get the const version of PointerLikeTypeTraits 285 // filled in for us, even for a non-pointer type 286 using TestPair = PointerIntPair<int *, 1>; 287 288 TEST(SmallPtrSetTest, ConstNonPtrTest) { 289 SmallPtrSet<TestPair, 8> IntSet; 290 int A[1]; 291 TestPair Pair(&A[0], 1); 292 IntSet.insert(Pair); 293 EXPECT_EQ(IntSet.count(Pair), 1u); 294 EXPECT_TRUE(IntSet.contains(Pair)); 295 } 296 297 // Test equality comparison. 298 TEST(SmallPtrSetTest, EqualityComparison) { 299 int buf[3]; 300 for (int i = 0; i < 3; ++i) 301 buf[i] = 0; 302 303 SmallPtrSet<int *, 1> a; 304 a.insert(&buf[0]); 305 a.insert(&buf[1]); 306 307 SmallPtrSet<int *, 2> b; 308 b.insert(&buf[1]); 309 b.insert(&buf[0]); 310 311 SmallPtrSet<int *, 3> c; 312 c.insert(&buf[1]); 313 c.insert(&buf[2]); 314 315 SmallPtrSet<int *, 4> d; 316 d.insert(&buf[0]); 317 318 SmallPtrSet<int *, 5> e; 319 e.insert(&buf[0]); 320 e.insert(&buf[1]); 321 e.insert(&buf[2]); 322 323 EXPECT_EQ(a, b); 324 EXPECT_EQ(b, a); 325 EXPECT_NE(b, c); 326 EXPECT_NE(c, a); 327 EXPECT_NE(d, a); 328 EXPECT_NE(a, d); 329 EXPECT_NE(a, e); 330 EXPECT_NE(e, a); 331 EXPECT_NE(c, e); 332 EXPECT_NE(e, d); 333 } 334 335 TEST(SmallPtrSetTest, Contains) { 336 SmallPtrSet<int *, 2> Set; 337 int buf[4] = {0, 11, 22, 11}; 338 EXPECT_FALSE(Set.contains(&buf[0])); 339 EXPECT_FALSE(Set.contains(&buf[1])); 340 341 Set.insert(&buf[0]); 342 Set.insert(&buf[1]); 343 EXPECT_TRUE(Set.contains(&buf[0])); 344 EXPECT_TRUE(Set.contains(&buf[1])); 345 EXPECT_FALSE(Set.contains(&buf[3])); 346 347 Set.insert(&buf[1]); 348 EXPECT_TRUE(Set.contains(&buf[0])); 349 EXPECT_TRUE(Set.contains(&buf[1])); 350 EXPECT_FALSE(Set.contains(&buf[3])); 351 352 Set.erase(&buf[1]); 353 EXPECT_TRUE(Set.contains(&buf[0])); 354 EXPECT_FALSE(Set.contains(&buf[1])); 355 356 Set.insert(&buf[1]); 357 Set.insert(&buf[2]); 358 EXPECT_TRUE(Set.contains(&buf[0])); 359 EXPECT_TRUE(Set.contains(&buf[1])); 360 EXPECT_TRUE(Set.contains(&buf[2])); 361 } 362 363 TEST(SmallPtrSetTest, InsertIterator) { 364 SmallPtrSet<int *, 5> Set; 365 int Vals[5] = {11, 22, 33, 44, 55}; 366 int *Buf[5] = {&Vals[0], &Vals[1], &Vals[2], &Vals[3], &Vals[4]}; 367 368 for (int *Ptr : Buf) 369 Set.insert(Set.begin(), Ptr); 370 371 // Ensure that all of the values were copied into the set. 372 for (const auto *Ptr : Buf) 373 EXPECT_TRUE(Set.contains(Ptr)); 374 } 375 376 TEST(SmallPtrSetTest, RemoveIf) { 377 SmallPtrSet<int *, 5> Set; 378 int Vals[6] = {0, 1, 2, 3, 4, 5}; 379 380 // Stay in small regime. 381 Set.insert(&Vals[0]); 382 Set.insert(&Vals[1]); 383 Set.insert(&Vals[2]); 384 Set.insert(&Vals[3]); 385 Set.erase(&Vals[0]); // Leave a tombstone. 386 387 // Remove odd elements. 388 bool Removed = Set.remove_if([](int *Ptr) { return *Ptr % 2 != 0; }); 389 // We should only have element 2 left now. 390 EXPECT_TRUE(Removed); 391 EXPECT_EQ(Set.size(), 1u); 392 EXPECT_TRUE(Set.contains(&Vals[2])); 393 394 // Switch to big regime. 395 Set.insert(&Vals[0]); 396 Set.insert(&Vals[1]); 397 Set.insert(&Vals[3]); 398 Set.insert(&Vals[4]); 399 Set.insert(&Vals[5]); 400 Set.erase(&Vals[0]); // Leave a tombstone. 401 402 // Remove odd elements. 403 Removed = Set.remove_if([](int *Ptr) { return *Ptr % 2 != 0; }); 404 // We should only have elements 2 and 4 left now. 405 EXPECT_TRUE(Removed); 406 EXPECT_EQ(Set.size(), 2u); 407 EXPECT_TRUE(Set.contains(&Vals[2])); 408 EXPECT_TRUE(Set.contains(&Vals[4])); 409 410 Removed = Set.remove_if([](int *Ptr) { return false; }); 411 EXPECT_FALSE(Removed); 412 } 413 414 TEST(SmallPtrSetTest, Reserve) { 415 // Check that we don't do anything silly when using reserve(). 416 SmallPtrSet<int *, 4> Set; 417 int Vals[8] = {0, 1, 2, 3, 4, 5, 6, 7}; 418 419 Set.insert(&Vals[0]); 420 421 // We shouldn't reallocate when this happens. 422 Set.reserve(4); 423 EXPECT_EQ(Set.capacity(), 4u); 424 425 Set.insert(&Vals[1]); 426 Set.insert(&Vals[2]); 427 Set.insert(&Vals[3]); 428 429 // We shouldn't reallocate this time either. 430 Set.reserve(4); 431 EXPECT_EQ(Set.capacity(), 4u); 432 EXPECT_EQ(Set.size(), 4u); 433 EXPECT_THAT(Set, 434 UnorderedElementsAre(&Vals[0], &Vals[1], &Vals[2], &Vals[3])); 435 436 // Reserving further should lead to a reallocation. And matching the existing 437 // insertion approach, we immediately allocate up to 128 elements. 438 Set.reserve(5); 439 EXPECT_EQ(Set.capacity(), 128u); 440 EXPECT_EQ(Set.size(), 4u); 441 EXPECT_THAT(Set, 442 UnorderedElementsAre(&Vals[0], &Vals[1], &Vals[2], &Vals[3])); 443 444 // And we should be able to insert another two or three elements without 445 // reallocating. 446 Set.insert(&Vals[4]); 447 Set.insert(&Vals[5]); 448 449 // Calling a smaller reserve size should have no effect. 450 Set.reserve(1); 451 EXPECT_EQ(Set.capacity(), 128u); 452 EXPECT_EQ(Set.size(), 6u); 453 454 // Reserving zero should have no effect either. 455 Set.reserve(0); 456 EXPECT_EQ(Set.capacity(), 128u); 457 EXPECT_EQ(Set.size(), 6u); 458 EXPECT_THAT(Set, UnorderedElementsAre(&Vals[0], &Vals[1], &Vals[2], &Vals[3], &Vals[4], &Vals[5])); 459 } 460