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   // Pop one element
 159   theVector.pop_back();
 160   assertValuesInOrder(theVector, 1u, 1);
 161
 162   // Pop another element
 163   theVector.pop_back();
 164   assertEmpty(theVector);
 165
 166   // Check number of constructor calls. Should be 2 for each list element,
 167   // one for the argument to push_back, and one for the list element itself.
 168   EXPECT_EQ(4, Constructable::getNumConstructorCalls());
 169   EXPECT_EQ(4, Constructable::getNumDestructorCalls());
 170 }
 171
 172 // Clear test.
 173 TEST_F(SmallVectorTest, ClearTest) {
 174   SCOPED_TRACE("ClearTest");
 175
 176   makeSequence(theVector, 1, 2);
 177   theVector.clear();
 178
 179   assertEmpty(theVector);
 180   EXPECT_EQ(4, Constructable::getNumConstructorCalls());
 181   EXPECT_EQ(4, Constructable::getNumDestructorCalls());
 182 }
 183
 184 // Resize smaller test.
 185 TEST_F(SmallVectorTest, ResizeShrinkTest) {
 186   SCOPED_TRACE("ResizeShrinkTest");
 187
 188   makeSequence(theVector, 1, 3);
 189   theVector.resize(1);
 190
 191   assertValuesInOrder(theVector, 1u, 1);
 192   EXPECT_EQ(6, Constructable::getNumConstructorCalls());
 193   EXPECT_EQ(5, Constructable::getNumDestructorCalls());
 194 }
 195
 196 // Resize bigger test.
 197 TEST_F(SmallVectorTest, ResizeGrowTest) {
 198   SCOPED_TRACE("ResizeGrowTest");
 199
 200   theVector.resize(2);
 201
 202   // The extra constructor/destructor calls come from the temporary object used
 203   // to initialize the contents of the resized array (via copy construction).
 204   EXPECT_EQ(3, Constructable::getNumConstructorCalls());
 205   EXPECT_EQ(1, Constructable::getNumDestructorCalls());
 206   EXPECT_EQ(2u, theVector.size());
 207 }
 208
 209 // Resize with fill value.
 210 TEST_F(SmallVectorTest, ResizeFillTest) {
 211   SCOPED_TRACE("ResizeFillTest");
 212
 213   theVector.resize(3, Constructable(77));
 214   assertValuesInOrder(theVector, 3u, 77, 77, 77);
 215 }
 216
 217 // Overflow past fixed size.
 218 TEST_F(SmallVectorTest, OverflowTest) {
 219   SCOPED_TRACE("OverflowTest");
 220
 221   // Push more elements than the fixed size.
 222   makeSequence(theVector, 1, 10);
 223
 224   // Test size and values.
 225   EXPECT_EQ(10u, theVector.size());
 226   for (int i = 0; i < 10; ++i) {
 227     EXPECT_EQ(i+1, theVector[i].getValue());
 228   }
 229
 230   // Now resize back to fixed size.
 231   theVector.resize(1);
 232
 233   assertValuesInOrder(theVector, 1u, 1);
 234 }
 235
 236 // Iteration tests.
 237 TEST_F(SmallVectorTest, IterationTest) {
 238   makeSequence(theVector, 1, 2);
 239
 240   // Forward Iteration
 241   VectorType::iterator it = theVector.begin();
 242   EXPECT_TRUE(*it == theVector.front());
 243   EXPECT_TRUE(*it == theVector[0]);
 244   EXPECT_EQ(1, it->getValue());
 245   ++it;
 246   EXPECT_TRUE(*it == theVector[1]);
 247   EXPECT_TRUE(*it == theVector.back());
 248   EXPECT_EQ(2, it->getValue());
 249   ++it;
 250   EXPECT_TRUE(it == theVector.end());
 251   --it;
 252   EXPECT_TRUE(*it == theVector[1]);
 253   EXPECT_EQ(2, it->getValue());
 254   --it;
 255   EXPECT_TRUE(*it == theVector[0]);
 256   EXPECT_EQ(1, it->getValue());
 257
 258   // Reverse Iteration
 259   VectorType::reverse_iterator rit = theVector.rbegin();
 260   EXPECT_TRUE(*rit == theVector[1]);
 261   EXPECT_EQ(2, rit->getValue());
 262   ++rit;
 263   EXPECT_TRUE(*rit == theVector[0]);
 264   EXPECT_EQ(1, rit->getValue());
 265   ++rit;
 266   EXPECT_TRUE(rit == theVector.rend());
 267   --rit;
 268   EXPECT_TRUE(*rit == theVector[0]);
 269   EXPECT_EQ(1, rit->getValue());
 270   --rit;
 271   EXPECT_TRUE(*rit == theVector[1]);
 272   EXPECT_EQ(2, rit->getValue());
 273 }
 274
 275 // Swap test.
 276 TEST_F(SmallVectorTest, SwapTest) {
 277   SCOPED_TRACE("SwapTest");
 278
 279   makeSequence(theVector, 1, 2);
 280   std::swap(theVector, otherVector);
 281
 282   assertEmpty(theVector);
 283   assertValuesInOrder(otherVector, 2u, 1, 2);
 284 }
 285
 286 // Append test
 287 TEST_F(SmallVectorTest, AppendTest) {
 288   SCOPED_TRACE("AppendTest");
 289
 290   makeSequence(otherVector, 2, 3);
 291
 292   theVector.push_back(Constructable(1));
 293   theVector.append(otherVector.begin(), otherVector.end());
 294
 295   assertValuesInOrder(theVector, 3u, 1, 2, 3);
 296 }
 297
 298 // Append repeated test
 299 TEST_F(SmallVectorTest, AppendRepeatedTest) {
 300   SCOPED_TRACE("AppendRepeatedTest");
 301
 302   theVector.push_back(Constructable(1));
 303   theVector.append(2, Constructable(77));
 304   assertValuesInOrder(theVector, 3u, 1, 77, 77);
 305 }
 306
 307 // Assign test
 308 TEST_F(SmallVectorTest, AssignTest) {
 309   SCOPED_TRACE("AssignTest");
 310
 311   theVector.push_back(Constructable(1));
 312   theVector.assign(2, Constructable(77));
 313   assertValuesInOrder(theVector, 2u, 77, 77);
 314 }
 315
 316 // Erase a single element
 317 TEST_F(SmallVectorTest, EraseTest) {
 318   SCOPED_TRACE("EraseTest");
 319
 320   makeSequence(theVector, 1, 3);
 321   theVector.erase(theVector.begin());
 322   assertValuesInOrder(theVector, 2u, 2, 3);
 323 }
 324
 325 // Erase a range of elements
 326 TEST_F(SmallVectorTest, EraseRangeTest) {
 327   SCOPED_TRACE("EraseRangeTest");
 328
 329   makeSequence(theVector, 1, 3);
 330   theVector.erase(theVector.begin(), theVector.begin() + 2);
 331   assertValuesInOrder(theVector, 1u, 3);
 332 }
 333
 334 // Insert a single element.
 335 TEST_F(SmallVectorTest, InsertTest) {
 336   SCOPED_TRACE("InsertTest");
 337
 338   makeSequence(theVector, 1, 3);
 339   theVector.insert(theVector.begin() + 1, Constructable(77));
 340   assertValuesInOrder(theVector, 4u, 1, 77, 2, 3);
 341 }
 342
 343 // Insert repeated elements.
 344 TEST_F(SmallVectorTest, InsertRepeatedTest) {
 345   SCOPED_TRACE("InsertRepeatedTest");
 346
 347   makeSequence(theVector, 10, 15);
 348   theVector.insert(theVector.begin() + 1, 2, Constructable(16));
 349   assertValuesInOrder(theVector, 8u, 10, 16, 16, 11, 12, 13, 14, 15);
 350 }
 351
 352 // Insert range.
 353 TEST_F(SmallVectorTest, InsertRangeTest) {
 354   SCOPED_TRACE("InsertRepeatedTest");
 355
 356   makeSequence(theVector, 1, 3);
 357   theVector.insert(theVector.begin() + 1, 3, Constructable(77));
 358   assertValuesInOrder(theVector, 6u, 1, 77, 77, 77, 2, 3);
 359 }
 360
 361 // Comparison tests.
 362 TEST_F(SmallVectorTest, ComparisonTest) {
 363   SCOPED_TRACE("ComparisonTest");
 364
 365   makeSequence(theVector, 1, 3);
 366   makeSequence(otherVector, 1, 3);
 367
 368   EXPECT_TRUE(theVector == otherVector);
 369   EXPECT_FALSE(theVector != otherVector);
 370
 371   otherVector.clear();
 372   makeSequence(otherVector, 2, 4);
 373
 374   EXPECT_FALSE(theVector == otherVector);
 375   EXPECT_TRUE(theVector != otherVector);
 376 }
 377
 378 // Constant vector tests.
 379 TEST_F(SmallVectorTest, ConstVectorTest) {
 380   const VectorType constVector;
 381
 382   EXPECT_EQ(0u, constVector.size());
 383   EXPECT_TRUE(constVector.empty());
 384   EXPECT_TRUE(constVector.begin() == constVector.end());
 385 }
 386
 387 // Direct array access.
 388 TEST_F(SmallVectorTest, DirectVectorTest) {
 389   EXPECT_EQ(0u, theVector.size());
 390   EXPECT_LE(4u, theVector.capacity());
 391   EXPECT_EQ(0, Constructable::getNumConstructorCalls());
 392   theVector.end()[0] = 1;
 393   theVector.end()[1] = 2;
 394   theVector.end()[2] = 3;
 395   theVector.end()[3] = 4;
 396   theVector.set_size(4);
 397   EXPECT_EQ(4u, theVector.size());
 398   EXPECT_EQ(4, Constructable::getNumConstructorCalls());
 399   EXPECT_EQ(1, theVector[0].getValue());
 400   EXPECT_EQ(2, theVector[1].getValue());
 401   EXPECT_EQ(3, theVector[2].getValue());
 402   EXPECT_EQ(4, theVector[3].getValue());
 403 }
 404
 405 TEST_F(SmallVectorTest, IteratorTest) {
 406   std::list<int> L;
 407   theVector.insert(theVector.end(), L.begin(), L.end());
 408 }
 409
 410 }