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 "gtest/gtest.h"
15 #include "llvm/ADT/SmallVector.h"
23 /// A helper class that counts the total number of constructor and
27 static int numConstructorCalls;
28 static int numDestructorCalls;
29 static int numAssignmentCalls;
34 Constructable() : value(0) {
35 ++numConstructorCalls;
38 Constructable(int val) : value(val) {
39 ++numConstructorCalls;
42 Constructable(const Constructable & src) {
44 ++numConstructorCalls;
51 Constructable & operator=(const Constructable & src) {
57 int getValue() const {
62 numConstructorCalls = 0;
63 numDestructorCalls = 0;
64 numAssignmentCalls = 0;
67 static int getNumConstructorCalls() {
68 return numConstructorCalls;
71 static int getNumDestructorCalls() {
72 return numDestructorCalls;
75 friend bool operator==(const Constructable & c0, const Constructable & c1) {
76 return c0.getValue() == c1.getValue();
79 friend bool operator!=(const Constructable & c0, const Constructable & c1) {
80 return c0.getValue() != c1.getValue();
84 int Constructable::numConstructorCalls;
85 int Constructable::numDestructorCalls;
86 int Constructable::numAssignmentCalls;
89 class SmallVectorTest : public testing::Test {
91 typedef SmallVector<Constructable, 4> VectorType;
94 VectorType otherVector;
97 Constructable::reset();
100 void assertEmpty(VectorType & v) {
102 EXPECT_EQ(0u, v.size());
103 EXPECT_TRUE(v.empty());
106 EXPECT_TRUE(v.begin() == v.end());
109 // Assert that theVector contains the specified values, in order.
110 void assertValuesInOrder(VectorType & v, size_t size, ...) {
111 EXPECT_EQ(size, v.size());
115 for (size_t i = 0; i < size; ++i) {
116 int value = va_arg(ap, int);
117 EXPECT_EQ(value, v[i].getValue());
123 // Generate a sequence of values to initialize the vector.
124 void makeSequence(VectorType & v, int start, int end) {
125 for (int i = start; i <= end; ++i) {
126 v.push_back(Constructable(i));
132 TEST_F(SmallVectorTest, EmptyVectorTest) {
133 SCOPED_TRACE("EmptyVectorTest");
134 assertEmpty(theVector);
135 EXPECT_TRUE(theVector.rbegin() == theVector.rend());
136 EXPECT_EQ(0, Constructable::getNumConstructorCalls());
137 EXPECT_EQ(0, Constructable::getNumDestructorCalls());
140 // Simple insertions and deletions.
141 TEST_F(SmallVectorTest, PushPopTest) {
142 SCOPED_TRACE("PushPopTest");
145 theVector.push_back(Constructable(1));
148 assertValuesInOrder(theVector, 1u, 1);
149 EXPECT_FALSE(theVector.begin() == theVector.end());
150 EXPECT_FALSE(theVector.empty());
152 // Push another element
153 theVector.push_back(Constructable(2));
154 assertValuesInOrder(theVector, 2u, 1, 2);
157 theVector.pop_back();
158 assertValuesInOrder(theVector, 1u, 1);
160 // Pop another element
161 theVector.pop_back();
162 assertEmpty(theVector);
164 // Check number of constructor calls. Should be 2 for each list element,
165 // one for the argument to push_back, and one for the list element itself.
166 EXPECT_EQ(4, Constructable::getNumConstructorCalls());
167 EXPECT_EQ(4, Constructable::getNumDestructorCalls());
171 TEST_F(SmallVectorTest, ClearTest) {
172 SCOPED_TRACE("ClearTest");
174 makeSequence(theVector, 1, 2);
177 assertEmpty(theVector);
178 EXPECT_EQ(4, Constructable::getNumConstructorCalls());
179 EXPECT_EQ(4, Constructable::getNumDestructorCalls());
182 // Resize smaller test.
183 TEST_F(SmallVectorTest, ResizeShrinkTest) {
184 SCOPED_TRACE("ResizeShrinkTest");
186 makeSequence(theVector, 1, 3);
189 assertValuesInOrder(theVector, 1u, 1);
190 EXPECT_EQ(6, Constructable::getNumConstructorCalls());
191 EXPECT_EQ(5, Constructable::getNumDestructorCalls());
194 // Resize bigger test.
195 TEST_F(SmallVectorTest, ResizeGrowTest) {
196 SCOPED_TRACE("ResizeGrowTest");
200 // The extra constructor/destructor calls come from the temporary object used
201 // to initialize the contents of the resized array (via copy construction).
202 EXPECT_EQ(3, Constructable::getNumConstructorCalls());
203 EXPECT_EQ(1, Constructable::getNumDestructorCalls());
204 EXPECT_EQ(2u, theVector.size());
207 // Resize with fill value.
208 TEST_F(SmallVectorTest, ResizeFillTest) {
209 SCOPED_TRACE("ResizeFillTest");
211 theVector.resize(3, Constructable(77));
212 assertValuesInOrder(theVector, 3u, 77, 77, 77);
215 // Overflow past fixed size.
216 TEST_F(SmallVectorTest, OverflowTest) {
217 SCOPED_TRACE("OverflowTest");
219 // Push more elements than the fixed size.
220 makeSequence(theVector, 1, 10);
222 // Test size and values.
223 EXPECT_EQ(10u, theVector.size());
224 for (int i = 0; i < 10; ++i) {
225 EXPECT_EQ(i+1, theVector[i].getValue());
228 // Now resize back to fixed size.
231 assertValuesInOrder(theVector, 1u, 1);
235 TEST_F(SmallVectorTest, IterationTest) {
236 makeSequence(theVector, 1, 2);
239 VectorType::iterator it = theVector.begin();
240 EXPECT_TRUE(*it == theVector.front());
241 EXPECT_TRUE(*it == theVector[0]);
242 EXPECT_EQ(1, it->getValue());
244 EXPECT_TRUE(*it == theVector[1]);
245 EXPECT_TRUE(*it == theVector.back());
246 EXPECT_EQ(2, it->getValue());
248 EXPECT_TRUE(it == theVector.end());
250 EXPECT_TRUE(*it == theVector[1]);
251 EXPECT_EQ(2, it->getValue());
253 EXPECT_TRUE(*it == theVector[0]);
254 EXPECT_EQ(1, it->getValue());
257 VectorType::reverse_iterator rit = theVector.rbegin();
258 EXPECT_TRUE(*rit == theVector[1]);
259 EXPECT_EQ(2, rit->getValue());
261 EXPECT_TRUE(*rit == theVector[0]);
262 EXPECT_EQ(1, rit->getValue());
264 EXPECT_TRUE(rit == theVector.rend());
266 EXPECT_TRUE(*rit == theVector[0]);
267 EXPECT_EQ(1, rit->getValue());
269 EXPECT_TRUE(*rit == theVector[1]);
270 EXPECT_EQ(2, rit->getValue());
274 TEST_F(SmallVectorTest, SwapTest) {
275 SCOPED_TRACE("SwapTest");
277 makeSequence(theVector, 1, 2);
278 std::swap(theVector, otherVector);
280 assertEmpty(theVector);
281 assertValuesInOrder(otherVector, 2u, 1, 2);
285 TEST_F(SmallVectorTest, AppendTest) {
286 SCOPED_TRACE("AppendTest");
288 makeSequence(otherVector, 2, 3);
290 theVector.push_back(Constructable(1));
291 theVector.append(otherVector.begin(), otherVector.end());
293 assertValuesInOrder(theVector, 3u, 1, 2, 3);
296 // Append repeated test
297 TEST_F(SmallVectorTest, AppendRepeatedTest) {
298 SCOPED_TRACE("AppendRepeatedTest");
300 theVector.push_back(Constructable(1));
301 theVector.append(2, Constructable(77));
302 assertValuesInOrder(theVector, 3u, 1, 77, 77);
306 TEST_F(SmallVectorTest, AssignTest) {
307 SCOPED_TRACE("AssignTest");
309 theVector.push_back(Constructable(1));
310 theVector.assign(2, Constructable(77));
311 assertValuesInOrder(theVector, 2u, 77, 77);
314 // Erase a single element
315 TEST_F(SmallVectorTest, EraseTest) {
316 SCOPED_TRACE("EraseTest");
318 makeSequence(theVector, 1, 3);
319 theVector.erase(theVector.begin());
320 assertValuesInOrder(theVector, 2u, 2, 3);
323 // Erase a range of elements
324 TEST_F(SmallVectorTest, EraseRangeTest) {
325 SCOPED_TRACE("EraseRangeTest");
327 makeSequence(theVector, 1, 3);
328 theVector.erase(theVector.begin(), theVector.begin() + 2);
329 assertValuesInOrder(theVector, 1u, 3);
332 // Insert a single element.
333 TEST_F(SmallVectorTest, InsertTest) {
334 SCOPED_TRACE("InsertTest");
336 makeSequence(theVector, 1, 3);
337 theVector.insert(theVector.begin() + 1, Constructable(77));
338 assertValuesInOrder(theVector, 4u, 1, 77, 2, 3);
341 // Insert repeated elements.
342 TEST_F(SmallVectorTest, InsertRepeatedTest) {
343 SCOPED_TRACE("InsertRepeatedTest");
345 makeSequence(theVector, 10, 15);
346 theVector.insert(theVector.begin() + 1, 2, Constructable(16));
347 assertValuesInOrder(theVector, 8u, 10, 16, 16, 11, 12, 13, 14, 15);
351 TEST_F(SmallVectorTest, InsertRangeTest) {
352 SCOPED_TRACE("InsertRepeatedTest");
354 makeSequence(theVector, 1, 3);
355 theVector.insert(theVector.begin() + 1, 3, Constructable(77));
356 assertValuesInOrder(theVector, 6u, 1, 77, 77, 77, 2, 3);
360 TEST_F(SmallVectorTest, ComparisonTest) {
361 SCOPED_TRACE("ComparisonTest");
363 makeSequence(theVector, 1, 3);
364 makeSequence(otherVector, 1, 3);
366 EXPECT_TRUE(theVector == otherVector);
367 EXPECT_FALSE(theVector != otherVector);
370 makeSequence(otherVector, 2, 4);
372 EXPECT_FALSE(theVector == otherVector);
373 EXPECT_TRUE(theVector != otherVector);
376 // Constant vector tests.
377 TEST_F(SmallVectorTest, ConstVectorTest) {
378 const VectorType constVector;
380 EXPECT_EQ(0u, constVector.size());
381 EXPECT_TRUE(constVector.empty());
382 EXPECT_TRUE(constVector.begin() == constVector.end());
385 // Direct array access.
386 TEST_F(SmallVectorTest, DirectVectorTest) {
387 EXPECT_EQ(0u, theVector.size());
388 EXPECT_LE(4u, theVector.capacity());
389 EXPECT_EQ(0, Constructable::getNumConstructorCalls());
390 theVector.end()[0] = 1;
391 theVector.end()[1] = 2;
392 theVector.end()[2] = 3;
393 theVector.end()[3] = 4;
394 theVector.set_size(4);
395 EXPECT_EQ(4u, theVector.size());
396 EXPECT_EQ(4, Constructable::getNumConstructorCalls());
397 EXPECT_EQ(1, theVector[0].getValue());
398 EXPECT_EQ(2, theVector[1].getValue());
399 EXPECT_EQ(3, theVector[2].getValue());
400 EXPECT_EQ(4, theVector[3].getValue());
403 TEST_F(SmallVectorTest, IteratorTest) {
405 theVector.insert(theVector.end(), L.begin(), L.end());