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 expectValues(const VectorT &V, ArrayRef<PtrT> Values) {
  64     EXPECT_EQ(Values.empty(), V.empty());
  65     EXPECT_EQ(Values.size(), V.size());
  66     for (size_t i = 0, e = Values.size(); i != e; ++i) {
  67       EXPECT_EQ(Values[i], V[i]);
  68       EXPECT_EQ(Values[i], *llvm::next(V.begin(), i));
  69     }
  70     EXPECT_EQ(V.end(), llvm::next(V.begin(), Values.size()));
  71   }
  72 };
  73
  74 typedef ::testing::Types<TinyPtrVector<int*>,
  75                          TinyPtrVector<double*>
  76                          > TinyPtrVectorTestTypes;
  77 TYPED_TEST_CASE(TinyPtrVectorTest, TinyPtrVectorTestTypes);
  78
  79 TYPED_TEST(TinyPtrVectorTest, EmptyTest) {
  80   this->expectValues(this->V, this->testArray(0));
  81 }
  82
  83 TYPED_TEST(TinyPtrVectorTest, PushPopBack) {
  84   this->V.push_back(this->TestPtrs[0]);
  85   this->expectValues(this->V, this->testArray(1));
  86   this->V.push_back(this->TestPtrs[1]);
  87   this->expectValues(this->V, this->testArray(2));
  88   this->V.push_back(this->TestPtrs[2]);
  89   this->expectValues(this->V, this->testArray(3));
  90   this->V.push_back(this->TestPtrs[3]);
  91   this->expectValues(this->V, this->testArray(4));
  92   this->V.push_back(this->TestPtrs[4]);
  93   this->expectValues(this->V, this->testArray(5));
  94
  95   // Pop and clobber a few values to keep things interesting.
  96   this->V.pop_back();
  97   this->expectValues(this->V, this->testArray(4));
  98   this->V.pop_back();
  99   this->expectValues(this->V, this->testArray(3));
 100   this->TestPtrs[3] = &this->TestValues[42];
 101   this->TestPtrs[4] = &this->TestValues[43];
 102   this->V.push_back(this->TestPtrs[3]);
 103   this->expectValues(this->V, this->testArray(4));
 104   this->V.push_back(this->TestPtrs[4]);
 105   this->expectValues(this->V, this->testArray(5));
 106
 107   this->V.pop_back();
 108   this->expectValues(this->V, this->testArray(4));
 109   this->V.pop_back();
 110   this->expectValues(this->V, this->testArray(3));
 111   this->V.pop_back();
 112   this->expectValues(this->V, this->testArray(2));
 113   this->V.pop_back();
 114   this->expectValues(this->V, this->testArray(1));
 115   this->V.pop_back();
 116   this->expectValues(this->V, this->testArray(0));
 117
 118   this->appendValues(this->V, this->testArray(42));
 119   this->expectValues(this->V, this->testArray(42));
 120 }
 121
 122 TYPED_TEST(TinyPtrVectorTest, ClearTest) {
 123   this->expectValues(this->V, this->testArray(0));
 124   this->V.clear();
 125   this->expectValues(this->V, this->testArray(0));
 126
 127   this->appendValues(this->V, this->testArray(1));
 128   this->expectValues(this->V, this->testArray(1));
 129   this->V.clear();
 130   this->expectValues(this->V, this->testArray(0));
 131
 132   this->appendValues(this->V, this->testArray(42));
 133   this->expectValues(this->V, this->testArray(42));
 134   this->V.clear();
 135   this->expectValues(this->V, this->testArray(0));
 136 }
 137
 138 TYPED_TEST(TinyPtrVectorTest, CopyAndMoveCtorTest) {
 139   this->appendValues(this->V, this->testArray(42));
 140   TypeParam Copy(this->V);
 141   this->expectValues(Copy, this->testArray(42));
 142
 143   // This is a separate copy, and so it shouldn't destroy the original.
 144   Copy.clear();
 145   this->expectValues(Copy, this->testArray(0));
 146   this->expectValues(this->V, this->testArray(42));
 147
 148   TypeParam Copy2(this->V2);
 149   this->appendValues(Copy2, this->testArray(42));
 150   this->expectValues(Copy2, this->testArray(42));
 151   this->expectValues(this->V2, this->testArray(0));
 152
 153 #if LLVM_USE_RVALUE_REFERENCES
 154   TypeParam Move(std::move(Copy2));
 155   this->expectValues(Move, this->testArray(42));
 156   this->expectValues(Copy2, this->testArray(0));
 157 #endif
 158 }
 159
 160 TYPED_TEST(TinyPtrVectorTest, EraseTest) {
 161   this->appendValues(this->V, this->testArray(1));
 162   this->expectValues(this->V, this->testArray(1));
 163   this->V.erase(this->V.begin());
 164   this->expectValues(this->V, this->testArray(0));
 165
 166   this->appendValues(this->V, this->testArray(42));
 167   this->expectValues(this->V, this->testArray(42));
 168   this->V.erase(this->V.begin());
 169   this->TestPtrs.erase(this->TestPtrs.begin());
 170   this->expectValues(this->V, this->testArray(41));
 171   this->V.erase(llvm::next(this->V.begin(), 1));
 172   this->TestPtrs.erase(llvm::next(this->TestPtrs.begin(), 1));
 173   this->expectValues(this->V, this->testArray(40));
 174   this->V.erase(llvm::next(this->V.begin(), 2));
 175   this->TestPtrs.erase(llvm::next(this->TestPtrs.begin(), 2));
 176   this->expectValues(this->V, this->testArray(39));
 177   this->V.erase(llvm::next(this->V.begin(), 5));
 178   this->TestPtrs.erase(llvm::next(this->TestPtrs.begin(), 5));
 179   this->expectValues(this->V, this->testArray(38));
 180   this->V.erase(llvm::next(this->V.begin(), 13));
 181   this->TestPtrs.erase(llvm::next(this->TestPtrs.begin(), 13));
 182   this->expectValues(this->V, this->testArray(37));
 183
 184   typename TypeParam::iterator I = this->V.begin();
 185   do {
 186     I = this->V.erase(I);
 187   } while (I != this->V.end());
 188   this->expectValues(this->V, this->testArray(0));
 189 }
 190
 191 }