1 //===- unittest/ADT/MapVectorTest.cpp - MapVector unit tests ----*- C++ -*-===//
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 #include "llvm/ADT/MapVector.h"
10 #include "llvm/ADT/iterator_range.h"
11 #include "gtest/gtest.h"
12 #include <memory>
13 #include <utility>
14
15 using namespace llvm;
16
17 namespace {
18 struct CountCopyAndMove {
19 CountCopyAndMove() = default;
CountCopyAndMove__anonb445f7f80111::CountCopyAndMove20 CountCopyAndMove(const CountCopyAndMove &) { copy = 1; }
CountCopyAndMove__anonb445f7f80111::CountCopyAndMove21 CountCopyAndMove(CountCopyAndMove &&) { move = 1; }
operator =__anonb445f7f80111::CountCopyAndMove22 void operator=(const CountCopyAndMove &) { ++copy; }
operator =__anonb445f7f80111::CountCopyAndMove23 void operator=(CountCopyAndMove &&) { ++move; }
24 int copy = 0;
25 int move = 0;
26 };
27
28 struct A : CountCopyAndMove {
A__anonb445f7f80111::A29 A(int v) : v(v) {}
30 int v;
31 };
32 } // namespace
33
34 namespace llvm {
35 template <> struct DenseMapInfo<A> {
getEmptyKeyllvm::DenseMapInfo36 static inline A getEmptyKey() { return 0x7fffffff; }
getTombstoneKeyllvm::DenseMapInfo37 static inline A getTombstoneKey() { return -0x7fffffff - 1; }
getHashValuellvm::DenseMapInfo38 static unsigned getHashValue(const A &Val) { return (unsigned)(Val.v * 37U); }
isEqualllvm::DenseMapInfo39 static bool isEqual(const A &LHS, const A &RHS) { return LHS.v == RHS.v; }
40 };
41 } // namespace llvm
42
43 namespace {
TEST(MapVectorTest,swap)44 TEST(MapVectorTest, swap) {
45 MapVector<int, int> MV1, MV2;
46 std::pair<MapVector<int, int>::iterator, bool> R;
47
48 R = MV1.insert(std::make_pair(1, 2));
49 ASSERT_EQ(R.first, MV1.begin());
50 EXPECT_EQ(R.first->first, 1);
51 EXPECT_EQ(R.first->second, 2);
52 EXPECT_TRUE(R.second);
53
54 EXPECT_FALSE(MV1.empty());
55 EXPECT_TRUE(MV2.empty());
56 MV2.swap(MV1);
57 EXPECT_TRUE(MV1.empty());
58 EXPECT_FALSE(MV2.empty());
59
60 auto I = MV1.find(1);
61 ASSERT_EQ(MV1.end(), I);
62
63 I = MV2.find(1);
64 ASSERT_EQ(I, MV2.begin());
65 EXPECT_EQ(I->first, 1);
66 EXPECT_EQ(I->second, 2);
67 }
68
TEST(MapVectorTest,insert_pop)69 TEST(MapVectorTest, insert_pop) {
70 MapVector<int, int> MV;
71 std::pair<MapVector<int, int>::iterator, bool> R;
72
73 R = MV.insert(std::make_pair(1, 2));
74 ASSERT_EQ(R.first, MV.begin());
75 EXPECT_EQ(R.first->first, 1);
76 EXPECT_EQ(R.first->second, 2);
77 EXPECT_TRUE(R.second);
78
79 R = MV.insert(std::make_pair(1, 3));
80 ASSERT_EQ(R.first, MV.begin());
81 EXPECT_EQ(R.first->first, 1);
82 EXPECT_EQ(R.first->second, 2);
83 EXPECT_FALSE(R.second);
84
85 R = MV.insert(std::make_pair(4, 5));
86 ASSERT_NE(R.first, MV.end());
87 EXPECT_EQ(R.first->first, 4);
88 EXPECT_EQ(R.first->second, 5);
89 EXPECT_TRUE(R.second);
90
91 EXPECT_EQ(MV.size(), 2u);
92 EXPECT_EQ(MV[1], 2);
93 EXPECT_EQ(MV[4], 5);
94
95 MV.pop_back();
96 EXPECT_EQ(MV.size(), 1u);
97 EXPECT_EQ(MV[1], 2);
98
99 R = MV.insert(std::make_pair(4, 7));
100 ASSERT_NE(R.first, MV.end());
101 EXPECT_EQ(R.first->first, 4);
102 EXPECT_EQ(R.first->second, 7);
103 EXPECT_TRUE(R.second);
104
105 EXPECT_EQ(MV.size(), 2u);
106 EXPECT_EQ(MV[1], 2);
107 EXPECT_EQ(MV[4], 7);
108 }
109
TEST(MapVectorTest,try_emplace)110 TEST(MapVectorTest, try_emplace) {
111 struct AAndU {
112 A a;
113 std::unique_ptr<int> b;
114 AAndU(A a, std::unique_ptr<int> b) : a(a), b(std::move(b)) {}
115 };
116 MapVector<A, AAndU> mv;
117
118 A zero(0);
119 auto try0 = mv.try_emplace(zero, zero, nullptr);
120 EXPECT_TRUE(try0.second);
121 EXPECT_EQ(0, try0.first->second.a.v);
122 EXPECT_EQ(1, try0.first->second.a.copy);
123 EXPECT_EQ(0, try0.first->second.a.move);
124
125 auto try1 = mv.try_emplace(zero, zero, nullptr);
126 EXPECT_FALSE(try1.second);
127 EXPECT_EQ(0, try1.first->second.a.v);
128 EXPECT_EQ(1, try1.first->second.a.copy);
129 EXPECT_EQ(0, try1.first->second.a.move);
130
131 EXPECT_EQ(try0.first, try1.first);
132 EXPECT_EQ(1, try1.first->first.copy);
133 EXPECT_EQ(0, try1.first->first.move);
134
135 A two(2);
136 auto try2 = mv.try_emplace(2, std::move(two), std::make_unique<int>(2));
137 EXPECT_TRUE(try2.second);
138 EXPECT_EQ(2, try2.first->second.a.v);
139 EXPECT_EQ(0, try2.first->second.a.move);
140
141 std::unique_ptr<int> p(new int(3));
142 auto try3 = mv.try_emplace(std::move(two), 3, std::move(p));
143 EXPECT_FALSE(try3.second);
144 EXPECT_EQ(2, try3.first->second.a.v);
145 EXPECT_EQ(1, try3.first->second.a.copy);
146 EXPECT_EQ(0, try3.first->second.a.move);
147
148 EXPECT_EQ(try2.first, try3.first);
149 EXPECT_EQ(0, try3.first->first.copy);
150 EXPECT_EQ(1, try3.first->first.move);
151 EXPECT_NE(nullptr, p);
152 }
153
TEST(MapVectorTest,insert_or_assign)154 TEST(MapVectorTest, insert_or_assign) {
155 MapVector<A, A> mv;
156
157 A zero(0);
158 auto try0 = mv.insert_or_assign(zero, zero);
159 EXPECT_TRUE(try0.second);
160 EXPECT_EQ(0, try0.first->second.v);
161 EXPECT_EQ(1, try0.first->second.copy);
162 EXPECT_EQ(0, try0.first->second.move);
163
164 auto try1 = mv.insert_or_assign(zero, zero);
165 EXPECT_FALSE(try1.second);
166 EXPECT_EQ(0, try1.first->second.v);
167 EXPECT_EQ(2, try1.first->second.copy);
168 EXPECT_EQ(0, try1.first->second.move);
169
170 EXPECT_EQ(try0.first, try1.first);
171 EXPECT_EQ(1, try1.first->first.copy);
172 EXPECT_EQ(0, try1.first->first.move);
173
174 A two(2);
175 auto try2 = mv.try_emplace(2, std::move(two));
176 EXPECT_TRUE(try2.second);
177 EXPECT_EQ(2, try2.first->second.v);
178 EXPECT_EQ(1, try2.first->second.move);
179
180 auto try3 = mv.insert_or_assign(std::move(two), 3);
181 EXPECT_FALSE(try3.second);
182 EXPECT_EQ(3, try3.first->second.v);
183 EXPECT_EQ(0, try3.first->second.copy);
184 EXPECT_EQ(2, try3.first->second.move);
185
186 EXPECT_EQ(try2.first, try3.first);
187 EXPECT_EQ(0, try3.first->first.copy);
188 EXPECT_EQ(1, try3.first->first.move);
189 }
190
TEST(MapVectorTest,erase)191 TEST(MapVectorTest, erase) {
192 MapVector<int, int> MV;
193
194 MV.insert(std::make_pair(1, 2));
195 MV.insert(std::make_pair(3, 4));
196 MV.insert(std::make_pair(5, 6));
197 ASSERT_EQ(MV.size(), 3u);
198
199 ASSERT_TRUE(MV.contains(1));
200 MV.erase(MV.find(1));
201 ASSERT_EQ(MV.size(), 2u);
202 ASSERT_FALSE(MV.contains(1));
203 ASSERT_EQ(MV.find(1), MV.end());
204 ASSERT_EQ(MV[3], 4);
205 ASSERT_EQ(MV[5], 6);
206
207 ASSERT_EQ(MV.erase(3), 1u);
208 ASSERT_EQ(MV.size(), 1u);
209 ASSERT_EQ(MV.find(3), MV.end());
210 ASSERT_EQ(MV[5], 6);
211
212 ASSERT_EQ(MV.erase(79), 0u);
213 ASSERT_EQ(MV.size(), 1u);
214 }
215
TEST(MapVectorTest,remove_if)216 TEST(MapVectorTest, remove_if) {
217 MapVector<int, int> MV;
218
219 MV.insert(std::make_pair(1, 11));
220 MV.insert(std::make_pair(2, 12));
221 MV.insert(std::make_pair(3, 13));
222 MV.insert(std::make_pair(4, 14));
223 MV.insert(std::make_pair(5, 15));
224 MV.insert(std::make_pair(6, 16));
225 ASSERT_EQ(MV.size(), 6u);
226
227 MV.remove_if([](const std::pair<int, int> &Val) { return Val.second % 2; });
228 ASSERT_EQ(MV.size(), 3u);
229 ASSERT_EQ(MV.find(1), MV.end());
230 ASSERT_EQ(MV.find(3), MV.end());
231 ASSERT_EQ(MV.find(5), MV.end());
232 ASSERT_EQ(MV[2], 12);
233 ASSERT_EQ(MV[4], 14);
234 ASSERT_EQ(MV[6], 16);
235 }
236
TEST(MapVectorTest,iteration_test)237 TEST(MapVectorTest, iteration_test) {
238 MapVector<int, int> MV;
239
240 MV.insert(std::make_pair(1, 11));
241 MV.insert(std::make_pair(2, 12));
242 MV.insert(std::make_pair(3, 13));
243 MV.insert(std::make_pair(4, 14));
244 MV.insert(std::make_pair(5, 15));
245 MV.insert(std::make_pair(6, 16));
246 ASSERT_EQ(MV.size(), 6u);
247
248 int count = 1;
249 for (auto P : make_range(MV.begin(), MV.end())) {
250 ASSERT_EQ(P.first, count);
251 count++;
252 }
253
254 count = 6;
255 for (auto P : make_range(MV.rbegin(), MV.rend())) {
256 ASSERT_EQ(P.first, count);
257 count--;
258 }
259 }
260
TEST(MapVectorTest,NonCopyable)261 TEST(MapVectorTest, NonCopyable) {
262 MapVector<int, std::unique_ptr<int>> MV;
263 MV.insert(std::make_pair(1, std::make_unique<int>(1)));
264 MV.insert(std::make_pair(2, std::make_unique<int>(2)));
265
266 ASSERT_EQ(MV.count(1), 1u);
267 ASSERT_EQ(*MV.find(2)->second, 2);
268 }
269
270 template <class IntType> struct MapVectorMappedTypeTest : ::testing::Test {
271 using int_type = IntType;
272 };
273
274 using MapIntTypes = ::testing::Types<int, long, long long, unsigned,
275 unsigned long, unsigned long long>;
276 TYPED_TEST_SUITE(MapVectorMappedTypeTest, MapIntTypes, );
277
TYPED_TEST(MapVectorMappedTypeTest,DifferentDenseMap)278 TYPED_TEST(MapVectorMappedTypeTest, DifferentDenseMap) {
279 // Test that using a map with a mapped type other than 'unsigned' compiles
280 // and works.
281 using IntType = typename TestFixture::int_type;
282 using MapVectorType = MapVector<int, int, DenseMap<int, IntType>>;
283
284 MapVectorType MV;
285 std::pair<typename MapVectorType::iterator, bool> R;
286
287 R = MV.insert(std::make_pair(1, 2));
288 ASSERT_EQ(R.first, MV.begin());
289 EXPECT_EQ(R.first->first, 1);
290 EXPECT_EQ(R.first->second, 2);
291 EXPECT_TRUE(R.second);
292
293 const std::pair<int, int> Elem(1, 3);
294 R = MV.insert(Elem);
295 ASSERT_EQ(R.first, MV.begin());
296 EXPECT_EQ(R.first->first, 1);
297 EXPECT_EQ(R.first->second, 2);
298 EXPECT_FALSE(R.second);
299
300 int& value = MV[4];
301 EXPECT_EQ(value, 0);
302 value = 5;
303
304 EXPECT_EQ(MV.size(), 2u);
305 EXPECT_EQ(MV[1], 2);
306 EXPECT_EQ(MV[4], 5);
307 }
308
TEST(SmallMapVectorSmallTest,insert_pop)309 TEST(SmallMapVectorSmallTest, insert_pop) {
310 SmallMapVector<int, int, 32> MV;
311 std::pair<SmallMapVector<int, int, 32>::iterator, bool> R;
312
313 R = MV.insert(std::make_pair(1, 2));
314 ASSERT_EQ(R.first, MV.begin());
315 EXPECT_EQ(R.first->first, 1);
316 EXPECT_EQ(R.first->second, 2);
317 EXPECT_TRUE(R.second);
318
319 R = MV.insert(std::make_pair(1, 3));
320 ASSERT_EQ(R.first, MV.begin());
321 EXPECT_EQ(R.first->first, 1);
322 EXPECT_EQ(R.first->second, 2);
323 EXPECT_FALSE(R.second);
324
325 R = MV.insert(std::make_pair(4, 5));
326 ASSERT_NE(R.first, MV.end());
327 EXPECT_EQ(R.first->first, 4);
328 EXPECT_EQ(R.first->second, 5);
329 EXPECT_TRUE(R.second);
330
331 EXPECT_EQ(MV.size(), 2u);
332 EXPECT_EQ(MV[1], 2);
333 EXPECT_EQ(MV[4], 5);
334
335 MV.pop_back();
336 EXPECT_EQ(MV.size(), 1u);
337 EXPECT_EQ(MV[1], 2);
338
339 R = MV.insert(std::make_pair(4, 7));
340 ASSERT_NE(R.first, MV.end());
341 EXPECT_EQ(R.first->first, 4);
342 EXPECT_EQ(R.first->second, 7);
343 EXPECT_TRUE(R.second);
344
345 EXPECT_EQ(MV.size(), 2u);
346 EXPECT_EQ(MV[1], 2);
347 EXPECT_EQ(MV[4], 7);
348 }
349
TEST(SmallMapVectorSmallTest,erase)350 TEST(SmallMapVectorSmallTest, erase) {
351 SmallMapVector<int, int, 32> MV;
352
353 MV.insert(std::make_pair(1, 2));
354 MV.insert(std::make_pair(3, 4));
355 MV.insert(std::make_pair(5, 6));
356 ASSERT_EQ(MV.size(), 3u);
357
358 MV.erase(MV.find(1));
359 ASSERT_EQ(MV.size(), 2u);
360 ASSERT_EQ(MV.find(1), MV.end());
361 ASSERT_EQ(MV[3], 4);
362 ASSERT_EQ(MV[5], 6);
363
364 ASSERT_EQ(MV.erase(3), 1u);
365 ASSERT_EQ(MV.size(), 1u);
366 ASSERT_EQ(MV.find(3), MV.end());
367 ASSERT_EQ(MV[5], 6);
368
369 ASSERT_EQ(MV.erase(79), 0u);
370 ASSERT_EQ(MV.size(), 1u);
371 }
372
TEST(SmallMapVectorSmallTest,remove_if)373 TEST(SmallMapVectorSmallTest, remove_if) {
374 SmallMapVector<int, int, 32> MV;
375
376 MV.insert(std::make_pair(1, 11));
377 MV.insert(std::make_pair(2, 12));
378 MV.insert(std::make_pair(3, 13));
379 MV.insert(std::make_pair(4, 14));
380 MV.insert(std::make_pair(5, 15));
381 MV.insert(std::make_pair(6, 16));
382 ASSERT_EQ(MV.size(), 6u);
383
384 MV.remove_if([](const std::pair<int, int> &Val) { return Val.second % 2; });
385 ASSERT_EQ(MV.size(), 3u);
386 ASSERT_EQ(MV.find(1), MV.end());
387 ASSERT_EQ(MV.find(3), MV.end());
388 ASSERT_EQ(MV.find(5), MV.end());
389 ASSERT_EQ(MV[2], 12);
390 ASSERT_EQ(MV[4], 14);
391 ASSERT_EQ(MV[6], 16);
392 }
393
TEST(SmallMapVectorSmallTest,iteration_test)394 TEST(SmallMapVectorSmallTest, iteration_test) {
395 SmallMapVector<int, int, 32> MV;
396
397 MV.insert(std::make_pair(1, 11));
398 MV.insert(std::make_pair(2, 12));
399 MV.insert(std::make_pair(3, 13));
400 MV.insert(std::make_pair(4, 14));
401 MV.insert(std::make_pair(5, 15));
402 MV.insert(std::make_pair(6, 16));
403 ASSERT_EQ(MV.size(), 6u);
404
405 int count = 1;
406 for (auto P : make_range(MV.begin(), MV.end())) {
407 ASSERT_EQ(P.first, count);
408 count++;
409 }
410
411 count = 6;
412 for (auto P : make_range(MV.rbegin(), MV.rend())) {
413 ASSERT_EQ(P.first, count);
414 count--;
415 }
416 }
417
TEST(SmallMapVectorSmallTest,NonCopyable)418 TEST(SmallMapVectorSmallTest, NonCopyable) {
419 SmallMapVector<int, std::unique_ptr<int>, 8> MV;
420 MV.insert(std::make_pair(1, std::make_unique<int>(1)));
421 MV.insert(std::make_pair(2, std::make_unique<int>(2)));
422
423 ASSERT_EQ(MV.count(1), 1u);
424 ASSERT_EQ(*MV.find(2)->second, 2);
425 }
426
TEST(SmallMapVectorLargeTest,insert_pop)427 TEST(SmallMapVectorLargeTest, insert_pop) {
428 SmallMapVector<int, int, 1> MV;
429 std::pair<SmallMapVector<int, int, 1>::iterator, bool> R;
430
431 R = MV.insert(std::make_pair(1, 2));
432 ASSERT_EQ(R.first, MV.begin());
433 EXPECT_EQ(R.first->first, 1);
434 EXPECT_EQ(R.first->second, 2);
435 EXPECT_TRUE(R.second);
436
437 R = MV.insert(std::make_pair(1, 3));
438 ASSERT_EQ(R.first, MV.begin());
439 EXPECT_EQ(R.first->first, 1);
440 EXPECT_EQ(R.first->second, 2);
441 EXPECT_FALSE(R.second);
442
443 R = MV.insert(std::make_pair(4, 5));
444 ASSERT_NE(R.first, MV.end());
445 EXPECT_EQ(R.first->first, 4);
446 EXPECT_EQ(R.first->second, 5);
447 EXPECT_TRUE(R.second);
448
449 EXPECT_EQ(MV.size(), 2u);
450 EXPECT_EQ(MV[1], 2);
451 EXPECT_EQ(MV[4], 5);
452
453 MV.pop_back();
454 EXPECT_EQ(MV.size(), 1u);
455 EXPECT_EQ(MV[1], 2);
456
457 R = MV.insert(std::make_pair(4, 7));
458 ASSERT_NE(R.first, MV.end());
459 EXPECT_EQ(R.first->first, 4);
460 EXPECT_EQ(R.first->second, 7);
461 EXPECT_TRUE(R.second);
462
463 EXPECT_EQ(MV.size(), 2u);
464 EXPECT_EQ(MV[1], 2);
465 EXPECT_EQ(MV[4], 7);
466 }
467
TEST(SmallMapVectorLargeTest,erase)468 TEST(SmallMapVectorLargeTest, erase) {
469 SmallMapVector<int, int, 1> MV;
470
471 MV.insert(std::make_pair(1, 2));
472 MV.insert(std::make_pair(3, 4));
473 MV.insert(std::make_pair(5, 6));
474 ASSERT_EQ(MV.size(), 3u);
475
476 MV.erase(MV.find(1));
477 ASSERT_EQ(MV.size(), 2u);
478 ASSERT_EQ(MV.find(1), MV.end());
479 ASSERT_EQ(MV[3], 4);
480 ASSERT_EQ(MV[5], 6);
481
482 ASSERT_EQ(MV.erase(3), 1u);
483 ASSERT_EQ(MV.size(), 1u);
484 ASSERT_EQ(MV.find(3), MV.end());
485 ASSERT_EQ(MV[5], 6);
486
487 ASSERT_EQ(MV.erase(79), 0u);
488 ASSERT_EQ(MV.size(), 1u);
489 }
490
TEST(SmallMapVectorLargeTest,remove_if)491 TEST(SmallMapVectorLargeTest, remove_if) {
492 SmallMapVector<int, int, 1> MV;
493
494 MV.insert(std::make_pair(1, 11));
495 MV.insert(std::make_pair(2, 12));
496 MV.insert(std::make_pair(3, 13));
497 MV.insert(std::make_pair(4, 14));
498 MV.insert(std::make_pair(5, 15));
499 MV.insert(std::make_pair(6, 16));
500 ASSERT_EQ(MV.size(), 6u);
501
502 MV.remove_if([](const std::pair<int, int> &Val) { return Val.second % 2; });
503 ASSERT_EQ(MV.size(), 3u);
504 ASSERT_EQ(MV.find(1), MV.end());
505 ASSERT_EQ(MV.find(3), MV.end());
506 ASSERT_EQ(MV.find(5), MV.end());
507 ASSERT_EQ(MV[2], 12);
508 ASSERT_EQ(MV[4], 14);
509 ASSERT_EQ(MV[6], 16);
510 }
511
TEST(SmallMapVectorLargeTest,iteration_test)512 TEST(SmallMapVectorLargeTest, iteration_test) {
513 SmallMapVector<int, int, 1> MV;
514
515 MV.insert(std::make_pair(1, 11));
516 MV.insert(std::make_pair(2, 12));
517 MV.insert(std::make_pair(3, 13));
518 MV.insert(std::make_pair(4, 14));
519 MV.insert(std::make_pair(5, 15));
520 MV.insert(std::make_pair(6, 16));
521 ASSERT_EQ(MV.size(), 6u);
522
523 int count = 1;
524 for (auto P : make_range(MV.begin(), MV.end())) {
525 ASSERT_EQ(P.first, count);
526 count++;
527 }
528
529 count = 6;
530 for (auto P : make_range(MV.rbegin(), MV.rend())) {
531 ASSERT_EQ(P.first, count);
532 count--;
533 }
534 }
535 } // namespace
536