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 } 385