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 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 493
