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