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