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