base/containers/small_map_unittest.cc

   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
  17 namespace base {
  18
  19 TEST(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
  74 TEST(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.
  95 TEST(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
 140 template<class inner>
 141 static 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
 152 template<class inner>
 153 static bool SmallMapEqual(SmallMap<inner> const& a,
 154                           SmallMap<inner> const& b) {
 155   return SmallMapIsSubset(a, b) && SmallMapIsSubset(b, a);
 156 }
 157
 158 TEST(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
 204 TEST(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
 239 TEST(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
 260 TEST(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
 334 TEST(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
 404 TEST(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
 413 namespace {
 414
 415 class 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
 424 void InitMap(ManualConstructor<hash_map_add_item>* map_ctor) {
 425   map_ctor->Init(std::make_pair(0, 0));
 426 }
 427
 428 class 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
 443 TEST(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
 463 TEST(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