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