SmallVectorTest.cpp revision 614be08dd6ae0755d8a4c32ad49f5f580602cc78 
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
18using namespace llvm;
19
20namespace {
21
22/// A helper class that counts the total number of constructor and
23/// destructor calls.
24class Constructable {
25private:
26  static int numConstructorCalls;
27  static int numDestructorCalls;
28  static int numAssignmentCalls;
29
30  int value;
31
32public:
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
83int Constructable::numConstructorCalls;
84int Constructable::numDestructorCalls;
85int Constructable::numAssignmentCalls;
86
87// Test fixture class
88class SmallVectorTest : public testing::Test {
89protected:
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.
131TEST_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.
140TEST_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.
170TEST_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.
182TEST_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.
194TEST_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.
207TEST_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.
215TEST_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.
234TEST_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.
273TEST_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
284TEST_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
296TEST_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
305TEST_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
314TEST_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
323TEST_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.
332TEST_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.
341TEST_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.
350TEST_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.
359TEST_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.
376TEST_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