small_map_unittest.cc revision 2a99a7e74a7f215066514fe81d2bfa6639d9eddd 
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/logging.h"
14#include "base/hash_tables.h"
15#include "testing/gtest/include/gtest/gtest.h"
16
17namespace base {
18
19TEST(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
74TEST(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.
95TEST(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
140template<class inner>
141static void SmallMapToMap(SmallMap<inner> const& src, inner* dest) {
142  typename SmallMap<inner>::const_iterator it;
143  for (it = src.begin(); it != src.end(); ++it) {
144    dest->insert(std::make_pair(it->first, it->second));
145  }
146}
147
148template<class inner>
149static bool SmallMapEqual(SmallMap<inner> const& a,
150                          SmallMap<inner> const& b) {
151  inner ia, ib;
152  SmallMapToMap(a, &ia);
153  SmallMapToMap(b, &ib);
154
155  // On most systems we can use operator== here, but under some lesser STL
156  // implementations it doesn't seem to work. So we manually compare.
157  if (ia.size() != ib.size())
158    return false;
159  for (typename inner::iterator ia_it = ia.begin(), ib_it = ib.begin();
160       ia_it != ia.end(); ++ia_it, ++ib_it) {
161    if (*ia_it != *ib_it)
162      return false;
163  }
164  return true;
165}
166
167TEST(SmallMap, AssignmentOperator) {
168  SmallMap<hash_map<int, int> > src_small;
169  SmallMap<hash_map<int, int> > src_large;
170
171  src_small[1] = 20;
172  src_small[2] = 21;
173  src_small[3] = 22;
174  EXPECT_FALSE(src_small.UsingFullMap());
175
176  src_large[1] = 20;
177  src_large[2] = 21;
178  src_large[3] = 22;
179  src_large[5] = 23;
180  src_large[6] = 24;
181  src_large[7] = 25;
182  EXPECT_TRUE(src_large.UsingFullMap());
183
184  // Assignments to empty.
185  SmallMap<hash_map<int, int> > dest_small;
186  dest_small = src_small;
187  EXPECT_TRUE(SmallMapEqual(dest_small, src_small));
188  EXPECT_EQ(dest_small.UsingFullMap(),
189            src_small.UsingFullMap());
190
191  SmallMap<hash_map<int, int> > dest_large;
192  dest_large = src_large;
193  EXPECT_TRUE(SmallMapEqual(dest_large, src_large));
194  EXPECT_EQ(dest_large.UsingFullMap(),
195            src_large.UsingFullMap());
196
197  // Assignments which assign from full to small, and vice versa.
198  dest_small = src_large;
199  EXPECT_TRUE(SmallMapEqual(dest_small, src_large));
200  EXPECT_EQ(dest_small.UsingFullMap(),
201            src_large.UsingFullMap());
202
203  dest_large = src_small;
204  EXPECT_TRUE(SmallMapEqual(dest_large, src_small));
205  EXPECT_EQ(dest_large.UsingFullMap(),
206            src_small.UsingFullMap());
207
208  // Double check that SmallMapEqual works:
209  dest_large[42] = 666;
210  EXPECT_FALSE(SmallMapEqual(dest_large, src_small));
211}
212
213TEST(SmallMap, Insert) {
214  SmallMap<hash_map<int, int> > sm;
215
216  // loop through the transition from small map to map.
217  for (int i = 1; i <= 10; ++i) {
218    VLOG(1) << "Iteration " << i;
219    // insert an element
220    std::pair<SmallMap<hash_map<int, int> >::iterator,
221        bool> ret;
222    ret = sm.insert(std::make_pair(i, 100*i));
223    EXPECT_TRUE(ret.second);
224    EXPECT_TRUE(ret.first == sm.find(i));
225    EXPECT_EQ(ret.first->first, i);
226    EXPECT_EQ(ret.first->second, 100*i);
227
228    // try to insert it again with different value, fails, but we still get an
229    // iterator back with the original value.
230    ret = sm.insert(std::make_pair(i, -i));
231    EXPECT_FALSE(ret.second);
232    EXPECT_TRUE(ret.first == sm.find(i));
233    EXPECT_EQ(ret.first->first, i);
234    EXPECT_EQ(ret.first->second, 100*i);
235
236    // check the state of the map.
237    for (int j = 1; j <= i; ++j) {
238      SmallMap<hash_map<int, int> >::iterator it = sm.find(j);
239      EXPECT_TRUE(it != sm.end());
240      EXPECT_EQ(it->first, j);
241      EXPECT_EQ(it->second, j * 100);
242    }
243    EXPECT_EQ(sm.size(), static_cast<size_t>(i));
244    EXPECT_FALSE(sm.empty());
245  }
246}
247
248TEST(SmallMap, InsertRange) {
249  // loop through the transition from small map to map.
250  for (int elements = 0; elements <= 10; ++elements) {
251    VLOG(1) << "Elements " << elements;
252    hash_map<int, int> normal_map;
253    for (int i = 1; i <= elements; ++i) {
254      normal_map.insert(std::make_pair(i, 100*i));
255    }
256
257    SmallMap<hash_map<int, int> > sm;
258    sm.insert(normal_map.begin(), normal_map.end());
259    EXPECT_EQ(normal_map.size(), sm.size());
260    for (int i = 1; i <= elements; ++i) {
261      VLOG(1) << "Iteration " << i;
262      EXPECT_TRUE(sm.find(i) != sm.end());
263      EXPECT_EQ(sm.find(i)->first, i);
264      EXPECT_EQ(sm.find(i)->second, 100*i);
265    }
266  }
267}
268
269TEST(SmallMap, Erase) {
270  SmallMap<hash_map<std::string, int> > m;
271  SmallMap<hash_map<std::string, int> >::iterator iter;
272
273  m["monday"] = 1;
274  m["tuesday"] = 2;
275  m["wednesday"] = 3;
276
277  EXPECT_EQ(m["monday"   ], 1);
278  EXPECT_EQ(m["tuesday"  ], 2);
279  EXPECT_EQ(m["wednesday"], 3);
280  EXPECT_EQ(m.count("tuesday"), 1u);
281  EXPECT_FALSE(m.UsingFullMap());
282
283  iter = m.begin();
284  ASSERT_TRUE(iter != m.end());
285  EXPECT_EQ(iter->first, "monday");
286  EXPECT_EQ(iter->second, 1);
287  ++iter;
288  ASSERT_TRUE(iter != m.end());
289  EXPECT_EQ(iter->first, "tuesday");
290  EXPECT_EQ(iter->second, 2);
291  ++iter;
292  ASSERT_TRUE(iter != m.end());
293  EXPECT_EQ(iter->first, "wednesday");
294  EXPECT_EQ(iter->second, 3);
295  ++iter;
296  EXPECT_TRUE(iter == m.end());
297
298  EXPECT_EQ(m.erase("tuesday"), 1u);
299
300  EXPECT_EQ(m["monday"   ], 1);
301  EXPECT_EQ(m["wednesday"], 3);
302  EXPECT_EQ(m.count("tuesday"), 0u);
303  EXPECT_EQ(m.erase("tuesday"), 0u);
304
305  iter = m.begin();
306  ASSERT_TRUE(iter != m.end());
307  EXPECT_EQ(iter->first, "monday");
308  EXPECT_EQ(iter->second, 1);
309  ++iter;
310  ASSERT_TRUE(iter != m.end());
311  EXPECT_EQ(iter->first, "wednesday");
312  EXPECT_EQ(iter->second, 3);
313  ++iter;
314  EXPECT_TRUE(iter == m.end());
315
316  m["thursday"] = 4;
317  m["friday"] = 5;
318  EXPECT_EQ(m.size(), 4u);
319  EXPECT_FALSE(m.empty());
320  EXPECT_FALSE(m.UsingFullMap());
321
322  m["saturday"] = 6;
323  EXPECT_TRUE(m.UsingFullMap());
324
325  EXPECT_EQ(m.count("friday"), 1u);
326  EXPECT_EQ(m.erase("friday"), 1u);
327  EXPECT_TRUE(m.UsingFullMap());
328  EXPECT_EQ(m.count("friday"), 0u);
329  EXPECT_EQ(m.erase("friday"), 0u);
330
331  EXPECT_EQ(m.size(), 4u);
332  EXPECT_FALSE(m.empty());
333  EXPECT_EQ(m.erase("monday"), 1u);
334  EXPECT_EQ(m.size(), 3u);
335  EXPECT_FALSE(m.empty());
336
337  m.clear();
338  EXPECT_FALSE(m.UsingFullMap());
339  EXPECT_EQ(m.size(), 0u);
340  EXPECT_TRUE(m.empty());
341}
342
343TEST(SmallMap, NonHashMap) {
344  SmallMap<std::map<int, int>, 4, std::equal_to<int> > m;
345  EXPECT_TRUE(m.empty());
346
347  m[9] = 2;
348  m[0] = 5;
349
350  EXPECT_EQ(m[9], 2);
351  EXPECT_EQ(m[0], 5);
352  EXPECT_EQ(m.size(), 2u);
353  EXPECT_FALSE(m.empty());
354  EXPECT_FALSE(m.UsingFullMap());
355
356  SmallMap<std::map<int, int>, 4, std::equal_to<int> >::iterator iter(
357      m.begin());
358  ASSERT_TRUE(iter != m.end());
359  EXPECT_EQ(iter->first, 9);
360  EXPECT_EQ(iter->second, 2);
361  ++iter;
362  ASSERT_TRUE(iter != m.end());
363  EXPECT_EQ(iter->first, 0);
364  EXPECT_EQ(iter->second, 5);
365  ++iter;
366  EXPECT_TRUE(iter == m.end());
367  --iter;
368  ASSERT_TRUE(iter != m.end());
369  EXPECT_EQ(iter->first, 0);
370  EXPECT_EQ(iter->second, 5);
371
372  m[8] = 23;
373  m[1234] = 90;
374  m[-5] = 6;
375
376  EXPECT_EQ(m[   9],  2);
377  EXPECT_EQ(m[   0],  5);
378  EXPECT_EQ(m[1234], 90);
379  EXPECT_EQ(m[   8], 23);
380  EXPECT_EQ(m[  -5],  6);
381  EXPECT_EQ(m.size(), 5u);
382  EXPECT_FALSE(m.empty());
383  EXPECT_TRUE(m.UsingFullMap());
384
385  iter = m.begin();
386  ASSERT_TRUE(iter != m.end());
387  EXPECT_EQ(iter->first, -5);
388  EXPECT_EQ(iter->second, 6);
389  ++iter;
390  ASSERT_TRUE(iter != m.end());
391  EXPECT_EQ(iter->first, 0);
392  EXPECT_EQ(iter->second, 5);
393  ++iter;
394  ASSERT_TRUE(iter != m.end());
395  EXPECT_EQ(iter->first, 8);
396  EXPECT_EQ(iter->second, 23);
397  ++iter;
398  ASSERT_TRUE(iter != m.end());
399  EXPECT_EQ(iter->first, 9);
400  EXPECT_EQ(iter->second, 2);
401  ++iter;
402  ASSERT_TRUE(iter != m.end());
403  EXPECT_EQ(iter->first, 1234);
404  EXPECT_EQ(iter->second, 90);
405  ++iter;
406  EXPECT_TRUE(iter == m.end());
407  --iter;
408  ASSERT_TRUE(iter != m.end());
409  EXPECT_EQ(iter->first, 1234);
410  EXPECT_EQ(iter->second, 90);
411}
412
413TEST(SmallMap, DefaultEqualKeyWorks) {
414  // If these tests compile, they pass. The EXPECT calls are only there to avoid
415  // unused variable warnings.
416  SmallMap<hash_map<int, int> > hm;
417  EXPECT_EQ(0u, hm.size());
418  SmallMap<std::map<int, int> > m;
419  EXPECT_EQ(0u, m.size());
420}
421
422namespace {
423
424class hash_map_add_item : public hash_map<int, int> {
425 public:
426  hash_map_add_item() : hash_map<int, int>() {}
427  explicit hash_map_add_item(const std::pair<int, int>& item)
428      : hash_map<int, int>() {
429    insert(item);
430  }
431};
432
433void InitMap(ManualConstructor<hash_map_add_item>* map_ctor) {
434  map_ctor->Init(std::make_pair(0, 0));
435}
436
437class hash_map_add_item_initializer {
438 public:
439  explicit hash_map_add_item_initializer(int item_to_add)
440      : item_(item_to_add) {}
441  hash_map_add_item_initializer()
442      : item_(0) {}
443  void operator()(ManualConstructor<hash_map_add_item>* map_ctor) const {
444    map_ctor->Init(std::make_pair(item_, item_));
445  }
446
447  int item_;
448};
449
450}  // anonymous namespace
451
452TEST(SmallMap, SubclassInitializationWithFunctionPointer) {
453  SmallMap<hash_map_add_item, 4, std::equal_to<int>,
454      void (&)(ManualConstructor<hash_map_add_item>*)> m(InitMap);
455
456  EXPECT_TRUE(m.empty());
457
458  m[1] = 1;
459  m[2] = 2;
460  m[3] = 3;
461  m[4] = 4;
462
463  EXPECT_EQ(4u, m.size());
464  EXPECT_EQ(0u, m.count(0));
465
466  m[5] = 5;
467  EXPECT_EQ(6u, m.size());
468  // Our function adds an extra item when we convert to a map.
469  EXPECT_EQ(1u, m.count(0));
470}
471
472TEST(SmallMap, SubclassInitializationWithFunctionObject) {
473  SmallMap<hash_map_add_item, 4, std::equal_to<int>,
474      hash_map_add_item_initializer> m(hash_map_add_item_initializer(-1));
475
476  EXPECT_TRUE(m.empty());
477
478  m[1] = 1;
479  m[2] = 2;
480  m[3] = 3;
481  m[4] = 4;
482
483  EXPECT_EQ(4u, m.size());
484  EXPECT_EQ(0u, m.count(-1));
485
486  m[5] = 5;
487  EXPECT_EQ(6u, m.size());
488  // Our functor adds an extra item when we convert to a map.
489  EXPECT_EQ(1u, m.count(-1));
490}
491
492}  // namespace base
493