1 //===- llvm/unittest/ADT/SmallVectorTest.cpp ------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // SmallVector unit tests.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/ADT/SmallVector.h"
15 #include "llvm/Support/Compiler.h"
16 #include "gtest/gtest.h"
24 /// A helper class that counts the total number of constructor and
28 static int numConstructorCalls;
29 static int numDestructorCalls;
30 static int numAssignmentCalls;
35 Constructable() : value(0) {
36 ++numConstructorCalls;
39 Constructable(int val) : value(val) {
40 ++numConstructorCalls;
43 Constructable(const Constructable & src) {
45 ++numConstructorCalls;
52 Constructable & operator=(const Constructable & src) {
58 int getValue() const {
63 numConstructorCalls = 0;
64 numDestructorCalls = 0;
65 numAssignmentCalls = 0;
68 static int getNumConstructorCalls() {
69 return numConstructorCalls;
72 static int getNumDestructorCalls() {
73 return numDestructorCalls;
76 friend bool operator==(const Constructable & c0, const Constructable & c1) {
77 return c0.getValue() == c1.getValue();
80 friend bool LLVM_ATTRIBUTE_UNUSED
81 operator!=(const Constructable & c0, const Constructable & c1) {
82 return c0.getValue() != c1.getValue();
86 int Constructable::numConstructorCalls;
87 int Constructable::numDestructorCalls;
88 int Constructable::numAssignmentCalls;
91 template <typename VectorT>
92 class SmallVectorTest : public testing::Test {
98 Constructable::reset();
101 void assertEmpty(VectorT & v) {
103 EXPECT_EQ(0u, v.size());
104 EXPECT_TRUE(v.empty());
107 EXPECT_TRUE(v.begin() == v.end());
110 // Assert that theVector contains the specified values, in order.
111 void assertValuesInOrder(VectorT & v, size_t size, ...) {
112 EXPECT_EQ(size, v.size());
116 for (size_t i = 0; i < size; ++i) {
117 int value = va_arg(ap, int);
118 EXPECT_EQ(value, v[i].getValue());
124 // Generate a sequence of values to initialize the vector.
125 void makeSequence(VectorT & v, int start, int end) {
126 for (int i = start; i <= end; ++i) {
127 v.push_back(Constructable(i));
132 typedef ::testing::Types<SmallVector<Constructable, 0>,
133 SmallVector<Constructable, 1>,
134 SmallVector<Constructable, 2>,
135 SmallVector<Constructable, 4>
136 > SmallVectorTestTypes;
137 TYPED_TEST_CASE(SmallVectorTest, SmallVectorTestTypes);
140 TYPED_TEST(SmallVectorTest, EmptyVectorTest) {
141 SCOPED_TRACE("EmptyVectorTest");
142 this->assertEmpty(this->theVector);
143 EXPECT_TRUE(this->theVector.rbegin() == this->theVector.rend());
144 EXPECT_EQ(0, Constructable::getNumConstructorCalls());
145 EXPECT_EQ(0, Constructable::getNumDestructorCalls());
148 // Simple insertions and deletions.
149 TYPED_TEST(SmallVectorTest, PushPopTest) {
150 SCOPED_TRACE("PushPopTest");
152 // Track whether the vector will potentially have to grow.
153 bool RequiresGrowth = this->theVector.capacity() < 3;
156 this->theVector.push_back(Constructable(1));
159 this->assertValuesInOrder(this->theVector, 1u, 1);
160 EXPECT_FALSE(this->theVector.begin() == this->theVector.end());
161 EXPECT_FALSE(this->theVector.empty());
163 // Push another element
164 this->theVector.push_back(Constructable(2));
165 this->assertValuesInOrder(this->theVector, 2u, 1, 2);
167 // Insert at beginning
168 this->theVector.insert(this->theVector.begin(), this->theVector[1]);
169 this->assertValuesInOrder(this->theVector, 3u, 2, 1, 2);
172 this->theVector.pop_back();
173 this->assertValuesInOrder(this->theVector, 2u, 2, 1);
175 // Pop remaining elements
176 this->theVector.pop_back();
177 this->theVector.pop_back();
178 this->assertEmpty(this->theVector);
180 // Check number of constructor calls. Should be 2 for each list element,
181 // one for the argument to push_back, one for the argument to insert,
182 // and one for the list element itself.
183 if (!RequiresGrowth) {
184 EXPECT_EQ(5, Constructable::getNumConstructorCalls());
185 EXPECT_EQ(5, Constructable::getNumDestructorCalls());
187 // If we had to grow the vector, these only have a lower bound, but should
189 EXPECT_LE(5, Constructable::getNumConstructorCalls());
190 EXPECT_EQ(Constructable::getNumConstructorCalls(),
191 Constructable::getNumDestructorCalls());
196 TYPED_TEST(SmallVectorTest, ClearTest) {
197 SCOPED_TRACE("ClearTest");
199 this->theVector.reserve(2);
200 this->makeSequence(this->theVector, 1, 2);
201 this->theVector.clear();
203 this->assertEmpty(this->theVector);
204 EXPECT_EQ(4, Constructable::getNumConstructorCalls());
205 EXPECT_EQ(4, Constructable::getNumDestructorCalls());
208 // Resize smaller test.
209 TYPED_TEST(SmallVectorTest, ResizeShrinkTest) {
210 SCOPED_TRACE("ResizeShrinkTest");
212 this->theVector.reserve(3);
213 this->makeSequence(this->theVector, 1, 3);
214 this->theVector.resize(1);
216 this->assertValuesInOrder(this->theVector, 1u, 1);
217 EXPECT_EQ(6, Constructable::getNumConstructorCalls());
218 EXPECT_EQ(5, Constructable::getNumDestructorCalls());
221 // Resize bigger test.
222 TYPED_TEST(SmallVectorTest, ResizeGrowTest) {
223 SCOPED_TRACE("ResizeGrowTest");
225 this->theVector.resize(2);
227 // The extra constructor/destructor calls come from the temporary object used
228 // to initialize the contents of the resized array (via copy construction).
229 EXPECT_EQ(3, Constructable::getNumConstructorCalls());
230 EXPECT_EQ(1, Constructable::getNumDestructorCalls());
231 EXPECT_EQ(2u, this->theVector.size());
234 // Resize with fill value.
235 TYPED_TEST(SmallVectorTest, ResizeFillTest) {
236 SCOPED_TRACE("ResizeFillTest");
238 this->theVector.resize(3, Constructable(77));
239 this->assertValuesInOrder(this->theVector, 3u, 77, 77, 77);
242 // Overflow past fixed size.
243 TYPED_TEST(SmallVectorTest, OverflowTest) {
244 SCOPED_TRACE("OverflowTest");
246 // Push more elements than the fixed size.
247 this->makeSequence(this->theVector, 1, 10);
249 // Test size and values.
250 EXPECT_EQ(10u, this->theVector.size());
251 for (int i = 0; i < 10; ++i) {
252 EXPECT_EQ(i+1, this->theVector[i].getValue());
255 // Now resize back to fixed size.
256 this->theVector.resize(1);
258 this->assertValuesInOrder(this->theVector, 1u, 1);
262 TYPED_TEST(SmallVectorTest, IterationTest) {
263 this->makeSequence(this->theVector, 1, 2);
266 typename TypeParam::iterator it = this->theVector.begin();
267 EXPECT_TRUE(*it == this->theVector.front());
268 EXPECT_TRUE(*it == this->theVector[0]);
269 EXPECT_EQ(1, it->getValue());
271 EXPECT_TRUE(*it == this->theVector[1]);
272 EXPECT_TRUE(*it == this->theVector.back());
273 EXPECT_EQ(2, it->getValue());
275 EXPECT_TRUE(it == this->theVector.end());
277 EXPECT_TRUE(*it == this->theVector[1]);
278 EXPECT_EQ(2, it->getValue());
280 EXPECT_TRUE(*it == this->theVector[0]);
281 EXPECT_EQ(1, it->getValue());
284 typename TypeParam::reverse_iterator rit = this->theVector.rbegin();
285 EXPECT_TRUE(*rit == this->theVector[1]);
286 EXPECT_EQ(2, rit->getValue());
288 EXPECT_TRUE(*rit == this->theVector[0]);
289 EXPECT_EQ(1, rit->getValue());
291 EXPECT_TRUE(rit == this->theVector.rend());
293 EXPECT_TRUE(*rit == this->theVector[0]);
294 EXPECT_EQ(1, rit->getValue());
296 EXPECT_TRUE(*rit == this->theVector[1]);
297 EXPECT_EQ(2, rit->getValue());
301 TYPED_TEST(SmallVectorTest, SwapTest) {
302 SCOPED_TRACE("SwapTest");
304 this->makeSequence(this->theVector, 1, 2);
305 std::swap(this->theVector, this->otherVector);
307 this->assertEmpty(this->theVector);
308 this->assertValuesInOrder(this->otherVector, 2u, 1, 2);
312 TYPED_TEST(SmallVectorTest, AppendTest) {
313 SCOPED_TRACE("AppendTest");
315 this->makeSequence(this->otherVector, 2, 3);
317 this->theVector.push_back(Constructable(1));
318 this->theVector.append(this->otherVector.begin(), this->otherVector.end());
320 this->assertValuesInOrder(this->theVector, 3u, 1, 2, 3);
323 // Append repeated test
324 TYPED_TEST(SmallVectorTest, AppendRepeatedTest) {
325 SCOPED_TRACE("AppendRepeatedTest");
327 this->theVector.push_back(Constructable(1));
328 this->theVector.append(2, Constructable(77));
329 this->assertValuesInOrder(this->theVector, 3u, 1, 77, 77);
333 TYPED_TEST(SmallVectorTest, AssignTest) {
334 SCOPED_TRACE("AssignTest");
336 this->theVector.push_back(Constructable(1));
337 this->theVector.assign(2, Constructable(77));
338 this->assertValuesInOrder(this->theVector, 2u, 77, 77);
341 // Erase a single element
342 TYPED_TEST(SmallVectorTest, EraseTest) {
343 SCOPED_TRACE("EraseTest");
345 this->makeSequence(this->theVector, 1, 3);
346 this->theVector.erase(this->theVector.begin());
347 this->assertValuesInOrder(this->theVector, 2u, 2, 3);
350 // Erase a range of elements
351 TYPED_TEST(SmallVectorTest, EraseRangeTest) {
352 SCOPED_TRACE("EraseRangeTest");
354 this->makeSequence(this->theVector, 1, 3);
355 this->theVector.erase(this->theVector.begin(), this->theVector.begin() + 2);
356 this->assertValuesInOrder(this->theVector, 1u, 3);
359 // Insert a single element.
360 TYPED_TEST(SmallVectorTest, InsertTest) {
361 SCOPED_TRACE("InsertTest");
363 this->makeSequence(this->theVector, 1, 3);
364 typename TypeParam::iterator I =
365 this->theVector.insert(this->theVector.begin() + 1, Constructable(77));
366 EXPECT_EQ(this->theVector.begin() + 1, I);
367 this->assertValuesInOrder(this->theVector, 4u, 1, 77, 2, 3);
370 // Insert repeated elements.
371 TYPED_TEST(SmallVectorTest, InsertRepeatedTest) {
372 SCOPED_TRACE("InsertRepeatedTest");
374 this->makeSequence(this->theVector, 10, 15);
375 typename TypeParam::iterator I =
376 this->theVector.insert(this->theVector.begin() + 1, 2, Constructable(16));
377 EXPECT_EQ(this->theVector.begin() + 1, I);
378 this->assertValuesInOrder(this->theVector, 8u,
379 10, 16, 16, 11, 12, 13, 14, 15);
382 I = this->theVector.insert(this->theVector.end(), 2, Constructable(16));
383 EXPECT_EQ(this->theVector.begin() + 8, I);
384 this->assertValuesInOrder(this->theVector, 10u,
385 10, 16, 16, 11, 12, 13, 14, 15, 16, 16);
388 EXPECT_EQ(this->theVector.end(),
389 this->theVector.insert(this->theVector.end(),
390 0, Constructable(42)));
391 EXPECT_EQ(this->theVector.begin() + 1,
392 this->theVector.insert(this->theVector.begin() + 1,
393 0, Constructable(42)));
397 TYPED_TEST(SmallVectorTest, InsertRangeTest) {
398 SCOPED_TRACE("InsertRangeTest");
400 Constructable Arr[3] =
401 { Constructable(77), Constructable(77), Constructable(77) };
403 this->makeSequence(this->theVector, 1, 3);
404 typename TypeParam::iterator I =
405 this->theVector.insert(this->theVector.begin() + 1, Arr, Arr+3);
406 EXPECT_EQ(this->theVector.begin() + 1, I);
407 this->assertValuesInOrder(this->theVector, 6u, 1, 77, 77, 77, 2, 3);
410 I = this->theVector.insert(this->theVector.end(), Arr, Arr+3);
411 EXPECT_EQ(this->theVector.begin() + 6, I);
412 this->assertValuesInOrder(this->theVector, 9u,
413 1, 77, 77, 77, 2, 3, 77, 77, 77);
416 EXPECT_EQ(this->theVector.end(),
417 this->theVector.insert(this->theVector.end(),
418 this->theVector.begin(),
419 this->theVector.begin()));
420 EXPECT_EQ(this->theVector.begin() + 1,
421 this->theVector.insert(this->theVector.begin() + 1,
422 this->theVector.begin(),
423 this->theVector.begin()));
427 TYPED_TEST(SmallVectorTest, ComparisonTest) {
428 SCOPED_TRACE("ComparisonTest");
430 this->makeSequence(this->theVector, 1, 3);
431 this->makeSequence(this->otherVector, 1, 3);
433 EXPECT_TRUE(this->theVector == this->otherVector);
434 EXPECT_FALSE(this->theVector != this->otherVector);
436 this->otherVector.clear();
437 this->makeSequence(this->otherVector, 2, 4);
439 EXPECT_FALSE(this->theVector == this->otherVector);
440 EXPECT_TRUE(this->theVector != this->otherVector);
443 // Constant vector tests.
444 TYPED_TEST(SmallVectorTest, ConstVectorTest) {
445 const TypeParam constVector;
447 EXPECT_EQ(0u, constVector.size());
448 EXPECT_TRUE(constVector.empty());
449 EXPECT_TRUE(constVector.begin() == constVector.end());
452 // Direct array access.
453 TYPED_TEST(SmallVectorTest, DirectVectorTest) {
454 EXPECT_EQ(0u, this->theVector.size());
455 this->theVector.reserve(4);
456 EXPECT_LE(4u, this->theVector.capacity());
457 EXPECT_EQ(0, Constructable::getNumConstructorCalls());
458 this->theVector.end()[0] = 1;
459 this->theVector.end()[1] = 2;
460 this->theVector.end()[2] = 3;
461 this->theVector.end()[3] = 4;
462 this->theVector.set_size(4);
463 EXPECT_EQ(4u, this->theVector.size());
464 EXPECT_EQ(4, Constructable::getNumConstructorCalls());
465 EXPECT_EQ(1, this->theVector[0].getValue());
466 EXPECT_EQ(2, this->theVector[1].getValue());
467 EXPECT_EQ(3, this->theVector[2].getValue());
468 EXPECT_EQ(4, this->theVector[3].getValue());
471 TYPED_TEST(SmallVectorTest, IteratorTest) {
473 this->theVector.insert(this->theVector.end(), L.begin(), L.end());
476 struct notassignable {
478 notassignable(int &x) : x(x) {}
481 TEST(SmallVectorCustomTest, NoAssignTest) {
483 SmallVector<notassignable, 2> vec;
484 vec.push_back(notassignable(x));
486 EXPECT_EQ(42, vec.pop_back_val().x);