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 
17 TEST(MapVectorTest, insert_pop) {
18   MapVector<int, int> MV;
19   std::pair<MapVector<int, int>::iterator, bool> R;
20 
21   R = MV.insert(std::make_pair(1, 2));
22   ASSERT_EQ(R.first, MV.begin());
23   EXPECT_EQ(R.first->first, 1);
24   EXPECT_EQ(R.first->second, 2);
25   EXPECT_TRUE(R.second);
26 
27   R = MV.insert(std::make_pair(1, 3));
28   ASSERT_EQ(R.first, MV.begin());
29   EXPECT_EQ(R.first->first, 1);
30   EXPECT_EQ(R.first->second, 2);
31   EXPECT_FALSE(R.second);
32 
33   R = MV.insert(std::make_pair(4, 5));
34   ASSERT_NE(R.first, MV.end());
35   EXPECT_EQ(R.first->first, 4);
36   EXPECT_EQ(R.first->second, 5);
37   EXPECT_TRUE(R.second);
38 
39   EXPECT_EQ(MV.size(), 2u);
40   EXPECT_EQ(MV[1], 2);
41   EXPECT_EQ(MV[4], 5);
42 
43   MV.pop_back();
44   EXPECT_EQ(MV.size(), 1u);
45   EXPECT_EQ(MV[1], 2);
46 
47   R = MV.insert(std::make_pair(4, 7));
48   ASSERT_NE(R.first, MV.end());
49   EXPECT_EQ(R.first->first, 4);
50   EXPECT_EQ(R.first->second, 7);
51   EXPECT_TRUE(R.second);
52 
53   EXPECT_EQ(MV.size(), 2u);
54   EXPECT_EQ(MV[1], 2);
55   EXPECT_EQ(MV[4], 7);
56 }
57 
58 TEST(MapVectorTest, erase) {
59   MapVector<int, int> MV;
60 
61   MV.insert(std::make_pair(1, 2));
62   MV.insert(std::make_pair(3, 4));
63   MV.insert(std::make_pair(5, 6));
64   ASSERT_EQ(MV.size(), 3u);
65 
66   MV.erase(MV.find(1));
67   ASSERT_EQ(MV.size(), 2u);
68   ASSERT_EQ(MV.find(1), MV.end());
69   ASSERT_EQ(MV[3], 4);
70   ASSERT_EQ(MV[5], 6);
71 
72   ASSERT_EQ(MV.erase(3), 1u);
73   ASSERT_EQ(MV.size(), 1u);
74   ASSERT_EQ(MV.find(3), MV.end());
75   ASSERT_EQ(MV[5], 6);
76 
77   ASSERT_EQ(MV.erase(79), 0u);
78   ASSERT_EQ(MV.size(), 1u);
79 }
80 
81 TEST(MapVectorTest, remove_if) {
82   MapVector<int, int> MV;
83 
84   MV.insert(std::make_pair(1, 11));
85   MV.insert(std::make_pair(2, 12));
86   MV.insert(std::make_pair(3, 13));
87   MV.insert(std::make_pair(4, 14));
88   MV.insert(std::make_pair(5, 15));
89   MV.insert(std::make_pair(6, 16));
90   ASSERT_EQ(MV.size(), 6u);
91 
92   MV.remove_if([](const std::pair<int, int> &Val) { return Val.second % 2; });
93   ASSERT_EQ(MV.size(), 3u);
94   ASSERT_EQ(MV.find(1), MV.end());
95   ASSERT_EQ(MV.find(3), MV.end());
96   ASSERT_EQ(MV.find(5), MV.end());
97   ASSERT_EQ(MV[2], 12);
98   ASSERT_EQ(MV[4], 14);
99   ASSERT_EQ(MV[6], 16);
100 }
101 
102 TEST(MapVectorTest, iteration_test) {
103   MapVector<int, int> MV;
104 
105   MV.insert(std::make_pair(1, 11));
106   MV.insert(std::make_pair(2, 12));
107   MV.insert(std::make_pair(3, 13));
108   MV.insert(std::make_pair(4, 14));
109   MV.insert(std::make_pair(5, 15));
110   MV.insert(std::make_pair(6, 16));
111   ASSERT_EQ(MV.size(), 6u);
112 
113   int count = 1;
114   for (auto P : make_range(MV.begin(), MV.end())) {
115     ASSERT_EQ(P.first, count);
116     count++;
117   }
118 
119   count = 6;
120   for (auto P : make_range(MV.rbegin(), MV.rend())) {
121     ASSERT_EQ(P.first, count);
122     count--;
123   }
124 }
125 
126 TEST(SmallMapVectorSmallTest, insert_pop) {
127   SmallMapVector<int, int, 32> MV;
128   std::pair<SmallMapVector<int, int, 32>::iterator, bool> R;
129 
130   R = MV.insert(std::make_pair(1, 2));
131   ASSERT_EQ(R.first, MV.begin());
132   EXPECT_EQ(R.first->first, 1);
133   EXPECT_EQ(R.first->second, 2);
134   EXPECT_TRUE(R.second);
135 
136   R = MV.insert(std::make_pair(1, 3));
137   ASSERT_EQ(R.first, MV.begin());
138   EXPECT_EQ(R.first->first, 1);
139   EXPECT_EQ(R.first->second, 2);
140   EXPECT_FALSE(R.second);
141 
142   R = MV.insert(std::make_pair(4, 5));
143   ASSERT_NE(R.first, MV.end());
144   EXPECT_EQ(R.first->first, 4);
145   EXPECT_EQ(R.first->second, 5);
146   EXPECT_TRUE(R.second);
147 
148   EXPECT_EQ(MV.size(), 2u);
149   EXPECT_EQ(MV[1], 2);
150   EXPECT_EQ(MV[4], 5);
151 
152   MV.pop_back();
153   EXPECT_EQ(MV.size(), 1u);
154   EXPECT_EQ(MV[1], 2);
155 
156   R = MV.insert(std::make_pair(4, 7));
157   ASSERT_NE(R.first, MV.end());
158   EXPECT_EQ(R.first->first, 4);
159   EXPECT_EQ(R.first->second, 7);
160   EXPECT_TRUE(R.second);
161 
162   EXPECT_EQ(MV.size(), 2u);
163   EXPECT_EQ(MV[1], 2);
164   EXPECT_EQ(MV[4], 7);
165 }
166 
167 TEST(SmallMapVectorSmallTest, erase) {
168   SmallMapVector<int, int, 32> MV;
169 
170   MV.insert(std::make_pair(1, 2));
171   MV.insert(std::make_pair(3, 4));
172   MV.insert(std::make_pair(5, 6));
173   ASSERT_EQ(MV.size(), 3u);
174 
175   MV.erase(MV.find(1));
176   ASSERT_EQ(MV.size(), 2u);
177   ASSERT_EQ(MV.find(1), MV.end());
178   ASSERT_EQ(MV[3], 4);
179   ASSERT_EQ(MV[5], 6);
180 
181   ASSERT_EQ(MV.erase(3), 1u);
182   ASSERT_EQ(MV.size(), 1u);
183   ASSERT_EQ(MV.find(3), MV.end());
184   ASSERT_EQ(MV[5], 6);
185 
186   ASSERT_EQ(MV.erase(79), 0u);
187   ASSERT_EQ(MV.size(), 1u);
188 }
189 
190 TEST(SmallMapVectorSmallTest, remove_if) {
191   SmallMapVector<int, int, 32> MV;
192 
193   MV.insert(std::make_pair(1, 11));
194   MV.insert(std::make_pair(2, 12));
195   MV.insert(std::make_pair(3, 13));
196   MV.insert(std::make_pair(4, 14));
197   MV.insert(std::make_pair(5, 15));
198   MV.insert(std::make_pair(6, 16));
199   ASSERT_EQ(MV.size(), 6u);
200 
201   MV.remove_if([](const std::pair<int, int> &Val) { return Val.second % 2; });
202   ASSERT_EQ(MV.size(), 3u);
203   ASSERT_EQ(MV.find(1), MV.end());
204   ASSERT_EQ(MV.find(3), MV.end());
205   ASSERT_EQ(MV.find(5), MV.end());
206   ASSERT_EQ(MV[2], 12);
207   ASSERT_EQ(MV[4], 14);
208   ASSERT_EQ(MV[6], 16);
209 }
210 
211 TEST(SmallMapVectorSmallTest, iteration_test) {
212   SmallMapVector<int, int, 32> MV;
213 
214   MV.insert(std::make_pair(1, 11));
215   MV.insert(std::make_pair(2, 12));
216   MV.insert(std::make_pair(3, 13));
217   MV.insert(std::make_pair(4, 14));
218   MV.insert(std::make_pair(5, 15));
219   MV.insert(std::make_pair(6, 16));
220   ASSERT_EQ(MV.size(), 6u);
221 
222   int count = 1;
223   for (auto P : make_range(MV.begin(), MV.end())) {
224     ASSERT_EQ(P.first, count);
225     count++;
226   }
227 
228   count = 6;
229   for (auto P : make_range(MV.rbegin(), MV.rend())) {
230     ASSERT_EQ(P.first, count);
231     count--;
232   }
233 }
234 
235 TEST(SmallMapVectorLargeTest, insert_pop) {
236   SmallMapVector<int, int, 1> MV;
237   std::pair<SmallMapVector<int, int, 1>::iterator, bool> R;
238 
239   R = MV.insert(std::make_pair(1, 2));
240   ASSERT_EQ(R.first, MV.begin());
241   EXPECT_EQ(R.first->first, 1);
242   EXPECT_EQ(R.first->second, 2);
243   EXPECT_TRUE(R.second);
244 
245   R = MV.insert(std::make_pair(1, 3));
246   ASSERT_EQ(R.first, MV.begin());
247   EXPECT_EQ(R.first->first, 1);
248   EXPECT_EQ(R.first->second, 2);
249   EXPECT_FALSE(R.second);
250 
251   R = MV.insert(std::make_pair(4, 5));
252   ASSERT_NE(R.first, MV.end());
253   EXPECT_EQ(R.first->first, 4);
254   EXPECT_EQ(R.first->second, 5);
255   EXPECT_TRUE(R.second);
256 
257   EXPECT_EQ(MV.size(), 2u);
258   EXPECT_EQ(MV[1], 2);
259   EXPECT_EQ(MV[4], 5);
260 
261   MV.pop_back();
262   EXPECT_EQ(MV.size(), 1u);
263   EXPECT_EQ(MV[1], 2);
264 
265   R = MV.insert(std::make_pair(4, 7));
266   ASSERT_NE(R.first, MV.end());
267   EXPECT_EQ(R.first->first, 4);
268   EXPECT_EQ(R.first->second, 7);
269   EXPECT_TRUE(R.second);
270 
271   EXPECT_EQ(MV.size(), 2u);
272   EXPECT_EQ(MV[1], 2);
273   EXPECT_EQ(MV[4], 7);
274 }
275 
276 TEST(SmallMapVectorLargeTest, erase) {
277   SmallMapVector<int, int, 1> MV;
278 
279   MV.insert(std::make_pair(1, 2));
280   MV.insert(std::make_pair(3, 4));
281   MV.insert(std::make_pair(5, 6));
282   ASSERT_EQ(MV.size(), 3u);
283 
284   MV.erase(MV.find(1));
285   ASSERT_EQ(MV.size(), 2u);
286   ASSERT_EQ(MV.find(1), MV.end());
287   ASSERT_EQ(MV[3], 4);
288   ASSERT_EQ(MV[5], 6);
289 
290   ASSERT_EQ(MV.erase(3), 1u);
291   ASSERT_EQ(MV.size(), 1u);
292   ASSERT_EQ(MV.find(3), MV.end());
293   ASSERT_EQ(MV[5], 6);
294 
295   ASSERT_EQ(MV.erase(79), 0u);
296   ASSERT_EQ(MV.size(), 1u);
297 }
298 
299 TEST(SmallMapVectorLargeTest, remove_if) {
300   SmallMapVector<int, int, 1> MV;
301 
302   MV.insert(std::make_pair(1, 11));
303   MV.insert(std::make_pair(2, 12));
304   MV.insert(std::make_pair(3, 13));
305   MV.insert(std::make_pair(4, 14));
306   MV.insert(std::make_pair(5, 15));
307   MV.insert(std::make_pair(6, 16));
308   ASSERT_EQ(MV.size(), 6u);
309 
310   MV.remove_if([](const std::pair<int, int> &Val) { return Val.second % 2; });
311   ASSERT_EQ(MV.size(), 3u);
312   ASSERT_EQ(MV.find(1), MV.end());
313   ASSERT_EQ(MV.find(3), MV.end());
314   ASSERT_EQ(MV.find(5), MV.end());
315   ASSERT_EQ(MV[2], 12);
316   ASSERT_EQ(MV[4], 14);
317   ASSERT_EQ(MV[6], 16);
318 }
319 
320 TEST(SmallMapVectorLargeTest, iteration_test) {
321   SmallMapVector<int, int, 1> MV;
322 
323   MV.insert(std::make_pair(1, 11));
324   MV.insert(std::make_pair(2, 12));
325   MV.insert(std::make_pair(3, 13));
326   MV.insert(std::make_pair(4, 14));
327   MV.insert(std::make_pair(5, 15));
328   MV.insert(std::make_pair(6, 16));
329   ASSERT_EQ(MV.size(), 6u);
330 
331   int count = 1;
332   for (auto P : make_range(MV.begin(), MV.end())) {
333     ASSERT_EQ(P.first, count);
334     count++;
335   }
336 
337   count = 6;
338   for (auto P : make_range(MV.rbegin(), MV.rend())) {
339     ASSERT_EQ(P.first, count);
340     count--;
341   }
342 }
343