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