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