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"
22 /// A helper class that counts the total number of constructor and
26 static int numConstructorCalls;
27 static int numDestructorCalls;
28 static int numAssignmentCalls;
33 Constructable() : value(0) {
34 ++numConstructorCalls;
37 Constructable(int val) : value(val) {
38 ++numConstructorCalls;
41 Constructable(const Constructable & src) {
43 ++numConstructorCalls;
50 Constructable & operator=(const Constructable & src) {
56 int getValue() const {
61 numConstructorCalls = 0;
62 numDestructorCalls = 0;
63 numAssignmentCalls = 0;
66 static int getNumConstructorCalls() {
67 return numConstructorCalls;
70 static int getNumDestructorCalls() {
71 return numDestructorCalls;
74 friend bool operator==(const Constructable & c0, const Constructable & c1) {
75 return c0.getValue() == c1.getValue();
78 friend bool operator!=(const Constructable & c0, const Constructable & c1) {
79 return c0.getValue() != c1.getValue();
83 int Constructable::numConstructorCalls;
84 int Constructable::numDestructorCalls;
85 int Constructable::numAssignmentCalls;
88 class SmallVectorTest : public testing::Test {
90 typedef SmallVector<Constructable, 4> VectorType;
93 VectorType otherVector;
96 Constructable::reset();
99 void assertEmpty(VectorType & v) {
101 EXPECT_EQ(0u, v.size());
102 EXPECT_TRUE(v.empty());
105 EXPECT_TRUE(v.begin() == v.end());
108 // Assert that theVector contains the specified values, in order.
109 void assertValuesInOrder(VectorType & v, size_t size, ...) {
110 EXPECT_EQ(size, v.size());
114 for (size_t i = 0; i < size; ++i) {
115 int value = va_arg(ap, int);
116 EXPECT_EQ(value, v[i].getValue());
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));
131 TEST_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());
139 // Simple insertions and deletions.
140 TEST_F(SmallVectorTest, PushPopTest) {
141 SCOPED_TRACE("PushPopTest");
144 theVector.push_back(Constructable(1));
147 assertValuesInOrder(theVector, 1u, 1);
148 EXPECT_FALSE(theVector.begin() == theVector.end());
149 EXPECT_FALSE(theVector.empty());
151 // Push another element
152 theVector.push_back(Constructable(2));
153 assertValuesInOrder(theVector, 2u, 1, 2);
156 theVector.pop_back();
157 assertValuesInOrder(theVector, 1u, 1);
159 // Pop another element
160 theVector.pop_back();
161 assertEmpty(theVector);
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());
170 TEST_F(SmallVectorTest, ClearTest) {
171 SCOPED_TRACE("ClearTest");
173 makeSequence(theVector, 1, 2);
176 assertEmpty(theVector);
177 EXPECT_EQ(4, Constructable::getNumConstructorCalls());
178 EXPECT_EQ(4, Constructable::getNumDestructorCalls());
181 // Resize smaller test.
182 TEST_F(SmallVectorTest, ResizeShrinkTest) {
183 SCOPED_TRACE("ResizeShrinkTest");
185 makeSequence(theVector, 1, 3);
188 assertValuesInOrder(theVector, 1u, 1);
189 EXPECT_EQ(6, Constructable::getNumConstructorCalls());
190 EXPECT_EQ(5, Constructable::getNumDestructorCalls());
193 // Resize bigger test.
194 TEST_F(SmallVectorTest, ResizeGrowTest) {
195 SCOPED_TRACE("ResizeGrowTest");
199 // XXX: I don't know where the extra construct/destruct is coming from.
200 EXPECT_EQ(3, Constructable::getNumConstructorCalls());
201 EXPECT_EQ(1, Constructable::getNumDestructorCalls());
202 EXPECT_EQ(2u, theVector.size());
205 // Resize with fill value.
206 TEST_F(SmallVectorTest, ResizeFillTest) {
207 SCOPED_TRACE("ResizeFillTest");
209 theVector.resize(3, Constructable(77));
210 assertValuesInOrder(theVector, 3u, 77, 77, 77);
213 // Overflow past fixed size.
214 TEST_F(SmallVectorTest, OverflowTest) {
215 SCOPED_TRACE("OverflowTest");
217 // Push more elements than the fixed size
218 makeSequence(theVector, 1, 10);
220 // test size and values
221 EXPECT_EQ(10u, theVector.size());
222 for (int i = 0; i < 10; ++i) {
223 EXPECT_EQ(i+1, theVector[i].getValue());
226 // Now resize back to fixed size
229 assertValuesInOrder(theVector, 1u, 1);
233 TEST_F(SmallVectorTest, IterationTest) {
234 makeSequence(theVector, 1, 2);
237 VectorType::iterator it = theVector.begin();
238 EXPECT_TRUE(*it == theVector.front());
239 EXPECT_TRUE(*it == theVector[0]);
240 EXPECT_EQ(1, it->getValue());
242 EXPECT_TRUE(*it == theVector[1]);
243 EXPECT_TRUE(*it == theVector.back());
244 EXPECT_EQ(2, it->getValue());
246 EXPECT_TRUE(it == theVector.end());
248 EXPECT_TRUE(*it == theVector[1]);
249 EXPECT_EQ(2, it->getValue());
251 EXPECT_TRUE(*it == theVector[0]);
252 EXPECT_EQ(1, it->getValue());
255 VectorType::reverse_iterator rit = theVector.rbegin();
256 EXPECT_TRUE(*rit == theVector[1]);
257 EXPECT_EQ(2, rit->getValue());
259 EXPECT_TRUE(*rit == theVector[0]);
260 EXPECT_EQ(1, rit->getValue());
262 EXPECT_TRUE(rit == theVector.rend());
264 EXPECT_TRUE(*rit == theVector[0]);
265 EXPECT_EQ(1, rit->getValue());
267 EXPECT_TRUE(*rit == theVector[1]);
268 EXPECT_EQ(2, rit->getValue());
272 TEST_F(SmallVectorTest, SwapTest) {
273 SCOPED_TRACE("SwapTest");
275 makeSequence(theVector, 1, 2);
276 std::swap(theVector, otherVector);
278 assertEmpty(theVector);
279 assertValuesInOrder(otherVector, 2u, 1, 2);
283 TEST_F(SmallVectorTest, AppendTest) {
284 SCOPED_TRACE("AppendTest");
286 makeSequence(otherVector, 2, 3);
288 theVector.push_back(Constructable(1));
289 theVector.append(otherVector.begin(), otherVector.end());
291 assertValuesInOrder(theVector, 3u, 1, 2, 3);
294 // Append repeated test
295 TEST_F(SmallVectorTest, AppendRepeatedTest) {
296 SCOPED_TRACE("AppendRepeatedTest");
298 theVector.push_back(Constructable(1));
299 theVector.append(2, Constructable(77));
300 assertValuesInOrder(theVector, 3u, 1, 77, 77);
304 TEST_F(SmallVectorTest, AssignTest) {
305 SCOPED_TRACE("AssignTest");
307 theVector.push_back(Constructable(1));
308 theVector.assign(2, Constructable(77));
309 assertValuesInOrder(theVector, 2u, 77, 77);
312 // Erase a single element
313 TEST_F(SmallVectorTest, EraseTest) {
314 SCOPED_TRACE("EraseTest");
316 makeSequence(theVector, 1, 3);
317 theVector.erase(theVector.begin());
318 assertValuesInOrder(theVector, 2u, 2, 3);
321 // Erase a range of elements
322 TEST_F(SmallVectorTest, EraseRangeTest) {
323 SCOPED_TRACE("EraseRangeTest");
325 makeSequence(theVector, 1, 3);
326 theVector.erase(theVector.begin(), theVector.begin() + 2);
327 assertValuesInOrder(theVector, 1u, 3);
330 // Insert a single element.
331 TEST_F(SmallVectorTest, InsertTest) {
332 SCOPED_TRACE("InsertTest");
334 makeSequence(theVector, 1, 3);
335 theVector.insert(theVector.begin() + 1, Constructable(77));
336 assertValuesInOrder(theVector, 4u, 1, 77, 2, 3);
339 // Insert repeated elements.
340 TEST_F(SmallVectorTest, InsertRepeatedTest) {
341 SCOPED_TRACE("InsertRepeatedTest");
343 makeSequence(theVector, 10, 15);
344 theVector.insert(theVector.begin() + 1, 2, Constructable(16));
345 assertValuesInOrder(theVector, 8u, 10, 16, 16, 11, 12, 13, 14, 15);
349 TEST_F(SmallVectorTest, InsertRangeTest) {
350 SCOPED_TRACE("InsertRepeatedTest");
352 makeSequence(theVector, 1, 3);
353 theVector.insert(theVector.begin() + 1, 3, Constructable(77));
354 assertValuesInOrder(theVector, 6u, 1, 77, 77, 77, 2, 3);
358 TEST_F(SmallVectorTest, ComparisonTest) {
359 SCOPED_TRACE("ComparisonTest");
361 makeSequence(theVector, 1, 3);
362 makeSequence(otherVector, 1, 3);
364 EXPECT_TRUE(theVector == otherVector);
365 EXPECT_FALSE(theVector != otherVector);
368 makeSequence(otherVector, 2, 4);
370 EXPECT_FALSE(theVector == otherVector);
371 EXPECT_TRUE(theVector != otherVector);
374 // Constant vector tests.
375 TEST_F(SmallVectorTest, ConstVectorTest) {
376 const VectorType constVector;
378 EXPECT_EQ(0u, constVector.size());
379 EXPECT_TRUE(constVector.empty());
380 EXPECT_TRUE(constVector.begin() == constVector.end());