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