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 --iter;
388 ASSERT_TRUE(iter != m.end());
389 EXPECT_EQ(iter->first, 0);
390 EXPECT_EQ(iter->second, 5);
391
392 m[8] = 23;
393 m[1234] = 90;
394 m[-5] = 6;
395
396 EXPECT_EQ(m[ 9], 2);
397 EXPECT_EQ(m[ 0], 5);
398 EXPECT_EQ(m[1234], 90);
399 EXPECT_EQ(m[ 8], 23);
400 EXPECT_EQ(m[ -5], 6);
401 EXPECT_EQ(m.size(), 5u);
402 EXPECT_FALSE(m.empty());
403 EXPECT_TRUE(m.UsingFullMap());
404
405 iter = m.begin();
406 ASSERT_TRUE(iter != m.end());
407 EXPECT_EQ(iter->first, -5);
408 EXPECT_EQ(iter->second, 6);
409 ++iter;
410 ASSERT_TRUE(iter != m.end());
411 EXPECT_EQ(iter->first, 0);
412 EXPECT_EQ(iter->second, 5);
413 ++iter;
414 ASSERT_TRUE(iter != m.end());
415 EXPECT_EQ(iter->first, 8);
416 EXPECT_EQ(iter->second, 23);
417 ++iter;
418 ASSERT_TRUE(iter != m.end());
419 EXPECT_EQ(iter->first, 9);
420 EXPECT_EQ(iter->second, 2);
421 ++iter;
422 ASSERT_TRUE(iter != m.end());
423 EXPECT_EQ(iter->first, 1234);
424 EXPECT_EQ(iter->second, 90);
425 ++iter;
426 EXPECT_TRUE(iter == m.end());
427 --iter;
428 ASSERT_TRUE(iter != m.end());
429 EXPECT_EQ(iter->first, 1234);
430 EXPECT_EQ(iter->second, 90);
431 }
432
TEST(SmallMap,DefaultEqualKeyWorks)433 TEST(SmallMap, DefaultEqualKeyWorks) {
434 // If these tests compile, they pass. The EXPECT calls are only there to avoid
435 // unused variable warnings.
436 small_map<std::unordered_map<int, int>> hm;
437 EXPECT_EQ(0u, hm.size());
438 small_map<std::map<int, int>> m;
439 EXPECT_EQ(0u, m.size());
440 }
441
442 namespace {
443
444 class unordered_map_add_item : public std::unordered_map<int, int> {
445 public:
446 unordered_map_add_item() = default;
unordered_map_add_item(const std::pair<int,int> & item)447 explicit unordered_map_add_item(const std::pair<int, int>& item) {
448 insert(item);
449 }
450 };
451
InitMap(unordered_map_add_item * map_ctor)452 void InitMap(unordered_map_add_item* map_ctor) {
453 new (map_ctor) unordered_map_add_item(std::make_pair(0, 0));
454 }
455
456 class unordered_map_add_item_initializer {
457 public:
unordered_map_add_item_initializer(int item_to_add)458 explicit unordered_map_add_item_initializer(int item_to_add)
459 : item_(item_to_add) {}
unordered_map_add_item_initializer()460 unordered_map_add_item_initializer() : item_(0) {}
operator ()(unordered_map_add_item * map_ctor) const461 void operator()(unordered_map_add_item* map_ctor) const {
462 new (map_ctor) unordered_map_add_item(std::make_pair(item_, item_));
463 }
464
465 int item_;
466 };
467
468 } // anonymous namespace
469
TEST(SmallMap,SubclassInitializationWithFunctionPointer)470 TEST(SmallMap, SubclassInitializationWithFunctionPointer) {
471 small_map<unordered_map_add_item, 4, std::equal_to<int>,
472 void (&)(unordered_map_add_item*)>
473 m(InitMap);
474
475 EXPECT_TRUE(m.empty());
476
477 m[1] = 1;
478 m[2] = 2;
479 m[3] = 3;
480 m[4] = 4;
481
482 EXPECT_EQ(4u, m.size());
483 EXPECT_EQ(0u, m.count(0));
484
485 m[5] = 5;
486 EXPECT_EQ(6u, m.size());
487 // Our function adds an extra item when we convert to a map.
488 EXPECT_EQ(1u, m.count(0));
489 }
490
TEST(SmallMap,SubclassInitializationWithFunctionObject)491 TEST(SmallMap, SubclassInitializationWithFunctionObject) {
492 small_map<unordered_map_add_item, 4, std::equal_to<int>,
493 unordered_map_add_item_initializer>
494 m(unordered_map_add_item_initializer(-1));
495
496 EXPECT_TRUE(m.empty());
497
498 m[1] = 1;
499 m[2] = 2;
500 m[3] = 3;
501 m[4] = 4;
502
503 EXPECT_EQ(4u, m.size());
504 EXPECT_EQ(0u, m.count(-1));
505
506 m[5] = 5;
507 EXPECT_EQ(6u, m.size());
508 // Our functor adds an extra item when we convert to a map.
509 EXPECT_EQ(1u, m.count(-1));
510 }
511
512 namespace {
513
514 // This class acts as a basic implementation of a move-only type. The canonical
515 // example of such a type is scoped_ptr/unique_ptr.
516 template <typename V>
517 class MoveOnlyType {
518 public:
MoveOnlyType()519 MoveOnlyType() : value_(0) {}
MoveOnlyType(V value)520 explicit MoveOnlyType(V value) : value_(value) {}
521
MoveOnlyType(MoveOnlyType && other)522 MoveOnlyType(MoveOnlyType&& other) {
523 *this = std::move(other);
524 }
525
operator =(MoveOnlyType && other)526 MoveOnlyType& operator=(MoveOnlyType&& other) {
527 value_ = other.value_;
528 other.value_ = 0;
529 return *this;
530 }
531
532 MoveOnlyType(const MoveOnlyType&) = delete;
533 MoveOnlyType& operator=(const MoveOnlyType&) = delete;
534
value() const535 V value() const { return value_; }
536
537 private:
538 V value_;
539 };
540
541 } // namespace
542
TEST(SmallMap,MoveOnlyValueType)543 TEST(SmallMap, MoveOnlyValueType) {
544 small_map<std::map<int, MoveOnlyType<int>>, 2> m;
545
546 m[0] = MoveOnlyType<int>(1);
547 m[1] = MoveOnlyType<int>(2);
548 m.erase(m.begin());
549
550 // small_map will move m[1] to an earlier index in the internal array.
551 EXPECT_EQ(m.size(), 1u);
552 EXPECT_EQ(m[1].value(), 2);
553
554 m[0] = MoveOnlyType<int>(1);
555 // small_map must move the values from the array into the internal std::map.
556 m[2] = MoveOnlyType<int>(3);
557
558 EXPECT_EQ(m.size(), 3u);
559 EXPECT_EQ(m[0].value(), 1);
560 EXPECT_EQ(m[1].value(), 2);
561 EXPECT_EQ(m[2].value(), 3);
562
563 m.erase(m.begin());
564
565 // small_map should also let internal std::map erase with a move-only type.
566 EXPECT_EQ(m.size(), 2u);
567 EXPECT_EQ(m[1].value(), 2);
568 EXPECT_EQ(m[2].value(), 3);
569 }
570
TEST(SmallMap,Emplace)571 TEST(SmallMap, Emplace) {
572 small_map<std::map<size_t, MoveOnlyType<size_t>>> sm;
573
574 // loop through the transition from small map to map.
575 for (size_t i = 1; i <= 10; ++i) {
576 // insert an element
577 auto ret = sm.emplace(i, MoveOnlyType<size_t>(100 * i));
578 EXPECT_TRUE(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 // try to insert it again with different value, fails, but we still get an
584 // iterator back with the original value.
585 ret = sm.emplace(i, MoveOnlyType<size_t>(i));
586 EXPECT_FALSE(ret.second);
587 EXPECT_TRUE(ret.first == sm.find(i));
588 EXPECT_EQ(ret.first->first, i);
589 EXPECT_EQ(ret.first->second.value(), 100 * i);
590
591 // check the state of the map.
592 for (size_t j = 1; j <= i; ++j) {
593 const auto it = sm.find(j);
594 EXPECT_TRUE(it != sm.end());
595 EXPECT_EQ(it->first, j);
596 EXPECT_EQ(it->second.value(), j * 100);
597 }
598 EXPECT_EQ(sm.size(), i);
599 EXPECT_FALSE(sm.empty());
600 }
601 }
602
603 } // namespace base
604