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/ArrayRef.h" 15 #include "llvm/ADT/SmallVector.h" 16 #include "llvm/Support/Compiler.h" 17 #include "gtest/gtest.h" 18 #include <list> 19 #include <stdarg.h> 20 21 using namespace llvm; 22 23 namespace { 24 25 /// A helper class that counts the total number of constructor and 26 /// destructor calls. 27 class Constructable { 28 private: 29 static int numConstructorCalls; 30 static int numMoveConstructorCalls; 31 static int numCopyConstructorCalls; 32 static int numDestructorCalls; 33 static int numAssignmentCalls; 34 static int numMoveAssignmentCalls; 35 static int numCopyAssignmentCalls; 36 37 bool constructed; 38 int value; 39 40 public: 41 Constructable() : constructed(true), value(0) { 42 ++numConstructorCalls; 43 } 44 45 Constructable(int val) : constructed(true), value(val) { 46 ++numConstructorCalls; 47 } 48 49 Constructable(const Constructable & src) : constructed(true) { 50 value = src.value; 51 ++numConstructorCalls; 52 ++numCopyConstructorCalls; 53 } 54 55 Constructable(Constructable && src) : constructed(true) { 56 value = src.value; 57 ++numConstructorCalls; 58 ++numMoveConstructorCalls; 59 } 60 61 ~Constructable() { 62 EXPECT_TRUE(constructed); 63 ++numDestructorCalls; 64 constructed = false; 65 } 66 67 Constructable & operator=(const Constructable & src) { 68 EXPECT_TRUE(constructed); 69 value = src.value; 70 ++numAssignmentCalls; 71 ++numCopyAssignmentCalls; 72 return *this; 73 } 74 75 Constructable & operator=(Constructable && src) { 76 EXPECT_TRUE(constructed); 77 value = src.value; 78 ++numAssignmentCalls; 79 ++numMoveAssignmentCalls; 80 return *this; 81 } 82 83 int getValue() const { 84 return abs(value); 85 } 86 87 static void reset() { 88 numConstructorCalls = 0; 89 numMoveConstructorCalls = 0; 90 numCopyConstructorCalls = 0; 91 numDestructorCalls = 0; 92 numAssignmentCalls = 0; 93 numMoveAssignmentCalls = 0; 94 numCopyAssignmentCalls = 0; 95 } 96 97 static int getNumConstructorCalls() { 98 return numConstructorCalls; 99 } 100 101 static int getNumMoveConstructorCalls() { 102 return numMoveConstructorCalls; 103 } 104 105 static int getNumCopyConstructorCalls() { 106 return numCopyConstructorCalls; 107 } 108 109 static int getNumDestructorCalls() { 110 return numDestructorCalls; 111 } 112 113 static int getNumAssignmentCalls() { 114 return numAssignmentCalls; 115 } 116 117 static int getNumMoveAssignmentCalls() { 118 return numMoveAssignmentCalls; 119 } 120 121 static int getNumCopyAssignmentCalls() { 122 return numCopyAssignmentCalls; 123 } 124 125 friend bool operator==(const Constructable & c0, const Constructable & c1) { 126 return c0.getValue() == c1.getValue(); 127 } 128 129 friend bool LLVM_ATTRIBUTE_UNUSED 130 operator!=(const Constructable & c0, const Constructable & c1) { 131 return c0.getValue() != c1.getValue(); 132 } 133 }; 134 135 int Constructable::numConstructorCalls; 136 int Constructable::numCopyConstructorCalls; 137 int Constructable::numMoveConstructorCalls; 138 int Constructable::numDestructorCalls; 139 int Constructable::numAssignmentCalls; 140 int Constructable::numCopyAssignmentCalls; 141 int Constructable::numMoveAssignmentCalls; 142 143 struct NonCopyable { 144 NonCopyable() {} 145 NonCopyable(NonCopyable &&) {} 146 NonCopyable &operator=(NonCopyable &&) { return *this; } 147 private: 148 NonCopyable(const NonCopyable &) = delete; 149 NonCopyable &operator=(const NonCopyable &) = delete; 150 }; 151 152 LLVM_ATTRIBUTE_USED void CompileTest() { 153 SmallVector<NonCopyable, 0> V; 154 V.resize(42); 155 } 156 157 class SmallVectorTestBase : public testing::Test { 158 protected: 159 void SetUp() override { Constructable::reset(); } 160 161 template <typename VectorT> 162 void assertEmpty(VectorT & v) { 163 // Size tests 164 EXPECT_EQ(0u, v.size()); 165 EXPECT_TRUE(v.empty()); 166 167 // Iterator tests 168 EXPECT_TRUE(v.begin() == v.end()); 169 } 170 171 // Assert that v contains the specified values, in order. 172 template <typename VectorT> 173 void assertValuesInOrder(VectorT & v, size_t size, ...) { 174 EXPECT_EQ(size, v.size()); 175 176 va_list ap; 177 va_start(ap, size); 178 for (size_t i = 0; i < size; ++i) { 179 int value = va_arg(ap, int); 180 EXPECT_EQ(value, v[i].getValue()); 181 } 182 183 va_end(ap); 184 } 185 186 // Generate a sequence of values to initialize the vector. 187 template <typename VectorT> 188 void makeSequence(VectorT & v, int start, int end) { 189 for (int i = start; i <= end; ++i) { 190 v.push_back(Constructable(i)); 191 } 192 } 193 }; 194 195 // Test fixture class 196 template <typename VectorT> 197 class SmallVectorTest : public SmallVectorTestBase { 198 protected: 199 VectorT theVector; 200 VectorT otherVector; 201 }; 202 203 204 typedef ::testing::Types<SmallVector<Constructable, 0>, 205 SmallVector<Constructable, 1>, 206 SmallVector<Constructable, 2>, 207 SmallVector<Constructable, 4>, 208 SmallVector<Constructable, 5> 209 > SmallVectorTestTypes; 210 TYPED_TEST_CASE(SmallVectorTest, SmallVectorTestTypes); 211 212 // New vector test. 213 TYPED_TEST(SmallVectorTest, EmptyVectorTest) { 214 SCOPED_TRACE("EmptyVectorTest"); 215 this->assertEmpty(this->theVector); 216 EXPECT_TRUE(this->theVector.rbegin() == this->theVector.rend()); 217 EXPECT_EQ(0, Constructable::getNumConstructorCalls()); 218 EXPECT_EQ(0, Constructable::getNumDestructorCalls()); 219 } 220 221 // Simple insertions and deletions. 222 TYPED_TEST(SmallVectorTest, PushPopTest) { 223 SCOPED_TRACE("PushPopTest"); 224 225 // Track whether the vector will potentially have to grow. 226 bool RequiresGrowth = this->theVector.capacity() < 3; 227 228 // Push an element 229 this->theVector.push_back(Constructable(1)); 230 231 // Size tests 232 this->assertValuesInOrder(this->theVector, 1u, 1); 233 EXPECT_FALSE(this->theVector.begin() == this->theVector.end()); 234 EXPECT_FALSE(this->theVector.empty()); 235 236 // Push another element 237 this->theVector.push_back(Constructable(2)); 238 this->assertValuesInOrder(this->theVector, 2u, 1, 2); 239 240 // Insert at beginning 241 this->theVector.insert(this->theVector.begin(), this->theVector[1]); 242 this->assertValuesInOrder(this->theVector, 3u, 2, 1, 2); 243 244 // Pop one element 245 this->theVector.pop_back(); 246 this->assertValuesInOrder(this->theVector, 2u, 2, 1); 247 248 // Pop remaining elements 249 this->theVector.pop_back(); 250 this->theVector.pop_back(); 251 this->assertEmpty(this->theVector); 252 253 // Check number of constructor calls. Should be 2 for each list element, 254 // one for the argument to push_back, one for the argument to insert, 255 // and one for the list element itself. 256 if (!RequiresGrowth) { 257 EXPECT_EQ(5, Constructable::getNumConstructorCalls()); 258 EXPECT_EQ(5, Constructable::getNumDestructorCalls()); 259 } else { 260 // If we had to grow the vector, these only have a lower bound, but should 261 // always be equal. 262 EXPECT_LE(5, Constructable::getNumConstructorCalls()); 263 EXPECT_EQ(Constructable::getNumConstructorCalls(), 264 Constructable::getNumDestructorCalls()); 265 } 266 } 267 268 // Clear test. 269 TYPED_TEST(SmallVectorTest, ClearTest) { 270 SCOPED_TRACE("ClearTest"); 271 272 this->theVector.reserve(2); 273 this->makeSequence(this->theVector, 1, 2); 274 this->theVector.clear(); 275 276 this->assertEmpty(this->theVector); 277 EXPECT_EQ(4, Constructable::getNumConstructorCalls()); 278 EXPECT_EQ(4, Constructable::getNumDestructorCalls()); 279 } 280 281 // Resize smaller test. 282 TYPED_TEST(SmallVectorTest, ResizeShrinkTest) { 283 SCOPED_TRACE("ResizeShrinkTest"); 284 285 this->theVector.reserve(3); 286 this->makeSequence(this->theVector, 1, 3); 287 this->theVector.resize(1); 288 289 this->assertValuesInOrder(this->theVector, 1u, 1); 290 EXPECT_EQ(6, Constructable::getNumConstructorCalls()); 291 EXPECT_EQ(5, Constructable::getNumDestructorCalls()); 292 } 293 294 // Resize bigger test. 295 TYPED_TEST(SmallVectorTest, ResizeGrowTest) { 296 SCOPED_TRACE("ResizeGrowTest"); 297 298 this->theVector.resize(2); 299 300 EXPECT_EQ(2, Constructable::getNumConstructorCalls()); 301 EXPECT_EQ(0, Constructable::getNumDestructorCalls()); 302 EXPECT_EQ(2u, this->theVector.size()); 303 } 304 305 TYPED_TEST(SmallVectorTest, ResizeWithElementsTest) { 306 this->theVector.resize(2); 307 308 Constructable::reset(); 309 310 this->theVector.resize(4); 311 312 size_t Ctors = Constructable::getNumConstructorCalls(); 313 EXPECT_TRUE(Ctors == 2 || Ctors == 4); 314 size_t MoveCtors = Constructable::getNumMoveConstructorCalls(); 315 EXPECT_TRUE(MoveCtors == 0 || MoveCtors == 2); 316 size_t Dtors = Constructable::getNumDestructorCalls(); 317 EXPECT_TRUE(Dtors == 0 || Dtors == 2); 318 } 319 320 // Resize with fill value. 321 TYPED_TEST(SmallVectorTest, ResizeFillTest) { 322 SCOPED_TRACE("ResizeFillTest"); 323 324 this->theVector.resize(3, Constructable(77)); 325 this->assertValuesInOrder(this->theVector, 3u, 77, 77, 77); 326 } 327 328 // Overflow past fixed size. 329 TYPED_TEST(SmallVectorTest, OverflowTest) { 330 SCOPED_TRACE("OverflowTest"); 331 332 // Push more elements than the fixed size. 333 this->makeSequence(this->theVector, 1, 10); 334 335 // Test size and values. 336 EXPECT_EQ(10u, this->theVector.size()); 337 for (int i = 0; i < 10; ++i) { 338 EXPECT_EQ(i+1, this->theVector[i].getValue()); 339 } 340 341 // Now resize back to fixed size. 342 this->theVector.resize(1); 343 344 this->assertValuesInOrder(this->theVector, 1u, 1); 345 } 346 347 // Iteration tests. 348 TYPED_TEST(SmallVectorTest, IterationTest) { 349 this->makeSequence(this->theVector, 1, 2); 350 351 // Forward Iteration 352 typename TypeParam::iterator it = this->theVector.begin(); 353 EXPECT_TRUE(*it == this->theVector.front()); 354 EXPECT_TRUE(*it == this->theVector[0]); 355 EXPECT_EQ(1, it->getValue()); 356 ++it; 357 EXPECT_TRUE(*it == this->theVector[1]); 358 EXPECT_TRUE(*it == this->theVector.back()); 359 EXPECT_EQ(2, it->getValue()); 360 ++it; 361 EXPECT_TRUE(it == this->theVector.end()); 362 --it; 363 EXPECT_TRUE(*it == this->theVector[1]); 364 EXPECT_EQ(2, it->getValue()); 365 --it; 366 EXPECT_TRUE(*it == this->theVector[0]); 367 EXPECT_EQ(1, it->getValue()); 368 369 // Reverse Iteration 370 typename TypeParam::reverse_iterator rit = this->theVector.rbegin(); 371 EXPECT_TRUE(*rit == this->theVector[1]); 372 EXPECT_EQ(2, rit->getValue()); 373 ++rit; 374 EXPECT_TRUE(*rit == this->theVector[0]); 375 EXPECT_EQ(1, rit->getValue()); 376 ++rit; 377 EXPECT_TRUE(rit == this->theVector.rend()); 378 --rit; 379 EXPECT_TRUE(*rit == this->theVector[0]); 380 EXPECT_EQ(1, rit->getValue()); 381 --rit; 382 EXPECT_TRUE(*rit == this->theVector[1]); 383 EXPECT_EQ(2, rit->getValue()); 384 } 385 386 // Swap test. 387 TYPED_TEST(SmallVectorTest, SwapTest) { 388 SCOPED_TRACE("SwapTest"); 389 390 this->makeSequence(this->theVector, 1, 2); 391 std::swap(this->theVector, this->otherVector); 392 393 this->assertEmpty(this->theVector); 394 this->assertValuesInOrder(this->otherVector, 2u, 1, 2); 395 } 396 397 // Append test 398 TYPED_TEST(SmallVectorTest, AppendTest) { 399 SCOPED_TRACE("AppendTest"); 400 401 this->makeSequence(this->otherVector, 2, 3); 402 403 this->theVector.push_back(Constructable(1)); 404 this->theVector.append(this->otherVector.begin(), this->otherVector.end()); 405 406 this->assertValuesInOrder(this->theVector, 3u, 1, 2, 3); 407 } 408 409 // Append repeated test 410 TYPED_TEST(SmallVectorTest, AppendRepeatedTest) { 411 SCOPED_TRACE("AppendRepeatedTest"); 412 413 this->theVector.push_back(Constructable(1)); 414 this->theVector.append(2, Constructable(77)); 415 this->assertValuesInOrder(this->theVector, 3u, 1, 77, 77); 416 } 417 418 // Assign test 419 TYPED_TEST(SmallVectorTest, AssignTest) { 420 SCOPED_TRACE("AssignTest"); 421 422 this->theVector.push_back(Constructable(1)); 423 this->theVector.assign(2, Constructable(77)); 424 this->assertValuesInOrder(this->theVector, 2u, 77, 77); 425 } 426 427 // Move-assign test 428 TYPED_TEST(SmallVectorTest, MoveAssignTest) { 429 SCOPED_TRACE("MoveAssignTest"); 430 431 // Set up our vector with a single element, but enough capacity for 4. 432 this->theVector.reserve(4); 433 this->theVector.push_back(Constructable(1)); 434 435 // Set up the other vector with 2 elements. 436 this->otherVector.push_back(Constructable(2)); 437 this->otherVector.push_back(Constructable(3)); 438 439 // Move-assign from the other vector. 440 this->theVector = std::move(this->otherVector); 441 442 // Make sure we have the right result. 443 this->assertValuesInOrder(this->theVector, 2u, 2, 3); 444 445 // Make sure the # of constructor/destructor calls line up. There 446 // are two live objects after clearing the other vector. 447 this->otherVector.clear(); 448 EXPECT_EQ(Constructable::getNumConstructorCalls()-2, 449 Constructable::getNumDestructorCalls()); 450 451 // There shouldn't be any live objects any more. 452 this->theVector.clear(); 453 EXPECT_EQ(Constructable::getNumConstructorCalls(), 454 Constructable::getNumDestructorCalls()); 455 } 456 457 // Erase a single element 458 TYPED_TEST(SmallVectorTest, EraseTest) { 459 SCOPED_TRACE("EraseTest"); 460 461 this->makeSequence(this->theVector, 1, 3); 462 const auto &theConstVector = this->theVector; 463 this->theVector.erase(theConstVector.begin()); 464 this->assertValuesInOrder(this->theVector, 2u, 2, 3); 465 } 466 467 // Erase a range of elements 468 TYPED_TEST(SmallVectorTest, EraseRangeTest) { 469 SCOPED_TRACE("EraseRangeTest"); 470 471 this->makeSequence(this->theVector, 1, 3); 472 const auto &theConstVector = this->theVector; 473 this->theVector.erase(theConstVector.begin(), theConstVector.begin() + 2); 474 this->assertValuesInOrder(this->theVector, 1u, 3); 475 } 476 477 // Insert a single element. 478 TYPED_TEST(SmallVectorTest, InsertTest) { 479 SCOPED_TRACE("InsertTest"); 480 481 this->makeSequence(this->theVector, 1, 3); 482 typename TypeParam::iterator I = 483 this->theVector.insert(this->theVector.begin() + 1, Constructable(77)); 484 EXPECT_EQ(this->theVector.begin() + 1, I); 485 this->assertValuesInOrder(this->theVector, 4u, 1, 77, 2, 3); 486 } 487 488 // Insert a copy of a single element. 489 TYPED_TEST(SmallVectorTest, InsertCopy) { 490 SCOPED_TRACE("InsertTest"); 491 492 this->makeSequence(this->theVector, 1, 3); 493 Constructable C(77); 494 typename TypeParam::iterator I = 495 this->theVector.insert(this->theVector.begin() + 1, C); 496 EXPECT_EQ(this->theVector.begin() + 1, I); 497 this->assertValuesInOrder(this->theVector, 4u, 1, 77, 2, 3); 498 } 499 500 // Insert repeated elements. 501 TYPED_TEST(SmallVectorTest, InsertRepeatedTest) { 502 SCOPED_TRACE("InsertRepeatedTest"); 503 504 this->makeSequence(this->theVector, 1, 4); 505 Constructable::reset(); 506 auto I = 507 this->theVector.insert(this->theVector.begin() + 1, 2, Constructable(16)); 508 // Move construct the top element into newly allocated space, and optionally 509 // reallocate the whole buffer, move constructing into it. 510 // FIXME: This is inefficient, we shouldn't move things into newly allocated 511 // space, then move them up/around, there should only be 2 or 4 move 512 // constructions here. 513 EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 || 514 Constructable::getNumMoveConstructorCalls() == 6); 515 // Move assign the next two to shift them up and make a gap. 516 EXPECT_EQ(1, Constructable::getNumMoveAssignmentCalls()); 517 // Copy construct the two new elements from the parameter. 518 EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls()); 519 // All without any copy construction. 520 EXPECT_EQ(0, Constructable::getNumCopyConstructorCalls()); 521 EXPECT_EQ(this->theVector.begin() + 1, I); 522 this->assertValuesInOrder(this->theVector, 6u, 1, 16, 16, 2, 3, 4); 523 } 524 525 526 TYPED_TEST(SmallVectorTest, InsertRepeatedAtEndTest) { 527 SCOPED_TRACE("InsertRepeatedTest"); 528 529 this->makeSequence(this->theVector, 1, 4); 530 Constructable::reset(); 531 auto I = this->theVector.insert(this->theVector.end(), 2, Constructable(16)); 532 // Just copy construct them into newly allocated space 533 EXPECT_EQ(2, Constructable::getNumCopyConstructorCalls()); 534 // Move everything across if reallocation is needed. 535 EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 0 || 536 Constructable::getNumMoveConstructorCalls() == 4); 537 // Without ever moving or copying anything else. 538 EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls()); 539 EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls()); 540 541 EXPECT_EQ(this->theVector.begin() + 4, I); 542 this->assertValuesInOrder(this->theVector, 6u, 1, 2, 3, 4, 16, 16); 543 } 544 545 TYPED_TEST(SmallVectorTest, InsertRepeatedEmptyTest) { 546 SCOPED_TRACE("InsertRepeatedTest"); 547 548 this->makeSequence(this->theVector, 10, 15); 549 550 // Empty insert. 551 EXPECT_EQ(this->theVector.end(), 552 this->theVector.insert(this->theVector.end(), 553 0, Constructable(42))); 554 EXPECT_EQ(this->theVector.begin() + 1, 555 this->theVector.insert(this->theVector.begin() + 1, 556 0, Constructable(42))); 557 } 558 559 // Insert range. 560 TYPED_TEST(SmallVectorTest, InsertRangeTest) { 561 SCOPED_TRACE("InsertRangeTest"); 562 563 Constructable Arr[3] = 564 { Constructable(77), Constructable(77), Constructable(77) }; 565 566 this->makeSequence(this->theVector, 1, 3); 567 Constructable::reset(); 568 auto I = this->theVector.insert(this->theVector.begin() + 1, Arr, Arr + 3); 569 // Move construct the top 3 elements into newly allocated space. 570 // Possibly move the whole sequence into new space first. 571 // FIXME: This is inefficient, we shouldn't move things into newly allocated 572 // space, then move them up/around, there should only be 2 or 3 move 573 // constructions here. 574 EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 || 575 Constructable::getNumMoveConstructorCalls() == 5); 576 // Copy assign the lower 2 new elements into existing space. 577 EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls()); 578 // Copy construct the third element into newly allocated space. 579 EXPECT_EQ(1, Constructable::getNumCopyConstructorCalls()); 580 EXPECT_EQ(this->theVector.begin() + 1, I); 581 this->assertValuesInOrder(this->theVector, 6u, 1, 77, 77, 77, 2, 3); 582 } 583 584 585 TYPED_TEST(SmallVectorTest, InsertRangeAtEndTest) { 586 SCOPED_TRACE("InsertRangeTest"); 587 588 Constructable Arr[3] = 589 { Constructable(77), Constructable(77), Constructable(77) }; 590 591 this->makeSequence(this->theVector, 1, 3); 592 593 // Insert at end. 594 Constructable::reset(); 595 auto I = this->theVector.insert(this->theVector.end(), Arr, Arr+3); 596 // Copy construct the 3 elements into new space at the top. 597 EXPECT_EQ(3, Constructable::getNumCopyConstructorCalls()); 598 // Don't copy/move anything else. 599 EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls()); 600 // Reallocation might occur, causing all elements to be moved into the new 601 // buffer. 602 EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 0 || 603 Constructable::getNumMoveConstructorCalls() == 3); 604 EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls()); 605 EXPECT_EQ(this->theVector.begin() + 3, I); 606 this->assertValuesInOrder(this->theVector, 6u, 607 1, 2, 3, 77, 77, 77); 608 } 609 610 TYPED_TEST(SmallVectorTest, InsertEmptyRangeTest) { 611 SCOPED_TRACE("InsertRangeTest"); 612 613 this->makeSequence(this->theVector, 1, 3); 614 615 // Empty insert. 616 EXPECT_EQ(this->theVector.end(), 617 this->theVector.insert(this->theVector.end(), 618 this->theVector.begin(), 619 this->theVector.begin())); 620 EXPECT_EQ(this->theVector.begin() + 1, 621 this->theVector.insert(this->theVector.begin() + 1, 622 this->theVector.begin(), 623 this->theVector.begin())); 624 } 625 626 // Comparison tests. 627 TYPED_TEST(SmallVectorTest, ComparisonTest) { 628 SCOPED_TRACE("ComparisonTest"); 629 630 this->makeSequence(this->theVector, 1, 3); 631 this->makeSequence(this->otherVector, 1, 3); 632 633 EXPECT_TRUE(this->theVector == this->otherVector); 634 EXPECT_FALSE(this->theVector != this->otherVector); 635 636 this->otherVector.clear(); 637 this->makeSequence(this->otherVector, 2, 4); 638 639 EXPECT_FALSE(this->theVector == this->otherVector); 640 EXPECT_TRUE(this->theVector != this->otherVector); 641 } 642 643 // Constant vector tests. 644 TYPED_TEST(SmallVectorTest, ConstVectorTest) { 645 const TypeParam constVector; 646 647 EXPECT_EQ(0u, constVector.size()); 648 EXPECT_TRUE(constVector.empty()); 649 EXPECT_TRUE(constVector.begin() == constVector.end()); 650 } 651 652 // Direct array access. 653 TYPED_TEST(SmallVectorTest, DirectVectorTest) { 654 EXPECT_EQ(0u, this->theVector.size()); 655 this->theVector.reserve(4); 656 EXPECT_LE(4u, this->theVector.capacity()); 657 EXPECT_EQ(0, Constructable::getNumConstructorCalls()); 658 this->theVector.push_back(1); 659 this->theVector.push_back(2); 660 this->theVector.push_back(3); 661 this->theVector.push_back(4); 662 EXPECT_EQ(4u, this->theVector.size()); 663 EXPECT_EQ(8, Constructable::getNumConstructorCalls()); 664 EXPECT_EQ(1, this->theVector[0].getValue()); 665 EXPECT_EQ(2, this->theVector[1].getValue()); 666 EXPECT_EQ(3, this->theVector[2].getValue()); 667 EXPECT_EQ(4, this->theVector[3].getValue()); 668 } 669 670 TYPED_TEST(SmallVectorTest, IteratorTest) { 671 std::list<int> L; 672 this->theVector.insert(this->theVector.end(), L.begin(), L.end()); 673 } 674 675 template <typename InvalidType> class DualSmallVectorsTest; 676 677 template <typename VectorT1, typename VectorT2> 678 class DualSmallVectorsTest<std::pair<VectorT1, VectorT2>> : public SmallVectorTestBase { 679 protected: 680 VectorT1 theVector; 681 VectorT2 otherVector; 682 683 template <typename T, unsigned N> 684 static unsigned NumBuiltinElts(const SmallVector<T, N>&) { return N; } 685 }; 686 687 typedef ::testing::Types< 688 // Small mode -> Small mode. 689 std::pair<SmallVector<Constructable, 4>, SmallVector<Constructable, 4>>, 690 // Small mode -> Big mode. 691 std::pair<SmallVector<Constructable, 4>, SmallVector<Constructable, 2>>, 692 // Big mode -> Small mode. 693 std::pair<SmallVector<Constructable, 2>, SmallVector<Constructable, 4>>, 694 // Big mode -> Big mode. 695 std::pair<SmallVector<Constructable, 2>, SmallVector<Constructable, 2>> 696 > DualSmallVectorTestTypes; 697 698 TYPED_TEST_CASE(DualSmallVectorsTest, DualSmallVectorTestTypes); 699 700 TYPED_TEST(DualSmallVectorsTest, MoveAssignment) { 701 SCOPED_TRACE("MoveAssignTest-DualVectorTypes"); 702 703 // Set up our vector with four elements. 704 for (unsigned I = 0; I < 4; ++I) 705 this->otherVector.push_back(Constructable(I)); 706 707 const Constructable *OrigDataPtr = this->otherVector.data(); 708 709 // Move-assign from the other vector. 710 this->theVector = 711 std::move(static_cast<SmallVectorImpl<Constructable>&>(this->otherVector)); 712 713 // Make sure we have the right result. 714 this->assertValuesInOrder(this->theVector, 4u, 0, 1, 2, 3); 715 716 // Make sure the # of constructor/destructor calls line up. There 717 // are two live objects after clearing the other vector. 718 this->otherVector.clear(); 719 EXPECT_EQ(Constructable::getNumConstructorCalls()-4, 720 Constructable::getNumDestructorCalls()); 721 722 // If the source vector (otherVector) was in small-mode, assert that we just 723 // moved the data pointer over. 724 EXPECT_TRUE(this->NumBuiltinElts(this->otherVector) == 4 || 725 this->theVector.data() == OrigDataPtr); 726 727 // There shouldn't be any live objects any more. 728 this->theVector.clear(); 729 EXPECT_EQ(Constructable::getNumConstructorCalls(), 730 Constructable::getNumDestructorCalls()); 731 732 // We shouldn't have copied anything in this whole process. 733 EXPECT_EQ(Constructable::getNumCopyConstructorCalls(), 0); 734 } 735 736 struct notassignable { 737 int &x; 738 notassignable(int &x) : x(x) {} 739 }; 740 741 TEST(SmallVectorCustomTest, NoAssignTest) { 742 int x = 0; 743 SmallVector<notassignable, 2> vec; 744 vec.push_back(notassignable(x)); 745 x = 42; 746 EXPECT_EQ(42, vec.pop_back_val().x); 747 } 748 749 struct MovedFrom { 750 bool hasValue; 751 MovedFrom() : hasValue(true) { 752 } 753 MovedFrom(MovedFrom&& m) : hasValue(m.hasValue) { 754 m.hasValue = false; 755 } 756 MovedFrom &operator=(MovedFrom&& m) { 757 hasValue = m.hasValue; 758 m.hasValue = false; 759 return *this; 760 } 761 }; 762 763 TEST(SmallVectorTest, MidInsert) { 764 SmallVector<MovedFrom, 3> v; 765 v.push_back(MovedFrom()); 766 v.insert(v.begin(), MovedFrom()); 767 for (MovedFrom &m : v) 768 EXPECT_TRUE(m.hasValue); 769 } 770 771 enum EmplaceableArgState { 772 EAS_Defaulted, 773 EAS_Arg, 774 EAS_LValue, 775 EAS_RValue, 776 EAS_Failure 777 }; 778 template <int I> struct EmplaceableArg { 779 EmplaceableArgState State; 780 EmplaceableArg() : State(EAS_Defaulted) {} 781 EmplaceableArg(EmplaceableArg &&X) 782 : State(X.State == EAS_Arg ? EAS_RValue : EAS_Failure) {} 783 EmplaceableArg(EmplaceableArg &X) 784 : State(X.State == EAS_Arg ? EAS_LValue : EAS_Failure) {} 785 786 explicit EmplaceableArg(bool) : State(EAS_Arg) {} 787 788 private: 789 EmplaceableArg &operator=(EmplaceableArg &&) = delete; 790 EmplaceableArg &operator=(const EmplaceableArg &) = delete; 791 }; 792 793 enum EmplaceableState { ES_Emplaced, ES_Moved }; 794 struct Emplaceable { 795 EmplaceableArg<0> A0; 796 EmplaceableArg<1> A1; 797 EmplaceableArg<2> A2; 798 EmplaceableArg<3> A3; 799 EmplaceableState State; 800 801 Emplaceable() : State(ES_Emplaced) {} 802 803 template <class A0Ty> 804 explicit Emplaceable(A0Ty &&A0) 805 : A0(std::forward<A0Ty>(A0)), State(ES_Emplaced) {} 806 807 template <class A0Ty, class A1Ty> 808 Emplaceable(A0Ty &&A0, A1Ty &&A1) 809 : A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)), 810 State(ES_Emplaced) {} 811 812 template <class A0Ty, class A1Ty, class A2Ty> 813 Emplaceable(A0Ty &&A0, A1Ty &&A1, A2Ty &&A2) 814 : A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)), 815 A2(std::forward<A2Ty>(A2)), State(ES_Emplaced) {} 816 817 template <class A0Ty, class A1Ty, class A2Ty, class A3Ty> 818 Emplaceable(A0Ty &&A0, A1Ty &&A1, A2Ty &&A2, A3Ty &&A3) 819 : A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)), 820 A2(std::forward<A2Ty>(A2)), A3(std::forward<A3Ty>(A3)), 821 State(ES_Emplaced) {} 822 823 Emplaceable(Emplaceable &&) : State(ES_Moved) {} 824 Emplaceable &operator=(Emplaceable &&) { 825 State = ES_Moved; 826 return *this; 827 } 828 829 private: 830 Emplaceable(const Emplaceable &) = delete; 831 Emplaceable &operator=(const Emplaceable &) = delete; 832 }; 833 834 TEST(SmallVectorTest, EmplaceBack) { 835 EmplaceableArg<0> A0(true); 836 EmplaceableArg<1> A1(true); 837 EmplaceableArg<2> A2(true); 838 EmplaceableArg<3> A3(true); 839 { 840 SmallVector<Emplaceable, 3> V; 841 V.emplace_back(); 842 EXPECT_TRUE(V.size() == 1); 843 EXPECT_TRUE(V.back().State == ES_Emplaced); 844 EXPECT_TRUE(V.back().A0.State == EAS_Defaulted); 845 EXPECT_TRUE(V.back().A1.State == EAS_Defaulted); 846 EXPECT_TRUE(V.back().A2.State == EAS_Defaulted); 847 EXPECT_TRUE(V.back().A3.State == EAS_Defaulted); 848 } 849 { 850 SmallVector<Emplaceable, 3> V; 851 V.emplace_back(std::move(A0)); 852 EXPECT_TRUE(V.size() == 1); 853 EXPECT_TRUE(V.back().State == ES_Emplaced); 854 EXPECT_TRUE(V.back().A0.State == EAS_RValue); 855 EXPECT_TRUE(V.back().A1.State == EAS_Defaulted); 856 EXPECT_TRUE(V.back().A2.State == EAS_Defaulted); 857 EXPECT_TRUE(V.back().A3.State == EAS_Defaulted); 858 } 859 { 860 SmallVector<Emplaceable, 3> V; 861 V.emplace_back(A0); 862 EXPECT_TRUE(V.size() == 1); 863 EXPECT_TRUE(V.back().State == ES_Emplaced); 864 EXPECT_TRUE(V.back().A0.State == EAS_LValue); 865 EXPECT_TRUE(V.back().A1.State == EAS_Defaulted); 866 EXPECT_TRUE(V.back().A2.State == EAS_Defaulted); 867 EXPECT_TRUE(V.back().A3.State == EAS_Defaulted); 868 } 869 { 870 SmallVector<Emplaceable, 3> V; 871 V.emplace_back(A0, A1); 872 EXPECT_TRUE(V.size() == 1); 873 EXPECT_TRUE(V.back().State == ES_Emplaced); 874 EXPECT_TRUE(V.back().A0.State == EAS_LValue); 875 EXPECT_TRUE(V.back().A1.State == EAS_LValue); 876 EXPECT_TRUE(V.back().A2.State == EAS_Defaulted); 877 EXPECT_TRUE(V.back().A3.State == EAS_Defaulted); 878 } 879 { 880 SmallVector<Emplaceable, 3> V; 881 V.emplace_back(std::move(A0), std::move(A1)); 882 EXPECT_TRUE(V.size() == 1); 883 EXPECT_TRUE(V.back().State == ES_Emplaced); 884 EXPECT_TRUE(V.back().A0.State == EAS_RValue); 885 EXPECT_TRUE(V.back().A1.State == EAS_RValue); 886 EXPECT_TRUE(V.back().A2.State == EAS_Defaulted); 887 EXPECT_TRUE(V.back().A3.State == EAS_Defaulted); 888 } 889 { 890 SmallVector<Emplaceable, 3> V; 891 V.emplace_back(std::move(A0), A1, std::move(A2), A3); 892 EXPECT_TRUE(V.size() == 1); 893 EXPECT_TRUE(V.back().State == ES_Emplaced); 894 EXPECT_TRUE(V.back().A0.State == EAS_RValue); 895 EXPECT_TRUE(V.back().A1.State == EAS_LValue); 896 EXPECT_TRUE(V.back().A2.State == EAS_RValue); 897 EXPECT_TRUE(V.back().A3.State == EAS_LValue); 898 } 899 { 900 SmallVector<int, 1> V; 901 V.emplace_back(); 902 V.emplace_back(42); 903 EXPECT_EQ(2U, V.size()); 904 EXPECT_EQ(0, V[0]); 905 EXPECT_EQ(42, V[1]); 906 } 907 } 908 909 TEST(SmallVectorTest, InitializerList) { 910 SmallVector<int, 2> V1 = {}; 911 EXPECT_TRUE(V1.empty()); 912 V1 = {0, 0}; 913 EXPECT_TRUE(makeArrayRef(V1).equals({0, 0})); 914 V1 = {-1, -1}; 915 EXPECT_TRUE(makeArrayRef(V1).equals({-1, -1})); 916 917 SmallVector<int, 2> V2 = {1, 2, 3, 4}; 918 EXPECT_TRUE(makeArrayRef(V2).equals({1, 2, 3, 4})); 919 V2.assign({4}); 920 EXPECT_TRUE(makeArrayRef(V2).equals({4})); 921 V2.append({3, 2}); 922 EXPECT_TRUE(makeArrayRef(V2).equals({4, 3, 2})); 923 V2.insert(V2.begin() + 1, 5); 924 EXPECT_TRUE(makeArrayRef(V2).equals({4, 5, 3, 2})); 925 } 926 927 } // end namespace 928