llvm/unittests/ADT/SmallPtrSetTest.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-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 }