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 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], *llvm::next(V.begin(), i));
76 }
77 EXPECT_EQ(V.end(), llvm::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 #if LLVM_HAS_RVALUE_REFERENCES
161 TypeParam Move(std::move(Copy2));
162 this->expectValues(Move, this->testArray(42));
163 this->expectValues(Copy2, this->testArray(0));
164 #endif
165 }
166
TYPED_TEST(TinyPtrVectorTest,CopyAndMoveTest)167 TYPED_TEST(TinyPtrVectorTest, CopyAndMoveTest) {
168 this->V = this->V2;
169 this->expectValues(this->V, this->testArray(0));
170 this->expectValues(this->V2, this->testArray(0));
171 #if LLVM_HAS_RVALUE_REFERENCES
172 this->V = std::move(this->V2);
173 this->expectValues(this->V, this->testArray(0));
174 #endif
175
176 this->setVectors(this->testArray(1), this->testArray(0));
177 this->V = this->V2;
178 this->expectValues(this->V, this->testArray(0));
179 this->expectValues(this->V2, this->testArray(0));
180 #if LLVM_HAS_RVALUE_REFERENCES
181 this->setVectors(this->testArray(1), this->testArray(0));
182 this->V = std::move(this->V2);
183 this->expectValues(this->V, this->testArray(0));
184 #endif
185
186 this->setVectors(this->testArray(2), 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 #if LLVM_HAS_RVALUE_REFERENCES
191 this->setVectors(this->testArray(2), this->testArray(0));
192 this->V = std::move(this->V2);
193 this->expectValues(this->V, this->testArray(0));
194 #endif
195
196 this->setVectors(this->testArray(42), this->testArray(0));
197 this->V = this->V2;
198 this->expectValues(this->V, this->testArray(0));
199 this->expectValues(this->V2, this->testArray(0));
200 #if LLVM_HAS_RVALUE_REFERENCES
201 this->setVectors(this->testArray(42), this->testArray(0));
202 this->V = std::move(this->V2);
203 this->expectValues(this->V, this->testArray(0));
204 #endif
205
206 this->setVectors(this->testArray(0), this->testArray(1));
207 this->V = this->V2;
208 this->expectValues(this->V, this->testArray(1));
209 this->expectValues(this->V2, this->testArray(1));
210 #if LLVM_HAS_RVALUE_REFERENCES
211 this->setVectors(this->testArray(0), this->testArray(1));
212 this->V = std::move(this->V2);
213 this->expectValues(this->V, this->testArray(1));
214 #endif
215
216 this->setVectors(this->testArray(0), this->testArray(2));
217 this->V = this->V2;
218 this->expectValues(this->V, this->testArray(2));
219 this->expectValues(this->V2, this->testArray(2));
220 #if LLVM_HAS_RVALUE_REFERENCES
221 this->setVectors(this->testArray(0), this->testArray(2));
222 this->V = std::move(this->V2);
223 this->expectValues(this->V, this->testArray(2));
224 #endif
225
226 this->setVectors(this->testArray(0), this->testArray(42));
227 this->V = this->V2;
228 this->expectValues(this->V, this->testArray(42));
229 this->expectValues(this->V2, this->testArray(42));
230 #if LLVM_HAS_RVALUE_REFERENCES
231 this->setVectors(this->testArray(0), this->testArray(42));
232 this->V = std::move(this->V2);
233 this->expectValues(this->V, this->testArray(42));
234 #endif
235
236 this->setVectors(this->testArray(1), this->testArray(1));
237 this->V = this->V2;
238 this->expectValues(this->V, this->testArray(1));
239 this->expectValues(this->V2, this->testArray(1));
240 #if LLVM_HAS_RVALUE_REFERENCES
241 this->V = std::move(this->V2);
242 this->expectValues(this->V, this->testArray(1));
243 #endif
244
245 this->setVectors(this->testArray(1), this->testArray(2));
246 this->V = this->V2;
247 this->expectValues(this->V, this->testArray(2));
248 this->expectValues(this->V2, this->testArray(2));
249 #if LLVM_HAS_RVALUE_REFERENCES
250 this->setVectors(this->testArray(1), this->testArray(2));
251 this->V = std::move(this->V2);
252 this->expectValues(this->V, this->testArray(2));
253 #endif
254
255 this->setVectors(this->testArray(1), this->testArray(42));
256 this->V = this->V2;
257 this->expectValues(this->V, this->testArray(42));
258 this->expectValues(this->V2, this->testArray(42));
259 #if LLVM_HAS_RVALUE_REFERENCES
260 this->setVectors(this->testArray(1), this->testArray(42));
261 this->V = std::move(this->V2);
262 this->expectValues(this->V, this->testArray(42));
263 #endif
264
265 this->setVectors(this->testArray(2), 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 #if LLVM_HAS_RVALUE_REFERENCES
270 this->setVectors(this->testArray(2), this->testArray(1));
271 this->V = std::move(this->V2);
272 this->expectValues(this->V, this->testArray(1));
273 #endif
274
275 this->setVectors(this->testArray(2), 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 #if LLVM_HAS_RVALUE_REFERENCES
280 this->setVectors(this->testArray(2), this->testArray(2));
281 this->V = std::move(this->V2);
282 this->expectValues(this->V, this->testArray(2));
283 #endif
284
285 this->setVectors(this->testArray(2), this->testArray(42));
286 this->V = this->V2;
287 this->expectValues(this->V, this->testArray(42));
288 this->expectValues(this->V2, this->testArray(42));
289 #if LLVM_HAS_RVALUE_REFERENCES
290 this->setVectors(this->testArray(2), this->testArray(42));
291 this->V = std::move(this->V2);
292 this->expectValues(this->V, this->testArray(42));
293 #endif
294
295 this->setVectors(this->testArray(42), this->testArray(1));
296 this->V = this->V2;
297 this->expectValues(this->V, this->testArray(1));
298 this->expectValues(this->V2, this->testArray(1));
299 #if LLVM_HAS_RVALUE_REFERENCES
300 this->setVectors(this->testArray(42), this->testArray(1));
301 this->V = std::move(this->V2);
302 this->expectValues(this->V, this->testArray(1));
303 #endif
304
305 this->setVectors(this->testArray(42), this->testArray(2));
306 this->V = this->V2;
307 this->expectValues(this->V, this->testArray(2));
308 this->expectValues(this->V2, this->testArray(2));
309 #if LLVM_HAS_RVALUE_REFERENCES
310 this->setVectors(this->testArray(42), this->testArray(2));
311 this->V = std::move(this->V2);
312 this->expectValues(this->V, this->testArray(2));
313 #endif
314
315 this->setVectors(this->testArray(42), this->testArray(42));
316 this->V = this->V2;
317 this->expectValues(this->V, this->testArray(42));
318 this->expectValues(this->V2, this->testArray(42));
319 #if LLVM_HAS_RVALUE_REFERENCES
320 this->setVectors(this->testArray(42), this->testArray(42));
321 this->V = std::move(this->V2);
322 this->expectValues(this->V, this->testArray(42));
323 #endif
324 }
325
TYPED_TEST(TinyPtrVectorTest,EraseTest)326 TYPED_TEST(TinyPtrVectorTest, EraseTest) {
327 this->appendValues(this->V, this->testArray(1));
328 this->expectValues(this->V, this->testArray(1));
329 this->V.erase(this->V.begin());
330 this->expectValues(this->V, this->testArray(0));
331
332 this->appendValues(this->V, this->testArray(42));
333 this->expectValues(this->V, this->testArray(42));
334 this->V.erase(this->V.begin());
335 this->TestPtrs.erase(this->TestPtrs.begin());
336 this->expectValues(this->V, this->testArray(41));
337 this->V.erase(llvm::next(this->V.begin(), 1));
338 this->TestPtrs.erase(llvm::next(this->TestPtrs.begin(), 1));
339 this->expectValues(this->V, this->testArray(40));
340 this->V.erase(llvm::next(this->V.begin(), 2));
341 this->TestPtrs.erase(llvm::next(this->TestPtrs.begin(), 2));
342 this->expectValues(this->V, this->testArray(39));
343 this->V.erase(llvm::next(this->V.begin(), 5));
344 this->TestPtrs.erase(llvm::next(this->TestPtrs.begin(), 5));
345 this->expectValues(this->V, this->testArray(38));
346 this->V.erase(llvm::next(this->V.begin(), 13));
347 this->TestPtrs.erase(llvm::next(this->TestPtrs.begin(), 13));
348 this->expectValues(this->V, this->testArray(37));
349
350 typename TypeParam::iterator I = this->V.begin();
351 do {
352 I = this->V.erase(I);
353 } while (I != this->V.end());
354 this->expectValues(this->V, this->testArray(0));
355 }
356
TYPED_TEST(TinyPtrVectorTest,EraseRangeTest)357 TYPED_TEST(TinyPtrVectorTest, EraseRangeTest) {
358 this->appendValues(this->V, this->testArray(1));
359 this->expectValues(this->V, this->testArray(1));
360 this->V.erase(this->V.begin(), this->V.begin());
361 this->expectValues(this->V, this->testArray(1));
362 this->V.erase(this->V.end(), this->V.end());
363 this->expectValues(this->V, this->testArray(1));
364 this->V.erase(this->V.begin(), this->V.end());
365 this->expectValues(this->V, this->testArray(0));
366
367 this->appendValues(this->V, this->testArray(42));
368 this->expectValues(this->V, this->testArray(42));
369 this->V.erase(this->V.begin(), llvm::next(this->V.begin(), 1));
370 this->TestPtrs.erase(this->TestPtrs.begin(),
371 llvm::next(this->TestPtrs.begin(), 1));
372 this->expectValues(this->V, this->testArray(41));
373 this->V.erase(llvm::next(this->V.begin(), 1), llvm::next(this->V.begin(), 2));
374 this->TestPtrs.erase(llvm::next(this->TestPtrs.begin(), 1),
375 llvm::next(this->TestPtrs.begin(), 2));
376 this->expectValues(this->V, this->testArray(40));
377 this->V.erase(llvm::next(this->V.begin(), 2), llvm::next(this->V.begin(), 4));
378 this->TestPtrs.erase(llvm::next(this->TestPtrs.begin(), 2),
379 llvm::next(this->TestPtrs.begin(), 4));
380 this->expectValues(this->V, this->testArray(38));
381 this->V.erase(llvm::next(this->V.begin(), 5), llvm::next(this->V.begin(), 10));
382 this->TestPtrs.erase(llvm::next(this->TestPtrs.begin(), 5),
383 llvm::next(this->TestPtrs.begin(), 10));
384 this->expectValues(this->V, this->testArray(33));
385 this->V.erase(llvm::next(this->V.begin(), 13), llvm::next(this->V.begin(), 26));
386 this->TestPtrs.erase(llvm::next(this->TestPtrs.begin(), 13),
387 llvm::next(this->TestPtrs.begin(), 26));
388 this->expectValues(this->V, this->testArray(20));
389 this->V.erase(llvm::next(this->V.begin(), 7), this->V.end());
390 this->expectValues(this->V, this->testArray(7));
391 this->V.erase(this->V.begin(), this->V.end());
392 this->expectValues(this->V, this->testArray(0));
393 }
394
TYPED_TEST(TinyPtrVectorTest,Insert)395 TYPED_TEST(TinyPtrVectorTest, Insert) {
396 this->V.insert(this->V.end(), this->TestPtrs[0]);
397 this->expectValues(this->V, this->testArray(1));
398 this->V.clear();
399 this->appendValues(this->V, this->testArray(4));
400 this->expectValues(this->V, this->testArray(4));
401 this->V.insert(this->V.end(), this->TestPtrs[4]);
402 this->expectValues(this->V, this->testArray(5));
403 this->V.insert(this->V.begin(), this->TestPtrs[42]);
404 this->TestPtrs.insert(this->TestPtrs.begin(), this->TestPtrs[42]);
405 this->expectValues(this->V, this->testArray(6));
406 this->V.insert(llvm::next(this->V.begin(), 3), this->TestPtrs[43]);
407 this->TestPtrs.insert(llvm::next(this->TestPtrs.begin(), 3),
408 this->TestPtrs[43]);
409 this->expectValues(this->V, this->testArray(7));
410 }
411
TYPED_TEST(TinyPtrVectorTest,InsertRange)412 TYPED_TEST(TinyPtrVectorTest, InsertRange) {
413 this->V.insert(this->V.end(), this->TestPtrs.begin(), this->TestPtrs.begin());
414 this->expectValues(this->V, this->testArray(0));
415 this->V.insert(this->V.begin(), this->TestPtrs.begin(),
416 this->TestPtrs.begin());
417 this->expectValues(this->V, this->testArray(0));
418 this->V.insert(this->V.end(), this->TestPtrs.end(), this->TestPtrs.end());
419 this->expectValues(this->V, this->testArray(0));
420 this->V.insert(this->V.end(), this->TestPtrs.begin(),
421 llvm::next(this->TestPtrs.begin()));
422 this->expectValues(this->V, this->testArray(1));
423 this->V.clear();
424 this->V.insert(this->V.end(), this->TestPtrs.begin(),
425 llvm::next(this->TestPtrs.begin(), 2));
426 this->expectValues(this->V, this->testArray(2));
427 this->V.clear();
428 this->V.insert(this->V.end(), this->TestPtrs.begin(),
429 llvm::next(this->TestPtrs.begin(), 42));
430 this->expectValues(this->V, this->testArray(42));
431 this->V.clear();
432 this->V.insert(this->V.end(),
433 llvm::next(this->TestPtrs.begin(), 5),
434 llvm::next(this->TestPtrs.begin(), 13));
435 this->V.insert(this->V.begin(),
436 llvm::next(this->TestPtrs.begin(), 0),
437 llvm::next(this->TestPtrs.begin(), 3));
438 this->V.insert(llvm::next(this->V.begin(), 2),
439 llvm::next(this->TestPtrs.begin(), 2),
440 llvm::next(this->TestPtrs.begin(), 4));
441 this->V.erase(llvm::next(this->V.begin(), 4));
442 this->V.insert(llvm::next(this->V.begin(), 4),
443 llvm::next(this->TestPtrs.begin(), 4),
444 llvm::next(this->TestPtrs.begin(), 5));
445 this->expectValues(this->V, this->testArray(13));
446 }
447
448 }
449