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
15using namespace llvm;
16
17namespace {
18struct CountCopyAndMove {
19 CountCopyAndMove() = default;
20 CountCopyAndMove(const CountCopyAndMove &) { copy = 1; }
21 CountCopyAndMove(CountCopyAndMove &&) { move = 1; }
22 void operator=(const CountCopyAndMove &) { ++copy; }
23 void operator=(CountCopyAndMove &&) { ++move; }
24 int copy = 0;
25 int move = 0;
26};
27
28struct A : CountCopyAndMove {
29 A(int v) : v(v) {}
30 int v;
31};
32} // namespace
33
34namespace llvm {
35template <> struct DenseMapInfo<A> {
36 static inline A getEmptyKey() { return 0x7fffffff; }
37 static inline A getTombstoneKey() { return -0x7fffffff - 1; }
38 static unsigned getHashValue(const A &Val) { return (unsigned)(Val.v * 37U); }
39 static bool isEqual(const A &LHS, const A &RHS) { return LHS.v == RHS.v; }
40};
41} // namespace llvm
42
43namespace {
44TEST(MapVectorTest, swap) {
45 MapVector<int, int> MV1, MV2;
46 std::pair<MapVector<int, int>::iterator, bool> R;
47
48 R = MV1.insert(KV: std::make_pair(x: 1, y: 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(RHS&: MV1);
57 EXPECT_TRUE(MV1.empty());
58 EXPECT_FALSE(MV2.empty());
59
60 auto I = MV1.find(Key: 1);
61 ASSERT_EQ(MV1.end(), I);
62
63 I = MV2.find(Key: 1);
64 ASSERT_EQ(I, MV2.begin());
65 EXPECT_EQ(I->first, 1);
66 EXPECT_EQ(I->second, 2);
67}
68
69TEST(MapVectorTest, insert_pop) {
70 MapVector<int, int> MV;
71 std::pair<MapVector<int, int>::iterator, bool> R;
72
73 R = MV.insert(KV: std::make_pair(x: 1, y: 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(KV: std::make_pair(x: 1, y: 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(KV: std::make_pair(x: 4, y: 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(KV: std::make_pair(x: 4, y: 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
110TEST(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(Key: zero, Args&: zero, Args: 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(Key: zero, Args&: zero, Args: 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(Key: 2, Args: std::move(two), Args: std::make_unique<int>(args: 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(Key: std::move(two), Args: 3, Args: 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
154TEST(MapVectorTest, insert_or_assign) {
155 MapVector<A, A> mv;
156
157 A zero(0);
158 auto try0 = mv.insert_or_assign(Key: zero, Val&: 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(Key: zero, Val&: 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(Key: 2, Args: 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(Key: std::move(two), Val: 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
191TEST(MapVectorTest, erase) {
192 MapVector<int, int> MV;
193
194 MV.insert(KV: std::make_pair(x: 1, y: 2));
195 MV.insert(KV: std::make_pair(x: 3, y: 4));
196 MV.insert(KV: std::make_pair(x: 5, y: 6));
197 ASSERT_EQ(MV.size(), 3u);
198
199 ASSERT_TRUE(MV.contains(1));
200 MV.erase(Iterator: MV.find(Key: 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
216TEST(MapVectorTest, remove_if) {
217 MapVector<int, int> MV;
218
219 MV.insert(KV: std::make_pair(x: 1, y: 11));
220 MV.insert(KV: std::make_pair(x: 2, y: 12));
221 MV.insert(KV: std::make_pair(x: 3, y: 13));
222 MV.insert(KV: std::make_pair(x: 4, y: 14));
223 MV.insert(KV: std::make_pair(x: 5, y: 15));
224 MV.insert(KV: std::make_pair(x: 6, y: 16));
225 ASSERT_EQ(MV.size(), 6u);
226
227 MV.remove_if(Pred: [](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
237TEST(MapVectorTest, iteration_test) {
238 MapVector<int, int> MV;
239
240 MV.insert(KV: std::make_pair(x: 1, y: 11));
241 MV.insert(KV: std::make_pair(x: 2, y: 12));
242 MV.insert(KV: std::make_pair(x: 3, y: 13));
243 MV.insert(KV: std::make_pair(x: 4, y: 14));
244 MV.insert(KV: std::make_pair(x: 5, y: 15));
245 MV.insert(KV: std::make_pair(x: 6, y: 16));
246 ASSERT_EQ(MV.size(), 6u);
247
248 int count = 1;
249 for (auto P : make_range(x: MV.begin(), y: MV.end())) {
250 ASSERT_EQ(P.first, count);
251 count++;
252 }
253
254 count = 6;
255 for (auto P : make_range(x: MV.rbegin(), y: MV.rend())) {
256 ASSERT_EQ(P.first, count);
257 count--;
258 }
259}
260
261TEST(MapVectorTest, NonCopyable) {
262 MapVector<int, std::unique_ptr<int>> MV;
263 MV.insert(KV: std::make_pair(x: 1, y: std::make_unique<int>(args: 1)));
264 MV.insert(KV: std::make_pair(x: 2, y: std::make_unique<int>(args: 2)));
265
266 ASSERT_EQ(MV.count(1), 1u);
267 ASSERT_EQ(*MV.find(2)->second, 2);
268}
269
270template <class IntType> struct MapVectorMappedTypeTest : ::testing::Test {
271 using int_type = IntType;
272};
273
274using MapIntTypes = ::testing::Types<int, long, long long, unsigned,
275 unsigned long, unsigned long long>;
276TYPED_TEST_SUITE(MapVectorMappedTypeTest, MapIntTypes, );
277
278TYPED_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(x: 1, y: 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
309TEST(SmallMapVectorSmallTest, insert_pop) {
310 SmallMapVector<int, int, 32> MV;
311 std::pair<SmallMapVector<int, int, 32>::iterator, bool> R;
312
313 R = MV.insert(KV: std::make_pair(x: 1, y: 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(KV: std::make_pair(x: 1, y: 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(KV: std::make_pair(x: 4, y: 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(KV: std::make_pair(x: 4, y: 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
350TEST(SmallMapVectorSmallTest, erase) {
351 SmallMapVector<int, int, 32> MV;
352
353 MV.insert(KV: std::make_pair(x: 1, y: 2));
354 MV.insert(KV: std::make_pair(x: 3, y: 4));
355 MV.insert(KV: std::make_pair(x: 5, y: 6));
356 ASSERT_EQ(MV.size(), 3u);
357
358 MV.erase(Iterator: MV.find(Key: 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
373TEST(SmallMapVectorSmallTest, remove_if) {
374 SmallMapVector<int, int, 32> MV;
375
376 MV.insert(KV: std::make_pair(x: 1, y: 11));
377 MV.insert(KV: std::make_pair(x: 2, y: 12));
378 MV.insert(KV: std::make_pair(x: 3, y: 13));
379 MV.insert(KV: std::make_pair(x: 4, y: 14));
380 MV.insert(KV: std::make_pair(x: 5, y: 15));
381 MV.insert(KV: std::make_pair(x: 6, y: 16));
382 ASSERT_EQ(MV.size(), 6u);
383
384 MV.remove_if(Pred: [](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
394TEST(SmallMapVectorSmallTest, iteration_test) {
395 SmallMapVector<int, int, 32> MV;
396
397 MV.insert(KV: std::make_pair(x: 1, y: 11));
398 MV.insert(KV: std::make_pair(x: 2, y: 12));
399 MV.insert(KV: std::make_pair(x: 3, y: 13));
400 MV.insert(KV: std::make_pair(x: 4, y: 14));
401 MV.insert(KV: std::make_pair(x: 5, y: 15));
402 MV.insert(KV: std::make_pair(x: 6, y: 16));
403 ASSERT_EQ(MV.size(), 6u);
404
405 int count = 1;
406 for (auto P : make_range(x: MV.begin(), y: MV.end())) {
407 ASSERT_EQ(P.first, count);
408 count++;
409 }
410
411 count = 6;
412 for (auto P : make_range(x: MV.rbegin(), y: MV.rend())) {
413 ASSERT_EQ(P.first, count);
414 count--;
415 }
416}
417
418TEST(SmallMapVectorSmallTest, NonCopyable) {
419 SmallMapVector<int, std::unique_ptr<int>, 8> MV;
420 MV.insert(KV: std::make_pair(x: 1, y: std::make_unique<int>(args: 1)));
421 MV.insert(KV: std::make_pair(x: 2, y: std::make_unique<int>(args: 2)));
422
423 ASSERT_EQ(MV.count(1), 1u);
424 ASSERT_EQ(*MV.find(2)->second, 2);
425}
426
427TEST(SmallMapVectorLargeTest, insert_pop) {
428 SmallMapVector<int, int, 1> MV;
429 std::pair<SmallMapVector<int, int, 1>::iterator, bool> R;
430
431 R = MV.insert(KV: std::make_pair(x: 1, y: 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(KV: std::make_pair(x: 1, y: 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(KV: std::make_pair(x: 4, y: 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(KV: std::make_pair(x: 4, y: 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
468TEST(SmallMapVectorLargeTest, erase) {
469 SmallMapVector<int, int, 1> MV;
470
471 MV.insert(KV: std::make_pair(x: 1, y: 2));
472 MV.insert(KV: std::make_pair(x: 3, y: 4));
473 MV.insert(KV: std::make_pair(x: 5, y: 6));
474 ASSERT_EQ(MV.size(), 3u);
475
476 MV.erase(Iterator: MV.find(Key: 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
491TEST(SmallMapVectorLargeTest, remove_if) {
492 SmallMapVector<int, int, 1> MV;
493
494 MV.insert(KV: std::make_pair(x: 1, y: 11));
495 MV.insert(KV: std::make_pair(x: 2, y: 12));
496 MV.insert(KV: std::make_pair(x: 3, y: 13));
497 MV.insert(KV: std::make_pair(x: 4, y: 14));
498 MV.insert(KV: std::make_pair(x: 5, y: 15));
499 MV.insert(KV: std::make_pair(x: 6, y: 16));
500 ASSERT_EQ(MV.size(), 6u);
501
502 MV.remove_if(Pred: [](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
512TEST(SmallMapVectorLargeTest, iteration_test) {
513 SmallMapVector<int, int, 1> MV;
514
515 MV.insert(KV: std::make_pair(x: 1, y: 11));
516 MV.insert(KV: std::make_pair(x: 2, y: 12));
517 MV.insert(KV: std::make_pair(x: 3, y: 13));
518 MV.insert(KV: std::make_pair(x: 4, y: 14));
519 MV.insert(KV: std::make_pair(x: 5, y: 15));
520 MV.insert(KV: std::make_pair(x: 6, y: 16));
521 ASSERT_EQ(MV.size(), 6u);
522
523 int count = 1;
524 for (auto P : make_range(x: MV.begin(), y: MV.end())) {
525 ASSERT_EQ(P.first, count);
526 count++;
527 }
528
529 count = 6;
530 for (auto P : make_range(x: MV.rbegin(), y: MV.rend())) {
531 ASSERT_EQ(P.first, count);
532 count--;
533 }
534}
535} // namespace
536

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