unittests/ADT/SmallPtrSetTest.cpp

   1 //===- llvm/unittest/ADT/SmallPtrSetTest.cpp ------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // SmallPtrSet unit tests.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/ADT/SmallPtrSet.h"
  15 #include "llvm/ADT/PointerIntPair.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 = 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   std::sort(std::begin(Found), std::end(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_NE(IntSet.find(B), IntSet.end());
 318   EXPECT_NE(IntSet.find(C), IntSet.end());
 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_NE(IntSet.find(Pair), IntSet.end());
 332 }