unittests/ADT/TinyPtrVectorTest.cpp

   1 //===- llvm/unittest/ADT/TinyPtrVectorTest.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 // TinyPtrVector unit tests.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "gtest/gtest.h"
  15 #include "llvm/ADT/ArrayRef.h"
  16 #include "llvm/ADT/SmallVector.h"
  17 #include "llvm/ADT/STLExtras.h"
  18 #include "llvm/ADT/TinyPtrVector.h"
  19 #include "llvm/Support/type_traits.h"
  20 #include <algorithm>
  21 #include <list>
  22 #include <vector>
  23
  24 using namespace llvm;
  25
  26 namespace {
  27
  28 // The world's worst RNG, but it is deterministic and makes it easy to get
  29 // *some* shuffling of elements.
  30 static ptrdiff_t test_shuffle_rng(ptrdiff_t i) {
  31   return (i + i * 33) % i;
  32 }
  33 static ptrdiff_t (*test_shuffle_rng_p)(ptrdiff_t) = &test_shuffle_rng;
  34
  35 template <typename VectorT>
  36 class TinyPtrVectorTest : public testing::Test {
  37 protected:
  38   typedef typename VectorT::value_type PtrT;
  39   typedef typename remove_pointer<PtrT>::type ValueT;
  40
  41   VectorT V;
  42   VectorT V2;
  43
  44   ValueT TestValues[1024];
  45   std::vector<PtrT> TestPtrs;
  46
  47   TinyPtrVectorTest() {
  48     for (size_t i = 0, e = array_lengthof(TestValues); i != e; ++i)
  49       TestPtrs.push_back(&TestValues[i]);
  50
  51     std::random_shuffle(TestPtrs.begin(), TestPtrs.end(), test_shuffle_rng_p);
  52   }
  53
  54   ArrayRef<PtrT> testArray(size_t N) {
  55     return makeArrayRef(&TestPtrs[0], N);
  56   }
  57
  58   void appendValues(VectorT &V, ArrayRef<PtrT> Values) {
  59     for (size_t i = 0, e = Values.size(); i != e; ++i)
  60       V.push_back(Values[i]);
  61   }
  62
  63   void setVectors(ArrayRef<PtrT> Values1, ArrayRef<PtrT> Values2) {
  64     V.clear();
  65     appendValues(V, Values1);
  66     V2.clear();
  67     appendValues(V2, Values2);
  68   }
  69
  70   void expectValues(const VectorT &V, ArrayRef<PtrT> Values) {
  71     EXPECT_EQ(Values.empty(), V.empty());
  72     EXPECT_EQ(Values.size(), V.size());
  73     for (size_t i = 0, e = Values.size(); i != e; ++i) {
  74       EXPECT_EQ(Values[i], V[i]);
  75       EXPECT_EQ(Values[i], *llvm::next(V.begin(), i));
  76     }
  77     EXPECT_EQ(V.end(), llvm::next(V.begin(), Values.size()));
  78   }
  79 };
  80
  81 typedef ::testing::Types<TinyPtrVector<int*>,
  82                          TinyPtrVector<double*>
  83                          > TinyPtrVectorTestTypes;
  84 TYPED_TEST_CASE(TinyPtrVectorTest, TinyPtrVectorTestTypes);
  85
  86 TYPED_TEST(TinyPtrVectorTest, EmptyTest) {
  87   this->expectValues(this->V, this->testArray(0));
  88 }
  89
  90 TYPED_TEST(TinyPtrVectorTest, PushPopBack) {
  91   this->V.push_back(this->TestPtrs[0]);
  92   this->expectValues(this->V, this->testArray(1));
  93   this->V.push_back(this->TestPtrs[1]);
  94   this->expectValues(this->V, this->testArray(2));
  95   this->V.push_back(this->TestPtrs[2]);
  96   this->expectValues(this->V, this->testArray(3));
  97   this->V.push_back(this->TestPtrs[3]);
  98   this->expectValues(this->V, this->testArray(4));
  99   this->V.push_back(this->TestPtrs[4]);
 100   this->expectValues(this->V, this->testArray(5));
 101
 102   // Pop and clobber a few values to keep things interesting.
 103   this->V.pop_back();
 104   this->expectValues(this->V, this->testArray(4));
 105   this->V.pop_back();
 106   this->expectValues(this->V, this->testArray(3));
 107   this->TestPtrs[3] = &this->TestValues[42];
 108   this->TestPtrs[4] = &this->TestValues[43];
 109   this->V.push_back(this->TestPtrs[3]);
 110   this->expectValues(this->V, this->testArray(4));
 111   this->V.push_back(this->TestPtrs[4]);
 112   this->expectValues(this->V, this->testArray(5));
 113
 114   this->V.pop_back();
 115   this->expectValues(this->V, this->testArray(4));
 116   this->V.pop_back();
 117   this->expectValues(this->V, this->testArray(3));
 118   this->V.pop_back();
 119   this->expectValues(this->V, this->testArray(2));
 120   this->V.pop_back();
 121   this->expectValues(this->V, this->testArray(1));
 122   this->V.pop_back();
 123   this->expectValues(this->V, this->testArray(0));
 124
 125   this->appendValues(this->V, this->testArray(42));
 126   this->expectValues(this->V, this->testArray(42));
 127 }
 128
 129 TYPED_TEST(TinyPtrVectorTest, ClearTest) {
 130   this->expectValues(this->V, this->testArray(0));
 131   this->V.clear();
 132   this->expectValues(this->V, this->testArray(0));
 133
 134   this->appendValues(this->V, this->testArray(1));
 135   this->expectValues(this->V, this->testArray(1));
 136   this->V.clear();
 137   this->expectValues(this->V, this->testArray(0));
 138
 139   this->appendValues(this->V, this->testArray(42));
 140   this->expectValues(this->V, this->testArray(42));
 141   this->V.clear();
 142   this->expectValues(this->V, this->testArray(0));
 143 }
 144
 145 TYPED_TEST(TinyPtrVectorTest, CopyAndMoveCtorTest) {
 146   this->appendValues(this->V, this->testArray(42));
 147   TypeParam Copy(this->V);
 148   this->expectValues(Copy, this->testArray(42));
 149
 150   // This is a separate copy, and so it shouldn't destroy the original.
 151   Copy.clear();
 152   this->expectValues(Copy, this->testArray(0));
 153   this->expectValues(this->V, this->testArray(42));
 154
 155   TypeParam Copy2(this->V2);
 156   this->appendValues(Copy2, this->testArray(42));
 157   this->expectValues(Copy2, this->testArray(42));
 158   this->expectValues(this->V2, this->testArray(0));
 159
 160 #if LLVM_HAS_RVALUE_REFERENCES
 161   TypeParam Move(std::move(Copy2));
 162   this->expectValues(Move, this->testArray(42));
 163   this->expectValues(Copy2, this->testArray(0));
 164 #endif
 165 }
 166
 167 TYPED_TEST(TinyPtrVectorTest, CopyAndMoveTest) {
 168   this->V = this->V2;
 169   this->expectValues(this->V, this->testArray(0));
 170   this->expectValues(this->V2, this->testArray(0));
 171 #if LLVM_HAS_RVALUE_REFERENCES
 172   this->V = std::move(this->V2);
 173   this->expectValues(this->V, this->testArray(0));
 174 #endif
 175
 176   this->setVectors(this->testArray(1), this->testArray(0));
 177   this->V = this->V2;
 178   this->expectValues(this->V, this->testArray(0));
 179   this->expectValues(this->V2, this->testArray(0));
 180 #if LLVM_HAS_RVALUE_REFERENCES
 181   this->setVectors(this->testArray(1), this->testArray(0));
 182   this->V = std::move(this->V2);
 183   this->expectValues(this->V, this->testArray(0));
 184 #endif
 185
 186   this->setVectors(this->testArray(2), this->testArray(0));
 187   this->V = this->V2;
 188   this->expectValues(this->V, this->testArray(0));
 189   this->expectValues(this->V2, this->testArray(0));
 190 #if LLVM_HAS_RVALUE_REFERENCES
 191   this->setVectors(this->testArray(2), this->testArray(0));
 192   this->V = std::move(this->V2);
 193   this->expectValues(this->V, this->testArray(0));
 194 #endif
 195
 196   this->setVectors(this->testArray(42), this->testArray(0));
 197   this->V = this->V2;
 198   this->expectValues(this->V, this->testArray(0));
 199   this->expectValues(this->V2, this->testArray(0));
 200 #if LLVM_HAS_RVALUE_REFERENCES
 201   this->setVectors(this->testArray(42), this->testArray(0));
 202   this->V = std::move(this->V2);
 203   this->expectValues(this->V, this->testArray(0));
 204 #endif
 205
 206   this->setVectors(this->testArray(0), this->testArray(1));
 207   this->V = this->V2;
 208   this->expectValues(this->V, this->testArray(1));
 209   this->expectValues(this->V2, this->testArray(1));
 210 #if LLVM_HAS_RVALUE_REFERENCES
 211   this->setVectors(this->testArray(0), this->testArray(1));
 212   this->V = std::move(this->V2);
 213   this->expectValues(this->V, this->testArray(1));
 214 #endif
 215
 216   this->setVectors(this->testArray(0), this->testArray(2));
 217   this->V = this->V2;
 218   this->expectValues(this->V, this->testArray(2));
 219   this->expectValues(this->V2, this->testArray(2));
 220 #if LLVM_HAS_RVALUE_REFERENCES
 221   this->setVectors(this->testArray(0), this->testArray(2));
 222   this->V = std::move(this->V2);
 223   this->expectValues(this->V, this->testArray(2));
 224 #endif
 225
 226   this->setVectors(this->testArray(0), this->testArray(42));
 227   this->V = this->V2;
 228   this->expectValues(this->V, this->testArray(42));
 229   this->expectValues(this->V2, this->testArray(42));
 230 #if LLVM_HAS_RVALUE_REFERENCES
 231   this->setVectors(this->testArray(0), this->testArray(42));
 232   this->V = std::move(this->V2);
 233   this->expectValues(this->V, this->testArray(42));
 234 #endif
 235
 236   this->setVectors(this->testArray(1), this->testArray(1));
 237   this->V = this->V2;
 238   this->expectValues(this->V, this->testArray(1));
 239   this->expectValues(this->V2, this->testArray(1));
 240 #if LLVM_HAS_RVALUE_REFERENCES
 241   this->V = std::move(this->V2);
 242   this->expectValues(this->V, this->testArray(1));
 243 #endif
 244
 245   this->setVectors(this->testArray(1), this->testArray(2));
 246   this->V = this->V2;
 247   this->expectValues(this->V, this->testArray(2));
 248   this->expectValues(this->V2, this->testArray(2));
 249 #if LLVM_HAS_RVALUE_REFERENCES
 250   this->setVectors(this->testArray(1), this->testArray(2));
 251   this->V = std::move(this->V2);
 252   this->expectValues(this->V, this->testArray(2));
 253 #endif
 254
 255   this->setVectors(this->testArray(1), this->testArray(42));
 256   this->V = this->V2;
 257   this->expectValues(this->V, this->testArray(42));
 258   this->expectValues(this->V2, this->testArray(42));
 259 #if LLVM_HAS_RVALUE_REFERENCES
 260   this->setVectors(this->testArray(1), this->testArray(42));
 261   this->V = std::move(this->V2);
 262   this->expectValues(this->V, this->testArray(42));
 263 #endif
 264
 265   this->setVectors(this->testArray(2), this->testArray(1));
 266   this->V = this->V2;
 267   this->expectValues(this->V, this->testArray(1));
 268   this->expectValues(this->V2, this->testArray(1));
 269 #if LLVM_HAS_RVALUE_REFERENCES
 270   this->setVectors(this->testArray(2), this->testArray(1));
 271   this->V = std::move(this->V2);
 272   this->expectValues(this->V, this->testArray(1));
 273 #endif
 274
 275   this->setVectors(this->testArray(2), this->testArray(2));
 276   this->V = this->V2;
 277   this->expectValues(this->V, this->testArray(2));
 278   this->expectValues(this->V2, this->testArray(2));
 279 #if LLVM_HAS_RVALUE_REFERENCES
 280   this->setVectors(this->testArray(2), this->testArray(2));
 281   this->V = std::move(this->V2);
 282   this->expectValues(this->V, this->testArray(2));
 283 #endif
 284
 285   this->setVectors(this->testArray(2), this->testArray(42));
 286   this->V = this->V2;
 287   this->expectValues(this->V, this->testArray(42));
 288   this->expectValues(this->V2, this->testArray(42));
 289 #if LLVM_HAS_RVALUE_REFERENCES
 290   this->setVectors(this->testArray(2), this->testArray(42));
 291   this->V = std::move(this->V2);
 292   this->expectValues(this->V, this->testArray(42));
 293 #endif
 294
 295   this->setVectors(this->testArray(42), this->testArray(1));
 296   this->V = this->V2;
 297   this->expectValues(this->V, this->testArray(1));
 298   this->expectValues(this->V2, this->testArray(1));
 299 #if LLVM_HAS_RVALUE_REFERENCES
 300   this->setVectors(this->testArray(42), this->testArray(1));
 301   this->V = std::move(this->V2);
 302   this->expectValues(this->V, this->testArray(1));
 303 #endif
 304
 305   this->setVectors(this->testArray(42), this->testArray(2));
 306   this->V = this->V2;
 307   this->expectValues(this->V, this->testArray(2));
 308   this->expectValues(this->V2, this->testArray(2));
 309 #if LLVM_HAS_RVALUE_REFERENCES
 310   this->setVectors(this->testArray(42), this->testArray(2));
 311   this->V = std::move(this->V2);
 312   this->expectValues(this->V, this->testArray(2));
 313 #endif
 314
 315   this->setVectors(this->testArray(42), this->testArray(42));
 316   this->V = this->V2;
 317   this->expectValues(this->V, this->testArray(42));
 318   this->expectValues(this->V2, this->testArray(42));
 319 #if LLVM_HAS_RVALUE_REFERENCES
 320   this->setVectors(this->testArray(42), this->testArray(42));
 321   this->V = std::move(this->V2);
 322   this->expectValues(this->V, this->testArray(42));
 323 #endif
 324 }
 325
 326 TYPED_TEST(TinyPtrVectorTest, EraseTest) {
 327   this->appendValues(this->V, this->testArray(1));
 328   this->expectValues(this->V, this->testArray(1));
 329   this->V.erase(this->V.begin());
 330   this->expectValues(this->V, this->testArray(0));
 331
 332   this->appendValues(this->V, this->testArray(42));
 333   this->expectValues(this->V, this->testArray(42));
 334   this->V.erase(this->V.begin());
 335   this->TestPtrs.erase(this->TestPtrs.begin());
 336   this->expectValues(this->V, this->testArray(41));
 337   this->V.erase(llvm::next(this->V.begin(), 1));
 338   this->TestPtrs.erase(llvm::next(this->TestPtrs.begin(), 1));
 339   this->expectValues(this->V, this->testArray(40));
 340   this->V.erase(llvm::next(this->V.begin(), 2));
 341   this->TestPtrs.erase(llvm::next(this->TestPtrs.begin(), 2));
 342   this->expectValues(this->V, this->testArray(39));
 343   this->V.erase(llvm::next(this->V.begin(), 5));
 344   this->TestPtrs.erase(llvm::next(this->TestPtrs.begin(), 5));
 345   this->expectValues(this->V, this->testArray(38));
 346   this->V.erase(llvm::next(this->V.begin(), 13));
 347   this->TestPtrs.erase(llvm::next(this->TestPtrs.begin(), 13));
 348   this->expectValues(this->V, this->testArray(37));
 349
 350   typename TypeParam::iterator I = this->V.begin();
 351   do {
 352     I = this->V.erase(I);
 353   } while (I != this->V.end());
 354   this->expectValues(this->V, this->testArray(0));
 355 }
 356
 357 TYPED_TEST(TinyPtrVectorTest, EraseRangeTest) {
 358   this->appendValues(this->V, this->testArray(1));
 359   this->expectValues(this->V, this->testArray(1));
 360   this->V.erase(this->V.begin(), this->V.begin());
 361   this->expectValues(this->V, this->testArray(1));
 362   this->V.erase(this->V.end(), this->V.end());
 363   this->expectValues(this->V, this->testArray(1));
 364   this->V.erase(this->V.begin(), this->V.end());
 365   this->expectValues(this->V, this->testArray(0));
 366
 367   this->appendValues(this->V, this->testArray(42));
 368   this->expectValues(this->V, this->testArray(42));
 369   this->V.erase(this->V.begin(), llvm::next(this->V.begin(), 1));
 370   this->TestPtrs.erase(this->TestPtrs.begin(),
 371                        llvm::next(this->TestPtrs.begin(), 1));
 372   this->expectValues(this->V, this->testArray(41));
 373   this->V.erase(llvm::next(this->V.begin(), 1), llvm::next(this->V.begin(), 2));
 374   this->TestPtrs.erase(llvm::next(this->TestPtrs.begin(), 1),
 375                        llvm::next(this->TestPtrs.begin(), 2));
 376   this->expectValues(this->V, this->testArray(40));
 377   this->V.erase(llvm::next(this->V.begin(), 2), llvm::next(this->V.begin(), 4));
 378   this->TestPtrs.erase(llvm::next(this->TestPtrs.begin(), 2),
 379                        llvm::next(this->TestPtrs.begin(), 4));
 380   this->expectValues(this->V, this->testArray(38));
 381   this->V.erase(llvm::next(this->V.begin(), 5), llvm::next(this->V.begin(), 10));
 382   this->TestPtrs.erase(llvm::next(this->TestPtrs.begin(), 5),
 383                        llvm::next(this->TestPtrs.begin(), 10));
 384   this->expectValues(this->V, this->testArray(33));
 385   this->V.erase(llvm::next(this->V.begin(), 13), llvm::next(this->V.begin(), 26));
 386   this->TestPtrs.erase(llvm::next(this->TestPtrs.begin(), 13),
 387                        llvm::next(this->TestPtrs.begin(), 26));
 388   this->expectValues(this->V, this->testArray(20));
 389   this->V.erase(llvm::next(this->V.begin(), 7), this->V.end());
 390   this->expectValues(this->V, this->testArray(7));
 391   this->V.erase(this->V.begin(), this->V.end());
 392   this->expectValues(this->V, this->testArray(0));
 393 }
 394
 395 TYPED_TEST(TinyPtrVectorTest, Insert) {
 396   this->V.insert(this->V.end(), this->TestPtrs[0]);
 397   this->expectValues(this->V, this->testArray(1));
 398   this->V.clear();
 399   this->appendValues(this->V, this->testArray(4));
 400   this->expectValues(this->V, this->testArray(4));
 401   this->V.insert(this->V.end(), this->TestPtrs[4]);
 402   this->expectValues(this->V, this->testArray(5));
 403   this->V.insert(this->V.begin(), this->TestPtrs[42]);
 404   this->TestPtrs.insert(this->TestPtrs.begin(), this->TestPtrs[42]);
 405   this->expectValues(this->V, this->testArray(6));
 406   this->V.insert(llvm::next(this->V.begin(), 3), this->TestPtrs[43]);
 407   this->TestPtrs.insert(llvm::next(this->TestPtrs.begin(), 3),
 408                         this->TestPtrs[43]);
 409   this->expectValues(this->V, this->testArray(7));
 410 }
 411
 412 TYPED_TEST(TinyPtrVectorTest, InsertRange) {
 413   this->V.insert(this->V.end(), this->TestPtrs.begin(), this->TestPtrs.begin());
 414   this->expectValues(this->V, this->testArray(0));
 415   this->V.insert(this->V.begin(), this->TestPtrs.begin(),
 416                  this->TestPtrs.begin());
 417   this->expectValues(this->V, this->testArray(0));
 418   this->V.insert(this->V.end(), this->TestPtrs.end(), this->TestPtrs.end());
 419   this->expectValues(this->V, this->testArray(0));
 420   this->V.insert(this->V.end(), this->TestPtrs.begin(),
 421                  llvm::next(this->TestPtrs.begin()));
 422   this->expectValues(this->V, this->testArray(1));
 423   this->V.clear();
 424   this->V.insert(this->V.end(), this->TestPtrs.begin(),
 425                  llvm::next(this->TestPtrs.begin(), 2));
 426   this->expectValues(this->V, this->testArray(2));
 427   this->V.clear();
 428   this->V.insert(this->V.end(), this->TestPtrs.begin(),
 429                  llvm::next(this->TestPtrs.begin(), 42));
 430   this->expectValues(this->V, this->testArray(42));
 431   this->V.clear();
 432   this->V.insert(this->V.end(),
 433                  llvm::next(this->TestPtrs.begin(), 5),
 434                  llvm::next(this->TestPtrs.begin(), 13));
 435   this->V.insert(this->V.begin(),
 436                  llvm::next(this->TestPtrs.begin(), 0),
 437                  llvm::next(this->TestPtrs.begin(), 3));
 438   this->V.insert(llvm::next(this->V.begin(), 2),
 439                  llvm::next(this->TestPtrs.begin(), 2),
 440                  llvm::next(this->TestPtrs.begin(), 4));
 441   this->V.erase(llvm::next(this->V.begin(), 4));
 442   this->V.insert(llvm::next(this->V.begin(), 4),
 443                  llvm::next(this->TestPtrs.begin(), 4),
 444                  llvm::next(this->TestPtrs.begin(), 5));
 445   this->expectValues(this->V, this->testArray(13));
 446 }
 447
 448 }