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