15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2012 The Chromium Authors. All rights reserved.
25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be
35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file.
45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/containers/small_map.h"
65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <stddef.h>
85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <algorithm>
105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <functional>
115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <map>
125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
137d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)#include "base/containers/hash_tables.h"
145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/logging.h"
155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "testing/gtest/include/gtest/gtest.h"
165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace base {
185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(SmallMap, General) {
205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SmallMap<hash_map<int, int> > m;
215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_TRUE(m.empty());
235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  m[0] = 5;
255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_FALSE(m.empty());
275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m.size(), 1u);
285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  m[9] = 2;
305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_FALSE(m.empty());
325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m.size(), 2u);
335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m[9], 2);
355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m[0], 5);
365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_FALSE(m.UsingFullMap());
375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SmallMap<hash_map<int, int> >::iterator iter(m.begin());
395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ASSERT_TRUE(iter != m.end());
405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->first, 0);
415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->second, 5);
425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ++iter;
435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ASSERT_TRUE(iter != m.end());
445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ((*iter).first, 9);
455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ((*iter).second, 2);
465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ++iter;
475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_TRUE(iter == m.end());
485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  m[8] = 23;
505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  m[1234] = 90;
515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  m[-5] = 6;
525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m[   9],  2);
545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m[   0],  5);
555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m[1234], 90);
565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m[   8], 23);
575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m[  -5],  6);
585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m.size(), 5u);
595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_FALSE(m.empty());
605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_TRUE(m.UsingFullMap());
615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  iter = m.begin();
635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < 5; i++) {
645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_TRUE(iter != m.end());
655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    ++iter;
665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_TRUE(iter == m.end());
685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  const SmallMap<hash_map<int, int> >& ref = m;
705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_TRUE(ref.find(1234) != m.end());
715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_TRUE(ref.find(5678) == m.end());
725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(SmallMap, PostFixIteratorIncrement) {
755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SmallMap<hash_map<int, int> > m;
765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  m[0] = 5;
775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  m[2] = 3;
785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  {
805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    SmallMap<hash_map<int, int> >::iterator iter(m.begin());
815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    SmallMap<hash_map<int, int> >::iterator last(iter++);
825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    ++last;
835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_TRUE(last == iter);
845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  {
875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    SmallMap<hash_map<int, int> >::const_iterator iter(m.begin());
885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    SmallMap<hash_map<int, int> >::const_iterator last(iter++);
895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    ++last;
905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_TRUE(last == iter);
915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Based on the General testcase.
955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(SmallMap, CopyConstructor) {
965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SmallMap<hash_map<int, int> > src;
975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  {
995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    SmallMap<hash_map<int, int> > m(src);
1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_TRUE(m.empty());
1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  src[0] = 5;
1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  {
1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    SmallMap<hash_map<int, int> > m(src);
1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_FALSE(m.empty());
1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_EQ(m.size(), 1u);
1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  src[9] = 2;
1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  {
1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    SmallMap<hash_map<int, int> > m(src);
1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_FALSE(m.empty());
1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_EQ(m.size(), 2u);
1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_EQ(m[9], 2);
1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_EQ(m[0], 5);
1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_FALSE(m.UsingFullMap());
1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  src[8] = 23;
1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  src[1234] = 90;
1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  src[-5] = 6;
1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  {
1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    SmallMap<hash_map<int, int> > m(src);
1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_EQ(m[   9],  2);
1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_EQ(m[   0],  5);
1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_EQ(m[1234], 90);
1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_EQ(m[   8], 23);
1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_EQ(m[  -5],  6);
1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_EQ(m.size(), 5u);
1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_FALSE(m.empty());
1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_TRUE(m.UsingFullMap());
1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<class inner>
1415d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)static bool SmallMapIsSubset(SmallMap<inner> const& a,
1425d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)                             SmallMap<inner> const& b) {
1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  typename SmallMap<inner>::const_iterator it;
1445d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  for (it = a.begin(); it != a.end(); ++it) {
1455d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    typename SmallMap<inner>::const_iterator it_in_b = b.find(it->first);
1465d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    if (it_in_b == b.end() || it_in_b->second != it->second)
1475d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      return false;
1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
1495d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  return true;
1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<class inner>
1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static bool SmallMapEqual(SmallMap<inner> const& a,
1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)                          SmallMap<inner> const& b) {
1555d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  return SmallMapIsSubset(a, b) && SmallMapIsSubset(b, a);
1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(SmallMap, AssignmentOperator) {
1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SmallMap<hash_map<int, int> > src_small;
1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SmallMap<hash_map<int, int> > src_large;
1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  src_small[1] = 20;
1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  src_small[2] = 21;
1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  src_small[3] = 22;
1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_FALSE(src_small.UsingFullMap());
1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  src_large[1] = 20;
1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  src_large[2] = 21;
1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  src_large[3] = 22;
1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  src_large[5] = 23;
1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  src_large[6] = 24;
1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  src_large[7] = 25;
1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_TRUE(src_large.UsingFullMap());
1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Assignments to empty.
1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SmallMap<hash_map<int, int> > dest_small;
1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  dest_small = src_small;
1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_TRUE(SmallMapEqual(dest_small, src_small));
1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(dest_small.UsingFullMap(),
1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)            src_small.UsingFullMap());
1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SmallMap<hash_map<int, int> > dest_large;
1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  dest_large = src_large;
1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_TRUE(SmallMapEqual(dest_large, src_large));
1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(dest_large.UsingFullMap(),
1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)            src_large.UsingFullMap());
1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Assignments which assign from full to small, and vice versa.
1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  dest_small = src_large;
1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_TRUE(SmallMapEqual(dest_small, src_large));
1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(dest_small.UsingFullMap(),
1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)            src_large.UsingFullMap());
1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  dest_large = src_small;
1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_TRUE(SmallMapEqual(dest_large, src_small));
1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(dest_large.UsingFullMap(),
1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)            src_small.UsingFullMap());
1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Double check that SmallMapEqual works:
2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  dest_large[42] = 666;
2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_FALSE(SmallMapEqual(dest_large, src_small));
2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(SmallMap, Insert) {
2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SmallMap<hash_map<int, int> > sm;
2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // loop through the transition from small map to map.
2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 1; i <= 10; ++i) {
2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    VLOG(1) << "Iteration " << i;
2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // insert an element
2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    std::pair<SmallMap<hash_map<int, int> >::iterator,
2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)        bool> ret;
2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    ret = sm.insert(std::make_pair(i, 100*i));
2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_TRUE(ret.second);
2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_TRUE(ret.first == sm.find(i));
2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_EQ(ret.first->first, i);
2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_EQ(ret.first->second, 100*i);
2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // try to insert it again with different value, fails, but we still get an
2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // iterator back with the original value.
2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    ret = sm.insert(std::make_pair(i, -i));
2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_FALSE(ret.second);
2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_TRUE(ret.first == sm.find(i));
2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_EQ(ret.first->first, i);
2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_EQ(ret.first->second, 100*i);
2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // check the state of the map.
2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    for (int j = 1; j <= i; ++j) {
2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      SmallMap<hash_map<int, int> >::iterator it = sm.find(j);
2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      EXPECT_TRUE(it != sm.end());
2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      EXPECT_EQ(it->first, j);
2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      EXPECT_EQ(it->second, j * 100);
2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_EQ(sm.size(), static_cast<size_t>(i));
2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_FALSE(sm.empty());
2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(SmallMap, InsertRange) {
2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // loop through the transition from small map to map.
2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int elements = 0; elements <= 10; ++elements) {
2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    VLOG(1) << "Elements " << elements;
2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    hash_map<int, int> normal_map;
2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    for (int i = 1; i <= elements; ++i) {
2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      normal_map.insert(std::make_pair(i, 100*i));
2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    SmallMap<hash_map<int, int> > sm;
2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    sm.insert(normal_map.begin(), normal_map.end());
2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_EQ(normal_map.size(), sm.size());
2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    for (int i = 1; i <= elements; ++i) {
2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      VLOG(1) << "Iteration " << i;
2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      EXPECT_TRUE(sm.find(i) != sm.end());
2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      EXPECT_EQ(sm.find(i)->first, i);
2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      EXPECT_EQ(sm.find(i)->second, 100*i);
2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(SmallMap, Erase) {
2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SmallMap<hash_map<std::string, int> > m;
2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SmallMap<hash_map<std::string, int> >::iterator iter;
2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  m["monday"] = 1;
2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  m["tuesday"] = 2;
2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  m["wednesday"] = 3;
2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m["monday"   ], 1);
2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m["tuesday"  ], 2);
2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m["wednesday"], 3);
2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m.count("tuesday"), 1u);
2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_FALSE(m.UsingFullMap());
2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  iter = m.begin();
2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ASSERT_TRUE(iter != m.end());
2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->first, "monday");
2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->second, 1);
2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ++iter;
2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ASSERT_TRUE(iter != m.end());
2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->first, "tuesday");
2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->second, 2);
2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ++iter;
2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ASSERT_TRUE(iter != m.end());
2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->first, "wednesday");
2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->second, 3);
2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ++iter;
2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_TRUE(iter == m.end());
2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m.erase("tuesday"), 1u);
2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m["monday"   ], 1);
2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m["wednesday"], 3);
2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m.count("tuesday"), 0u);
2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m.erase("tuesday"), 0u);
2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  iter = m.begin();
2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ASSERT_TRUE(iter != m.end());
2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->first, "monday");
2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->second, 1);
3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ++iter;
3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ASSERT_TRUE(iter != m.end());
3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->first, "wednesday");
3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->second, 3);
3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ++iter;
3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_TRUE(iter == m.end());
3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  m["thursday"] = 4;
3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  m["friday"] = 5;
3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m.size(), 4u);
3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_FALSE(m.empty());
3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_FALSE(m.UsingFullMap());
3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  m["saturday"] = 6;
3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_TRUE(m.UsingFullMap());
3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m.count("friday"), 1u);
3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m.erase("friday"), 1u);
3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_TRUE(m.UsingFullMap());
3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m.count("friday"), 0u);
3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m.erase("friday"), 0u);
3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m.size(), 4u);
3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_FALSE(m.empty());
3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m.erase("monday"), 1u);
3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m.size(), 3u);
3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_FALSE(m.empty());
3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  m.clear();
3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_FALSE(m.UsingFullMap());
3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m.size(), 0u);
3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_TRUE(m.empty());
3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(SmallMap, NonHashMap) {
3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SmallMap<std::map<int, int>, 4, std::equal_to<int> > m;
3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_TRUE(m.empty());
3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  m[9] = 2;
3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  m[0] = 5;
3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m[9], 2);
3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m[0], 5);
3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m.size(), 2u);
3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_FALSE(m.empty());
3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_FALSE(m.UsingFullMap());
3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SmallMap<std::map<int, int>, 4, std::equal_to<int> >::iterator iter(
3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      m.begin());
3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ASSERT_TRUE(iter != m.end());
3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->first, 9);
3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->second, 2);
3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ++iter;
3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ASSERT_TRUE(iter != m.end());
3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->first, 0);
3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->second, 5);
3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ++iter;
3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_TRUE(iter == m.end());
3585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  --iter;
3595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ASSERT_TRUE(iter != m.end());
3605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->first, 0);
3615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->second, 5);
3625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  m[8] = 23;
3645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  m[1234] = 90;
3655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  m[-5] = 6;
3665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m[   9],  2);
3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m[   0],  5);
3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m[1234], 90);
3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m[   8], 23);
3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m[  -5],  6);
3725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(m.size(), 5u);
3735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_FALSE(m.empty());
3745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_TRUE(m.UsingFullMap());
3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  iter = m.begin();
3775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ASSERT_TRUE(iter != m.end());
3785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->first, -5);
3795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->second, 6);
3805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ++iter;
3815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ASSERT_TRUE(iter != m.end());
3825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->first, 0);
3835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->second, 5);
3845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ++iter;
3855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ASSERT_TRUE(iter != m.end());
3865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->first, 8);
3875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->second, 23);
3885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ++iter;
3895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ASSERT_TRUE(iter != m.end());
3905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->first, 9);
3915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->second, 2);
3925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ++iter;
3935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ASSERT_TRUE(iter != m.end());
3945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->first, 1234);
3955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->second, 90);
3965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ++iter;
3975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_TRUE(iter == m.end());
3985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  --iter;
3995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ASSERT_TRUE(iter != m.end());
4005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->first, 1234);
4015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(iter->second, 90);
4025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
4035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(SmallMap, DefaultEqualKeyWorks) {
4055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // If these tests compile, they pass. The EXPECT calls are only there to avoid
4065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // unused variable warnings.
4075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SmallMap<hash_map<int, int> > hm;
4085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(0u, hm.size());
4095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SmallMap<std::map<int, int> > m;
4105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(0u, m.size());
4115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
4125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace {
4145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class hash_map_add_item : public hash_map<int, int> {
4165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public:
4175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  hash_map_add_item() : hash_map<int, int>() {}
4182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  explicit hash_map_add_item(const std::pair<int, int>& item)
4192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)      : hash_map<int, int>() {
4205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    insert(item);
4215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
4225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)};
4235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void InitMap(ManualConstructor<hash_map_add_item>* map_ctor) {
4255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  map_ctor->Init(std::make_pair(0, 0));
4265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
4275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class hash_map_add_item_initializer {
4295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public:
4305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  explicit hash_map_add_item_initializer(int item_to_add)
4315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      : item_(item_to_add) {}
4325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  hash_map_add_item_initializer()
4335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      : item_(0) {}
4345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void operator()(ManualConstructor<hash_map_add_item>* map_ctor) const {
4355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    map_ctor->Init(std::make_pair(item_, item_));
4365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
4375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int item_;
4395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)};
4405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}  // anonymous namespace
4425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(SmallMap, SubclassInitializationWithFunctionPointer) {
4445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SmallMap<hash_map_add_item, 4, std::equal_to<int>,
4455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      void (&)(ManualConstructor<hash_map_add_item>*)> m(InitMap);
4465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_TRUE(m.empty());
4485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  m[1] = 1;
4505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  m[2] = 2;
4515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  m[3] = 3;
4525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  m[4] = 4;
4535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(4u, m.size());
4555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(0u, m.count(0));
4565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  m[5] = 5;
4585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(6u, m.size());
4595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Our function adds an extra item when we convert to a map.
4605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(1u, m.count(0));
4615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
4625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(SmallMap, SubclassInitializationWithFunctionObject) {
4645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SmallMap<hash_map_add_item, 4, std::equal_to<int>,
4655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      hash_map_add_item_initializer> m(hash_map_add_item_initializer(-1));
4665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_TRUE(m.empty());
4685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  m[1] = 1;
4705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  m[2] = 2;
4715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  m[3] = 3;
4725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  m[4] = 4;
4735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(4u, m.size());
4755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(0u, m.count(-1));
4765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  m[5] = 5;
4785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(6u, m.size());
4795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Our functor adds an extra item when we convert to a map.
4805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(1u, m.count(-1));
4815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
4825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}  // namespace base
484