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 "llvm/Support/Compiler.h"
17#include <stdarg.h>
18#include <list>
19
20using namespace llvm;
21
22namespace {
23
24/// A helper class that counts the total number of constructor and
25/// destructor calls.
26class Constructable {
27private:
28  static int numConstructorCalls;
29  static int numDestructorCalls;
30  static int numAssignmentCalls;
31
32  int value;
33
34public:
35  Constructable() : value(0) {
36    ++numConstructorCalls;
37  }
38
39  Constructable(int val) : value(val) {
40    ++numConstructorCalls;
41  }
42
43  Constructable(const Constructable & src) {
44    value = src.value;
45    ++numConstructorCalls;
46  }
47
48  ~Constructable() {
49    ++numDestructorCalls;
50  }
51
52  Constructable & operator=(const Constructable & src) {
53    value = src.value;
54    ++numAssignmentCalls;
55    return *this;
56  }
57
58  int getValue() const {
59    return abs(value);
60  }
61
62  static void reset() {
63    numConstructorCalls = 0;
64    numDestructorCalls = 0;
65    numAssignmentCalls = 0;
66  }
67
68  static int getNumConstructorCalls() {
69    return numConstructorCalls;
70  }
71
72  static int getNumDestructorCalls() {
73    return numDestructorCalls;
74  }
75
76  friend bool operator==(const Constructable & c0, const Constructable & c1) {
77    return c0.getValue() == c1.getValue();
78  }
79
80  friend bool LLVM_ATTRIBUTE_UNUSED
81  operator!=(const Constructable & c0, const Constructable & c1) {
82    return c0.getValue() != c1.getValue();
83  }
84};
85
86int Constructable::numConstructorCalls;
87int Constructable::numDestructorCalls;
88int Constructable::numAssignmentCalls;
89
90// Test fixture class
91template <typename VectorT>
92class SmallVectorTest : public testing::Test {
93protected:
94  VectorT theVector;
95  VectorT otherVector;
96
97  void SetUp() {
98    Constructable::reset();
99  }
100
101  void assertEmpty(VectorT & v) {
102    // Size tests
103    EXPECT_EQ(0u, v.size());
104    EXPECT_TRUE(v.empty());
105
106    // Iterator tests
107    EXPECT_TRUE(v.begin() == v.end());
108  }
109
110  // Assert that theVector contains the specified values, in order.
111  void assertValuesInOrder(VectorT & v, size_t size, ...) {
112    EXPECT_EQ(size, v.size());
113
114    va_list ap;
115    va_start(ap, size);
116    for (size_t i = 0; i < size; ++i) {
117      int value = va_arg(ap, int);
118      EXPECT_EQ(value, v[i].getValue());
119    }
120
121    va_end(ap);
122  }
123
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));
128    }
129  }
130};
131
132typedef ::testing::Types<SmallVector<Constructable, 0>,
133                         SmallVector<Constructable, 1>,
134                         SmallVector<Constructable, 2>,
135                         SmallVector<Constructable, 4>
136                         > SmallVectorTestTypes;
137TYPED_TEST_CASE(SmallVectorTest, SmallVectorTestTypes);
138
139// New vector test.
140TYPED_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());
146}
147
148// Simple insertions and deletions.
149TYPED_TEST(SmallVectorTest, PushPopTest) {
150  SCOPED_TRACE("PushPopTest");
151
152  // Track whether the vector will potentially have to grow.
153  bool RequiresGrowth = this->theVector.capacity() < 3;
154
155  // Push an element
156  this->theVector.push_back(Constructable(1));
157
158  // Size tests
159  this->assertValuesInOrder(this->theVector, 1u, 1);
160  EXPECT_FALSE(this->theVector.begin() == this->theVector.end());
161  EXPECT_FALSE(this->theVector.empty());
162
163  // Push another element
164  this->theVector.push_back(Constructable(2));
165  this->assertValuesInOrder(this->theVector, 2u, 1, 2);
166
167  // Insert at beginning
168  this->theVector.insert(this->theVector.begin(), this->theVector[1]);
169  this->assertValuesInOrder(this->theVector, 3u, 2, 1, 2);
170
171  // Pop one element
172  this->theVector.pop_back();
173  this->assertValuesInOrder(this->theVector, 2u, 2, 1);
174
175  // Pop remaining elements
176  this->theVector.pop_back();
177  this->theVector.pop_back();
178  this->assertEmpty(this->theVector);
179
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());
186  } else {
187    // If we had to grow the vector, these only have a lower bound, but should
188    // always be equal.
189    EXPECT_LE(5, Constructable::getNumConstructorCalls());
190    EXPECT_EQ(Constructable::getNumConstructorCalls(),
191              Constructable::getNumDestructorCalls());
192  }
193}
194
195// Clear test.
196TYPED_TEST(SmallVectorTest, ClearTest) {
197  SCOPED_TRACE("ClearTest");
198
199  this->theVector.reserve(2);
200  this->makeSequence(this->theVector, 1, 2);
201  this->theVector.clear();
202
203  this->assertEmpty(this->theVector);
204  EXPECT_EQ(4, Constructable::getNumConstructorCalls());
205  EXPECT_EQ(4, Constructable::getNumDestructorCalls());
206}
207
208// Resize smaller test.
209TYPED_TEST(SmallVectorTest, ResizeShrinkTest) {
210  SCOPED_TRACE("ResizeShrinkTest");
211
212  this->theVector.reserve(3);
213  this->makeSequence(this->theVector, 1, 3);
214  this->theVector.resize(1);
215
216  this->assertValuesInOrder(this->theVector, 1u, 1);
217  EXPECT_EQ(6, Constructable::getNumConstructorCalls());
218  EXPECT_EQ(5, Constructable::getNumDestructorCalls());
219}
220
221// Resize bigger test.
222TYPED_TEST(SmallVectorTest, ResizeGrowTest) {
223  SCOPED_TRACE("ResizeGrowTest");
224
225  this->theVector.resize(2);
226
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());
232}
233
234// Resize with fill value.
235TYPED_TEST(SmallVectorTest, ResizeFillTest) {
236  SCOPED_TRACE("ResizeFillTest");
237
238  this->theVector.resize(3, Constructable(77));
239  this->assertValuesInOrder(this->theVector, 3u, 77, 77, 77);
240}
241
242// Overflow past fixed size.
243TYPED_TEST(SmallVectorTest, OverflowTest) {
244  SCOPED_TRACE("OverflowTest");
245
246  // Push more elements than the fixed size.
247  this->makeSequence(this->theVector, 1, 10);
248
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());
253  }
254
255  // Now resize back to fixed size.
256  this->theVector.resize(1);
257
258  this->assertValuesInOrder(this->theVector, 1u, 1);
259}
260
261// Iteration tests.
262TYPED_TEST(SmallVectorTest, IterationTest) {
263  this->makeSequence(this->theVector, 1, 2);
264
265  // Forward Iteration
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());
270  ++it;
271  EXPECT_TRUE(*it == this->theVector[1]);
272  EXPECT_TRUE(*it == this->theVector.back());
273  EXPECT_EQ(2, it->getValue());
274  ++it;
275  EXPECT_TRUE(it == this->theVector.end());
276  --it;
277  EXPECT_TRUE(*it == this->theVector[1]);
278  EXPECT_EQ(2, it->getValue());
279  --it;
280  EXPECT_TRUE(*it == this->theVector[0]);
281  EXPECT_EQ(1, it->getValue());
282
283  // Reverse Iteration
284  typename TypeParam::reverse_iterator rit = this->theVector.rbegin();
285  EXPECT_TRUE(*rit == this->theVector[1]);
286  EXPECT_EQ(2, rit->getValue());
287  ++rit;
288  EXPECT_TRUE(*rit == this->theVector[0]);
289  EXPECT_EQ(1, rit->getValue());
290  ++rit;
291  EXPECT_TRUE(rit == this->theVector.rend());
292  --rit;
293  EXPECT_TRUE(*rit == this->theVector[0]);
294  EXPECT_EQ(1, rit->getValue());
295  --rit;
296  EXPECT_TRUE(*rit == this->theVector[1]);
297  EXPECT_EQ(2, rit->getValue());
298}
299
300// Swap test.
301TYPED_TEST(SmallVectorTest, SwapTest) {
302  SCOPED_TRACE("SwapTest");
303
304  this->makeSequence(this->theVector, 1, 2);
305  std::swap(this->theVector, this->otherVector);
306
307  this->assertEmpty(this->theVector);
308  this->assertValuesInOrder(this->otherVector, 2u, 1, 2);
309}
310
311// Append test
312TYPED_TEST(SmallVectorTest, AppendTest) {
313  SCOPED_TRACE("AppendTest");
314
315  this->makeSequence(this->otherVector, 2, 3);
316
317  this->theVector.push_back(Constructable(1));
318  this->theVector.append(this->otherVector.begin(), this->otherVector.end());
319
320  this->assertValuesInOrder(this->theVector, 3u, 1, 2, 3);
321}
322
323// Append repeated test
324TYPED_TEST(SmallVectorTest, AppendRepeatedTest) {
325  SCOPED_TRACE("AppendRepeatedTest");
326
327  this->theVector.push_back(Constructable(1));
328  this->theVector.append(2, Constructable(77));
329  this->assertValuesInOrder(this->theVector, 3u, 1, 77, 77);
330}
331
332// Assign test
333TYPED_TEST(SmallVectorTest, AssignTest) {
334  SCOPED_TRACE("AssignTest");
335
336  this->theVector.push_back(Constructable(1));
337  this->theVector.assign(2, Constructable(77));
338  this->assertValuesInOrder(this->theVector, 2u, 77, 77);
339}
340
341// Erase a single element
342TYPED_TEST(SmallVectorTest, EraseTest) {
343  SCOPED_TRACE("EraseTest");
344
345  this->makeSequence(this->theVector, 1, 3);
346  this->theVector.erase(this->theVector.begin());
347  this->assertValuesInOrder(this->theVector, 2u, 2, 3);
348}
349
350// Erase a range of elements
351TYPED_TEST(SmallVectorTest, EraseRangeTest) {
352  SCOPED_TRACE("EraseRangeTest");
353
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);
357}
358
359// Insert a single element.
360TYPED_TEST(SmallVectorTest, InsertTest) {
361  SCOPED_TRACE("InsertTest");
362
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);
368}
369
370// Insert repeated elements.
371TYPED_TEST(SmallVectorTest, InsertRepeatedTest) {
372  SCOPED_TRACE("InsertRepeatedTest");
373
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);
380
381  // Insert at end.
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);
386
387  // Empty insert.
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)));
394}
395
396// Insert range.
397TYPED_TEST(SmallVectorTest, InsertRangeTest) {
398  SCOPED_TRACE("InsertRangeTest");
399
400  Constructable Arr[3] =
401    { Constructable(77), Constructable(77), Constructable(77) };
402
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);
408
409  // Insert at end.
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);
414
415  // Empty insert.
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()));
424}
425
426// Comparison tests.
427TYPED_TEST(SmallVectorTest, ComparisonTest) {
428  SCOPED_TRACE("ComparisonTest");
429
430  this->makeSequence(this->theVector, 1, 3);
431  this->makeSequence(this->otherVector, 1, 3);
432
433  EXPECT_TRUE(this->theVector == this->otherVector);
434  EXPECT_FALSE(this->theVector != this->otherVector);
435
436  this->otherVector.clear();
437  this->makeSequence(this->otherVector, 2, 4);
438
439  EXPECT_FALSE(this->theVector == this->otherVector);
440  EXPECT_TRUE(this->theVector != this->otherVector);
441}
442
443// Constant vector tests.
444TYPED_TEST(SmallVectorTest, ConstVectorTest) {
445  const TypeParam constVector;
446
447  EXPECT_EQ(0u, constVector.size());
448  EXPECT_TRUE(constVector.empty());
449  EXPECT_TRUE(constVector.begin() == constVector.end());
450}
451
452// Direct array access.
453TYPED_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());
469}
470
471TYPED_TEST(SmallVectorTest, IteratorTest) {
472  std::list<int> L;
473  this->theVector.insert(this->theVector.end(), L.begin(), L.end());
474}
475
476struct notassignable {
477  int &x;
478  notassignable(int &x) : x(x) {}
479};
480
481TEST(SmallVectorCustomTest, NoAssignTest) {
482  int x = 0;
483  SmallVector<notassignable, 2> vec;
484  vec.push_back(notassignable(x));
485  x = 42;
486  EXPECT_EQ(42, vec.pop_back_val().x);
487}
488
489}
490