| OLD | NEW |
|---|
| (Empty) |
| 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() {} | |
| 418 explicit hash_map_add_item(const std::pair<int, int>& item) { | |
| 419 insert(item); | |
| 420 } | |
| 421 }; | |
| 422 | |
| 423 void InitMap(ManualConstructor<hash_map_add_item>* map_ctor) { | |
| 424 map_ctor->Init(std::make_pair(0, 0)); | |
| 425 } | |
| 426 | |
| 427 class hash_map_add_item_initializer { | |
| 428 public: | |
| 429 explicit hash_map_add_item_initializer(int item_to_add) | |
| 430 : item_(item_to_add) {} | |
| 431 hash_map_add_item_initializer() | |
| 432 : item_(0) {} | |
| 433 void operator()(ManualConstructor<hash_map_add_item>* map_ctor) const { | |
| 434 map_ctor->Init(std::make_pair(item_, item_)); | |
| 435 } | |
| 436 | |
| 437 int item_; | |
| 438 }; | |
| 439 | |
| 440 } // anonymous namespace | |
| 441 | |
| 442 TEST(SmallMap, SubclassInitializationWithFunctionPointer) { | |
| 443 SmallMap<hash_map_add_item, 4, std::equal_to<int>, | |
| 444 void (&)(ManualConstructor<hash_map_add_item>*)> m(InitMap); | |
| 445 | |
| 446 EXPECT_TRUE(m.empty()); | |
| 447 | |
| 448 m[1] = 1; | |
| 449 m[2] = 2; | |
| 450 m[3] = 3; | |
| 451 m[4] = 4; | |
| 452 | |
| 453 EXPECT_EQ(4u, m.size()); | |
| 454 EXPECT_EQ(0u, m.count(0)); | |
| 455 | |
| 456 m[5] = 5; | |
| 457 EXPECT_EQ(6u, m.size()); | |
| 458 // Our function adds an extra item when we convert to a map. | |
| 459 EXPECT_EQ(1u, m.count(0)); | |
| 460 } | |
| 461 | |
| 462 TEST(SmallMap, SubclassInitializationWithFunctionObject) { | |
| 463 SmallMap<hash_map_add_item, 4, std::equal_to<int>, | |
| 464 hash_map_add_item_initializer> m(hash_map_add_item_initializer(-1)); | |
| 465 | |
| 466 EXPECT_TRUE(m.empty()); | |
| 467 | |
| 468 m[1] = 1; | |
| 469 m[2] = 2; | |
| 470 m[3] = 3; | |
| 471 m[4] = 4; | |
| 472 | |
| 473 EXPECT_EQ(4u, m.size()); | |
| 474 EXPECT_EQ(0u, m.count(-1)); | |
| 475 | |
| 476 m[5] = 5; | |
| 477 EXPECT_EQ(6u, m.size()); | |
| 478 // Our functor adds an extra item when we convert to a map. | |
| 479 EXPECT_EQ(1u, m.count(-1)); | |
| 480 } | |
| 481 | |
| 482 } // namespace base | |
| OLD | NEW |
|---|
Chromium Code Reviews
