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 = 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 | |
81 | typedef ::testing::Types<TinyPtrVector<int *>, TinyPtrVector<double *>, |
82 | TinyPtrVector<PointerIntPair<int *, 1>>> |
83 | TinyPtrVectorTestTypes; |
84 | TYPED_TEST_SUITE(TinyPtrVectorTest, TinyPtrVectorTestTypes, ); |
85 | |
86 | TYPED_TEST(TinyPtrVectorTest, EmptyTest) { |
87 | this->expectValues(this->V, this->testArray(0)); |
88 | } |
89 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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(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 | |
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(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 | |