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
22using namespace llvm;
23
24namespace {
25template <typename T> struct RemovePointer : std::remove_pointer<T> {};
26
27template <typename PointerTy, unsigned IntBits, typename IntType,
28 typename PtrTraits, typename Info>
29struct RemovePointer<
30 PointerIntPair<PointerTy, IntBits, IntType, PtrTraits, Info>> {
31 typedef typename RemovePointer<PointerTy>::type type;
32};
33
34template <typename VectorT>
35class TinyPtrVectorTest : public testing::Test {
36protected:
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 = 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
54 PtrT makePtr(ValueT *V) { return PtrT(V); }
55
56 ArrayRef<PtrT> testArray(size_t N) { return ArrayRef(&TestPtrs[0], N); }
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, Values: Values1);
66 V2.clear();
67 appendValues(V&: V2, Values: 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 *>, TinyPtrVector<double *>,
82 TinyPtrVector<PointerIntPair<int *, 1>>>
83 TinyPtrVectorTestTypes;
84TYPED_TEST_SUITE(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->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
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 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
171TYPED_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
298TYPED_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
329TYPED_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
367TYPED_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
384TYPED_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
422TEST(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
431TEST(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(x: &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
448TEST(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(x: &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

source code of llvm/unittests/ADT/TinyPtrVectorTest.cpp