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   // XXX: I don't know where the extra construct/destruct is coming from.
 200   EXPECT_EQ(3, Constructable::getNumConstructorCalls());
 201   EXPECT_EQ(1, Constructable::getNumDestructorCalls());
 202   EXPECT_EQ(2u, theVector.size());
 203 }
 204
 205 // Resize with fill value.
 206 TEST_F(SmallVectorTest, ResizeFillTest) {
 207   SCOPED_TRACE("ResizeFillTest");
 208
 209   theVector.resize(3, Constructable(77));
 210   assertValuesInOrder(theVector, 3u, 77, 77, 77);
 211 }
 212
 213 // Overflow past fixed size.
 214 TEST_F(SmallVectorTest, OverflowTest) {
 215   SCOPED_TRACE("OverflowTest");
 216
 217   // Push more elements than the fixed size
 218   makeSequence(theVector, 1, 10);
 219
 220   // test size and values
 221   EXPECT_EQ(10u, theVector.size());
 222   for (int i = 0; i < 10; ++i) {
 223     EXPECT_EQ(i+1, theVector[i].getValue());
 224   }
 225
 226   // Now resize back to fixed size
 227   theVector.resize(1);
 228
 229   assertValuesInOrder(theVector, 1u, 1);
 230 }
 231
 232 // Iteration tests.
 233 TEST_F(SmallVectorTest, IterationTest) {
 234   makeSequence(theVector, 1, 2);
 235
 236   // Forward Iteration
 237   VectorType::iterator it = theVector.begin();
 238   EXPECT_TRUE(*it == theVector.front());
 239   EXPECT_TRUE(*it == theVector[0]);
 240   EXPECT_EQ(1, it->getValue());
 241   ++it;
 242   EXPECT_TRUE(*it == theVector[1]);
 243   EXPECT_TRUE(*it == theVector.back());
 244   EXPECT_EQ(2, it->getValue());
 245   ++it;
 246   EXPECT_TRUE(it == theVector.end());
 247   --it;
 248   EXPECT_TRUE(*it == theVector[1]);
 249   EXPECT_EQ(2, it->getValue());
 250   --it;
 251   EXPECT_TRUE(*it == theVector[0]);
 252   EXPECT_EQ(1, it->getValue());
 253
 254   // Reverse Iteration
 255   VectorType::reverse_iterator rit = theVector.rbegin();
 256   EXPECT_TRUE(*rit == theVector[1]);
 257   EXPECT_EQ(2, rit->getValue());
 258   ++rit;
 259   EXPECT_TRUE(*rit == theVector[0]);
 260   EXPECT_EQ(1, rit->getValue());
 261   ++rit;
 262   EXPECT_TRUE(rit == theVector.rend());
 263   --rit;
 264   EXPECT_TRUE(*rit == theVector[0]);
 265   EXPECT_EQ(1, rit->getValue());
 266   --rit;
 267   EXPECT_TRUE(*rit == theVector[1]);
 268   EXPECT_EQ(2, rit->getValue());
 269 }
 270
 271 // Swap test.
 272 TEST_F(SmallVectorTest, SwapTest) {
 273   SCOPED_TRACE("SwapTest");
 274
 275   makeSequence(theVector, 1, 2);
 276   std::swap(theVector, otherVector);
 277
 278   assertEmpty(theVector);
 279   assertValuesInOrder(otherVector, 2u, 1, 2);
 280 }
 281
 282 // Append test
 283 TEST_F(SmallVectorTest, AppendTest) {
 284   SCOPED_TRACE("AppendTest");
 285
 286   makeSequence(otherVector, 2, 3);
 287
 288   theVector.push_back(Constructable(1));
 289   theVector.append(otherVector.begin(), otherVector.end());
 290
 291   assertValuesInOrder(theVector, 3u, 1, 2, 3);
 292 }
 293
 294 // Append repeated test
 295 TEST_F(SmallVectorTest, AppendRepeatedTest) {
 296   SCOPED_TRACE("AppendRepeatedTest");
 297
 298   theVector.push_back(Constructable(1));
 299   theVector.append(2, Constructable(77));
 300   assertValuesInOrder(theVector, 3u, 1, 77, 77);
 301 }
 302
 303 // Assign test
 304 TEST_F(SmallVectorTest, AssignTest) {
 305   SCOPED_TRACE("AssignTest");
 306
 307   theVector.push_back(Constructable(1));
 308   theVector.assign(2, Constructable(77));
 309   assertValuesInOrder(theVector, 2u, 77, 77);
 310 }
 311
 312 // Erase a single element
 313 TEST_F(SmallVectorTest, EraseTest) {
 314   SCOPED_TRACE("EraseTest");
 315
 316   makeSequence(theVector, 1, 3);
 317   theVector.erase(theVector.begin());
 318   assertValuesInOrder(theVector, 2u, 2, 3);
 319 }
 320
 321 // Erase a range of elements
 322 TEST_F(SmallVectorTest, EraseRangeTest) {
 323   SCOPED_TRACE("EraseRangeTest");
 324
 325   makeSequence(theVector, 1, 3);
 326   theVector.erase(theVector.begin(), theVector.begin() + 2);
 327   assertValuesInOrder(theVector, 1u, 3);
 328 }
 329
 330 // Insert a single element.
 331 TEST_F(SmallVectorTest, InsertTest) {
 332   SCOPED_TRACE("InsertTest");
 333
 334   makeSequence(theVector, 1, 3);
 335   theVector.insert(theVector.begin() + 1, Constructable(77));
 336   assertValuesInOrder(theVector, 4u, 1, 77, 2, 3);
 337 }
 338
 339 // Insert repeated elements.
 340 TEST_F(SmallVectorTest, InsertRepeatedTest) {
 341   SCOPED_TRACE("InsertRepeatedTest");
 342
 343   makeSequence(theVector, 1, 3);
 344   theVector.insert(theVector.begin() + 1, 3, Constructable(77));
 345   assertValuesInOrder(theVector, 6u, 1, 77, 77, 77, 2, 3);
 346 }
 347
 348 // Insert range.
 349 TEST_F(SmallVectorTest, InsertRangeTest) {
 350   SCOPED_TRACE("InsertRepeatedTest");
 351
 352   makeSequence(theVector, 1, 3);
 353   theVector.insert(theVector.begin() + 1, 3, Constructable(77));
 354   assertValuesInOrder(theVector, 6u, 1, 77, 77, 77, 2, 3);
 355 }
 356
 357 // Comparison tests.
 358 TEST_F(SmallVectorTest, ComparisonTest) {
 359   SCOPED_TRACE("ComparisonTest");
 360
 361   makeSequence(theVector, 1, 3);
 362   makeSequence(otherVector, 1, 3);
 363
 364   EXPECT_TRUE(theVector == otherVector);
 365   EXPECT_FALSE(theVector != otherVector);
 366
 367   otherVector.clear();
 368   makeSequence(otherVector, 2, 4);
 369
 370   EXPECT_FALSE(theVector == otherVector);
 371   EXPECT_TRUE(theVector != otherVector);
 372 }
 373
 374 // Constant vector tests.
 375 TEST_F(SmallVectorTest, ConstVectorTest) {
 376   const VectorType constVector;
 377
 378   EXPECT_EQ(0u, constVector.size());
 379   EXPECT_TRUE(constVector.empty());
 380   EXPECT_TRUE(constVector.begin() == constVector.end());
 381 }
 382
 383 }