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
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 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
152template<class inner>
153static bool SmallMapEqual(SmallMap<inner> const& a,
154                          SmallMap<inner> const& b) {
155  return SmallMapIsSubset(a, b) && SmallMapIsSubset(b, a);
156}
157
158TEST(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
204TEST(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
239TEST(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
260TEST(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
334TEST(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
404TEST(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
413namespace {
414
415class hash_map_add_item : public hash_map<int, int> {
416 public:
417  hash_map_add_item() : hash_map<int, int>() {}
418  explicit hash_map_add_item(const std::pair<int, int>& item)
419      : hash_map<int, int>() {
420    insert(item);
421  }
422};
423
424void InitMap(ManualConstructor<hash_map_add_item>* map_ctor) {
425  map_ctor->Init(std::make_pair(0, 0));
426}
427
428class hash_map_add_item_initializer {
429 public:
430  explicit hash_map_add_item_initializer(int item_to_add)
431      : item_(item_to_add) {}
432  hash_map_add_item_initializer()
433      : item_(0) {}
434  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
443TEST(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
463TEST(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