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/logging.h"
  14 #include "base/hash_tables.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 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
 148 template<class inner>
 149 static 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
 167 TEST(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
 213 TEST(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
 248 TEST(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
 269 TEST(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
 343 TEST(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
 413 TEST(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
 422 namespace {
 423
 424 class 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
 433 void InitMap(ManualConstructor<hash_map_add_item>* map_ctor) {
 434   map_ctor->Init(std::make_pair(0, 0));
 435 }
 436
 437 class 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
 452 TEST(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
 472 TEST(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