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