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/Support/PointerLikeTypeTraits.h"
  16 #include "gtest/gtest.h"
  17
  18 using namespace llvm;
  19
  20 TEST(SmallPtrSetTest, Assignment) {
  21   int buf[8];
  22   for (int i = 0; i < 8; ++i)
  23     buf[i] = 0;
  24
  25   SmallPtrSet<int *, 4> s1 = {&buf[0], &buf[1]};
  26   SmallPtrSet<int *, 4> s2;
  27   (s2 = s1).insert(&buf[2]);
  28
  29   // Self assign as well.
  30   (s2 = static_cast<SmallPtrSet<int *, 4> &>(s2)).insert(&buf[3]);
  31
  32   s1 = s2;
  33   EXPECT_EQ(4U, s1.size());
  34   for (int i = 0; i < 8; ++i)
  35     if (i < 4)
  36       EXPECT_TRUE(s1.count(&buf[i]));
  37     else
  38       EXPECT_FALSE(s1.count(&buf[i]));
  39
  40   // Assign and insert with initializer lists, and ones that contain both
  41   // duplicates and out-of-order elements.
  42   (s2 = {&buf[6], &buf[7], &buf[6]}).insert({&buf[5], &buf[4]});
  43   for (int i = 0; i < 8; ++i)
  44     if (i < 4)
  45       EXPECT_FALSE(s2.count(&buf[i]));
  46     else
  47       EXPECT_TRUE(s2.count(&buf[i]));
  48 }
  49
  50 TEST(SmallPtrSetTest, GrowthTest) {
  51   int i;
  52   int buf[8];
  53   for(i=0; i<8; ++i) buf[i]=0;
  54
  55
  56   SmallPtrSet<int *, 4> s;
  57   typedef SmallPtrSet<int *, 4>::iterator iter;
  58
  59   s.insert(&buf[0]);
  60   s.insert(&buf[1]);
  61   s.insert(&buf[2]);
  62   s.insert(&buf[3]);
  63   EXPECT_EQ(4U, s.size());
  64
  65   i = 0;
  66   for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i)
  67       (**I)++;
  68   EXPECT_EQ(4, i);
  69   for(i=0; i<8; ++i)
  70       EXPECT_EQ(i<4?1:0,buf[i]);
  71
  72   s.insert(&buf[4]);
  73   s.insert(&buf[5]);
  74   s.insert(&buf[6]);
  75   s.insert(&buf[7]);
  76
  77   i = 0;
  78   for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i)
  79       (**I)++;
  80   EXPECT_EQ(8, i);
  81   s.erase(&buf[4]);
  82   s.erase(&buf[5]);
  83   s.erase(&buf[6]);
  84   s.erase(&buf[7]);
  85   EXPECT_EQ(4U, s.size());
  86
  87   i = 0;
  88   for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i)
  89       (**I)++;
  90   EXPECT_EQ(4, i);
  91   for(i=0; i<8; ++i)
  92       EXPECT_EQ(i<4?3:1,buf[i]);
  93
  94   s.clear();
  95   for(i=0; i<8; ++i) buf[i]=0;
  96   for(i=0; i<128; ++i) s.insert(&buf[i%8]); // test repeated entires
  97   EXPECT_EQ(8U, s.size());
  98   for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i)
  99       (**I)++;
 100   for(i=0; i<8; ++i)
 101       EXPECT_EQ(1,buf[i]);
 102 }
 103
 104 TEST(SmallPtrSetTest, CopyAndMoveTest) {
 105   int buf[8];
 106   for (int i = 0; i < 8; ++i)
 107     buf[i] = 0;
 108
 109   SmallPtrSet<int *, 4> s1;
 110   s1.insert(&buf[0]);
 111   s1.insert(&buf[1]);
 112   s1.insert(&buf[2]);
 113   s1.insert(&buf[3]);
 114   EXPECT_EQ(4U, s1.size());
 115   for (int i = 0; i < 8; ++i)
 116     if (i < 4)
 117       EXPECT_TRUE(s1.count(&buf[i]));
 118     else
 119       EXPECT_FALSE(s1.count(&buf[i]));
 120
 121   SmallPtrSet<int *, 4> s2(s1);
 122   EXPECT_EQ(4U, s2.size());
 123   for (int i = 0; i < 8; ++i)
 124     if (i < 4)
 125       EXPECT_TRUE(s2.count(&buf[i]));
 126     else
 127       EXPECT_FALSE(s2.count(&buf[i]));
 128
 129   s1 = s2;
 130   EXPECT_EQ(4U, s1.size());
 131   EXPECT_EQ(4U, s2.size());
 132   for (int i = 0; i < 8; ++i)
 133     if (i < 4)
 134       EXPECT_TRUE(s1.count(&buf[i]));
 135     else
 136       EXPECT_FALSE(s1.count(&buf[i]));
 137
 138   SmallPtrSet<int *, 4> s3(std::move(s1));
 139   EXPECT_EQ(4U, s3.size());
 140   EXPECT_TRUE(s1.empty());
 141   for (int i = 0; i < 8; ++i)
 142     if (i < 4)
 143       EXPECT_TRUE(s3.count(&buf[i]));
 144     else
 145       EXPECT_FALSE(s3.count(&buf[i]));
 146
 147   // Move assign into the moved-from object. Also test move of a non-small
 148   // container.
 149   s3.insert(&buf[4]);
 150   s3.insert(&buf[5]);
 151   s3.insert(&buf[6]);
 152   s3.insert(&buf[7]);
 153   s1 = std::move(s3);
 154   EXPECT_EQ(8U, s1.size());
 155   EXPECT_TRUE(s3.empty());
 156   for (int i = 0; i < 8; ++i)
 157     EXPECT_TRUE(s1.count(&buf[i]));
 158
 159   // Copy assign into a moved-from object.
 160   s3 = s1;
 161   EXPECT_EQ(8U, s3.size());
 162   EXPECT_EQ(8U, s1.size());
 163   for (int i = 0; i < 8; ++i)
 164     EXPECT_TRUE(s3.count(&buf[i]));
 165 }
 166
 167 TEST(SmallPtrSetTest, SwapTest) {
 168   int buf[10];
 169
 170   SmallPtrSet<int *, 2> a;
 171   SmallPtrSet<int *, 2> b;
 172
 173   a.insert(&buf[0]);
 174   a.insert(&buf[1]);
 175   b.insert(&buf[2]);
 176
 177   EXPECT_EQ(2U, a.size());
 178   EXPECT_EQ(1U, b.size());
 179   EXPECT_TRUE(a.count(&buf[0]));
 180   EXPECT_TRUE(a.count(&buf[1]));
 181   EXPECT_FALSE(a.count(&buf[2]));
 182   EXPECT_FALSE(a.count(&buf[3]));
 183   EXPECT_FALSE(b.count(&buf[0]));
 184   EXPECT_FALSE(b.count(&buf[1]));
 185   EXPECT_TRUE(b.count(&buf[2]));
 186   EXPECT_FALSE(b.count(&buf[3]));
 187
 188   std::swap(a, b);
 189
 190   EXPECT_EQ(1U, a.size());
 191   EXPECT_EQ(2U, b.size());
 192   EXPECT_FALSE(a.count(&buf[0]));
 193   EXPECT_FALSE(a.count(&buf[1]));
 194   EXPECT_TRUE(a.count(&buf[2]));
 195   EXPECT_FALSE(a.count(&buf[3]));
 196   EXPECT_TRUE(b.count(&buf[0]));
 197   EXPECT_TRUE(b.count(&buf[1]));
 198   EXPECT_FALSE(b.count(&buf[2]));
 199   EXPECT_FALSE(b.count(&buf[3]));
 200
 201   b.insert(&buf[3]);
 202   std::swap(a, b);
 203
 204   EXPECT_EQ(3U, a.size());
 205   EXPECT_EQ(1U, b.size());
 206   EXPECT_TRUE(a.count(&buf[0]));
 207   EXPECT_TRUE(a.count(&buf[1]));
 208   EXPECT_FALSE(a.count(&buf[2]));
 209   EXPECT_TRUE(a.count(&buf[3]));
 210   EXPECT_FALSE(b.count(&buf[0]));
 211   EXPECT_FALSE(b.count(&buf[1]));
 212   EXPECT_TRUE(b.count(&buf[2]));
 213   EXPECT_FALSE(b.count(&buf[3]));
 214
 215   std::swap(a, b);
 216
 217   EXPECT_EQ(1U, a.size());
 218   EXPECT_EQ(3U, b.size());
 219   EXPECT_FALSE(a.count(&buf[0]));
 220   EXPECT_FALSE(a.count(&buf[1]));
 221   EXPECT_TRUE(a.count(&buf[2]));
 222   EXPECT_FALSE(a.count(&buf[3]));
 223   EXPECT_TRUE(b.count(&buf[0]));
 224   EXPECT_TRUE(b.count(&buf[1]));
 225   EXPECT_FALSE(b.count(&buf[2]));
 226   EXPECT_TRUE(b.count(&buf[3]));
 227
 228   a.insert(&buf[4]);
 229   a.insert(&buf[5]);
 230   a.insert(&buf[6]);
 231
 232   std::swap(b, a);
 233
 234   EXPECT_EQ(3U, a.size());
 235   EXPECT_EQ(4U, b.size());
 236   EXPECT_TRUE(b.count(&buf[2]));
 237   EXPECT_TRUE(b.count(&buf[4]));
 238   EXPECT_TRUE(b.count(&buf[5]));
 239   EXPECT_TRUE(b.count(&buf[6]));
 240   EXPECT_TRUE(a.count(&buf[0]));
 241   EXPECT_TRUE(a.count(&buf[1]));
 242   EXPECT_TRUE(a.count(&buf[3]));
 243 }
 244
 245 void checkEraseAndIterators(SmallPtrSetImpl<int*> &S) {
 246   int buf[3];
 247
 248   S.insert(&buf[0]);
 249   S.insert(&buf[1]);
 250   S.insert(&buf[2]);
 251
 252   // Iterators must still be valid after erase() calls;
 253   auto B = S.begin();
 254   auto M = std::next(B);
 255   auto E = S.end();
 256   EXPECT_TRUE(*B == &buf[0] || *B == &buf[1] || *B == &buf[2]);
 257   EXPECT_TRUE(*M == &buf[0] || *M == &buf[1] || *M == &buf[2]);
 258   EXPECT_TRUE(*B != *M);
 259   int *Removable = *std::next(M);
 260   // No iterator points to Removable now.
 261   EXPECT_TRUE(Removable == &buf[0] || Removable == &buf[1] ||
 262               Removable == &buf[2]);
 263   EXPECT_TRUE(Removable != *B && Removable != *M);
 264
 265   S.erase(Removable);
 266
 267   // B,M,E iterators should still be valid
 268   EXPECT_EQ(B, S.begin());
 269   EXPECT_EQ(M, std::next(B));
 270   EXPECT_EQ(E, S.end());
 271   EXPECT_EQ(std::next(M), E);
 272 }
 273
 274 TEST(SmallPtrSetTest, EraseTest) {
 275   // Test when set stays small.
 276   SmallPtrSet<int *, 8> B;
 277   checkEraseAndIterators(B);
 278
 279   // Test when set grows big.
 280   SmallPtrSet<int *, 2> A;
 281   checkEraseAndIterators(A);
 282 }
 283
 284 // Verify that dereferencing and iteration work.
 285 TEST(SmallPtrSetTest, dereferenceAndIterate) {
 286   int Ints[] = {0, 1, 2, 3, 4, 5, 6, 7};
 287   SmallPtrSet<const int *, 4> S;
 288   for (int &I : Ints) {
 289     EXPECT_EQ(&I, *S.insert(&I).first);
 290     EXPECT_EQ(&I, *S.find(&I));
 291   }
 292
 293   // Iterate from each and count how many times each element is found.
 294   int Found[sizeof(Ints)/sizeof(int)] = {0};
 295   for (int &I : Ints)
 296     for (auto F = S.find(&I), E = S.end(); F != E; ++F)
 297       ++Found[*F - Ints];
 298
 299   // Sort.  We should hit the first element just once and the final element N
 300   // times.
 301   llvm::sort(std::begin(Found), std::end(Found));
 302   for (auto F = std::begin(Found), E = std::end(Found); F != E; ++F)
 303     EXPECT_EQ(F - Found + 1, *F);
 304 }
 305
 306 // Verify that const pointers work for count and find even when the underlying
 307 // SmallPtrSet is not for a const pointer type.
 308 TEST(SmallPtrSetTest, ConstTest) {
 309   SmallPtrSet<int *, 8> IntSet;
 310   int A;
 311   int *B = &A;
 312   const int *C = &A;
 313   IntSet.insert(B);
 314   EXPECT_EQ(IntSet.count(B), 1u);
 315   EXPECT_EQ(IntSet.count(C), 1u);
 316   EXPECT_NE(IntSet.find(B), IntSet.end());
 317   EXPECT_NE(IntSet.find(C), IntSet.end());
 318 }
 319
 320 // Verify that we automatically get the const version of PointerLikeTypeTraits
 321 // filled in for us, even for a non-pointer type
 322 using TestPair = PointerIntPair<int *, 1>;
 323
 324 TEST(SmallPtrSetTest, ConstNonPtrTest) {
 325   SmallPtrSet<TestPair, 8> IntSet;
 326   int A[1];
 327   TestPair Pair(&A[0], 1);
 328   IntSet.insert(Pair);
 329   EXPECT_EQ(IntSet.count(Pair), 1u);
 330   EXPECT_NE(IntSet.find(Pair), IntSet.end());
 331 }