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