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 "gtest/gtest.h"
11 #include "llvm/ADT/MapVector.h"
12 #include "llvm/ADT/iterator_range.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(SmallMapVectorSmallTest,insert_pop)151 TEST(SmallMapVectorSmallTest, insert_pop) {
152 SmallMapVector<int, int, 32> MV;
153 std::pair<SmallMapVector<int, int, 32>::iterator, bool> R;
154
155 R = MV.insert(std::make_pair(1, 2));
156 ASSERT_EQ(R.first, MV.begin());
157 EXPECT_EQ(R.first->first, 1);
158 EXPECT_EQ(R.first->second, 2);
159 EXPECT_TRUE(R.second);
160
161 R = MV.insert(std::make_pair(1, 3));
162 ASSERT_EQ(R.first, MV.begin());
163 EXPECT_EQ(R.first->first, 1);
164 EXPECT_EQ(R.first->second, 2);
165 EXPECT_FALSE(R.second);
166
167 R = MV.insert(std::make_pair(4, 5));
168 ASSERT_NE(R.first, MV.end());
169 EXPECT_EQ(R.first->first, 4);
170 EXPECT_EQ(R.first->second, 5);
171 EXPECT_TRUE(R.second);
172
173 EXPECT_EQ(MV.size(), 2u);
174 EXPECT_EQ(MV[1], 2);
175 EXPECT_EQ(MV[4], 5);
176
177 MV.pop_back();
178 EXPECT_EQ(MV.size(), 1u);
179 EXPECT_EQ(MV[1], 2);
180
181 R = MV.insert(std::make_pair(4, 7));
182 ASSERT_NE(R.first, MV.end());
183 EXPECT_EQ(R.first->first, 4);
184 EXPECT_EQ(R.first->second, 7);
185 EXPECT_TRUE(R.second);
186
187 EXPECT_EQ(MV.size(), 2u);
188 EXPECT_EQ(MV[1], 2);
189 EXPECT_EQ(MV[4], 7);
190 }
191
TEST(SmallMapVectorSmallTest,erase)192 TEST(SmallMapVectorSmallTest, erase) {
193 SmallMapVector<int, int, 32> MV;
194
195 MV.insert(std::make_pair(1, 2));
196 MV.insert(std::make_pair(3, 4));
197 MV.insert(std::make_pair(5, 6));
198 ASSERT_EQ(MV.size(), 3u);
199
200 MV.erase(MV.find(1));
201 ASSERT_EQ(MV.size(), 2u);
202 ASSERT_EQ(MV.find(1), MV.end());
203 ASSERT_EQ(MV[3], 4);
204 ASSERT_EQ(MV[5], 6);
205
206 ASSERT_EQ(MV.erase(3), 1u);
207 ASSERT_EQ(MV.size(), 1u);
208 ASSERT_EQ(MV.find(3), MV.end());
209 ASSERT_EQ(MV[5], 6);
210
211 ASSERT_EQ(MV.erase(79), 0u);
212 ASSERT_EQ(MV.size(), 1u);
213 }
214
TEST(SmallMapVectorSmallTest,remove_if)215 TEST(SmallMapVectorSmallTest, remove_if) {
216 SmallMapVector<int, int, 32> MV;
217
218 MV.insert(std::make_pair(1, 11));
219 MV.insert(std::make_pair(2, 12));
220 MV.insert(std::make_pair(3, 13));
221 MV.insert(std::make_pair(4, 14));
222 MV.insert(std::make_pair(5, 15));
223 MV.insert(std::make_pair(6, 16));
224 ASSERT_EQ(MV.size(), 6u);
225
226 MV.remove_if([](const std::pair<int, int> &Val) { return Val.second % 2; });
227 ASSERT_EQ(MV.size(), 3u);
228 ASSERT_EQ(MV.find(1), MV.end());
229 ASSERT_EQ(MV.find(3), MV.end());
230 ASSERT_EQ(MV.find(5), MV.end());
231 ASSERT_EQ(MV[2], 12);
232 ASSERT_EQ(MV[4], 14);
233 ASSERT_EQ(MV[6], 16);
234 }
235
TEST(SmallMapVectorSmallTest,iteration_test)236 TEST(SmallMapVectorSmallTest, iteration_test) {
237 SmallMapVector<int, int, 32> MV;
238
239 MV.insert(std::make_pair(1, 11));
240 MV.insert(std::make_pair(2, 12));
241 MV.insert(std::make_pair(3, 13));
242 MV.insert(std::make_pair(4, 14));
243 MV.insert(std::make_pair(5, 15));
244 MV.insert(std::make_pair(6, 16));
245 ASSERT_EQ(MV.size(), 6u);
246
247 int count = 1;
248 for (auto P : make_range(MV.begin(), MV.end())) {
249 ASSERT_EQ(P.first, count);
250 count++;
251 }
252
253 count = 6;
254 for (auto P : make_range(MV.rbegin(), MV.rend())) {
255 ASSERT_EQ(P.first, count);
256 count--;
257 }
258 }
259
TEST(SmallMapVectorLargeTest,insert_pop)260 TEST(SmallMapVectorLargeTest, insert_pop) {
261 SmallMapVector<int, int, 1> MV;
262 std::pair<SmallMapVector<int, int, 1>::iterator, bool> R;
263
264 R = MV.insert(std::make_pair(1, 2));
265 ASSERT_EQ(R.first, MV.begin());
266 EXPECT_EQ(R.first->first, 1);
267 EXPECT_EQ(R.first->second, 2);
268 EXPECT_TRUE(R.second);
269
270 R = MV.insert(std::make_pair(1, 3));
271 ASSERT_EQ(R.first, MV.begin());
272 EXPECT_EQ(R.first->first, 1);
273 EXPECT_EQ(R.first->second, 2);
274 EXPECT_FALSE(R.second);
275
276 R = MV.insert(std::make_pair(4, 5));
277 ASSERT_NE(R.first, MV.end());
278 EXPECT_EQ(R.first->first, 4);
279 EXPECT_EQ(R.first->second, 5);
280 EXPECT_TRUE(R.second);
281
282 EXPECT_EQ(MV.size(), 2u);
283 EXPECT_EQ(MV[1], 2);
284 EXPECT_EQ(MV[4], 5);
285
286 MV.pop_back();
287 EXPECT_EQ(MV.size(), 1u);
288 EXPECT_EQ(MV[1], 2);
289
290 R = MV.insert(std::make_pair(4, 7));
291 ASSERT_NE(R.first, MV.end());
292 EXPECT_EQ(R.first->first, 4);
293 EXPECT_EQ(R.first->second, 7);
294 EXPECT_TRUE(R.second);
295
296 EXPECT_EQ(MV.size(), 2u);
297 EXPECT_EQ(MV[1], 2);
298 EXPECT_EQ(MV[4], 7);
299 }
300
TEST(SmallMapVectorLargeTest,erase)301 TEST(SmallMapVectorLargeTest, erase) {
302 SmallMapVector<int, int, 1> MV;
303
304 MV.insert(std::make_pair(1, 2));
305 MV.insert(std::make_pair(3, 4));
306 MV.insert(std::make_pair(5, 6));
307 ASSERT_EQ(MV.size(), 3u);
308
309 MV.erase(MV.find(1));
310 ASSERT_EQ(MV.size(), 2u);
311 ASSERT_EQ(MV.find(1), MV.end());
312 ASSERT_EQ(MV[3], 4);
313 ASSERT_EQ(MV[5], 6);
314
315 ASSERT_EQ(MV.erase(3), 1u);
316 ASSERT_EQ(MV.size(), 1u);
317 ASSERT_EQ(MV.find(3), MV.end());
318 ASSERT_EQ(MV[5], 6);
319
320 ASSERT_EQ(MV.erase(79), 0u);
321 ASSERT_EQ(MV.size(), 1u);
322 }
323
TEST(SmallMapVectorLargeTest,remove_if)324 TEST(SmallMapVectorLargeTest, remove_if) {
325 SmallMapVector<int, int, 1> MV;
326
327 MV.insert(std::make_pair(1, 11));
328 MV.insert(std::make_pair(2, 12));
329 MV.insert(std::make_pair(3, 13));
330 MV.insert(std::make_pair(4, 14));
331 MV.insert(std::make_pair(5, 15));
332 MV.insert(std::make_pair(6, 16));
333 ASSERT_EQ(MV.size(), 6u);
334
335 MV.remove_if([](const std::pair<int, int> &Val) { return Val.second % 2; });
336 ASSERT_EQ(MV.size(), 3u);
337 ASSERT_EQ(MV.find(1), MV.end());
338 ASSERT_EQ(MV.find(3), MV.end());
339 ASSERT_EQ(MV.find(5), MV.end());
340 ASSERT_EQ(MV[2], 12);
341 ASSERT_EQ(MV[4], 14);
342 ASSERT_EQ(MV[6], 16);
343 }
344
TEST(SmallMapVectorLargeTest,iteration_test)345 TEST(SmallMapVectorLargeTest, iteration_test) {
346 SmallMapVector<int, int, 1> MV;
347
348 MV.insert(std::make_pair(1, 11));
349 MV.insert(std::make_pair(2, 12));
350 MV.insert(std::make_pair(3, 13));
351 MV.insert(std::make_pair(4, 14));
352 MV.insert(std::make_pair(5, 15));
353 MV.insert(std::make_pair(6, 16));
354 ASSERT_EQ(MV.size(), 6u);
355
356 int count = 1;
357 for (auto P : make_range(MV.begin(), MV.end())) {
358 ASSERT_EQ(P.first, count);
359 count++;
360 }
361
362 count = 6;
363 for (auto P : make_range(MV.rbegin(), MV.rend())) {
364 ASSERT_EQ(P.first, count);
365 count--;
366 }
367 }
368