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