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