xref: /llvm-project/llvm/unittests/ADT/TinyPtrVectorTest.cpp (revision 38818b60c58c76ba89b990978cdfd2d7b6799260) 
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 
TinyPtrVectorTest()47   TinyPtrVectorTest() {
48     for (size_t i = 0, e = std::size(TestValues); i != e; ++i)
49       TestPtrs.push_back(PtrT(&TestValues[i]));
50 
51     std::shuffle(TestPtrs.begin(), TestPtrs.end(), std::mt19937{});
52   }
53 
makePtr(ValueT * V)54   PtrT makePtr(ValueT *V) { return PtrT(V); }
55 
testArray(size_t N)56   ArrayRef<PtrT> testArray(size_t N) { return ArrayRef(&TestPtrs[0], N); }
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 *>, TinyPtrVector<double *>,
82                          TinyPtrVector<PointerIntPair<int *, 1>>>
83     TinyPtrVectorTestTypes;
84 TYPED_TEST_SUITE(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->makePtr(&this->TestValues[42]);
108   this->TestPtrs[4] = this->makePtr(&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   TypeParam MultipleElements(this->testArray(2));
165   TypeParam SingleElement(this->testArray(1));
166   MultipleElements = std::move(SingleElement);
167   this->expectValues(MultipleElements, this->testArray(1));
168   this->expectValues(SingleElement, this->testArray(0));
169 }
170 
TYPED_TEST(TinyPtrVectorTest,CopyAndMoveTest)171 TYPED_TEST(TinyPtrVectorTest, CopyAndMoveTest) {
172   this->V = this->V2;
173   this->expectValues(this->V, this->testArray(0));
174   this->expectValues(this->V2, this->testArray(0));
175   this->V = std::move(this->V2);
176   this->expectValues(this->V, this->testArray(0));
177 
178   this->setVectors(this->testArray(1), this->testArray(0));
179   this->V = this->V2;
180   this->expectValues(this->V, this->testArray(0));
181   this->expectValues(this->V2, this->testArray(0));
182   this->setVectors(this->testArray(1), this->testArray(0));
183   this->V = std::move(this->V2);
184   this->expectValues(this->V, this->testArray(0));
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   this->setVectors(this->testArray(2), this->testArray(0));
191   this->V = std::move(this->V2);
192   this->expectValues(this->V, this->testArray(0));
193 
194   this->setVectors(this->testArray(42), this->testArray(0));
195   this->V = this->V2;
196   this->expectValues(this->V, this->testArray(0));
197   this->expectValues(this->V2, this->testArray(0));
198   this->setVectors(this->testArray(42), this->testArray(0));
199   this->V = std::move(this->V2);
200   this->expectValues(this->V, this->testArray(0));
201 
202   this->setVectors(this->testArray(0), this->testArray(1));
203   this->V = this->V2;
204   this->expectValues(this->V, this->testArray(1));
205   this->expectValues(this->V2, this->testArray(1));
206   this->setVectors(this->testArray(0), this->testArray(1));
207   this->V = std::move(this->V2);
208   this->expectValues(this->V, this->testArray(1));
209 
210   this->setVectors(this->testArray(0), this->testArray(2));
211   this->V = this->V2;
212   this->expectValues(this->V, this->testArray(2));
213   this->expectValues(this->V2, this->testArray(2));
214   this->setVectors(this->testArray(0), this->testArray(2));
215   this->V = std::move(this->V2);
216   this->expectValues(this->V, this->testArray(2));
217 
218   this->setVectors(this->testArray(0), this->testArray(42));
219   this->V = this->V2;
220   this->expectValues(this->V, this->testArray(42));
221   this->expectValues(this->V2, this->testArray(42));
222   this->setVectors(this->testArray(0), this->testArray(42));
223   this->V = std::move(this->V2);
224   this->expectValues(this->V, this->testArray(42));
225 
226   this->setVectors(this->testArray(1), this->testArray(1));
227   this->V = this->V2;
228   this->expectValues(this->V, this->testArray(1));
229   this->expectValues(this->V2, this->testArray(1));
230   this->V = std::move(this->V2);
231   this->expectValues(this->V, this->testArray(1));
232 
233   this->setVectors(this->testArray(1), this->testArray(2));
234   this->V = this->V2;
235   this->expectValues(this->V, this->testArray(2));
236   this->expectValues(this->V2, this->testArray(2));
237   this->setVectors(this->testArray(1), this->testArray(2));
238   this->V = std::move(this->V2);
239   this->expectValues(this->V, this->testArray(2));
240 
241   this->setVectors(this->testArray(1), this->testArray(42));
242   this->V = this->V2;
243   this->expectValues(this->V, this->testArray(42));
244   this->expectValues(this->V2, this->testArray(42));
245   this->setVectors(this->testArray(1), this->testArray(42));
246   this->V = std::move(this->V2);
247   this->expectValues(this->V, this->testArray(42));
248 
249   this->setVectors(this->testArray(2), this->testArray(1));
250   this->V = this->V2;
251   this->expectValues(this->V, this->testArray(1));
252   this->expectValues(this->V2, this->testArray(1));
253   this->setVectors(this->testArray(2), this->testArray(1));
254   this->V = std::move(this->V2);
255   this->expectValues(this->V, this->testArray(1));
256 
257   this->setVectors(this->testArray(2), this->testArray(2));
258   this->V = this->V2;
259   this->expectValues(this->V, this->testArray(2));
260   this->expectValues(this->V2, this->testArray(2));
261   this->setVectors(this->testArray(2), this->testArray(2));
262   this->V = std::move(this->V2);
263   this->expectValues(this->V, this->testArray(2));
264 
265   this->setVectors(this->testArray(2), this->testArray(42));
266   this->V = this->V2;
267   this->expectValues(this->V, this->testArray(42));
268   this->expectValues(this->V2, this->testArray(42));
269   this->setVectors(this->testArray(2), this->testArray(42));
270   this->V = std::move(this->V2);
271   this->expectValues(this->V, this->testArray(42));
272 
273   this->setVectors(this->testArray(42), this->testArray(1));
274   this->V = this->V2;
275   this->expectValues(this->V, this->testArray(1));
276   this->expectValues(this->V2, this->testArray(1));
277   this->setVectors(this->testArray(42), this->testArray(1));
278   this->V = std::move(this->V2);
279   this->expectValues(this->V, this->testArray(1));
280 
281   this->setVectors(this->testArray(42), this->testArray(2));
282   this->V = this->V2;
283   this->expectValues(this->V, this->testArray(2));
284   this->expectValues(this->V2, this->testArray(2));
285   this->setVectors(this->testArray(42), this->testArray(2));
286   this->V = std::move(this->V2);
287   this->expectValues(this->V, this->testArray(2));
288 
289   this->setVectors(this->testArray(42), this->testArray(42));
290   this->V = this->V2;
291   this->expectValues(this->V, this->testArray(42));
292   this->expectValues(this->V2, this->testArray(42));
293   this->setVectors(this->testArray(42), this->testArray(42));
294   this->V = std::move(this->V2);
295   this->expectValues(this->V, this->testArray(42));
296 }
297 
TYPED_TEST(TinyPtrVectorTest,EraseTest)298 TYPED_TEST(TinyPtrVectorTest, EraseTest) {
299   this->appendValues(this->V, this->testArray(1));
300   this->expectValues(this->V, this->testArray(1));
301   this->V.erase(this->V.begin());
302   this->expectValues(this->V, this->testArray(0));
303 
304   this->appendValues(this->V, this->testArray(42));
305   this->expectValues(this->V, this->testArray(42));
306   this->V.erase(this->V.begin());
307   this->TestPtrs.erase(this->TestPtrs.begin());
308   this->expectValues(this->V, this->testArray(41));
309   this->V.erase(std::next(this->V.begin(), 1));
310   this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 1));
311   this->expectValues(this->V, this->testArray(40));
312   this->V.erase(std::next(this->V.begin(), 2));
313   this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 2));
314   this->expectValues(this->V, this->testArray(39));
315   this->V.erase(std::next(this->V.begin(), 5));
316   this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 5));
317   this->expectValues(this->V, this->testArray(38));
318   this->V.erase(std::next(this->V.begin(), 13));
319   this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 13));
320   this->expectValues(this->V, this->testArray(37));
321 
322   typename TypeParam::iterator I = this->V.begin();
323   do {
324     I = this->V.erase(I);
325   } while (I != this->V.end());
326   this->expectValues(this->V, this->testArray(0));
327 }
328 
TYPED_TEST(TinyPtrVectorTest,EraseRangeTest)329 TYPED_TEST(TinyPtrVectorTest, EraseRangeTest) {
330   this->appendValues(this->V, this->testArray(1));
331   this->expectValues(this->V, this->testArray(1));
332   this->V.erase(this->V.begin(), this->V.begin());
333   this->expectValues(this->V, this->testArray(1));
334   this->V.erase(this->V.end(), this->V.end());
335   this->expectValues(this->V, this->testArray(1));
336   this->V.erase(this->V.begin(), this->V.end());
337   this->expectValues(this->V, this->testArray(0));
338 
339   this->appendValues(this->V, this->testArray(42));
340   this->expectValues(this->V, this->testArray(42));
341   this->V.erase(this->V.begin(), std::next(this->V.begin(), 1));
342   this->TestPtrs.erase(this->TestPtrs.begin(),
343                        std::next(this->TestPtrs.begin(), 1));
344   this->expectValues(this->V, this->testArray(41));
345   this->V.erase(std::next(this->V.begin(), 1), std::next(this->V.begin(), 2));
346   this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 1),
347                        std::next(this->TestPtrs.begin(), 2));
348   this->expectValues(this->V, this->testArray(40));
349   this->V.erase(std::next(this->V.begin(), 2), std::next(this->V.begin(), 4));
350   this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 2),
351                        std::next(this->TestPtrs.begin(), 4));
352   this->expectValues(this->V, this->testArray(38));
353   this->V.erase(std::next(this->V.begin(), 5), std::next(this->V.begin(), 10));
354   this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 5),
355                        std::next(this->TestPtrs.begin(), 10));
356   this->expectValues(this->V, this->testArray(33));
357   this->V.erase(std::next(this->V.begin(), 13), std::next(this->V.begin(), 26));
358   this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 13),
359                        std::next(this->TestPtrs.begin(), 26));
360   this->expectValues(this->V, this->testArray(20));
361   this->V.erase(std::next(this->V.begin(), 7), this->V.end());
362   this->expectValues(this->V, this->testArray(7));
363   this->V.erase(this->V.begin(), this->V.end());
364   this->expectValues(this->V, this->testArray(0));
365 }
366 
TYPED_TEST(TinyPtrVectorTest,Insert)367 TYPED_TEST(TinyPtrVectorTest, Insert) {
368   this->V.insert(this->V.end(), this->TestPtrs[0]);
369   this->expectValues(this->V, this->testArray(1));
370   this->V.clear();
371   this->appendValues(this->V, this->testArray(4));
372   this->expectValues(this->V, this->testArray(4));
373   this->V.insert(this->V.end(), this->TestPtrs[4]);
374   this->expectValues(this->V, this->testArray(5));
375   this->V.insert(this->V.begin(), this->TestPtrs[42]);
376   this->TestPtrs.insert(this->TestPtrs.begin(), this->TestPtrs[42]);
377   this->expectValues(this->V, this->testArray(6));
378   this->V.insert(std::next(this->V.begin(), 3), this->TestPtrs[43]);
379   this->TestPtrs.insert(std::next(this->TestPtrs.begin(), 3),
380                         this->TestPtrs[43]);
381   this->expectValues(this->V, this->testArray(7));
382 }
383 
TYPED_TEST(TinyPtrVectorTest,InsertRange)384 TYPED_TEST(TinyPtrVectorTest, InsertRange) {
385   this->V.insert(this->V.end(), this->TestPtrs.begin(), this->TestPtrs.begin());
386   this->expectValues(this->V, this->testArray(0));
387   this->V.insert(this->V.begin(), this->TestPtrs.begin(),
388                  this->TestPtrs.begin());
389   this->expectValues(this->V, this->testArray(0));
390   this->V.insert(this->V.end(), this->TestPtrs.end(), this->TestPtrs.end());
391   this->expectValues(this->V, this->testArray(0));
392   this->V.insert(this->V.end(), this->TestPtrs.begin(),
393                  std::next(this->TestPtrs.begin()));
394   this->expectValues(this->V, this->testArray(1));
395   this->V.clear();
396   this->V.insert(this->V.end(), this->TestPtrs.begin(),
397                  std::next(this->TestPtrs.begin(), 2));
398   this->expectValues(this->V, this->testArray(2));
399   this->V.clear();
400   this->V.insert(this->V.end(), this->TestPtrs.begin(),
401                  std::next(this->TestPtrs.begin(), 42));
402   this->expectValues(this->V, this->testArray(42));
403   this->V.clear();
404   this->V.insert(this->V.end(),
405                  std::next(this->TestPtrs.begin(), 5),
406                  std::next(this->TestPtrs.begin(), 13));
407   this->V.insert(this->V.begin(),
408                  std::next(this->TestPtrs.begin(), 0),
409                  std::next(this->TestPtrs.begin(), 3));
410   this->V.insert(std::next(this->V.begin(), 2),
411                  std::next(this->TestPtrs.begin(), 2),
412                  std::next(this->TestPtrs.begin(), 4));
413   this->V.erase(std::next(this->V.begin(), 4));
414   this->V.insert(std::next(this->V.begin(), 4),
415                  std::next(this->TestPtrs.begin(), 4),
416                  std::next(this->TestPtrs.begin(), 5));
417   this->expectValues(this->V, this->testArray(13));
418 }
419 
420 }
421 
TEST(TinyPtrVectorTest,SingleEltCtorTest)422 TEST(TinyPtrVectorTest, SingleEltCtorTest) {
423   int v = 55;
424   TinyPtrVector<int *> V(&v);
425 
426   EXPECT_TRUE(V.size() == 1);
427   EXPECT_FALSE(V.empty());
428   EXPECT_TRUE(V.front() == &v);
429 }
430 
TEST(TinyPtrVectorTest,ArrayRefCtorTest)431 TEST(TinyPtrVectorTest, ArrayRefCtorTest) {
432   int data_array[128];
433   std::vector<int *> data;
434 
435   for (unsigned i = 0, e = 128; i != e; ++i) {
436     data_array[i] = 324 - int(i);
437     data.push_back(&data_array[i]);
438   }
439 
440   TinyPtrVector<int *> V(data);
441   EXPECT_TRUE(V.size() == 128);
442   EXPECT_FALSE(V.empty());
443   for (unsigned i = 0, e = 128; i != e; ++i) {
444     EXPECT_TRUE(V[i] == data[i]);
445   }
446 }
447 
TEST(TinyPtrVectorTest,MutableArrayRefTest)448 TEST(TinyPtrVectorTest, MutableArrayRefTest) {
449   int data_array[128];
450   std::vector<int *> data;
451 
452   for (unsigned i = 0, e = 128; i != e; ++i) {
453     data_array[i] = 324 - int(i);
454     data.push_back(&data_array[i]);
455   }
456 
457   TinyPtrVector<int *> V(data);
458   EXPECT_TRUE(V.size() == 128);
459   EXPECT_FALSE(V.empty());
460 
461   MutableArrayRef<int *> mut_array = V;
462   for (unsigned i = 0, e = 128; i != e; ++i) {
463     EXPECT_TRUE(mut_array[i] == data[i]);
464     mut_array[i] = 324 + mut_array[i];
465     EXPECT_TRUE(mut_array[i] == (324 + data[i]));
466   }
467 }
468