1 //===- llvm/unittest/ADT/TinyPtrVectorTest.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 // TinyPtrVector unit tests.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "llvm/ADT/TinyPtrVector.h"
15 #include "llvm/ADT/ArrayRef.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/Support/type_traits.h"
18 #include "gtest/gtest.h"
19 #include <algorithm>
20 #include <vector>
21
22 using namespace llvm;
23
24 namespace {
25
26 // The world's worst RNG, but it is deterministic and makes it easy to get
27 // *some* shuffling of elements.
test_shuffle_rng(ptrdiff_t i)28 static ptrdiff_t test_shuffle_rng(ptrdiff_t i) {
29 return (i + i * 33) % i;
30 }
31 static ptrdiff_t (*test_shuffle_rng_p)(ptrdiff_t) = &test_shuffle_rng;
32
33 template <typename VectorT>
34 class TinyPtrVectorTest : public testing::Test {
35 protected:
36 typedef typename VectorT::value_type PtrT;
37 typedef typename std::remove_pointer<PtrT>::type ValueT;
38
39 VectorT V;
40 VectorT V2;
41
42 ValueT TestValues[1024];
43 std::vector<PtrT> TestPtrs;
44
TinyPtrVectorTest()45 TinyPtrVectorTest() {
46 for (size_t i = 0, e = array_lengthof(TestValues); i != e; ++i)
47 TestPtrs.push_back(&TestValues[i]);
48
49 std::random_shuffle(TestPtrs.begin(), TestPtrs.end(), test_shuffle_rng_p);
50 }
51
testArray(size_t N)52 ArrayRef<PtrT> testArray(size_t N) {
53 return makeArrayRef(&TestPtrs[0], N);
54 }
55
appendValues(VectorT & V,ArrayRef<PtrT> Values)56 void appendValues(VectorT &V, ArrayRef<PtrT> Values) {
57 for (size_t i = 0, e = Values.size(); i != e; ++i)
58 V.push_back(Values[i]);
59 }
60
setVectors(ArrayRef<PtrT> Values1,ArrayRef<PtrT> Values2)61 void setVectors(ArrayRef<PtrT> Values1, ArrayRef<PtrT> Values2) {
62 V.clear();
63 appendValues(V, Values1);
64 V2.clear();
65 appendValues(V2, Values2);
66 }
67
expectValues(const VectorT & V,ArrayRef<PtrT> Values)68 void expectValues(const VectorT &V, ArrayRef<PtrT> Values) {
69 EXPECT_EQ(Values.empty(), V.empty());
70 EXPECT_EQ(Values.size(), V.size());
71 for (size_t i = 0, e = Values.size(); i != e; ++i) {
72 EXPECT_EQ(Values[i], V[i]);
73 EXPECT_EQ(Values[i], *std::next(V.begin(), i));
74 }
75 EXPECT_EQ(V.end(), std::next(V.begin(), Values.size()));
76 }
77 };
78
79 typedef ::testing::Types<TinyPtrVector<int*>,
80 TinyPtrVector<double*>
81 > TinyPtrVectorTestTypes;
82 TYPED_TEST_CASE(TinyPtrVectorTest, TinyPtrVectorTestTypes);
83
TYPED_TEST(TinyPtrVectorTest,EmptyTest)84 TYPED_TEST(TinyPtrVectorTest, EmptyTest) {
85 this->expectValues(this->V, this->testArray(0));
86 }
87
TYPED_TEST(TinyPtrVectorTest,PushPopBack)88 TYPED_TEST(TinyPtrVectorTest, PushPopBack) {
89 this->V.push_back(this->TestPtrs[0]);
90 this->expectValues(this->V, this->testArray(1));
91 this->V.push_back(this->TestPtrs[1]);
92 this->expectValues(this->V, this->testArray(2));
93 this->V.push_back(this->TestPtrs[2]);
94 this->expectValues(this->V, this->testArray(3));
95 this->V.push_back(this->TestPtrs[3]);
96 this->expectValues(this->V, this->testArray(4));
97 this->V.push_back(this->TestPtrs[4]);
98 this->expectValues(this->V, this->testArray(5));
99
100 // Pop and clobber a few values to keep things interesting.
101 this->V.pop_back();
102 this->expectValues(this->V, this->testArray(4));
103 this->V.pop_back();
104 this->expectValues(this->V, this->testArray(3));
105 this->TestPtrs[3] = &this->TestValues[42];
106 this->TestPtrs[4] = &this->TestValues[43];
107 this->V.push_back(this->TestPtrs[3]);
108 this->expectValues(this->V, this->testArray(4));
109 this->V.push_back(this->TestPtrs[4]);
110 this->expectValues(this->V, this->testArray(5));
111
112 this->V.pop_back();
113 this->expectValues(this->V, this->testArray(4));
114 this->V.pop_back();
115 this->expectValues(this->V, this->testArray(3));
116 this->V.pop_back();
117 this->expectValues(this->V, this->testArray(2));
118 this->V.pop_back();
119 this->expectValues(this->V, this->testArray(1));
120 this->V.pop_back();
121 this->expectValues(this->V, this->testArray(0));
122
123 this->appendValues(this->V, this->testArray(42));
124 this->expectValues(this->V, this->testArray(42));
125 }
126
TYPED_TEST(TinyPtrVectorTest,ClearTest)127 TYPED_TEST(TinyPtrVectorTest, ClearTest) {
128 this->expectValues(this->V, this->testArray(0));
129 this->V.clear();
130 this->expectValues(this->V, this->testArray(0));
131
132 this->appendValues(this->V, this->testArray(1));
133 this->expectValues(this->V, this->testArray(1));
134 this->V.clear();
135 this->expectValues(this->V, this->testArray(0));
136
137 this->appendValues(this->V, this->testArray(42));
138 this->expectValues(this->V, this->testArray(42));
139 this->V.clear();
140 this->expectValues(this->V, this->testArray(0));
141 }
142
TYPED_TEST(TinyPtrVectorTest,CopyAndMoveCtorTest)143 TYPED_TEST(TinyPtrVectorTest, CopyAndMoveCtorTest) {
144 this->appendValues(this->V, this->testArray(42));
145 TypeParam Copy(this->V);
146 this->expectValues(Copy, this->testArray(42));
147
148 // This is a separate copy, and so it shouldn't destroy the original.
149 Copy.clear();
150 this->expectValues(Copy, this->testArray(0));
151 this->expectValues(this->V, this->testArray(42));
152
153 TypeParam Copy2(this->V2);
154 this->appendValues(Copy2, this->testArray(42));
155 this->expectValues(Copy2, this->testArray(42));
156 this->expectValues(this->V2, this->testArray(0));
157
158 TypeParam Move(std::move(Copy2));
159 this->expectValues(Move, this->testArray(42));
160 this->expectValues(Copy2, this->testArray(0));
161 }
162
TYPED_TEST(TinyPtrVectorTest,CopyAndMoveTest)163 TYPED_TEST(TinyPtrVectorTest, CopyAndMoveTest) {
164 this->V = this->V2;
165 this->expectValues(this->V, this->testArray(0));
166 this->expectValues(this->V2, this->testArray(0));
167 this->V = std::move(this->V2);
168 this->expectValues(this->V, this->testArray(0));
169
170 this->setVectors(this->testArray(1), this->testArray(0));
171 this->V = this->V2;
172 this->expectValues(this->V, this->testArray(0));
173 this->expectValues(this->V2, this->testArray(0));
174 this->setVectors(this->testArray(1), this->testArray(0));
175 this->V = std::move(this->V2);
176 this->expectValues(this->V, this->testArray(0));
177
178 this->setVectors(this->testArray(2), this->testArray(0));
179 this->V = this->V2;
180 this->expectValues(this->V, this->testArray(0));
181 this->expectValues(this->V2, this->testArray(0));
182 this->setVectors(this->testArray(2), this->testArray(0));
183 this->V = std::move(this->V2);
184 this->expectValues(this->V, this->testArray(0));
185
186 this->setVectors(this->testArray(42), this->testArray(0));
187 this->V = this->V2;
188 this->expectValues(this->V, this->testArray(0));
189 this->expectValues(this->V2, this->testArray(0));
190 this->setVectors(this->testArray(42), this->testArray(0));
191 this->V = std::move(this->V2);
192 this->expectValues(this->V, this->testArray(0));
193
194 this->setVectors(this->testArray(0), this->testArray(1));
195 this->V = this->V2;
196 this->expectValues(this->V, this->testArray(1));
197 this->expectValues(this->V2, this->testArray(1));
198 this->setVectors(this->testArray(0), this->testArray(1));
199 this->V = std::move(this->V2);
200 this->expectValues(this->V, this->testArray(1));
201
202 this->setVectors(this->testArray(0), this->testArray(2));
203 this->V = this->V2;
204 this->expectValues(this->V, this->testArray(2));
205 this->expectValues(this->V2, this->testArray(2));
206 this->setVectors(this->testArray(0), this->testArray(2));
207 this->V = std::move(this->V2);
208 this->expectValues(this->V, this->testArray(2));
209
210 this->setVectors(this->testArray(0), this->testArray(42));
211 this->V = this->V2;
212 this->expectValues(this->V, this->testArray(42));
213 this->expectValues(this->V2, this->testArray(42));
214 this->setVectors(this->testArray(0), this->testArray(42));
215 this->V = std::move(this->V2);
216 this->expectValues(this->V, this->testArray(42));
217
218 this->setVectors(this->testArray(1), this->testArray(1));
219 this->V = this->V2;
220 this->expectValues(this->V, this->testArray(1));
221 this->expectValues(this->V2, this->testArray(1));
222 this->V = std::move(this->V2);
223 this->expectValues(this->V, this->testArray(1));
224
225 this->setVectors(this->testArray(1), this->testArray(2));
226 this->V = this->V2;
227 this->expectValues(this->V, this->testArray(2));
228 this->expectValues(this->V2, this->testArray(2));
229 this->setVectors(this->testArray(1), this->testArray(2));
230 this->V = std::move(this->V2);
231 this->expectValues(this->V, this->testArray(2));
232
233 this->setVectors(this->testArray(1), this->testArray(42));
234 this->V = this->V2;
235 this->expectValues(this->V, this->testArray(42));
236 this->expectValues(this->V2, this->testArray(42));
237 this->setVectors(this->testArray(1), this->testArray(42));
238 this->V = std::move(this->V2);
239 this->expectValues(this->V, this->testArray(42));
240
241 this->setVectors(this->testArray(2), this->testArray(1));
242 this->V = this->V2;
243 this->expectValues(this->V, this->testArray(1));
244 this->expectValues(this->V2, this->testArray(1));
245 this->setVectors(this->testArray(2), this->testArray(1));
246 this->V = std::move(this->V2);
247 this->expectValues(this->V, this->testArray(1));
248
249 this->setVectors(this->testArray(2), this->testArray(2));
250 this->V = this->V2;
251 this->expectValues(this->V, this->testArray(2));
252 this->expectValues(this->V2, this->testArray(2));
253 this->setVectors(this->testArray(2), this->testArray(2));
254 this->V = std::move(this->V2);
255 this->expectValues(this->V, this->testArray(2));
256
257 this->setVectors(this->testArray(2), this->testArray(42));
258 this->V = this->V2;
259 this->expectValues(this->V, this->testArray(42));
260 this->expectValues(this->V2, this->testArray(42));
261 this->setVectors(this->testArray(2), this->testArray(42));
262 this->V = std::move(this->V2);
263 this->expectValues(this->V, this->testArray(42));
264
265 this->setVectors(this->testArray(42), this->testArray(1));
266 this->V = this->V2;
267 this->expectValues(this->V, this->testArray(1));
268 this->expectValues(this->V2, this->testArray(1));
269 this->setVectors(this->testArray(42), this->testArray(1));
270 this->V = std::move(this->V2);
271 this->expectValues(this->V, this->testArray(1));
272
273 this->setVectors(this->testArray(42), this->testArray(2));
274 this->V = this->V2;
275 this->expectValues(this->V, this->testArray(2));
276 this->expectValues(this->V2, this->testArray(2));
277 this->setVectors(this->testArray(42), this->testArray(2));
278 this->V = std::move(this->V2);
279 this->expectValues(this->V, this->testArray(2));
280
281 this->setVectors(this->testArray(42), this->testArray(42));
282 this->V = this->V2;
283 this->expectValues(this->V, this->testArray(42));
284 this->expectValues(this->V2, this->testArray(42));
285 this->setVectors(this->testArray(42), this->testArray(42));
286 this->V = std::move(this->V2);
287 this->expectValues(this->V, this->testArray(42));
288 }
289
TYPED_TEST(TinyPtrVectorTest,EraseTest)290 TYPED_TEST(TinyPtrVectorTest, EraseTest) {
291 this->appendValues(this->V, this->testArray(1));
292 this->expectValues(this->V, this->testArray(1));
293 this->V.erase(this->V.begin());
294 this->expectValues(this->V, this->testArray(0));
295
296 this->appendValues(this->V, this->testArray(42));
297 this->expectValues(this->V, this->testArray(42));
298 this->V.erase(this->V.begin());
299 this->TestPtrs.erase(this->TestPtrs.begin());
300 this->expectValues(this->V, this->testArray(41));
301 this->V.erase(std::next(this->V.begin(), 1));
302 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 1));
303 this->expectValues(this->V, this->testArray(40));
304 this->V.erase(std::next(this->V.begin(), 2));
305 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 2));
306 this->expectValues(this->V, this->testArray(39));
307 this->V.erase(std::next(this->V.begin(), 5));
308 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 5));
309 this->expectValues(this->V, this->testArray(38));
310 this->V.erase(std::next(this->V.begin(), 13));
311 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 13));
312 this->expectValues(this->V, this->testArray(37));
313
314 typename TypeParam::iterator I = this->V.begin();
315 do {
316 I = this->V.erase(I);
317 } while (I != this->V.end());
318 this->expectValues(this->V, this->testArray(0));
319 }
320
TYPED_TEST(TinyPtrVectorTest,EraseRangeTest)321 TYPED_TEST(TinyPtrVectorTest, EraseRangeTest) {
322 this->appendValues(this->V, this->testArray(1));
323 this->expectValues(this->V, this->testArray(1));
324 this->V.erase(this->V.begin(), this->V.begin());
325 this->expectValues(this->V, this->testArray(1));
326 this->V.erase(this->V.end(), this->V.end());
327 this->expectValues(this->V, this->testArray(1));
328 this->V.erase(this->V.begin(), this->V.end());
329 this->expectValues(this->V, this->testArray(0));
330
331 this->appendValues(this->V, this->testArray(42));
332 this->expectValues(this->V, this->testArray(42));
333 this->V.erase(this->V.begin(), std::next(this->V.begin(), 1));
334 this->TestPtrs.erase(this->TestPtrs.begin(),
335 std::next(this->TestPtrs.begin(), 1));
336 this->expectValues(this->V, this->testArray(41));
337 this->V.erase(std::next(this->V.begin(), 1), std::next(this->V.begin(), 2));
338 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 1),
339 std::next(this->TestPtrs.begin(), 2));
340 this->expectValues(this->V, this->testArray(40));
341 this->V.erase(std::next(this->V.begin(), 2), std::next(this->V.begin(), 4));
342 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 2),
343 std::next(this->TestPtrs.begin(), 4));
344 this->expectValues(this->V, this->testArray(38));
345 this->V.erase(std::next(this->V.begin(), 5), std::next(this->V.begin(), 10));
346 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 5),
347 std::next(this->TestPtrs.begin(), 10));
348 this->expectValues(this->V, this->testArray(33));
349 this->V.erase(std::next(this->V.begin(), 13), std::next(this->V.begin(), 26));
350 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 13),
351 std::next(this->TestPtrs.begin(), 26));
352 this->expectValues(this->V, this->testArray(20));
353 this->V.erase(std::next(this->V.begin(), 7), this->V.end());
354 this->expectValues(this->V, this->testArray(7));
355 this->V.erase(this->V.begin(), this->V.end());
356 this->expectValues(this->V, this->testArray(0));
357 }
358
TYPED_TEST(TinyPtrVectorTest,Insert)359 TYPED_TEST(TinyPtrVectorTest, Insert) {
360 this->V.insert(this->V.end(), this->TestPtrs[0]);
361 this->expectValues(this->V, this->testArray(1));
362 this->V.clear();
363 this->appendValues(this->V, this->testArray(4));
364 this->expectValues(this->V, this->testArray(4));
365 this->V.insert(this->V.end(), this->TestPtrs[4]);
366 this->expectValues(this->V, this->testArray(5));
367 this->V.insert(this->V.begin(), this->TestPtrs[42]);
368 this->TestPtrs.insert(this->TestPtrs.begin(), this->TestPtrs[42]);
369 this->expectValues(this->V, this->testArray(6));
370 this->V.insert(std::next(this->V.begin(), 3), this->TestPtrs[43]);
371 this->TestPtrs.insert(std::next(this->TestPtrs.begin(), 3),
372 this->TestPtrs[43]);
373 this->expectValues(this->V, this->testArray(7));
374 }
375
TYPED_TEST(TinyPtrVectorTest,InsertRange)376 TYPED_TEST(TinyPtrVectorTest, InsertRange) {
377 this->V.insert(this->V.end(), this->TestPtrs.begin(), this->TestPtrs.begin());
378 this->expectValues(this->V, this->testArray(0));
379 this->V.insert(this->V.begin(), this->TestPtrs.begin(),
380 this->TestPtrs.begin());
381 this->expectValues(this->V, this->testArray(0));
382 this->V.insert(this->V.end(), this->TestPtrs.end(), this->TestPtrs.end());
383 this->expectValues(this->V, this->testArray(0));
384 this->V.insert(this->V.end(), this->TestPtrs.begin(),
385 std::next(this->TestPtrs.begin()));
386 this->expectValues(this->V, this->testArray(1));
387 this->V.clear();
388 this->V.insert(this->V.end(), this->TestPtrs.begin(),
389 std::next(this->TestPtrs.begin(), 2));
390 this->expectValues(this->V, this->testArray(2));
391 this->V.clear();
392 this->V.insert(this->V.end(), this->TestPtrs.begin(),
393 std::next(this->TestPtrs.begin(), 42));
394 this->expectValues(this->V, this->testArray(42));
395 this->V.clear();
396 this->V.insert(this->V.end(),
397 std::next(this->TestPtrs.begin(), 5),
398 std::next(this->TestPtrs.begin(), 13));
399 this->V.insert(this->V.begin(),
400 std::next(this->TestPtrs.begin(), 0),
401 std::next(this->TestPtrs.begin(), 3));
402 this->V.insert(std::next(this->V.begin(), 2),
403 std::next(this->TestPtrs.begin(), 2),
404 std::next(this->TestPtrs.begin(), 4));
405 this->V.erase(std::next(this->V.begin(), 4));
406 this->V.insert(std::next(this->V.begin(), 4),
407 std::next(this->TestPtrs.begin(), 4),
408 std::next(this->TestPtrs.begin(), 5));
409 this->expectValues(this->V, this->testArray(13));
410 }
411
412 }
413
TEST(TinyPtrVectorTest,SingleEltCtorTest)414 TEST(TinyPtrVectorTest, SingleEltCtorTest) {
415 int v = 55;
416 TinyPtrVector<int *> V(&v);
417
418 EXPECT_TRUE(V.size() == 1);
419 EXPECT_FALSE(V.empty());
420 EXPECT_TRUE(V.front() == &v);
421 }
422
TEST(TinyPtrVectorTest,ArrayRefCtorTest)423 TEST(TinyPtrVectorTest, ArrayRefCtorTest) {
424 int data_array[128];
425 std::vector<int *> data;
426
427 for (unsigned i = 0, e = 128; i != e; ++i) {
428 data_array[i] = 324 - int(i);
429 data.push_back(&data_array[i]);
430 }
431
432 TinyPtrVector<int *> V(data);
433 EXPECT_TRUE(V.size() == 128);
434 EXPECT_FALSE(V.empty());
435 for (unsigned i = 0, e = 128; i != e; ++i) {
436 EXPECT_TRUE(V[i] == data[i]);
437 }
438 }
439
TEST(TinyPtrVectorTest,MutableArrayRefTest)440 TEST(TinyPtrVectorTest, MutableArrayRefTest) {
441 int data_array[128];
442 std::vector<int *> data;
443
444 for (unsigned i = 0, e = 128; i != e; ++i) {
445 data_array[i] = 324 - int(i);
446 data.push_back(&data_array[i]);
447 }
448
449 TinyPtrVector<int *> V(data);
450 EXPECT_TRUE(V.size() == 128);
451 EXPECT_FALSE(V.empty());
452
453 MutableArrayRef<int *> mut_array = V;
454 for (unsigned i = 0, e = 128; i != e; ++i) {
455 EXPECT_TRUE(mut_array[i] == data[i]);
456 mut_array[i] = 324 + mut_array[i];
457 EXPECT_TRUE(mut_array[i] == (324 + data[i]));
458 }
459 }
460