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 "gtest/gtest.h"
15#include "llvm/ADT/ArrayRef.h"
16#include "llvm/ADT/SmallVector.h"
17#include "llvm/ADT/STLExtras.h"
18#include "llvm/ADT/TinyPtrVector.h"
19#include "llvm/Support/type_traits.h"
20#include <algorithm>
21#include <list>
22#include <vector>
23
24using namespace llvm;
25
26namespace {
27
28// The world's worst RNG, but it is deterministic and makes it easy to get
29// *some* shuffling of elements.
30static ptrdiff_t test_shuffle_rng(ptrdiff_t i) {
31  return (i + i * 33) % i;
32}
33static ptrdiff_t (*test_shuffle_rng_p)(ptrdiff_t) = &test_shuffle_rng;
34
35template <typename VectorT>
36class TinyPtrVectorTest : public testing::Test {
37protected:
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
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
54  ArrayRef<PtrT> testArray(size_t N) {
55    return makeArrayRef(&TestPtrs[0], N);
56  }
57
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
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
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
81typedef ::testing::Types<TinyPtrVector<int*>,
82                         TinyPtrVector<double*>
83                         > TinyPtrVectorTestTypes;
84TYPED_TEST_CASE(TinyPtrVectorTest, TinyPtrVectorTestTypes);
85
86TYPED_TEST(TinyPtrVectorTest, EmptyTest) {
87  this->expectValues(this->V, this->testArray(0));
88}
89
90TYPED_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
129TYPED_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
145TYPED_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_USE_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
167TYPED_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_USE_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_USE_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_USE_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_USE_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_USE_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_USE_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_USE_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_USE_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_USE_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_USE_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_USE_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_USE_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_USE_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_USE_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_USE_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_USE_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
326TYPED_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
357TYPED_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
395TYPED_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
412TYPED_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