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