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 
20 using namespace llvm;
21 
22 namespace {
23 
24 /// A helper class that counts the total number of constructor and
25 /// destructor calls.
26 class Constructable {
27 private:
28   static int numConstructorCalls;
29   static int numDestructorCalls;
30   static int numAssignmentCalls;
31 
32   int value;
33 
34 public:
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 
86 int Constructable::numConstructorCalls;
87 int Constructable::numDestructorCalls;
88 int Constructable::numAssignmentCalls;
89 
90 // Test fixture class
91 class SmallVectorTest : public testing::Test {
92 protected:
93   typedef SmallVector<Constructable, 4> VectorType;
94 
95   VectorType theVector;
96   VectorType otherVector;
97 
98   void SetUp() {
99     Constructable::reset();
100   }
101 
102   void assertEmpty(VectorType & v) {
103     // Size tests
104     EXPECT_EQ(0u, v.size());
105     EXPECT_TRUE(v.empty());
106 
107     // Iterator tests
108     EXPECT_TRUE(v.begin() == v.end());
109   }
110 
111   // Assert that theVector contains the specified values, in order.
112   void assertValuesInOrder(VectorType & v, size_t size, ...) {
113     EXPECT_EQ(size, v.size());
114 
115     va_list ap;
116     va_start(ap, size);
117     for (size_t i = 0; i < size; ++i) {
118       int value = va_arg(ap, int);
119       EXPECT_EQ(value, v[i].getValue());
120     }
121 
122     va_end(ap);
123   }
124 
125   // Generate a sequence of values to initialize the vector.
126   void makeSequence(VectorType & v, int start, int end) {
127     for (int i = start; i <= end; ++i) {
128       v.push_back(Constructable(i));
129     }
130   }
131 };
132 
133 // New vector test.
134 TEST_F(SmallVectorTest, EmptyVectorTest) {
135   SCOPED_TRACE("EmptyVectorTest");
136   assertEmpty(theVector);
137   EXPECT_TRUE(theVector.rbegin() == theVector.rend());
138   EXPECT_EQ(0, Constructable::getNumConstructorCalls());
139   EXPECT_EQ(0, Constructable::getNumDestructorCalls());
140 }
141 
142 // Simple insertions and deletions.
143 TEST_F(SmallVectorTest, PushPopTest) {
144   SCOPED_TRACE("PushPopTest");
145 
146   // Push an element
147   theVector.push_back(Constructable(1));
148 
149   // Size tests
150   assertValuesInOrder(theVector, 1u, 1);
151   EXPECT_FALSE(theVector.begin() == theVector.end());
152   EXPECT_FALSE(theVector.empty());
153 
154   // Push another element
155   theVector.push_back(Constructable(2));
156   assertValuesInOrder(theVector, 2u, 1, 2);
157 
158   // Pop one element
159   theVector.pop_back();
160   assertValuesInOrder(theVector, 1u, 1);
161 
162   // Pop another element
163   theVector.pop_back();
164   assertEmpty(theVector);
165 
166   // Check number of constructor calls. Should be 2 for each list element,
167   // one for the argument to push_back, and one for the list element itself.
168   EXPECT_EQ(4, Constructable::getNumConstructorCalls());
169   EXPECT_EQ(4, Constructable::getNumDestructorCalls());
170 }
171 
172 // Clear test.
173 TEST_F(SmallVectorTest, ClearTest) {
174   SCOPED_TRACE("ClearTest");
175 
176   makeSequence(theVector, 1, 2);
177   theVector.clear();
178 
179   assertEmpty(theVector);
180   EXPECT_EQ(4, Constructable::getNumConstructorCalls());
181   EXPECT_EQ(4, Constructable::getNumDestructorCalls());
182 }
183 
184 // Resize smaller test.
185 TEST_F(SmallVectorTest, ResizeShrinkTest) {
186   SCOPED_TRACE("ResizeShrinkTest");
187 
188   makeSequence(theVector, 1, 3);
189   theVector.resize(1);
190 
191   assertValuesInOrder(theVector, 1u, 1);
192   EXPECT_EQ(6, Constructable::getNumConstructorCalls());
193   EXPECT_EQ(5, Constructable::getNumDestructorCalls());
194 }
195 
196 // Resize bigger test.
197 TEST_F(SmallVectorTest, ResizeGrowTest) {
198   SCOPED_TRACE("ResizeGrowTest");
199 
200   theVector.resize(2);
201 
202   // The extra constructor/destructor calls come from the temporary object used
203   // to initialize the contents of the resized array (via copy construction).
204   EXPECT_EQ(3, Constructable::getNumConstructorCalls());
205   EXPECT_EQ(1, Constructable::getNumDestructorCalls());
206   EXPECT_EQ(2u, theVector.size());
207 }
208 
209 // Resize with fill value.
210 TEST_F(SmallVectorTest, ResizeFillTest) {
211   SCOPED_TRACE("ResizeFillTest");
212 
213   theVector.resize(3, Constructable(77));
214   assertValuesInOrder(theVector, 3u, 77, 77, 77);
215 }
216 
217 // Overflow past fixed size.
218 TEST_F(SmallVectorTest, OverflowTest) {
219   SCOPED_TRACE("OverflowTest");
220 
221   // Push more elements than the fixed size.
222   makeSequence(theVector, 1, 10);
223 
224   // Test size and values.
225   EXPECT_EQ(10u, theVector.size());
226   for (int i = 0; i < 10; ++i) {
227     EXPECT_EQ(i+1, theVector[i].getValue());
228   }
229 
230   // Now resize back to fixed size.
231   theVector.resize(1);
232 
233   assertValuesInOrder(theVector, 1u, 1);
234 }
235 
236 // Iteration tests.
237 TEST_F(SmallVectorTest, IterationTest) {
238   makeSequence(theVector, 1, 2);
239 
240   // Forward Iteration
241   VectorType::iterator it = theVector.begin();
242   EXPECT_TRUE(*it == theVector.front());
243   EXPECT_TRUE(*it == theVector[0]);
244   EXPECT_EQ(1, it->getValue());
245   ++it;
246   EXPECT_TRUE(*it == theVector[1]);
247   EXPECT_TRUE(*it == theVector.back());
248   EXPECT_EQ(2, it->getValue());
249   ++it;
250   EXPECT_TRUE(it == theVector.end());
251   --it;
252   EXPECT_TRUE(*it == theVector[1]);
253   EXPECT_EQ(2, it->getValue());
254   --it;
255   EXPECT_TRUE(*it == theVector[0]);
256   EXPECT_EQ(1, it->getValue());
257 
258   // Reverse Iteration
259   VectorType::reverse_iterator rit = theVector.rbegin();
260   EXPECT_TRUE(*rit == theVector[1]);
261   EXPECT_EQ(2, rit->getValue());
262   ++rit;
263   EXPECT_TRUE(*rit == theVector[0]);
264   EXPECT_EQ(1, rit->getValue());
265   ++rit;
266   EXPECT_TRUE(rit == theVector.rend());
267   --rit;
268   EXPECT_TRUE(*rit == theVector[0]);
269   EXPECT_EQ(1, rit->getValue());
270   --rit;
271   EXPECT_TRUE(*rit == theVector[1]);
272   EXPECT_EQ(2, rit->getValue());
273 }
274 
275 // Swap test.
276 TEST_F(SmallVectorTest, SwapTest) {
277   SCOPED_TRACE("SwapTest");
278 
279   makeSequence(theVector, 1, 2);
280   std::swap(theVector, otherVector);
281 
282   assertEmpty(theVector);
283   assertValuesInOrder(otherVector, 2u, 1, 2);
284 }
285 
286 // Append test
287 TEST_F(SmallVectorTest, AppendTest) {
288   SCOPED_TRACE("AppendTest");
289 
290   makeSequence(otherVector, 2, 3);
291 
292   theVector.push_back(Constructable(1));
293   theVector.append(otherVector.begin(), otherVector.end());
294 
295   assertValuesInOrder(theVector, 3u, 1, 2, 3);
296 }
297 
298 // Append repeated test
299 TEST_F(SmallVectorTest, AppendRepeatedTest) {
300   SCOPED_TRACE("AppendRepeatedTest");
301 
302   theVector.push_back(Constructable(1));
303   theVector.append(2, Constructable(77));
304   assertValuesInOrder(theVector, 3u, 1, 77, 77);
305 }
306 
307 // Assign test
308 TEST_F(SmallVectorTest, AssignTest) {
309   SCOPED_TRACE("AssignTest");
310 
311   theVector.push_back(Constructable(1));
312   theVector.assign(2, Constructable(77));
313   assertValuesInOrder(theVector, 2u, 77, 77);
314 }
315 
316 // Erase a single element
317 TEST_F(SmallVectorTest, EraseTest) {
318   SCOPED_TRACE("EraseTest");
319 
320   makeSequence(theVector, 1, 3);
321   theVector.erase(theVector.begin());
322   assertValuesInOrder(theVector, 2u, 2, 3);
323 }
324 
325 // Erase a range of elements
326 TEST_F(SmallVectorTest, EraseRangeTest) {
327   SCOPED_TRACE("EraseRangeTest");
328 
329   makeSequence(theVector, 1, 3);
330   theVector.erase(theVector.begin(), theVector.begin() + 2);
331   assertValuesInOrder(theVector, 1u, 3);
332 }
333 
334 // Insert a single element.
335 TEST_F(SmallVectorTest, InsertTest) {
336   SCOPED_TRACE("InsertTest");
337 
338   makeSequence(theVector, 1, 3);
339   theVector.insert(theVector.begin() + 1, Constructable(77));
340   assertValuesInOrder(theVector, 4u, 1, 77, 2, 3);
341 }
342 
343 // Insert repeated elements.
344 TEST_F(SmallVectorTest, InsertRepeatedTest) {
345   SCOPED_TRACE("InsertRepeatedTest");
346 
347   makeSequence(theVector, 10, 15);
348   theVector.insert(theVector.begin() + 1, 2, Constructable(16));
349   assertValuesInOrder(theVector, 8u, 10, 16, 16, 11, 12, 13, 14, 15);
350 }
351 
352 // Insert range.
353 TEST_F(SmallVectorTest, InsertRangeTest) {
354   SCOPED_TRACE("InsertRepeatedTest");
355 
356   makeSequence(theVector, 1, 3);
357   theVector.insert(theVector.begin() + 1, 3, Constructable(77));
358   assertValuesInOrder(theVector, 6u, 1, 77, 77, 77, 2, 3);
359 }
360 
361 // Comparison tests.
362 TEST_F(SmallVectorTest, ComparisonTest) {
363   SCOPED_TRACE("ComparisonTest");
364 
365   makeSequence(theVector, 1, 3);
366   makeSequence(otherVector, 1, 3);
367 
368   EXPECT_TRUE(theVector == otherVector);
369   EXPECT_FALSE(theVector != otherVector);
370 
371   otherVector.clear();
372   makeSequence(otherVector, 2, 4);
373 
374   EXPECT_FALSE(theVector == otherVector);
375   EXPECT_TRUE(theVector != otherVector);
376 }
377 
378 // Constant vector tests.
379 TEST_F(SmallVectorTest, ConstVectorTest) {
380   const VectorType constVector;
381 
382   EXPECT_EQ(0u, constVector.size());
383   EXPECT_TRUE(constVector.empty());
384   EXPECT_TRUE(constVector.begin() == constVector.end());
385 }
386 
387 // Direct array access.
388 TEST_F(SmallVectorTest, DirectVectorTest) {
389   EXPECT_EQ(0u, theVector.size());
390   EXPECT_LE(4u, theVector.capacity());
391   EXPECT_EQ(0, Constructable::getNumConstructorCalls());
392   theVector.end()[0] = 1;
393   theVector.end()[1] = 2;
394   theVector.end()[2] = 3;
395   theVector.end()[3] = 4;
396   theVector.set_size(4);
397   EXPECT_EQ(4u, theVector.size());
398   EXPECT_EQ(4, Constructable::getNumConstructorCalls());
399   EXPECT_EQ(1, theVector[0].getValue());
400   EXPECT_EQ(2, theVector[1].getValue());
401   EXPECT_EQ(3, theVector[2].getValue());
402   EXPECT_EQ(4, theVector[3].getValue());
403 }
404 
405 TEST_F(SmallVectorTest, IteratorTest) {
406   std::list<int> L;
407   theVector.insert(theVector.end(), L.begin(), L.end());
408 }
409 
410 }
411