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
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 std::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], *std::next(V.begin(), i));
76    }
77    EXPECT_EQ(V.end(), std::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  TypeParam Move(std::move(Copy2));
161  this->expectValues(Move, this->testArray(42));
162  this->expectValues(Copy2, this->testArray(0));
163}
164
165TYPED_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
292TYPED_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
323TYPED_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
361TYPED_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
378TYPED_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