Home | History | Annotate | Download | only in ADT 
      1 //===- llvm/unittest/ADT/SmallVectorTest.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 // SmallVector unit tests.
     11 //
     12 //===----------------------------------------------------------------------===//
     13 
     14 #include "llvm/ADT/SmallVector.h"
     15 #include "llvm/Support/Compiler.h"
     16 #include "gtest/gtest.h"
     17 #include <list>
     18 #include <stdarg.h>
     19 
     20 using namespace llvm;
     21 
     22 namespace {
     23 
     24 /// A helper class that counts the total number of constructor and
     25 /// destructor calls.
     26 class Constructable {
     27 private:
     28   static int numConstructorCalls;
     29   static int numDestructorCalls;
     30   static int numAssignmentCalls;
     31 
     32   int value;
     33 
     34 public:
     35   Constructable() : value(0) {
     36     ++numConstructorCalls;
     37   }
     38 
     39   Constructable(int val) : value(val) {
     40     ++numConstructorCalls;
     41   }
     42 
     43   Constructable(const Constructable & src) {
     44     value = src.value;
     45     ++numConstructorCalls;
     46   }
     47 
     48   ~Constructable() {
     49     ++numDestructorCalls;
     50   }
     51 
     52   Constructable & operator=(const Constructable & src) {
     53     value = src.value;
     54     ++numAssignmentCalls;
     55     return *this;
     56   }
     57 
     58   int getValue() const {
     59     return abs(value);
     60   }
     61 
     62   static void reset() {
     63     numConstructorCalls = 0;
     64     numDestructorCalls = 0;
     65     numAssignmentCalls = 0;
     66   }
     67 
     68   static int getNumConstructorCalls() {
     69     return numConstructorCalls;
     70   }
     71 
     72   static int getNumDestructorCalls() {
     73     return numDestructorCalls;
     74   }
     75 
     76   friend bool operator==(const Constructable & c0, const Constructable & c1) {
     77     return c0.getValue() == c1.getValue();
     78   }
     79 
     80   friend bool LLVM_ATTRIBUTE_UNUSED
     81   operator!=(const Constructable & c0, const Constructable & c1) {
     82     return c0.getValue() != c1.getValue();
     83   }
     84 };
     85 
     86 int Constructable::numConstructorCalls;
     87 int Constructable::numDestructorCalls;
     88 int Constructable::numAssignmentCalls;
     89 
     90 // Test fixture class
     91 template <typename VectorT>
     92 class SmallVectorTest : public testing::Test {
     93 protected:
     94   VectorT theVector;
     95   VectorT otherVector;
     96 
     97   void SetUp() {
     98     Constructable::reset();
     99   }
    100 
    101   void assertEmpty(VectorT & v) {
    102     // Size tests
    103     EXPECT_EQ(0u, v.size());
    104     EXPECT_TRUE(v.empty());
    105 
    106     // Iterator tests
    107     EXPECT_TRUE(v.begin() == v.end());
    108   }
    109 
    110   // Assert that theVector contains the specified values, in order.
    111   void assertValuesInOrder(VectorT & v, size_t size, ...) {
    112     EXPECT_EQ(size, v.size());
    113 
    114     va_list ap;
    115     va_start(ap, size);
    116     for (size_t i = 0; i < size; ++i) {
    117       int value = va_arg(ap, int);
    118       EXPECT_EQ(value, v[i].getValue());
    119     }
    120 
    121     va_end(ap);
    122   }
    123 
    124   // Generate a sequence of values to initialize the vector.
    125   void makeSequence(VectorT & v, int start, int end) {
    126     for (int i = start; i <= end; ++i) {
    127       v.push_back(Constructable(i));
    128     }
    129   }
    130 };
    131 
    132 typedef ::testing::Types<SmallVector<Constructable, 0>,
    133                          SmallVector<Constructable, 1>,
    134                          SmallVector<Constructable, 2>,
    135                          SmallVector<Constructable, 4>
    136                          > SmallVectorTestTypes;
    137 TYPED_TEST_CASE(SmallVectorTest, SmallVectorTestTypes);
    138 
    139 // New vector test.
    140 TYPED_TEST(SmallVectorTest, EmptyVectorTest) {
    141   SCOPED_TRACE("EmptyVectorTest");
    142   this->assertEmpty(this->theVector);
    143   EXPECT_TRUE(this->theVector.rbegin() == this->theVector.rend());
    144   EXPECT_EQ(0, Constructable::getNumConstructorCalls());
    145   EXPECT_EQ(0, Constructable::getNumDestructorCalls());
    146 }
    147 
    148 // Simple insertions and deletions.
    149 TYPED_TEST(SmallVectorTest, PushPopTest) {
    150   SCOPED_TRACE("PushPopTest");
    151 
    152   // Track whether the vector will potentially have to grow.
    153   bool RequiresGrowth = this->theVector.capacity() < 3;
    154 
    155   // Push an element
    156   this->theVector.push_back(Constructable(1));
    157 
    158   // Size tests
    159   this->assertValuesInOrder(this->theVector, 1u, 1);
    160   EXPECT_FALSE(this->theVector.begin() == this->theVector.end());
    161   EXPECT_FALSE(this->theVector.empty());
    162 
    163   // Push another element
    164   this->theVector.push_back(Constructable(2));
    165   this->assertValuesInOrder(this->theVector, 2u, 1, 2);
    166 
    167   // Insert at beginning
    168   this->theVector.insert(this->theVector.begin(), this->theVector[1]);
    169   this->assertValuesInOrder(this->theVector, 3u, 2, 1, 2);
    170 
    171   // Pop one element
    172   this->theVector.pop_back();
    173   this->assertValuesInOrder(this->theVector, 2u, 2, 1);
    174 
    175   // Pop remaining elements
    176   this->theVector.pop_back();
    177   this->theVector.pop_back();
    178   this->assertEmpty(this->theVector);
    179 
    180   // Check number of constructor calls. Should be 2 for each list element,
    181   // one for the argument to push_back, one for the argument to insert,
    182   // and one for the list element itself.
    183   if (!RequiresGrowth) {
    184     EXPECT_EQ(5, Constructable::getNumConstructorCalls());
    185     EXPECT_EQ(5, Constructable::getNumDestructorCalls());
    186   } else {
    187     // If we had to grow the vector, these only have a lower bound, but should
    188     // always be equal.
    189     EXPECT_LE(5, Constructable::getNumConstructorCalls());
    190     EXPECT_EQ(Constructable::getNumConstructorCalls(),
    191               Constructable::getNumDestructorCalls());
    192   }
    193 }
    194 
    195 // Clear test.
    196 TYPED_TEST(SmallVectorTest, ClearTest) {
    197   SCOPED_TRACE("ClearTest");
    198 
    199   this->theVector.reserve(2);
    200   this->makeSequence(this->theVector, 1, 2);
    201   this->theVector.clear();
    202 
    203   this->assertEmpty(this->theVector);
    204   EXPECT_EQ(4, Constructable::getNumConstructorCalls());
    205   EXPECT_EQ(4, Constructable::getNumDestructorCalls());
    206 }
    207 
    208 // Resize smaller test.
    209 TYPED_TEST(SmallVectorTest, ResizeShrinkTest) {
    210   SCOPED_TRACE("ResizeShrinkTest");
    211 
    212   this->theVector.reserve(3);
    213   this->makeSequence(this->theVector, 1, 3);
    214   this->theVector.resize(1);
    215 
    216   this->assertValuesInOrder(this->theVector, 1u, 1);
    217   EXPECT_EQ(6, Constructable::getNumConstructorCalls());
    218   EXPECT_EQ(5, Constructable::getNumDestructorCalls());
    219 }
    220 
    221 // Resize bigger test.
    222 TYPED_TEST(SmallVectorTest, ResizeGrowTest) {
    223   SCOPED_TRACE("ResizeGrowTest");
    224 
    225   this->theVector.resize(2);
    226 
    227   // The extra constructor/destructor calls come from the temporary object used
    228   // to initialize the contents of the resized array (via copy construction).
    229   EXPECT_EQ(3, Constructable::getNumConstructorCalls());
    230   EXPECT_EQ(1, Constructable::getNumDestructorCalls());
    231   EXPECT_EQ(2u, this->theVector.size());
    232 }
    233 
    234 // Resize with fill value.
    235 TYPED_TEST(SmallVectorTest, ResizeFillTest) {
    236   SCOPED_TRACE("ResizeFillTest");
    237 
    238   this->theVector.resize(3, Constructable(77));
    239   this->assertValuesInOrder(this->theVector, 3u, 77, 77, 77);
    240 }
    241 
    242 // Overflow past fixed size.
    243 TYPED_TEST(SmallVectorTest, OverflowTest) {
    244   SCOPED_TRACE("OverflowTest");
    245 
    246   // Push more elements than the fixed size.
    247   this->makeSequence(this->theVector, 1, 10);
    248 
    249   // Test size and values.
    250   EXPECT_EQ(10u, this->theVector.size());
    251   for (int i = 0; i < 10; ++i) {
    252     EXPECT_EQ(i+1, this->theVector[i].getValue());
    253   }
    254 
    255   // Now resize back to fixed size.
    256   this->theVector.resize(1);
    257 
    258   this->assertValuesInOrder(this->theVector, 1u, 1);
    259 }
    260 
    261 // Iteration tests.
    262 TYPED_TEST(SmallVectorTest, IterationTest) {
    263   this->makeSequence(this->theVector, 1, 2);
    264 
    265   // Forward Iteration
    266   typename TypeParam::iterator it = this->theVector.begin();
    267   EXPECT_TRUE(*it == this->theVector.front());
    268   EXPECT_TRUE(*it == this->theVector[0]);
    269   EXPECT_EQ(1, it->getValue());
    270   ++it;
    271   EXPECT_TRUE(*it == this->theVector[1]);
    272   EXPECT_TRUE(*it == this->theVector.back());
    273   EXPECT_EQ(2, it->getValue());
    274   ++it;
    275   EXPECT_TRUE(it == this->theVector.end());
    276   --it;
    277   EXPECT_TRUE(*it == this->theVector[1]);
    278   EXPECT_EQ(2, it->getValue());
    279   --it;
    280   EXPECT_TRUE(*it == this->theVector[0]);
    281   EXPECT_EQ(1, it->getValue());
    282 
    283   // Reverse Iteration
    284   typename TypeParam::reverse_iterator rit = this->theVector.rbegin();
    285   EXPECT_TRUE(*rit == this->theVector[1]);
    286   EXPECT_EQ(2, rit->getValue());
    287   ++rit;
    288   EXPECT_TRUE(*rit == this->theVector[0]);
    289   EXPECT_EQ(1, rit->getValue());
    290   ++rit;
    291   EXPECT_TRUE(rit == this->theVector.rend());
    292   --rit;
    293   EXPECT_TRUE(*rit == this->theVector[0]);
    294   EXPECT_EQ(1, rit->getValue());
    295   --rit;
    296   EXPECT_TRUE(*rit == this->theVector[1]);
    297   EXPECT_EQ(2, rit->getValue());
    298 }
    299 
    300 // Swap test.
    301 TYPED_TEST(SmallVectorTest, SwapTest) {
    302   SCOPED_TRACE("SwapTest");
    303 
    304   this->makeSequence(this->theVector, 1, 2);
    305   std::swap(this->theVector, this->otherVector);
    306 
    307   this->assertEmpty(this->theVector);
    308   this->assertValuesInOrder(this->otherVector, 2u, 1, 2);
    309 }
    310 
    311 // Append test
    312 TYPED_TEST(SmallVectorTest, AppendTest) {
    313   SCOPED_TRACE("AppendTest");
    314 
    315   this->makeSequence(this->otherVector, 2, 3);
    316 
    317   this->theVector.push_back(Constructable(1));
    318   this->theVector.append(this->otherVector.begin(), this->otherVector.end());
    319 
    320   this->assertValuesInOrder(this->theVector, 3u, 1, 2, 3);
    321 }
    322 
    323 // Append repeated test
    324 TYPED_TEST(SmallVectorTest, AppendRepeatedTest) {
    325   SCOPED_TRACE("AppendRepeatedTest");
    326 
    327   this->theVector.push_back(Constructable(1));
    328   this->theVector.append(2, Constructable(77));
    329   this->assertValuesInOrder(this->theVector, 3u, 1, 77, 77);
    330 }
    331 
    332 // Assign test
    333 TYPED_TEST(SmallVectorTest, AssignTest) {
    334   SCOPED_TRACE("AssignTest");
    335 
    336   this->theVector.push_back(Constructable(1));
    337   this->theVector.assign(2, Constructable(77));
    338   this->assertValuesInOrder(this->theVector, 2u, 77, 77);
    339 }
    340 
    341 // Erase a single element
    342 TYPED_TEST(SmallVectorTest, EraseTest) {
    343   SCOPED_TRACE("EraseTest");
    344 
    345   this->makeSequence(this->theVector, 1, 3);
    346   this->theVector.erase(this->theVector.begin());
    347   this->assertValuesInOrder(this->theVector, 2u, 2, 3);
    348 }
    349 
    350 // Erase a range of elements
    351 TYPED_TEST(SmallVectorTest, EraseRangeTest) {
    352   SCOPED_TRACE("EraseRangeTest");
    353 
    354   this->makeSequence(this->theVector, 1, 3);
    355   this->theVector.erase(this->theVector.begin(), this->theVector.begin() + 2);
    356   this->assertValuesInOrder(this->theVector, 1u, 3);
    357 }
    358 
    359 // Insert a single element.
    360 TYPED_TEST(SmallVectorTest, InsertTest) {
    361   SCOPED_TRACE("InsertTest");
    362 
    363   this->makeSequence(this->theVector, 1, 3);
    364   typename TypeParam::iterator I =
    365     this->theVector.insert(this->theVector.begin() + 1, Constructable(77));
    366   EXPECT_EQ(this->theVector.begin() + 1, I);
    367   this->assertValuesInOrder(this->theVector, 4u, 1, 77, 2, 3);
    368 }
    369 
    370 // Insert repeated elements.
    371 TYPED_TEST(SmallVectorTest, InsertRepeatedTest) {
    372   SCOPED_TRACE("InsertRepeatedTest");
    373 
    374   this->makeSequence(this->theVector, 10, 15);
    375   typename TypeParam::iterator I =
    376     this->theVector.insert(this->theVector.begin() + 1, 2, Constructable(16));
    377   EXPECT_EQ(this->theVector.begin() + 1, I);
    378   this->assertValuesInOrder(this->theVector, 8u,
    379                       10, 16, 16, 11, 12, 13, 14, 15);
    380 
    381   // Insert at end.
    382   I = this->theVector.insert(this->theVector.end(), 2, Constructable(16));
    383   EXPECT_EQ(this->theVector.begin() + 8, I);
    384   this->assertValuesInOrder(this->theVector, 10u,
    385                       10, 16, 16, 11, 12, 13, 14, 15, 16, 16);
    386 
    387   // Empty insert.
    388   EXPECT_EQ(this->theVector.end(),
    389             this->theVector.insert(this->theVector.end(),
    390                                    0, Constructable(42)));
    391   EXPECT_EQ(this->theVector.begin() + 1,
    392             this->theVector.insert(this->theVector.begin() + 1,
    393                                    0, Constructable(42)));
    394 }
    395 
    396 // Insert range.
    397 TYPED_TEST(SmallVectorTest, InsertRangeTest) {
    398   SCOPED_TRACE("InsertRangeTest");
    399 
    400   Constructable Arr[3] =
    401     { Constructable(77), Constructable(77), Constructable(77) };
    402 
    403   this->makeSequence(this->theVector, 1, 3);
    404   typename TypeParam::iterator I =
    405     this->theVector.insert(this->theVector.begin() + 1, Arr, Arr+3);
    406   EXPECT_EQ(this->theVector.begin() + 1, I);
    407   this->assertValuesInOrder(this->theVector, 6u, 1, 77, 77, 77, 2, 3);
    408 
    409   // Insert at end.
    410   I = this->theVector.insert(this->theVector.end(), Arr, Arr+3);
    411   EXPECT_EQ(this->theVector.begin() + 6, I);
    412   this->assertValuesInOrder(this->theVector, 9u,
    413                             1, 77, 77, 77, 2, 3, 77, 77, 77);
    414 
    415   // Empty insert.
    416   EXPECT_EQ(this->theVector.end(),
    417             this->theVector.insert(this->theVector.end(),
    418                                    this->theVector.begin(),
    419                                    this->theVector.begin()));
    420   EXPECT_EQ(this->theVector.begin() + 1,
    421             this->theVector.insert(this->theVector.begin() + 1,
    422                                    this->theVector.begin(),
    423                                    this->theVector.begin()));
    424 }
    425 
    426 // Comparison tests.
    427 TYPED_TEST(SmallVectorTest, ComparisonTest) {
    428   SCOPED_TRACE("ComparisonTest");
    429 
    430   this->makeSequence(this->theVector, 1, 3);
    431   this->makeSequence(this->otherVector, 1, 3);
    432 
    433   EXPECT_TRUE(this->theVector == this->otherVector);
    434   EXPECT_FALSE(this->theVector != this->otherVector);
    435 
    436   this->otherVector.clear();
    437   this->makeSequence(this->otherVector, 2, 4);
    438 
    439   EXPECT_FALSE(this->theVector == this->otherVector);
    440   EXPECT_TRUE(this->theVector != this->otherVector);
    441 }
    442 
    443 // Constant vector tests.
    444 TYPED_TEST(SmallVectorTest, ConstVectorTest) {
    445   const TypeParam constVector;
    446 
    447   EXPECT_EQ(0u, constVector.size());
    448   EXPECT_TRUE(constVector.empty());
    449   EXPECT_TRUE(constVector.begin() == constVector.end());
    450 }
    451 
    452 // Direct array access.
    453 TYPED_TEST(SmallVectorTest, DirectVectorTest) {
    454   EXPECT_EQ(0u, this->theVector.size());
    455   this->theVector.reserve(4);
    456   EXPECT_LE(4u, this->theVector.capacity());
    457   EXPECT_EQ(0, Constructable::getNumConstructorCalls());
    458   this->theVector.end()[0] = 1;
    459   this->theVector.end()[1] = 2;
    460   this->theVector.end()[2] = 3;
    461   this->theVector.end()[3] = 4;
    462   this->theVector.set_size(4);
    463   EXPECT_EQ(4u, this->theVector.size());
    464   EXPECT_EQ(4, Constructable::getNumConstructorCalls());
    465   EXPECT_EQ(1, this->theVector[0].getValue());
    466   EXPECT_EQ(2, this->theVector[1].getValue());
    467   EXPECT_EQ(3, this->theVector[2].getValue());
    468   EXPECT_EQ(4, this->theVector[3].getValue());
    469 }
    470 
    471 TYPED_TEST(SmallVectorTest, IteratorTest) {
    472   std::list<int> L;
    473   this->theVector.insert(this->theVector.end(), L.begin(), L.end());
    474 }
    475 
    476 struct notassignable {
    477   int &x;
    478   notassignable(int &x) : x(x) {}
    479 };
    480 
    481 TEST(SmallVectorCustomTest, NoAssignTest) {
    482   int x = 0;
    483   SmallVector<notassignable, 2> vec;
    484   vec.push_back(notassignable(x));
    485   x = 42;
    486   EXPECT_EQ(42, vec.pop_back_val().x);
    487 }
    488 
    489 }
    490