unittests/ADT/SmallVectorTest.cpp

   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 }