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 "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 }