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 <utility>
13
14 using namespace llvm;
15
TEST(MapVectorTest,swap)16 TEST(MapVectorTest, swap) {
17 MapVector<int, int> MV1, MV2;
18 std::pair<MapVector<int, int>::iterator, bool> R;
19
20 R = MV1.insert(std::make_pair(1, 2));
21 ASSERT_EQ(R.first, MV1.begin());
22 EXPECT_EQ(R.first->first, 1);
23 EXPECT_EQ(R.first->second, 2);
24 EXPECT_TRUE(R.second);
25
26 EXPECT_FALSE(MV1.empty());
27 EXPECT_TRUE(MV2.empty());
28 MV2.swap(MV1);
29 EXPECT_TRUE(MV1.empty());
30 EXPECT_FALSE(MV2.empty());
31
32 auto I = MV1.find(1);
33 ASSERT_EQ(MV1.end(), I);
34
35 I = MV2.find(1);
36 ASSERT_EQ(I, MV2.begin());
37 EXPECT_EQ(I->first, 1);
38 EXPECT_EQ(I->second, 2);
39 }
40
TEST(MapVectorTest,insert_pop)41 TEST(MapVectorTest, insert_pop) {
42 MapVector<int, int> MV;
43 std::pair<MapVector<int, int>::iterator, bool> R;
44
45 R = MV.insert(std::make_pair(1, 2));
46 ASSERT_EQ(R.first, MV.begin());
47 EXPECT_EQ(R.first->first, 1);
48 EXPECT_EQ(R.first->second, 2);
49 EXPECT_TRUE(R.second);
50
51 R = MV.insert(std::make_pair(1, 3));
52 ASSERT_EQ(R.first, MV.begin());
53 EXPECT_EQ(R.first->first, 1);
54 EXPECT_EQ(R.first->second, 2);
55 EXPECT_FALSE(R.second);
56
57 R = MV.insert(std::make_pair(4, 5));
58 ASSERT_NE(R.first, MV.end());
59 EXPECT_EQ(R.first->first, 4);
60 EXPECT_EQ(R.first->second, 5);
61 EXPECT_TRUE(R.second);
62
63 EXPECT_EQ(MV.size(), 2u);
64 EXPECT_EQ(MV[1], 2);
65 EXPECT_EQ(MV[4], 5);
66
67 MV.pop_back();
68 EXPECT_EQ(MV.size(), 1u);
69 EXPECT_EQ(MV[1], 2);
70
71 R = MV.insert(std::make_pair(4, 7));
72 ASSERT_NE(R.first, MV.end());
73 EXPECT_EQ(R.first->first, 4);
74 EXPECT_EQ(R.first->second, 7);
75 EXPECT_TRUE(R.second);
76
77 EXPECT_EQ(MV.size(), 2u);
78 EXPECT_EQ(MV[1], 2);
79 EXPECT_EQ(MV[4], 7);
80 }
81
TEST(MapVectorTest,erase)82 TEST(MapVectorTest, erase) {
83 MapVector<int, int> MV;
84
85 MV.insert(std::make_pair(1, 2));
86 MV.insert(std::make_pair(3, 4));
87 MV.insert(std::make_pair(5, 6));
88 ASSERT_EQ(MV.size(), 3u);
89
90 MV.erase(MV.find(1));
91 ASSERT_EQ(MV.size(), 2u);
92 ASSERT_EQ(MV.find(1), MV.end());
93 ASSERT_EQ(MV[3], 4);
94 ASSERT_EQ(MV[5], 6);
95
96 ASSERT_EQ(MV.erase(3), 1u);
97 ASSERT_EQ(MV.size(), 1u);
98 ASSERT_EQ(MV.find(3), MV.end());
99 ASSERT_EQ(MV[5], 6);
100
101 ASSERT_EQ(MV.erase(79), 0u);
102 ASSERT_EQ(MV.size(), 1u);
103 }
104
TEST(MapVectorTest,remove_if)105 TEST(MapVectorTest, remove_if) {
106 MapVector<int, int> MV;
107
108 MV.insert(std::make_pair(1, 11));
109 MV.insert(std::make_pair(2, 12));
110 MV.insert(std::make_pair(3, 13));
111 MV.insert(std::make_pair(4, 14));
112 MV.insert(std::make_pair(5, 15));
113 MV.insert(std::make_pair(6, 16));
114 ASSERT_EQ(MV.size(), 6u);
115
116 MV.remove_if([](const std::pair<int, int> &Val) { return Val.second % 2; });
117 ASSERT_EQ(MV.size(), 3u);
118 ASSERT_EQ(MV.find(1), MV.end());
119 ASSERT_EQ(MV.find(3), MV.end());
120 ASSERT_EQ(MV.find(5), MV.end());
121 ASSERT_EQ(MV[2], 12);
122 ASSERT_EQ(MV[4], 14);
123 ASSERT_EQ(MV[6], 16);
124 }
125
TEST(MapVectorTest,iteration_test)126 TEST(MapVectorTest, iteration_test) {
127 MapVector<int, int> MV;
128
129 MV.insert(std::make_pair(1, 11));
130 MV.insert(std::make_pair(2, 12));
131 MV.insert(std::make_pair(3, 13));
132 MV.insert(std::make_pair(4, 14));
133 MV.insert(std::make_pair(5, 15));
134 MV.insert(std::make_pair(6, 16));
135 ASSERT_EQ(MV.size(), 6u);
136
137 int count = 1;
138 for (auto P : make_range(MV.begin(), MV.end())) {
139 ASSERT_EQ(P.first, count);
140 count++;
141 }
142
143 count = 6;
144 for (auto P : make_range(MV.rbegin(), MV.rend())) {
145 ASSERT_EQ(P.first, count);
146 count--;
147 }
148 }
149
TEST(MapVectorTest,NonCopyable)150 TEST(MapVectorTest, NonCopyable) {
151 MapVector<int, std::unique_ptr<int>> MV;
152 MV.insert(std::make_pair(1, std::make_unique<int>(1)));
153 MV.insert(std::make_pair(2, std::make_unique<int>(2)));
154
155 ASSERT_EQ(MV.count(1), 1u);
156 ASSERT_EQ(*MV.find(2)->second, 2);
157 }
158
159 template <class IntType> struct MapVectorMappedTypeTest : ::testing::Test {
160 using int_type = IntType;
161 };
162
163 using MapIntTypes = ::testing::Types<int, long, long long, unsigned,
164 unsigned long, unsigned long long>;
165 TYPED_TEST_SUITE(MapVectorMappedTypeTest, MapIntTypes, );
166
TYPED_TEST(MapVectorMappedTypeTest,DifferentDenseMap)167 TYPED_TEST(MapVectorMappedTypeTest, DifferentDenseMap) {
168 // Test that using a map with a mapped type other than 'unsigned' compiles
169 // and works.
170 using IntType = typename TestFixture::int_type;
171 using MapVectorType = MapVector<int, int, DenseMap<int, IntType>>;
172
173 MapVectorType MV;
174 std::pair<typename MapVectorType::iterator, bool> R;
175
176 R = MV.insert(std::make_pair(1, 2));
177 ASSERT_EQ(R.first, MV.begin());
178 EXPECT_EQ(R.first->first, 1);
179 EXPECT_EQ(R.first->second, 2);
180 EXPECT_TRUE(R.second);
181
182 const std::pair<int, int> Elem(1, 3);
183 R = MV.insert(Elem);
184 ASSERT_EQ(R.first, MV.begin());
185 EXPECT_EQ(R.first->first, 1);
186 EXPECT_EQ(R.first->second, 2);
187 EXPECT_FALSE(R.second);
188
189 int& value = MV[4];
190 EXPECT_EQ(value, 0);
191 value = 5;
192
193 EXPECT_EQ(MV.size(), 2u);
194 EXPECT_EQ(MV[1], 2);
195 EXPECT_EQ(MV[4], 5);
196 }
197
TEST(SmallMapVectorSmallTest,insert_pop)198 TEST(SmallMapVectorSmallTest, insert_pop) {
199 SmallMapVector<int, int, 32> MV;
200 std::pair<SmallMapVector<int, int, 32>::iterator, bool> R;
201
202 R = MV.insert(std::make_pair(1, 2));
203 ASSERT_EQ(R.first, MV.begin());
204 EXPECT_EQ(R.first->first, 1);
205 EXPECT_EQ(R.first->second, 2);
206 EXPECT_TRUE(R.second);
207
208 R = MV.insert(std::make_pair(1, 3));
209 ASSERT_EQ(R.first, MV.begin());
210 EXPECT_EQ(R.first->first, 1);
211 EXPECT_EQ(R.first->second, 2);
212 EXPECT_FALSE(R.second);
213
214 R = MV.insert(std::make_pair(4, 5));
215 ASSERT_NE(R.first, MV.end());
216 EXPECT_EQ(R.first->first, 4);
217 EXPECT_EQ(R.first->second, 5);
218 EXPECT_TRUE(R.second);
219
220 EXPECT_EQ(MV.size(), 2u);
221 EXPECT_EQ(MV[1], 2);
222 EXPECT_EQ(MV[4], 5);
223
224 MV.pop_back();
225 EXPECT_EQ(MV.size(), 1u);
226 EXPECT_EQ(MV[1], 2);
227
228 R = MV.insert(std::make_pair(4, 7));
229 ASSERT_NE(R.first, MV.end());
230 EXPECT_EQ(R.first->first, 4);
231 EXPECT_EQ(R.first->second, 7);
232 EXPECT_TRUE(R.second);
233
234 EXPECT_EQ(MV.size(), 2u);
235 EXPECT_EQ(MV[1], 2);
236 EXPECT_EQ(MV[4], 7);
237 }
238
TEST(SmallMapVectorSmallTest,erase)239 TEST(SmallMapVectorSmallTest, erase) {
240 SmallMapVector<int, int, 32> MV;
241
242 MV.insert(std::make_pair(1, 2));
243 MV.insert(std::make_pair(3, 4));
244 MV.insert(std::make_pair(5, 6));
245 ASSERT_EQ(MV.size(), 3u);
246
247 MV.erase(MV.find(1));
248 ASSERT_EQ(MV.size(), 2u);
249 ASSERT_EQ(MV.find(1), MV.end());
250 ASSERT_EQ(MV[3], 4);
251 ASSERT_EQ(MV[5], 6);
252
253 ASSERT_EQ(MV.erase(3), 1u);
254 ASSERT_EQ(MV.size(), 1u);
255 ASSERT_EQ(MV.find(3), MV.end());
256 ASSERT_EQ(MV[5], 6);
257
258 ASSERT_EQ(MV.erase(79), 0u);
259 ASSERT_EQ(MV.size(), 1u);
260 }
261
TEST(SmallMapVectorSmallTest,remove_if)262 TEST(SmallMapVectorSmallTest, remove_if) {
263 SmallMapVector<int, int, 32> MV;
264
265 MV.insert(std::make_pair(1, 11));
266 MV.insert(std::make_pair(2, 12));
267 MV.insert(std::make_pair(3, 13));
268 MV.insert(std::make_pair(4, 14));
269 MV.insert(std::make_pair(5, 15));
270 MV.insert(std::make_pair(6, 16));
271 ASSERT_EQ(MV.size(), 6u);
272
273 MV.remove_if([](const std::pair<int, int> &Val) { return Val.second % 2; });
274 ASSERT_EQ(MV.size(), 3u);
275 ASSERT_EQ(MV.find(1), MV.end());
276 ASSERT_EQ(MV.find(3), MV.end());
277 ASSERT_EQ(MV.find(5), MV.end());
278 ASSERT_EQ(MV[2], 12);
279 ASSERT_EQ(MV[4], 14);
280 ASSERT_EQ(MV[6], 16);
281 }
282
TEST(SmallMapVectorSmallTest,iteration_test)283 TEST(SmallMapVectorSmallTest, iteration_test) {
284 SmallMapVector<int, int, 32> MV;
285
286 MV.insert(std::make_pair(1, 11));
287 MV.insert(std::make_pair(2, 12));
288 MV.insert(std::make_pair(3, 13));
289 MV.insert(std::make_pair(4, 14));
290 MV.insert(std::make_pair(5, 15));
291 MV.insert(std::make_pair(6, 16));
292 ASSERT_EQ(MV.size(), 6u);
293
294 int count = 1;
295 for (auto P : make_range(MV.begin(), MV.end())) {
296 ASSERT_EQ(P.first, count);
297 count++;
298 }
299
300 count = 6;
301 for (auto P : make_range(MV.rbegin(), MV.rend())) {
302 ASSERT_EQ(P.first, count);
303 count--;
304 }
305 }
306
TEST(SmallMapVectorSmallTest,NonCopyable)307 TEST(SmallMapVectorSmallTest, NonCopyable) {
308 SmallMapVector<int, std::unique_ptr<int>, 8> MV;
309 MV.insert(std::make_pair(1, std::make_unique<int>(1)));
310 MV.insert(std::make_pair(2, std::make_unique<int>(2)));
311
312 ASSERT_EQ(MV.count(1), 1u);
313 ASSERT_EQ(*MV.find(2)->second, 2);
314 }
315
TEST(SmallMapVectorLargeTest,insert_pop)316 TEST(SmallMapVectorLargeTest, insert_pop) {
317 SmallMapVector<int, int, 1> MV;
318 std::pair<SmallMapVector<int, int, 1>::iterator, bool> R;
319
320 R = MV.insert(std::make_pair(1, 2));
321 ASSERT_EQ(R.first, MV.begin());
322 EXPECT_EQ(R.first->first, 1);
323 EXPECT_EQ(R.first->second, 2);
324 EXPECT_TRUE(R.second);
325
326 R = MV.insert(std::make_pair(1, 3));
327 ASSERT_EQ(R.first, MV.begin());
328 EXPECT_EQ(R.first->first, 1);
329 EXPECT_EQ(R.first->second, 2);
330 EXPECT_FALSE(R.second);
331
332 R = MV.insert(std::make_pair(4, 5));
333 ASSERT_NE(R.first, MV.end());
334 EXPECT_EQ(R.first->first, 4);
335 EXPECT_EQ(R.first->second, 5);
336 EXPECT_TRUE(R.second);
337
338 EXPECT_EQ(MV.size(), 2u);
339 EXPECT_EQ(MV[1], 2);
340 EXPECT_EQ(MV[4], 5);
341
342 MV.pop_back();
343 EXPECT_EQ(MV.size(), 1u);
344 EXPECT_EQ(MV[1], 2);
345
346 R = MV.insert(std::make_pair(4, 7));
347 ASSERT_NE(R.first, MV.end());
348 EXPECT_EQ(R.first->first, 4);
349 EXPECT_EQ(R.first->second, 7);
350 EXPECT_TRUE(R.second);
351
352 EXPECT_EQ(MV.size(), 2u);
353 EXPECT_EQ(MV[1], 2);
354 EXPECT_EQ(MV[4], 7);
355 }
356
TEST(SmallMapVectorLargeTest,erase)357 TEST(SmallMapVectorLargeTest, erase) {
358 SmallMapVector<int, int, 1> MV;
359
360 MV.insert(std::make_pair(1, 2));
361 MV.insert(std::make_pair(3, 4));
362 MV.insert(std::make_pair(5, 6));
363 ASSERT_EQ(MV.size(), 3u);
364
365 MV.erase(MV.find(1));
366 ASSERT_EQ(MV.size(), 2u);
367 ASSERT_EQ(MV.find(1), MV.end());
368 ASSERT_EQ(MV[3], 4);
369 ASSERT_EQ(MV[5], 6);
370
371 ASSERT_EQ(MV.erase(3), 1u);
372 ASSERT_EQ(MV.size(), 1u);
373 ASSERT_EQ(MV.find(3), MV.end());
374 ASSERT_EQ(MV[5], 6);
375
376 ASSERT_EQ(MV.erase(79), 0u);
377 ASSERT_EQ(MV.size(), 1u);
378 }
379
TEST(SmallMapVectorLargeTest,remove_if)380 TEST(SmallMapVectorLargeTest, remove_if) {
381 SmallMapVector<int, int, 1> MV;
382
383 MV.insert(std::make_pair(1, 11));
384 MV.insert(std::make_pair(2, 12));
385 MV.insert(std::make_pair(3, 13));
386 MV.insert(std::make_pair(4, 14));
387 MV.insert(std::make_pair(5, 15));
388 MV.insert(std::make_pair(6, 16));
389 ASSERT_EQ(MV.size(), 6u);
390
391 MV.remove_if([](const std::pair<int, int> &Val) { return Val.second % 2; });
392 ASSERT_EQ(MV.size(), 3u);
393 ASSERT_EQ(MV.find(1), MV.end());
394 ASSERT_EQ(MV.find(3), MV.end());
395 ASSERT_EQ(MV.find(5), MV.end());
396 ASSERT_EQ(MV[2], 12);
397 ASSERT_EQ(MV[4], 14);
398 ASSERT_EQ(MV[6], 16);
399 }
400
TEST(SmallMapVectorLargeTest,iteration_test)401 TEST(SmallMapVectorLargeTest, iteration_test) {
402 SmallMapVector<int, int, 1> MV;
403
404 MV.insert(std::make_pair(1, 11));
405 MV.insert(std::make_pair(2, 12));
406 MV.insert(std::make_pair(3, 13));
407 MV.insert(std::make_pair(4, 14));
408 MV.insert(std::make_pair(5, 15));
409 MV.insert(std::make_pair(6, 16));
410 ASSERT_EQ(MV.size(), 6u);
411
412 int count = 1;
413 for (auto P : make_range(MV.begin(), MV.end())) {
414 ASSERT_EQ(P.first, count);
415 count++;
416 }
417
418 count = 6;
419 for (auto P : make_range(MV.rbegin(), MV.rend())) {
420 ASSERT_EQ(P.first, count);
421 count--;
422 }
423 }
424