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 "gtest/gtest.h"
  15 #include "llvm/ADT/SmallVector.h"
  16 #include "llvm/Support/Compiler.h"
  17 #include <stdarg.h>
  18 #include <list>
  19
  20 using namespace llvm;
  21
  22 namespace {
  23
  24 /// A helper class that counts the total number of constructor and
  25 /// destructor calls.
  26 class Constructable {
  27 private:
  28   static int numConstructorCalls;
  29   static int numDestructorCalls;
  30   static int numAssignmentCalls;
  31
  32   int value;
  33
  34 public:
  35   Constructable() : value(0) {
  36     ++numConstructorCalls;
  37   }
  38
  39   Constructable(int val) : value(val) {
  40     ++numConstructorCalls;
  41   }
  42
  43   Constructable(const Constructable & src) {
  44     value = src.value;
  45     ++numConstructorCalls;
  46   }
  47
  48   ~Constructable() {
  49     ++numDestructorCalls;
  50   }
  51
  52   Constructable & operator=(const Constructable & src) {
  53     value = src.value;
  54     ++numAssignmentCalls;
  55     return *this;
  56   }
  57
  58   int getValue() const {
  59     return abs(value);
  60   }
  61
  62   static void reset() {
  63     numConstructorCalls = 0;
  64     numDestructorCalls = 0;
  65     numAssignmentCalls = 0;
  66   }
  67
  68   static int getNumConstructorCalls() {
  69     return numConstructorCalls;
  70   }
  71
  72   static int getNumDestructorCalls() {
  73     return numDestructorCalls;
  74   }
  75
  76   friend bool operator==(const Constructable & c0, const Constructable & c1) {
  77     return c0.getValue() == c1.getValue();
  78   }
  79
  80   friend bool LLVM_ATTRIBUTE_UNUSED
  81   operator!=(const Constructable & c0, const Constructable & c1) {
  82     return c0.getValue() != c1.getValue();
  83   }
  84 };
  85
  86 int Constructable::numConstructorCalls;
  87 int Constructable::numDestructorCalls;
  88 int Constructable::numAssignmentCalls;
  89
  90 // Test fixture class
  91 class SmallVectorTest : public testing::Test {
  92 protected:
  93   typedef SmallVector<Constructable, 4> VectorType;
  94
  95   VectorType theVector;
  96   VectorType otherVector;
  97
  98   void SetUp() {
  99     Constructable::reset();
 100   }
 101
 102   void assertEmpty(VectorType & v) {
 103     // Size tests
 104     EXPECT_EQ(0u, v.size());
 105     EXPECT_TRUE(v.empty());
 106
 107     // Iterator tests
 108     EXPECT_TRUE(v.begin() == v.end());
 109   }
 110
 111   // Assert that theVector contains the specified values, in order.
 112   void assertValuesInOrder(VectorType & v, size_t size, ...) {
 113     EXPECT_EQ(size, v.size());
 114
 115     va_list ap;
 116     va_start(ap, size);
 117     for (size_t i = 0; i < size; ++i) {
 118       int value = va_arg(ap, int);
 119       EXPECT_EQ(value, v[i].getValue());
 120     }
 121
 122     va_end(ap);
 123   }
 124
 125   // Generate a sequence of values to initialize the vector.
 126   void makeSequence(VectorType & v, int start, int end) {
 127     for (int i = start; i <= end; ++i) {
 128       v.push_back(Constructable(i));
 129     }
 130   }
 131 };
 132
 133 // New vector test.
 134 TEST_F(SmallVectorTest, EmptyVectorTest) {
 135   SCOPED_TRACE("EmptyVectorTest");
 136   assertEmpty(theVector);
 137   EXPECT_TRUE(theVector.rbegin() == theVector.rend());
 138   EXPECT_EQ(0, Constructable::getNumConstructorCalls());
 139   EXPECT_EQ(0, Constructable::getNumDestructorCalls());
 140 }
 141
 142 // Simple insertions and deletions.
 143 TEST_F(SmallVectorTest, PushPopTest) {
 144   SCOPED_TRACE("PushPopTest");
 145
 146   // Push an element
 147   theVector.push_back(Constructable(1));
 148
 149   // Size tests
 150   assertValuesInOrder(theVector, 1u, 1);
 151   EXPECT_FALSE(theVector.begin() == theVector.end());
 152   EXPECT_FALSE(theVector.empty());
 153
 154   // Push another element
 155   theVector.push_back(Constructable(2));
 156   assertValuesInOrder(theVector, 2u, 1, 2);
 157
 158   // Insert at beginning
 159   theVector.insert(theVector.begin(), theVector[1]);
 160   assertValuesInOrder(theVector, 3u, 2, 1, 2);
 161
 162   // Pop one element
 163   theVector.pop_back();
 164   assertValuesInOrder(theVector, 2u, 2, 1);
 165
 166   // Pop remaining elements
 167   theVector.pop_back();
 168   theVector.pop_back();
 169   assertEmpty(theVector);
 170
 171   // Check number of constructor calls. Should be 2 for each list element,
 172   // one for the argument to push_back, one for the argument to insert,
 173   // and one for the list element itself.
 174   EXPECT_EQ(5, Constructable::getNumConstructorCalls());
 175   EXPECT_EQ(5, Constructable::getNumDestructorCalls());
 176 }
 177
 178 // Clear test.
 179 TEST_F(SmallVectorTest, ClearTest) {
 180   SCOPED_TRACE("ClearTest");
 181
 182   makeSequence(theVector, 1, 2);
 183   theVector.clear();
 184
 185   assertEmpty(theVector);
 186   EXPECT_EQ(4, Constructable::getNumConstructorCalls());
 187   EXPECT_EQ(4, Constructable::getNumDestructorCalls());
 188 }
 189
 190 // Resize smaller test.
 191 TEST_F(SmallVectorTest, ResizeShrinkTest) {
 192   SCOPED_TRACE("ResizeShrinkTest");
 193
 194   makeSequence(theVector, 1, 3);
 195   theVector.resize(1);
 196
 197   assertValuesInOrder(theVector, 1u, 1);
 198   EXPECT_EQ(6, Constructable::getNumConstructorCalls());
 199   EXPECT_EQ(5, Constructable::getNumDestructorCalls());
 200 }
 201
 202 // Resize bigger test.
 203 TEST_F(SmallVectorTest, ResizeGrowTest) {
 204   SCOPED_TRACE("ResizeGrowTest");
 205
 206   theVector.resize(2);
 207
 208   // The extra constructor/destructor calls come from the temporary object used
 209   // to initialize the contents of the resized array (via copy construction).
 210   EXPECT_EQ(3, Constructable::getNumConstructorCalls());
 211   EXPECT_EQ(1, Constructable::getNumDestructorCalls());
 212   EXPECT_EQ(2u, theVector.size());
 213 }
 214
 215 // Resize with fill value.
 216 TEST_F(SmallVectorTest, ResizeFillTest) {
 217   SCOPED_TRACE("ResizeFillTest");
 218
 219   theVector.resize(3, Constructable(77));
 220   assertValuesInOrder(theVector, 3u, 77, 77, 77);
 221 }
 222
 223 // Overflow past fixed size.
 224 TEST_F(SmallVectorTest, OverflowTest) {
 225   SCOPED_TRACE("OverflowTest");
 226
 227   // Push more elements than the fixed size.
 228   makeSequence(theVector, 1, 10);
 229
 230   // Test size and values.
 231   EXPECT_EQ(10u, theVector.size());
 232   for (int i = 0; i < 10; ++i) {
 233     EXPECT_EQ(i+1, theVector[i].getValue());
 234   }
 235
 236   // Now resize back to fixed size.
 237   theVector.resize(1);
 238
 239   assertValuesInOrder(theVector, 1u, 1);
 240 }
 241
 242 // Iteration tests.
 243 TEST_F(SmallVectorTest, IterationTest) {
 244   makeSequence(theVector, 1, 2);
 245
 246   // Forward Iteration
 247   VectorType::iterator it = theVector.begin();
 248   EXPECT_TRUE(*it == theVector.front());
 249   EXPECT_TRUE(*it == theVector[0]);
 250   EXPECT_EQ(1, it->getValue());
 251   ++it;
 252   EXPECT_TRUE(*it == theVector[1]);
 253   EXPECT_TRUE(*it == theVector.back());
 254   EXPECT_EQ(2, it->getValue());
 255   ++it;
 256   EXPECT_TRUE(it == theVector.end());
 257   --it;
 258   EXPECT_TRUE(*it == theVector[1]);
 259   EXPECT_EQ(2, it->getValue());
 260   --it;
 261   EXPECT_TRUE(*it == theVector[0]);
 262   EXPECT_EQ(1, it->getValue());
 263
 264   // Reverse Iteration
 265   VectorType::reverse_iterator rit = theVector.rbegin();
 266   EXPECT_TRUE(*rit == theVector[1]);
 267   EXPECT_EQ(2, rit->getValue());
 268   ++rit;
 269   EXPECT_TRUE(*rit == theVector[0]);
 270   EXPECT_EQ(1, rit->getValue());
 271   ++rit;
 272   EXPECT_TRUE(rit == theVector.rend());
 273   --rit;
 274   EXPECT_TRUE(*rit == theVector[0]);
 275   EXPECT_EQ(1, rit->getValue());
 276   --rit;
 277   EXPECT_TRUE(*rit == theVector[1]);
 278   EXPECT_EQ(2, rit->getValue());
 279 }
 280
 281 // Swap test.
 282 TEST_F(SmallVectorTest, SwapTest) {
 283   SCOPED_TRACE("SwapTest");
 284
 285   makeSequence(theVector, 1, 2);
 286   std::swap(theVector, otherVector);
 287
 288   assertEmpty(theVector);
 289   assertValuesInOrder(otherVector, 2u, 1, 2);
 290 }
 291
 292 // Append test
 293 TEST_F(SmallVectorTest, AppendTest) {
 294   SCOPED_TRACE("AppendTest");
 295
 296   makeSequence(otherVector, 2, 3);
 297
 298   theVector.push_back(Constructable(1));
 299   theVector.append(otherVector.begin(), otherVector.end());
 300
 301   assertValuesInOrder(theVector, 3u, 1, 2, 3);
 302 }
 303
 304 // Append repeated test
 305 TEST_F(SmallVectorTest, AppendRepeatedTest) {
 306   SCOPED_TRACE("AppendRepeatedTest");
 307
 308   theVector.push_back(Constructable(1));
 309   theVector.append(2, Constructable(77));
 310   assertValuesInOrder(theVector, 3u, 1, 77, 77);
 311 }
 312
 313 // Assign test
 314 TEST_F(SmallVectorTest, AssignTest) {
 315   SCOPED_TRACE("AssignTest");
 316
 317   theVector.push_back(Constructable(1));
 318   theVector.assign(2, Constructable(77));
 319   assertValuesInOrder(theVector, 2u, 77, 77);
 320 }
 321
 322 // Erase a single element
 323 TEST_F(SmallVectorTest, EraseTest) {
 324   SCOPED_TRACE("EraseTest");
 325
 326   makeSequence(theVector, 1, 3);
 327   theVector.erase(theVector.begin());
 328   assertValuesInOrder(theVector, 2u, 2, 3);
 329 }
 330
 331 // Erase a range of elements
 332 TEST_F(SmallVectorTest, EraseRangeTest) {
 333   SCOPED_TRACE("EraseRangeTest");
 334
 335   makeSequence(theVector, 1, 3);
 336   theVector.erase(theVector.begin(), theVector.begin() + 2);
 337   assertValuesInOrder(theVector, 1u, 3);
 338 }
 339
 340 // Insert a single element.
 341 TEST_F(SmallVectorTest, InsertTest) {
 342   SCOPED_TRACE("InsertTest");
 343
 344   makeSequence(theVector, 1, 3);
 345   VectorType::iterator I =
 346     theVector.insert(theVector.begin() + 1, Constructable(77));
 347   EXPECT_EQ(theVector.begin() + 1, I);
 348   assertValuesInOrder(theVector, 4u, 1, 77, 2, 3);
 349 }
 350
 351 // Insert repeated elements.
 352 TEST_F(SmallVectorTest, InsertRepeatedTest) {
 353   SCOPED_TRACE("InsertRepeatedTest");
 354
 355   makeSequence(theVector, 10, 15);
 356   VectorType::iterator I =
 357     theVector.insert(theVector.begin() + 1, 2, Constructable(16));
 358   EXPECT_EQ(theVector.begin() + 1, I);
 359   assertValuesInOrder(theVector, 8u, 10, 16, 16, 11, 12, 13, 14, 15);
 360
 361   // Insert at end.
 362   I = theVector.insert(theVector.end(), 2, Constructable(16));
 363   EXPECT_EQ(theVector.begin() + 8, I);
 364   assertValuesInOrder(theVector, 10u, 10, 16, 16, 11, 12, 13, 14, 15, 16, 16);
 365
 366   // Empty insert.
 367   EXPECT_EQ(theVector.end(),
 368             theVector.insert(theVector.end(), 0, Constructable(42)));
 369   EXPECT_EQ(theVector.begin() + 1,
 370             theVector.insert(theVector.begin() + 1, 0, Constructable(42)));
 371 }
 372
 373 // Insert range.
 374 TEST_F(SmallVectorTest, InsertRangeTest) {
 375   SCOPED_TRACE("InsertRangeTest");
 376
 377   Constructable Arr[3] =
 378     { Constructable(77), Constructable(77), Constructable(77) };
 379
 380   makeSequence(theVector, 1, 3);
 381   VectorType::iterator I =
 382     theVector.insert(theVector.begin() + 1, Arr, Arr+3);
 383   EXPECT_EQ(theVector.begin() + 1, I);
 384   assertValuesInOrder(theVector, 6u, 1, 77, 77, 77, 2, 3);
 385
 386   // Insert at end.
 387   I = theVector.insert(theVector.end(), Arr, Arr+3);
 388   EXPECT_EQ(theVector.begin() + 6, I);
 389   assertValuesInOrder(theVector, 9u, 1, 77, 77, 77, 2, 3, 77, 77, 77);
 390
 391   // Empty insert.
 392   EXPECT_EQ(theVector.end(), theVector.insert(theVector.end(),
 393                                               theVector.begin(),
 394                                               theVector.begin()));
 395   EXPECT_EQ(theVector.begin() + 1, theVector.insert(theVector.begin() + 1,
 396                                                     theVector.begin(),
 397                                                     theVector.begin()));
 398 }
 399
 400 // Comparison tests.
 401 TEST_F(SmallVectorTest, ComparisonTest) {
 402   SCOPED_TRACE("ComparisonTest");
 403
 404   makeSequence(theVector, 1, 3);
 405   makeSequence(otherVector, 1, 3);
 406
 407   EXPECT_TRUE(theVector == otherVector);
 408   EXPECT_FALSE(theVector != otherVector);
 409
 410   otherVector.clear();
 411   makeSequence(otherVector, 2, 4);
 412
 413   EXPECT_FALSE(theVector == otherVector);
 414   EXPECT_TRUE(theVector != otherVector);
 415 }
 416
 417 // Constant vector tests.
 418 TEST_F(SmallVectorTest, ConstVectorTest) {
 419   VectorType constVector;
 420
 421   EXPECT_EQ(0u, constVector.size());
 422   EXPECT_TRUE(constVector.empty());
 423   EXPECT_TRUE(constVector.begin() == constVector.end());
 424 }
 425
 426 // Direct array access.
 427 TEST_F(SmallVectorTest, DirectVectorTest) {
 428   EXPECT_EQ(0u, theVector.size());
 429   EXPECT_LE(4u, theVector.capacity());
 430   EXPECT_EQ(0, Constructable::getNumConstructorCalls());
 431   theVector.end()[0] = 1;
 432   theVector.end()[1] = 2;
 433   theVector.end()[2] = 3;
 434   theVector.end()[3] = 4;
 435   theVector.set_size(4);
 436   EXPECT_EQ(4u, theVector.size());
 437   EXPECT_EQ(4, Constructable::getNumConstructorCalls());
 438   EXPECT_EQ(1, theVector[0].getValue());
 439   EXPECT_EQ(2, theVector[1].getValue());
 440   EXPECT_EQ(3, theVector[2].getValue());
 441   EXPECT_EQ(4, theVector[3].getValue());
 442 }
 443
 444 TEST_F(SmallVectorTest, IteratorTest) {
 445   std::list<int> L;
 446   theVector.insert(theVector.end(), L.begin(), L.end());
 447 }
 448
 449 struct notassignable {
 450   int &x;
 451   notassignable(int &x) : x(x) {}
 452 };
 453
 454 TEST_F(SmallVectorTest, NoAssignTest) {
 455   int x = 0;
 456   SmallVector<notassignable, 2> vec;
 457   vec.push_back(notassignable(x));
 458   x = 42;
 459   EXPECT_EQ(42, vec.pop_back_val().x);
 460 }
 461
 462 }