unittests/ADT/TinyPtrVectorTest.cpp

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