483 lines · cpp
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-exception6//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 20using namespace llvm;21using testing::UnorderedElementsAre;22 23TEST(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 else41 EXPECT_FALSE(s1.count(&buf[i]));42 43 // Assign and insert with initializer lists, and ones that contain both44 // 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 else50 EXPECT_TRUE(s2.count(&buf[i]));51}52 53TEST(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 using iter = SmallPtrSet<int *, 4>::iterator;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 entires100 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 107TEST(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 else122 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 else130 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 else139 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 else148 EXPECT_FALSE(s3.count(&buf[i]));149 150 // Move assign into the moved-from object. Also test move of a non-small151 // 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 170TEST(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.249TEST(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 N264 // 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 underlying271// SmallPtrSet is not for a const pointer type.272TEST(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 PointerLikeTypeTraits285// filled in for us, even for a non-pointer type286using TestPair = PointerIntPair<int *, 1>;287 288TEST(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.298TEST(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 335TEST(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 363TEST(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 376TEST(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 414TEST(SmallPtrSetTest, CtorRange) {415 int V0 = 0;416 int V1 = 1;417 int V2 = 2;418 int *Args[] = {&V2, &V0, &V1};419 SmallPtrSet<int *, 4> Set(llvm::from_range, Args);420 EXPECT_THAT(Set, UnorderedElementsAre(&V0, &V1, &V2));421}422 423TEST(SmallPtrSetTest, InsertRange) {424 int V0 = 0;425 int V1 = 1;426 int V2 = 2;427 SmallPtrSet<int *, 4> Set;428 int *Args[] = {&V2, &V0, &V1};429 Set.insert_range(Args);430 EXPECT_THAT(Set, UnorderedElementsAre(&V0, &V1, &V2));431}432 433TEST(SmallPtrSetTest, Reserve) {434 // Check that we don't do anything silly when using reserve().435 SmallPtrSet<int *, 4> Set;436 int Vals[8] = {0, 1, 2, 3, 4, 5, 6, 7};437 438 Set.insert(&Vals[0]);439 440 // We shouldn't reallocate when this happens.441 Set.reserve(4);442 EXPECT_EQ(Set.capacity(), 4u);443 444 Set.insert(&Vals[1]);445 Set.insert(&Vals[2]);446 Set.insert(&Vals[3]);447 448 // We shouldn't reallocate this time either.449 Set.reserve(4);450 EXPECT_EQ(Set.capacity(), 4u);451 EXPECT_EQ(Set.size(), 4u);452 EXPECT_THAT(Set,453 UnorderedElementsAre(&Vals[0], &Vals[1], &Vals[2], &Vals[3]));454 455 // Reserving further should lead to a reallocation. And matching the existing456 // insertion approach, we immediately allocate up to 128 elements.457 Set.reserve(5);458 EXPECT_EQ(Set.capacity(), 128u);459 EXPECT_EQ(Set.size(), 4u);460 EXPECT_THAT(Set,461 UnorderedElementsAre(&Vals[0], &Vals[1], &Vals[2], &Vals[3]));462 463 // And we should be able to insert another two or three elements without464 // reallocating.465 Set.insert(&Vals[4]);466 Set.insert(&Vals[5]);467 468 // Calling a smaller reserve size should have no effect.469 Set.reserve(1);470 EXPECT_EQ(Set.capacity(), 128u);471 EXPECT_EQ(Set.size(), 6u);472 473 // Reserving zero should have no effect either.474 Set.reserve(0);475 EXPECT_EQ(Set.capacity(), 128u);476 EXPECT_EQ(Set.size(), 6u);477 EXPECT_THAT(Set, UnorderedElementsAre(&Vals[0], &Vals[1], &Vals[2], &Vals[3], &Vals[4], &Vals[5]));478 479 // Reserving 192 should result in 256 buckets.480 Set.reserve(192);481 EXPECT_EQ(Set.capacity(), 256u);482}483