1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "base/containers/small_map.h"
6
7 #include <stddef.h>
8
9 #include <algorithm>
10 #include <functional>
11 #include <map>
12
13 #include "base/containers/hash_tables.h"
14 #include "base/logging.h"
15 #include "testing/gtest/include/gtest/gtest.h"
16
17 namespace base {
18
TEST(SmallMap,General)19 TEST(SmallMap, General) {
20 SmallMap<hash_map<int, int> > m;
21
22 EXPECT_TRUE(m.empty());
23
24 m[0] = 5;
25
26 EXPECT_FALSE(m.empty());
27 EXPECT_EQ(m.size(), 1u);
28
29 m[9] = 2;
30
31 EXPECT_FALSE(m.empty());
32 EXPECT_EQ(m.size(), 2u);
33
34 EXPECT_EQ(m[9], 2);
35 EXPECT_EQ(m[0], 5);
36 EXPECT_FALSE(m.UsingFullMap());
37
38 SmallMap<hash_map<int, int> >::iterator iter(m.begin());
39 ASSERT_TRUE(iter != m.end());
40 EXPECT_EQ(iter->first, 0);
41 EXPECT_EQ(iter->second, 5);
42 ++iter;
43 ASSERT_TRUE(iter != m.end());
44 EXPECT_EQ((*iter).first, 9);
45 EXPECT_EQ((*iter).second, 2);
46 ++iter;
47 EXPECT_TRUE(iter == m.end());
48
49 m[8] = 23;
50 m[1234] = 90;
51 m[-5] = 6;
52
53 EXPECT_EQ(m[ 9], 2);
54 EXPECT_EQ(m[ 0], 5);
55 EXPECT_EQ(m[1234], 90);
56 EXPECT_EQ(m[ 8], 23);
57 EXPECT_EQ(m[ -5], 6);
58 EXPECT_EQ(m.size(), 5u);
59 EXPECT_FALSE(m.empty());
60 EXPECT_TRUE(m.UsingFullMap());
61
62 iter = m.begin();
63 for (int i = 0; i < 5; i++) {
64 EXPECT_TRUE(iter != m.end());
65 ++iter;
66 }
67 EXPECT_TRUE(iter == m.end());
68
69 const SmallMap<hash_map<int, int> >& ref = m;
70 EXPECT_TRUE(ref.find(1234) != m.end());
71 EXPECT_TRUE(ref.find(5678) == m.end());
72 }
73
TEST(SmallMap,PostFixIteratorIncrement)74 TEST(SmallMap, PostFixIteratorIncrement) {
75 SmallMap<hash_map<int, int> > m;
76 m[0] = 5;
77 m[2] = 3;
78
79 {
80 SmallMap<hash_map<int, int> >::iterator iter(m.begin());
81 SmallMap<hash_map<int, int> >::iterator last(iter++);
82 ++last;
83 EXPECT_TRUE(last == iter);
84 }
85
86 {
87 SmallMap<hash_map<int, int> >::const_iterator iter(m.begin());
88 SmallMap<hash_map<int, int> >::const_iterator last(iter++);
89 ++last;
90 EXPECT_TRUE(last == iter);
91 }
92 }
93
94 // Based on the General testcase.
TEST(SmallMap,CopyConstructor)95 TEST(SmallMap, CopyConstructor) {
96 SmallMap<hash_map<int, int> > src;
97
98 {
99 SmallMap<hash_map<int, int> > m(src);
100 EXPECT_TRUE(m.empty());
101 }
102
103 src[0] = 5;
104
105 {
106 SmallMap<hash_map<int, int> > m(src);
107 EXPECT_FALSE(m.empty());
108 EXPECT_EQ(m.size(), 1u);
109 }
110
111 src[9] = 2;
112
113 {
114 SmallMap<hash_map<int, int> > m(src);
115 EXPECT_FALSE(m.empty());
116 EXPECT_EQ(m.size(), 2u);
117
118 EXPECT_EQ(m[9], 2);
119 EXPECT_EQ(m[0], 5);
120 EXPECT_FALSE(m.UsingFullMap());
121 }
122
123 src[8] = 23;
124 src[1234] = 90;
125 src[-5] = 6;
126
127 {
128 SmallMap<hash_map<int, int> > m(src);
129 EXPECT_EQ(m[ 9], 2);
130 EXPECT_EQ(m[ 0], 5);
131 EXPECT_EQ(m[1234], 90);
132 EXPECT_EQ(m[ 8], 23);
133 EXPECT_EQ(m[ -5], 6);
134 EXPECT_EQ(m.size(), 5u);
135 EXPECT_FALSE(m.empty());
136 EXPECT_TRUE(m.UsingFullMap());
137 }
138 }
139
140 template<class inner>
SmallMapIsSubset(SmallMap<inner> const & a,SmallMap<inner> const & b)141 static bool SmallMapIsSubset(SmallMap<inner> const& a,
142 SmallMap<inner> const& b) {
143 typename SmallMap<inner>::const_iterator it;
144 for (it = a.begin(); it != a.end(); ++it) {
145 typename SmallMap<inner>::const_iterator it_in_b = b.find(it->first);
146 if (it_in_b == b.end() || it_in_b->second != it->second)
147 return false;
148 }
149 return true;
150 }
151
152 template<class inner>
SmallMapEqual(SmallMap<inner> const & a,SmallMap<inner> const & b)153 static bool SmallMapEqual(SmallMap<inner> const& a,
154 SmallMap<inner> const& b) {
155 return SmallMapIsSubset(a, b) && SmallMapIsSubset(b, a);
156 }
157
TEST(SmallMap,AssignmentOperator)158 TEST(SmallMap, AssignmentOperator) {
159 SmallMap<hash_map<int, int> > src_small;
160 SmallMap<hash_map<int, int> > src_large;
161
162 src_small[1] = 20;
163 src_small[2] = 21;
164 src_small[3] = 22;
165 EXPECT_FALSE(src_small.UsingFullMap());
166
167 src_large[1] = 20;
168 src_large[2] = 21;
169 src_large[3] = 22;
170 src_large[5] = 23;
171 src_large[6] = 24;
172 src_large[7] = 25;
173 EXPECT_TRUE(src_large.UsingFullMap());
174
175 // Assignments to empty.
176 SmallMap<hash_map<int, int> > dest_small;
177 dest_small = src_small;
178 EXPECT_TRUE(SmallMapEqual(dest_small, src_small));
179 EXPECT_EQ(dest_small.UsingFullMap(),
180 src_small.UsingFullMap());
181
182 SmallMap<hash_map<int, int> > dest_large;
183 dest_large = src_large;
184 EXPECT_TRUE(SmallMapEqual(dest_large, src_large));
185 EXPECT_EQ(dest_large.UsingFullMap(),
186 src_large.UsingFullMap());
187
188 // Assignments which assign from full to small, and vice versa.
189 dest_small = src_large;
190 EXPECT_TRUE(SmallMapEqual(dest_small, src_large));
191 EXPECT_EQ(dest_small.UsingFullMap(),
192 src_large.UsingFullMap());
193
194 dest_large = src_small;
195 EXPECT_TRUE(SmallMapEqual(dest_large, src_small));
196 EXPECT_EQ(dest_large.UsingFullMap(),
197 src_small.UsingFullMap());
198
199 // Double check that SmallMapEqual works:
200 dest_large[42] = 666;
201 EXPECT_FALSE(SmallMapEqual(dest_large, src_small));
202 }
203
TEST(SmallMap,Insert)204 TEST(SmallMap, Insert) {
205 SmallMap<hash_map<int, int> > sm;
206
207 // loop through the transition from small map to map.
208 for (int i = 1; i <= 10; ++i) {
209 VLOG(1) << "Iteration " << i;
210 // insert an element
211 std::pair<SmallMap<hash_map<int, int> >::iterator,
212 bool> ret;
213 ret = sm.insert(std::make_pair(i, 100*i));
214 EXPECT_TRUE(ret.second);
215 EXPECT_TRUE(ret.first == sm.find(i));
216 EXPECT_EQ(ret.first->first, i);
217 EXPECT_EQ(ret.first->second, 100*i);
218
219 // try to insert it again with different value, fails, but we still get an
220 // iterator back with the original value.
221 ret = sm.insert(std::make_pair(i, -i));
222 EXPECT_FALSE(ret.second);
223 EXPECT_TRUE(ret.first == sm.find(i));
224 EXPECT_EQ(ret.first->first, i);
225 EXPECT_EQ(ret.first->second, 100*i);
226
227 // check the state of the map.
228 for (int j = 1; j <= i; ++j) {
229 SmallMap<hash_map<int, int> >::iterator it = sm.find(j);
230 EXPECT_TRUE(it != sm.end());
231 EXPECT_EQ(it->first, j);
232 EXPECT_EQ(it->second, j * 100);
233 }
234 EXPECT_EQ(sm.size(), static_cast<size_t>(i));
235 EXPECT_FALSE(sm.empty());
236 }
237 }
238
TEST(SmallMap,InsertRange)239 TEST(SmallMap, InsertRange) {
240 // loop through the transition from small map to map.
241 for (int elements = 0; elements <= 10; ++elements) {
242 VLOG(1) << "Elements " << elements;
243 hash_map<int, int> normal_map;
244 for (int i = 1; i <= elements; ++i) {
245 normal_map.insert(std::make_pair(i, 100*i));
246 }
247
248 SmallMap<hash_map<int, int> > sm;
249 sm.insert(normal_map.begin(), normal_map.end());
250 EXPECT_EQ(normal_map.size(), sm.size());
251 for (int i = 1; i <= elements; ++i) {
252 VLOG(1) << "Iteration " << i;
253 EXPECT_TRUE(sm.find(i) != sm.end());
254 EXPECT_EQ(sm.find(i)->first, i);
255 EXPECT_EQ(sm.find(i)->second, 100*i);
256 }
257 }
258 }
259
TEST(SmallMap,Erase)260 TEST(SmallMap, Erase) {
261 SmallMap<hash_map<std::string, int> > m;
262 SmallMap<hash_map<std::string, int> >::iterator iter;
263
264 m["monday"] = 1;
265 m["tuesday"] = 2;
266 m["wednesday"] = 3;
267
268 EXPECT_EQ(m["monday" ], 1);
269 EXPECT_EQ(m["tuesday" ], 2);
270 EXPECT_EQ(m["wednesday"], 3);
271 EXPECT_EQ(m.count("tuesday"), 1u);
272 EXPECT_FALSE(m.UsingFullMap());
273
274 iter = m.begin();
275 ASSERT_TRUE(iter != m.end());
276 EXPECT_EQ(iter->first, "monday");
277 EXPECT_EQ(iter->second, 1);
278 ++iter;
279 ASSERT_TRUE(iter != m.end());
280 EXPECT_EQ(iter->first, "tuesday");
281 EXPECT_EQ(iter->second, 2);
282 ++iter;
283 ASSERT_TRUE(iter != m.end());
284 EXPECT_EQ(iter->first, "wednesday");
285 EXPECT_EQ(iter->second, 3);
286 ++iter;
287 EXPECT_TRUE(iter == m.end());
288
289 EXPECT_EQ(m.erase("tuesday"), 1u);
290
291 EXPECT_EQ(m["monday" ], 1);
292 EXPECT_EQ(m["wednesday"], 3);
293 EXPECT_EQ(m.count("tuesday"), 0u);
294 EXPECT_EQ(m.erase("tuesday"), 0u);
295
296 iter = m.begin();
297 ASSERT_TRUE(iter != m.end());
298 EXPECT_EQ(iter->first, "monday");
299 EXPECT_EQ(iter->second, 1);
300 ++iter;
301 ASSERT_TRUE(iter != m.end());
302 EXPECT_EQ(iter->first, "wednesday");
303 EXPECT_EQ(iter->second, 3);
304 ++iter;
305 EXPECT_TRUE(iter == m.end());
306
307 m["thursday"] = 4;
308 m["friday"] = 5;
309 EXPECT_EQ(m.size(), 4u);
310 EXPECT_FALSE(m.empty());
311 EXPECT_FALSE(m.UsingFullMap());
312
313 m["saturday"] = 6;
314 EXPECT_TRUE(m.UsingFullMap());
315
316 EXPECT_EQ(m.count("friday"), 1u);
317 EXPECT_EQ(m.erase("friday"), 1u);
318 EXPECT_TRUE(m.UsingFullMap());
319 EXPECT_EQ(m.count("friday"), 0u);
320 EXPECT_EQ(m.erase("friday"), 0u);
321
322 EXPECT_EQ(m.size(), 4u);
323 EXPECT_FALSE(m.empty());
324 EXPECT_EQ(m.erase("monday"), 1u);
325 EXPECT_EQ(m.size(), 3u);
326 EXPECT_FALSE(m.empty());
327
328 m.clear();
329 EXPECT_FALSE(m.UsingFullMap());
330 EXPECT_EQ(m.size(), 0u);
331 EXPECT_TRUE(m.empty());
332 }
333
TEST(SmallMap,NonHashMap)334 TEST(SmallMap, NonHashMap) {
335 SmallMap<std::map<int, int>, 4, std::equal_to<int> > m;
336 EXPECT_TRUE(m.empty());
337
338 m[9] = 2;
339 m[0] = 5;
340
341 EXPECT_EQ(m[9], 2);
342 EXPECT_EQ(m[0], 5);
343 EXPECT_EQ(m.size(), 2u);
344 EXPECT_FALSE(m.empty());
345 EXPECT_FALSE(m.UsingFullMap());
346
347 SmallMap<std::map<int, int>, 4, std::equal_to<int> >::iterator iter(
348 m.begin());
349 ASSERT_TRUE(iter != m.end());
350 EXPECT_EQ(iter->first, 9);
351 EXPECT_EQ(iter->second, 2);
352 ++iter;
353 ASSERT_TRUE(iter != m.end());
354 EXPECT_EQ(iter->first, 0);
355 EXPECT_EQ(iter->second, 5);
356 ++iter;
357 EXPECT_TRUE(iter == m.end());
358 --iter;
359 ASSERT_TRUE(iter != m.end());
360 EXPECT_EQ(iter->first, 0);
361 EXPECT_EQ(iter->second, 5);
362
363 m[8] = 23;
364 m[1234] = 90;
365 m[-5] = 6;
366
367 EXPECT_EQ(m[ 9], 2);
368 EXPECT_EQ(m[ 0], 5);
369 EXPECT_EQ(m[1234], 90);
370 EXPECT_EQ(m[ 8], 23);
371 EXPECT_EQ(m[ -5], 6);
372 EXPECT_EQ(m.size(), 5u);
373 EXPECT_FALSE(m.empty());
374 EXPECT_TRUE(m.UsingFullMap());
375
376 iter = m.begin();
377 ASSERT_TRUE(iter != m.end());
378 EXPECT_EQ(iter->first, -5);
379 EXPECT_EQ(iter->second, 6);
380 ++iter;
381 ASSERT_TRUE(iter != m.end());
382 EXPECT_EQ(iter->first, 0);
383 EXPECT_EQ(iter->second, 5);
384 ++iter;
385 ASSERT_TRUE(iter != m.end());
386 EXPECT_EQ(iter->first, 8);
387 EXPECT_EQ(iter->second, 23);
388 ++iter;
389 ASSERT_TRUE(iter != m.end());
390 EXPECT_EQ(iter->first, 9);
391 EXPECT_EQ(iter->second, 2);
392 ++iter;
393 ASSERT_TRUE(iter != m.end());
394 EXPECT_EQ(iter->first, 1234);
395 EXPECT_EQ(iter->second, 90);
396 ++iter;
397 EXPECT_TRUE(iter == m.end());
398 --iter;
399 ASSERT_TRUE(iter != m.end());
400 EXPECT_EQ(iter->first, 1234);
401 EXPECT_EQ(iter->second, 90);
402 }
403
TEST(SmallMap,DefaultEqualKeyWorks)404 TEST(SmallMap, DefaultEqualKeyWorks) {
405 // If these tests compile, they pass. The EXPECT calls are only there to avoid
406 // unused variable warnings.
407 SmallMap<hash_map<int, int> > hm;
408 EXPECT_EQ(0u, hm.size());
409 SmallMap<std::map<int, int> > m;
410 EXPECT_EQ(0u, m.size());
411 }
412
413 namespace {
414
415 class hash_map_add_item : public hash_map<int, int> {
416 public:
hash_map_add_item()417 hash_map_add_item() : hash_map<int, int>() {}
hash_map_add_item(const std::pair<int,int> & item)418 explicit hash_map_add_item(const std::pair<int, int>& item)
419 : hash_map<int, int>() {
420 insert(item);
421 }
422 };
423
InitMap(ManualConstructor<hash_map_add_item> * map_ctor)424 void InitMap(ManualConstructor<hash_map_add_item>* map_ctor) {
425 map_ctor->Init(std::make_pair(0, 0));
426 }
427
428 class hash_map_add_item_initializer {
429 public:
hash_map_add_item_initializer(int item_to_add)430 explicit hash_map_add_item_initializer(int item_to_add)
431 : item_(item_to_add) {}
hash_map_add_item_initializer()432 hash_map_add_item_initializer()
433 : item_(0) {}
operator ()(ManualConstructor<hash_map_add_item> * map_ctor) const434 void operator()(ManualConstructor<hash_map_add_item>* map_ctor) const {
435 map_ctor->Init(std::make_pair(item_, item_));
436 }
437
438 int item_;
439 };
440
441 } // anonymous namespace
442
TEST(SmallMap,SubclassInitializationWithFunctionPointer)443 TEST(SmallMap, SubclassInitializationWithFunctionPointer) {
444 SmallMap<hash_map_add_item, 4, std::equal_to<int>,
445 void (&)(ManualConstructor<hash_map_add_item>*)> m(InitMap);
446
447 EXPECT_TRUE(m.empty());
448
449 m[1] = 1;
450 m[2] = 2;
451 m[3] = 3;
452 m[4] = 4;
453
454 EXPECT_EQ(4u, m.size());
455 EXPECT_EQ(0u, m.count(0));
456
457 m[5] = 5;
458 EXPECT_EQ(6u, m.size());
459 // Our function adds an extra item when we convert to a map.
460 EXPECT_EQ(1u, m.count(0));
461 }
462
TEST(SmallMap,SubclassInitializationWithFunctionObject)463 TEST(SmallMap, SubclassInitializationWithFunctionObject) {
464 SmallMap<hash_map_add_item, 4, std::equal_to<int>,
465 hash_map_add_item_initializer> m(hash_map_add_item_initializer(-1));
466
467 EXPECT_TRUE(m.empty());
468
469 m[1] = 1;
470 m[2] = 2;
471 m[3] = 3;
472 m[4] = 4;
473
474 EXPECT_EQ(4u, m.size());
475 EXPECT_EQ(0u, m.count(-1));
476
477 m[5] = 5;
478 EXPECT_EQ(6u, m.size());
479 // Our functor adds an extra item when we convert to a map.
480 EXPECT_EQ(1u, m.count(-1));
481 }
482
483 } // namespace base
484