1 // Copyright 2012 The Chromium Authors
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 #include <unordered_map>
13
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 small_map<std::unordered_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 small_map<std::unordered_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 small_map<std::unordered_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 small_map<std::unordered_map<int, int>> m;
76 m[0] = 5;
77 m[2] = 3;
78
79 {
80 small_map<std::unordered_map<int, int>>::iterator iter(m.begin());
81 small_map<std::unordered_map<int, int>>::iterator last(iter++);
82 ++last;
83 EXPECT_TRUE(last == iter);
84 }
85
86 {
87 small_map<std::unordered_map<int, int>>::const_iterator iter(m.begin());
88 small_map<std::unordered_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 small_map<std::unordered_map<int, int>> src;
97
98 {
99 small_map<std::unordered_map<int, int>> m(src);
100 EXPECT_TRUE(m.empty());
101 }
102
103 src[0] = 5;
104
105 {
106 small_map<std::unordered_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 small_map<std::unordered_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 small_map<std::unordered_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(small_map<inner> const & a,small_map<inner> const & b)141 static bool SmallMapIsSubset(small_map<inner> const& a,
142 small_map<inner> const& b) {
143 typename small_map<inner>::const_iterator it;
144 for (it = a.begin(); it != a.end(); ++it) {
145 typename small_map<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(small_map<inner> const & a,small_map<inner> const & b)153 static bool SmallMapEqual(small_map<inner> const& a,
154 small_map<inner> const& b) {
155 return SmallMapIsSubset(a, b) && SmallMapIsSubset(b, a);
156 }
157
TEST(SmallMap,AssignmentOperator)158 TEST(SmallMap, AssignmentOperator) {
159 small_map<std::unordered_map<int, int>> src_small;
160 small_map<std::unordered_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 small_map<std::unordered_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 small_map<std::unordered_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 small_map<std::unordered_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<small_map<std::unordered_map<int, int>>::iterator, bool> ret;
212 ret = sm.insert(std::make_pair(i, 100*i));
213 EXPECT_TRUE(ret.second);
214 EXPECT_TRUE(ret.first == sm.find(i));
215 EXPECT_EQ(ret.first->first, i);
216 EXPECT_EQ(ret.first->second, 100*i);
217
218 // try to insert it again with different value, fails, but we still get an
219 // iterator back with the original value.
220 ret = sm.insert(std::make_pair(i, -i));
221 EXPECT_FALSE(ret.second);
222 EXPECT_TRUE(ret.first == sm.find(i));
223 EXPECT_EQ(ret.first->first, i);
224 EXPECT_EQ(ret.first->second, 100*i);
225
226 // check the state of the map.
227 for (int j = 1; j <= i; ++j) {
228 small_map<std::unordered_map<int, int>>::iterator it = sm.find(j);
229 EXPECT_TRUE(it != sm.end());
230 EXPECT_EQ(it->first, j);
231 EXPECT_EQ(it->second, j * 100);
232 }
233 EXPECT_EQ(sm.size(), static_cast<size_t>(i));
234 EXPECT_FALSE(sm.empty());
235 }
236 }
237
TEST(SmallMap,InsertRange)238 TEST(SmallMap, InsertRange) {
239 // loop through the transition from small map to map.
240 for (int elements = 0; elements <= 10; ++elements) {
241 VLOG(1) << "Elements " << elements;
242 std::unordered_map<int, int> normal_map;
243 for (int i = 1; i <= elements; ++i) {
244 normal_map.insert(std::make_pair(i, 100*i));
245 }
246
247 small_map<std::unordered_map<int, int>> sm;
248 sm.insert(normal_map.begin(), normal_map.end());
249 EXPECT_EQ(normal_map.size(), sm.size());
250 for (int i = 1; i <= elements; ++i) {
251 VLOG(1) << "Iteration " << i;
252 EXPECT_TRUE(sm.find(i) != sm.end());
253 EXPECT_EQ(sm.find(i)->first, i);
254 EXPECT_EQ(sm.find(i)->second, 100*i);
255 }
256 }
257 }
258
TEST(SmallMap,Erase)259 TEST(SmallMap, Erase) {
260 small_map<std::unordered_map<std::string, int>> m;
261 small_map<std::unordered_map<std::string, int>>::iterator iter;
262
263 m["monday"] = 1;
264 m["tuesday"] = 2;
265 m["wednesday"] = 3;
266
267 EXPECT_EQ(m["monday" ], 1);
268 EXPECT_EQ(m["tuesday" ], 2);
269 EXPECT_EQ(m["wednesday"], 3);
270 EXPECT_EQ(m.count("tuesday"), 1u);
271 EXPECT_FALSE(m.UsingFullMap());
272
273 iter = m.begin();
274 ASSERT_TRUE(iter != m.end());
275 EXPECT_EQ(iter->first, "monday");
276 EXPECT_EQ(iter->second, 1);
277 ++iter;
278 ASSERT_TRUE(iter != m.end());
279 EXPECT_EQ(iter->first, "tuesday");
280 EXPECT_EQ(iter->second, 2);
281 ++iter;
282 ASSERT_TRUE(iter != m.end());
283 EXPECT_EQ(iter->first, "wednesday");
284 EXPECT_EQ(iter->second, 3);
285 ++iter;
286 EXPECT_TRUE(iter == m.end());
287
288 EXPECT_EQ(m.erase("tuesday"), 1u);
289
290 EXPECT_EQ(m["monday" ], 1);
291 EXPECT_EQ(m["wednesday"], 3);
292 EXPECT_EQ(m.count("tuesday"), 0u);
293 EXPECT_EQ(m.erase("tuesday"), 0u);
294
295 iter = m.begin();
296 ASSERT_TRUE(iter != m.end());
297 EXPECT_EQ(iter->first, "monday");
298 EXPECT_EQ(iter->second, 1);
299 ++iter;
300 ASSERT_TRUE(iter != m.end());
301 EXPECT_EQ(iter->first, "wednesday");
302 EXPECT_EQ(iter->second, 3);
303 ++iter;
304 EXPECT_TRUE(iter == m.end());
305
306 m["thursday"] = 4;
307 m["friday"] = 5;
308 EXPECT_EQ(m.size(), 4u);
309 EXPECT_FALSE(m.empty());
310 EXPECT_FALSE(m.UsingFullMap());
311
312 m["saturday"] = 6;
313 EXPECT_TRUE(m.UsingFullMap());
314
315 EXPECT_EQ(m.count("friday"), 1u);
316 EXPECT_EQ(m.erase("friday"), 1u);
317 EXPECT_TRUE(m.UsingFullMap());
318 EXPECT_EQ(m.count("friday"), 0u);
319 EXPECT_EQ(m.erase("friday"), 0u);
320
321 EXPECT_EQ(m.size(), 4u);
322 EXPECT_FALSE(m.empty());
323 EXPECT_EQ(m.erase("monday"), 1u);
324 EXPECT_EQ(m.size(), 3u);
325 EXPECT_FALSE(m.empty());
326
327 m.clear();
328 EXPECT_FALSE(m.UsingFullMap());
329 EXPECT_EQ(m.size(), 0u);
330 EXPECT_TRUE(m.empty());
331 }
332
TEST(SmallMap,EraseReturnsIteratorFollowingRemovedElement)333 TEST(SmallMap, EraseReturnsIteratorFollowingRemovedElement) {
334 small_map<std::unordered_map<std::string, int>> m;
335 small_map<std::unordered_map<std::string, int>>::iterator iter;
336
337 m["a"] = 0;
338 m["b"] = 1;
339 m["c"] = 2;
340
341 // Erase first item.
342 auto following_iter = m.erase(m.begin());
343 EXPECT_EQ(m.begin(), following_iter);
344 EXPECT_EQ(2u, m.size());
345 EXPECT_EQ(m.count("a"), 0u);
346 EXPECT_EQ(m.count("b"), 1u);
347 EXPECT_EQ(m.count("c"), 1u);
348
349 // Iterate to last item and erase it.
350 ++following_iter;
351 following_iter = m.erase(following_iter);
352 ASSERT_EQ(1u, m.size());
353 EXPECT_EQ(m.end(), following_iter);
354 EXPECT_EQ(m.count("b"), 0u);
355 EXPECT_EQ(m.count("c"), 1u);
356
357 // Erase remaining item.
358 following_iter = m.erase(m.begin());
359 EXPECT_TRUE(m.empty());
360 EXPECT_EQ(m.end(), following_iter);
361 }
362
TEST(SmallMap,NonHashMap)363 TEST(SmallMap, NonHashMap) {
364 small_map<std::map<int, int>, 4, std::equal_to<int>> m;
365 EXPECT_TRUE(m.empty());
366
367 m[9] = 2;
368 m[0] = 5;
369
370 EXPECT_EQ(m[9], 2);
371 EXPECT_EQ(m[0], 5);
372 EXPECT_EQ(m.size(), 2u);
373 EXPECT_FALSE(m.empty());
374 EXPECT_FALSE(m.UsingFullMap());
375
376 small_map<std::map<int, int>, 4, std::equal_to<int>>::iterator iter(
377 m.begin());
378 ASSERT_TRUE(iter != m.end());
379 EXPECT_EQ(iter->first, 9);
380 EXPECT_EQ(iter->second, 2);
381 ++iter;
382 ASSERT_TRUE(iter != m.end());
383 EXPECT_EQ(iter->first, 0);
384 EXPECT_EQ(iter->second, 5);
385 ++iter;
386 EXPECT_TRUE(iter == m.end());
387
388 m[8] = 23;
389 m[1234] = 90;
390 m[-5] = 6;
391
392 EXPECT_EQ(m[ 9], 2);
393 EXPECT_EQ(m[ 0], 5);
394 EXPECT_EQ(m[1234], 90);
395 EXPECT_EQ(m[ 8], 23);
396 EXPECT_EQ(m[ -5], 6);
397 EXPECT_EQ(m.size(), 5u);
398 EXPECT_FALSE(m.empty());
399 EXPECT_TRUE(m.UsingFullMap());
400
401 iter = m.begin();
402 ASSERT_TRUE(iter != m.end());
403 EXPECT_EQ(iter->first, -5);
404 EXPECT_EQ(iter->second, 6);
405 ++iter;
406 ASSERT_TRUE(iter != m.end());
407 EXPECT_EQ(iter->first, 0);
408 EXPECT_EQ(iter->second, 5);
409 ++iter;
410 ASSERT_TRUE(iter != m.end());
411 EXPECT_EQ(iter->first, 8);
412 EXPECT_EQ(iter->second, 23);
413 ++iter;
414 ASSERT_TRUE(iter != m.end());
415 EXPECT_EQ(iter->first, 9);
416 EXPECT_EQ(iter->second, 2);
417 ++iter;
418 ASSERT_TRUE(iter != m.end());
419 EXPECT_EQ(iter->first, 1234);
420 EXPECT_EQ(iter->second, 90);
421 ++iter;
422 EXPECT_TRUE(iter == m.end());
423 }
424
TEST(SmallMap,DefaultEqualKeyWorks)425 TEST(SmallMap, DefaultEqualKeyWorks) {
426 // If these tests compile, they pass. The EXPECT calls are only there to avoid
427 // unused variable warnings.
428 small_map<std::unordered_map<int, int>> hm;
429 EXPECT_EQ(0u, hm.size());
430 small_map<std::map<int, int>> m;
431 EXPECT_EQ(0u, m.size());
432 }
433
434 namespace {
435
436 class unordered_map_add_item : public std::unordered_map<int, int> {
437 public:
438 unordered_map_add_item() = default;
unordered_map_add_item(const std::pair<int,int> & item)439 explicit unordered_map_add_item(const std::pair<int, int>& item) {
440 insert(item);
441 }
442 };
443
InitMap(unordered_map_add_item * map_ctor)444 void InitMap(unordered_map_add_item* map_ctor) {
445 new (map_ctor) unordered_map_add_item(std::make_pair(0, 0));
446 }
447
448 class unordered_map_add_item_initializer {
449 public:
unordered_map_add_item_initializer(int item_to_add)450 explicit unordered_map_add_item_initializer(int item_to_add)
451 : item_(item_to_add) {}
unordered_map_add_item_initializer()452 unordered_map_add_item_initializer() : item_(0) {}
operator ()(unordered_map_add_item * map_ctor) const453 void operator()(unordered_map_add_item* map_ctor) const {
454 new (map_ctor) unordered_map_add_item(std::make_pair(item_, item_));
455 }
456
457 int item_;
458 };
459
460 } // anonymous namespace
461
TEST(SmallMap,SubclassInitializationWithFunctionPointer)462 TEST(SmallMap, SubclassInitializationWithFunctionPointer) {
463 small_map<unordered_map_add_item, 4, std::equal_to<int>,
464 void (&)(unordered_map_add_item*)>
465 m(InitMap);
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(0));
476
477 m[5] = 5;
478 EXPECT_EQ(6u, m.size());
479 // Our function adds an extra item when we convert to a map.
480 EXPECT_EQ(1u, m.count(0));
481 }
482
TEST(SmallMap,SubclassInitializationWithFunctionObject)483 TEST(SmallMap, SubclassInitializationWithFunctionObject) {
484 small_map<unordered_map_add_item, 4, std::equal_to<int>,
485 unordered_map_add_item_initializer>
486 m(unordered_map_add_item_initializer(-1));
487
488 EXPECT_TRUE(m.empty());
489
490 m[1] = 1;
491 m[2] = 2;
492 m[3] = 3;
493 m[4] = 4;
494
495 EXPECT_EQ(4u, m.size());
496 EXPECT_EQ(0u, m.count(-1));
497
498 m[5] = 5;
499 EXPECT_EQ(6u, m.size());
500 // Our functor adds an extra item when we convert to a map.
501 EXPECT_EQ(1u, m.count(-1));
502 }
503
504 namespace {
505
506 // This class acts as a basic implementation of a move-only type. The canonical
507 // example of such a type is scoped_ptr/unique_ptr.
508 template <typename V>
509 class MoveOnlyType {
510 public:
MoveOnlyType()511 MoveOnlyType() : value_(0) {}
MoveOnlyType(V value)512 explicit MoveOnlyType(V value) : value_(value) {}
513
MoveOnlyType(MoveOnlyType && other)514 MoveOnlyType(MoveOnlyType&& other) {
515 *this = std::move(other);
516 }
517
operator =(MoveOnlyType && other)518 MoveOnlyType& operator=(MoveOnlyType&& other) {
519 value_ = other.value_;
520 other.value_ = 0;
521 return *this;
522 }
523
524 MoveOnlyType(const MoveOnlyType&) = delete;
525 MoveOnlyType& operator=(const MoveOnlyType&) = delete;
526
value() const527 V value() const { return value_; }
528
529 private:
530 V value_;
531 };
532
533 } // namespace
534
TEST(SmallMap,MoveOnlyValueType)535 TEST(SmallMap, MoveOnlyValueType) {
536 small_map<std::map<int, MoveOnlyType<int>>, 2> m;
537
538 m[0] = MoveOnlyType<int>(1);
539 m[1] = MoveOnlyType<int>(2);
540 m.erase(m.begin());
541
542 // small_map will move m[1] to an earlier index in the internal array.
543 EXPECT_EQ(m.size(), 1u);
544 EXPECT_EQ(m[1].value(), 2);
545
546 m[0] = MoveOnlyType<int>(1);
547 // small_map must move the values from the array into the internal std::map.
548 m[2] = MoveOnlyType<int>(3);
549
550 EXPECT_EQ(m.size(), 3u);
551 EXPECT_EQ(m[0].value(), 1);
552 EXPECT_EQ(m[1].value(), 2);
553 EXPECT_EQ(m[2].value(), 3);
554
555 m.erase(m.begin());
556
557 // small_map should also let internal std::map erase with a move-only type.
558 EXPECT_EQ(m.size(), 2u);
559 EXPECT_EQ(m[1].value(), 2);
560 EXPECT_EQ(m[2].value(), 3);
561 }
562
TEST(SmallMap,Emplace)563 TEST(SmallMap, Emplace) {
564 small_map<std::map<size_t, MoveOnlyType<size_t>>> sm;
565
566 // loop through the transition from small map to map.
567 for (size_t i = 1; i <= 10; ++i) {
568 // insert an element
569 auto ret = sm.emplace(i, MoveOnlyType<size_t>(100 * i));
570 EXPECT_TRUE(ret.second);
571 EXPECT_TRUE(ret.first == sm.find(i));
572 EXPECT_EQ(ret.first->first, i);
573 EXPECT_EQ(ret.first->second.value(), 100 * i);
574
575 // try to insert it again with different value, fails, but we still get an
576 // iterator back with the original value.
577 ret = sm.emplace(i, MoveOnlyType<size_t>(i));
578 EXPECT_FALSE(ret.second);
579 EXPECT_TRUE(ret.first == sm.find(i));
580 EXPECT_EQ(ret.first->first, i);
581 EXPECT_EQ(ret.first->second.value(), 100 * i);
582
583 // check the state of the map.
584 for (size_t j = 1; j <= i; ++j) {
585 const auto it = sm.find(j);
586 EXPECT_TRUE(it != sm.end());
587 EXPECT_EQ(it->first, j);
588 EXPECT_EQ(it->second.value(), j * 100);
589 }
590 EXPECT_EQ(sm.size(), i);
591 EXPECT_FALSE(sm.empty());
592 }
593 }
594
595 } // namespace base
596