1 /* Copyright 2016 The TensorFlow Authors. All Rights Reserved. 2 3 Licensed under the Apache License, Version 2.0 (the "License"); 4 you may not use this file except in compliance with the License. 5 You may obtain a copy of the License at 6 7 http://www.apache.org/licenses/LICENSE-2.0 8 9 Unless required by applicable law or agreed to in writing, software 10 distributed under the License is distributed on an "AS IS" BASIS, 11 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 See the License for the specific language governing permissions and 13 limitations under the License. 14 ==============================================================================*/ 15 16 #include "tensorflow/core/lib/gtl/flatmap.h" 17 18 #include <algorithm> 19 #include <string> 20 #include <unordered_map> 21 #include <vector> 22 #include "tensorflow/core/lib/hash/hash.h" 23 #include "tensorflow/core/platform/test.h" 24 #include "tensorflow/core/platform/types.h" 25 26 namespace tensorflow { 27 namespace gtl { 28 namespace { 29 30 typedef FlatMap<int64, int32> NumMap; 31 32 // If map has an entry for k, return the corresponding value, else return def. 33 int32 Get(const NumMap& map, int64 k, int32 def = -1) { 34 auto iter = map.find(k); 35 if (iter == map.end()) { 36 EXPECT_EQ(map.count(k), 0); 37 return def; 38 } else { 39 EXPECT_EQ(map.count(k), 1); 40 EXPECT_EQ(&map.at(k), &iter->second); 41 EXPECT_EQ(iter->first, k); 42 return iter->second; 43 } 44 } 45 46 // Return contents of map as a sorted list of pairs. 47 typedef std::vector<std::pair<int64, int32>> NumMapContents; 48 NumMapContents Contents(const NumMap& map) { 49 NumMapContents result; 50 for (const auto& p : map) { 51 result.push_back({p.first, p.second}); 52 } 53 std::sort(result.begin(), result.end()); 54 return result; 55 } 56 57 // Fill entries with keys [start,limit). 58 void Fill(NumMap* map, int64 start, int64 limit) { 59 for (int64 i = start; i < limit; i++) { 60 map->insert({i, i * 100}); 61 } 62 } 63 64 TEST(FlatMapTest, Find) { 65 NumMap map; 66 EXPECT_EQ(Get(map, 1), -1); 67 map.insert({1, 100}); 68 map.insert({2, 200}); 69 EXPECT_EQ(Get(map, 1), 100); 70 EXPECT_EQ(Get(map, 2), 200); 71 EXPECT_EQ(Get(map, 3), -1); 72 } 73 74 TEST(FlatMapTest, Insert) { 75 NumMap map; 76 EXPECT_EQ(Get(map, 1), -1); 77 78 // New entry. 79 auto result = map.insert({1, 100}); 80 EXPECT_TRUE(result.second); 81 EXPECT_EQ(result.first->first, 1); 82 EXPECT_EQ(result.first->second, 100); 83 EXPECT_EQ(Get(map, 1), 100); 84 85 // Attempt to insert over existing entry. 86 result = map.insert({1, 200}); 87 EXPECT_FALSE(result.second); 88 EXPECT_EQ(result.first->first, 1); 89 EXPECT_EQ(result.first->second, 100); 90 EXPECT_EQ(Get(map, 1), 100); 91 92 // Overwrite through iterator. 93 result.first->second = 300; 94 EXPECT_EQ(result.first->second, 300); 95 EXPECT_EQ(Get(map, 1), 300); 96 97 // Should get updated value. 98 result = map.insert({1, 400}); 99 EXPECT_FALSE(result.second); 100 EXPECT_EQ(result.first->first, 1); 101 EXPECT_EQ(result.first->second, 300); 102 EXPECT_EQ(Get(map, 1), 300); 103 } 104 105 TEST(FlatMapTest, InsertGrowth) { 106 NumMap map; 107 const int n = 100; 108 Fill(&map, 0, 100); 109 EXPECT_EQ(map.size(), n); 110 for (int i = 0; i < n; i++) { 111 EXPECT_EQ(Get(map, i), i * 100) << i; 112 } 113 } 114 115 TEST(FlatMapTest, Emplace) { 116 NumMap map; 117 118 // New entry. 119 auto result = map.emplace(1, 100); 120 EXPECT_TRUE(result.second); 121 EXPECT_EQ(result.first->first, 1); 122 EXPECT_EQ(result.first->second, 100); 123 EXPECT_EQ(Get(map, 1), 100); 124 125 // Attempt to insert over existing entry. 126 result = map.emplace(1, 200); 127 EXPECT_FALSE(result.second); 128 EXPECT_EQ(result.first->first, 1); 129 EXPECT_EQ(result.first->second, 100); 130 EXPECT_EQ(Get(map, 1), 100); 131 132 // Overwrite through iterator. 133 result.first->second = 300; 134 EXPECT_EQ(result.first->second, 300); 135 EXPECT_EQ(Get(map, 1), 300); 136 137 // Update a second value 138 result = map.emplace(2, 400); 139 EXPECT_TRUE(result.second); 140 EXPECT_EQ(result.first->first, 2); 141 EXPECT_EQ(result.first->second, 400); 142 EXPECT_EQ(Get(map, 2), 400); 143 } 144 145 TEST(FlatMapTest, EmplaceUniquePtr) { 146 FlatMap<int64, std::unique_ptr<string>> smap; 147 smap.emplace(1, std::unique_ptr<string>(new string("hello"))); 148 } 149 150 TEST(FlatMapTest, Size) { 151 NumMap map; 152 EXPECT_EQ(map.size(), 0); 153 154 map.insert({1, 100}); 155 map.insert({2, 200}); 156 EXPECT_EQ(map.size(), 2); 157 } 158 159 TEST(FlatMapTest, Empty) { 160 NumMap map; 161 EXPECT_TRUE(map.empty()); 162 163 map.insert({1, 100}); 164 map.insert({2, 200}); 165 EXPECT_FALSE(map.empty()); 166 } 167 168 TEST(FlatMapTest, ArrayOperator) { 169 NumMap map; 170 171 // Create new element if not found. 172 auto v1 = &map[1]; 173 EXPECT_EQ(*v1, 0); 174 EXPECT_EQ(Get(map, 1), 0); 175 176 // Write through returned reference. 177 *v1 = 100; 178 EXPECT_EQ(map[1], 100); 179 EXPECT_EQ(Get(map, 1), 100); 180 181 // Reuse existing element if found. 182 auto v1a = &map[1]; 183 EXPECT_EQ(v1, v1a); 184 EXPECT_EQ(*v1, 100); 185 186 // Create another element. 187 map[2] = 200; 188 EXPECT_EQ(Get(map, 1), 100); 189 EXPECT_EQ(Get(map, 2), 200); 190 } 191 192 TEST(FlatMapTest, Count) { 193 NumMap map; 194 EXPECT_EQ(map.count(1), 0); 195 EXPECT_EQ(map.count(2), 0); 196 197 map.insert({1, 100}); 198 EXPECT_EQ(map.count(1), 1); 199 EXPECT_EQ(map.count(2), 0); 200 201 map.insert({2, 200}); 202 EXPECT_EQ(map.count(1), 1); 203 EXPECT_EQ(map.count(2), 1); 204 } 205 206 TEST(FlatMapTest, Iter) { 207 NumMap map; 208 EXPECT_EQ(Contents(map), NumMapContents()); 209 210 map.insert({1, 100}); 211 map.insert({2, 200}); 212 EXPECT_EQ(Contents(map), NumMapContents({{1, 100}, {2, 200}})); 213 } 214 215 TEST(FlatMapTest, Erase) { 216 NumMap map; 217 EXPECT_EQ(map.erase(1), 0); 218 map[1] = 100; 219 map[2] = 200; 220 EXPECT_EQ(map.erase(3), 0); 221 EXPECT_EQ(map.erase(1), 1); 222 EXPECT_EQ(map.size(), 1); 223 EXPECT_EQ(Get(map, 2), 200); 224 EXPECT_EQ(Contents(map), NumMapContents({{2, 200}})); 225 EXPECT_EQ(map.erase(2), 1); 226 EXPECT_EQ(Contents(map), NumMapContents()); 227 } 228 229 TEST(FlatMapTest, EraseIter) { 230 NumMap map; 231 Fill(&map, 1, 11); 232 size_t size = 10; 233 for (auto iter = map.begin(); iter != map.end();) { 234 iter = map.erase(iter); 235 size--; 236 EXPECT_EQ(map.size(), size); 237 } 238 EXPECT_EQ(Contents(map), NumMapContents()); 239 } 240 241 TEST(FlatMapTest, EraseIterPair) { 242 NumMap map; 243 Fill(&map, 1, 11); 244 NumMap expected; 245 auto p1 = map.begin(); 246 expected.insert(*p1); 247 ++p1; 248 expected.insert(*p1); 249 ++p1; 250 auto p2 = map.end(); 251 EXPECT_EQ(map.erase(p1, p2), map.end()); 252 EXPECT_EQ(map.size(), 2); 253 EXPECT_EQ(Contents(map), Contents(expected)); 254 } 255 256 TEST(FlatMapTest, EraseLongChains) { 257 // Make a map with lots of elements and erase a bunch of them to ensure 258 // that we are likely to hit them on future lookups. 259 NumMap map; 260 const int num = 128; 261 Fill(&map, 0, num); 262 for (int i = 0; i < num; i += 3) { 263 EXPECT_EQ(map.erase(i), 1); 264 } 265 for (int i = 0; i < num; i++) { 266 if ((i % 3) != 0) { 267 EXPECT_EQ(Get(map, i), i * 100); 268 } else { 269 EXPECT_EQ(map.count(i), 0); 270 } 271 } 272 273 // Erase remainder to trigger table shrinking. 274 const size_t orig_buckets = map.bucket_count(); 275 for (int i = 0; i < num; i++) { 276 map.erase(i); 277 } 278 EXPECT_TRUE(map.empty()); 279 EXPECT_EQ(map.bucket_count(), orig_buckets); 280 map[1] = 100; // Actual shrinking is triggered by an insert. 281 EXPECT_LT(map.bucket_count(), orig_buckets); 282 } 283 284 TEST(FlatMap, AlternatingInsertRemove) { 285 NumMap map; 286 map.insert({1000, 1000}); 287 map.insert({2000, 1000}); 288 map.insert({3000, 1000}); 289 for (int i = 0; i < 10000; i++) { 290 map.insert({i, i}); 291 map.erase(i); 292 } 293 } 294 295 TEST(FlatMap, ClearNoResize) { 296 NumMap map; 297 Fill(&map, 0, 100); 298 const size_t orig = map.bucket_count(); 299 map.clear_no_resize(); 300 EXPECT_EQ(map.size(), 0); 301 EXPECT_EQ(Contents(map), NumMapContents()); 302 EXPECT_EQ(map.bucket_count(), orig); 303 } 304 305 TEST(FlatMap, Clear) { 306 NumMap map; 307 Fill(&map, 0, 100); 308 const size_t orig = map.bucket_count(); 309 map.clear(); 310 EXPECT_EQ(map.size(), 0); 311 EXPECT_EQ(Contents(map), NumMapContents()); 312 EXPECT_LT(map.bucket_count(), orig); 313 } 314 315 TEST(FlatMap, Copy) { 316 for (int n = 0; n < 10; n++) { 317 NumMap src; 318 Fill(&src, 0, n); 319 NumMap copy = src; 320 EXPECT_EQ(Contents(src), Contents(copy)); 321 NumMap copy2; 322 copy2 = src; 323 EXPECT_EQ(Contents(src), Contents(copy2)); 324 copy2 = copy2; // Self-assignment 325 EXPECT_EQ(Contents(src), Contents(copy2)); 326 } 327 } 328 329 TEST(FlatMap, InitFromIter) { 330 for (int n = 0; n < 10; n++) { 331 NumMap src; 332 Fill(&src, 0, n); 333 auto vec = Contents(src); 334 NumMap dst(vec.begin(), vec.end()); 335 EXPECT_EQ(Contents(dst), vec); 336 } 337 } 338 339 TEST(FlatMap, InitializerList) { 340 NumMap a{{1, 10}, {2, 20}, {3, 30}}; 341 NumMap b({{1, 10}, {2, 20}, {3, 30}}); 342 NumMap c = {{1, 10}, {2, 20}, {3, 30}}; 343 344 typedef std::unordered_map<int64, int32> StdNumMap; 345 StdNumMap std({{1, 10}, {2, 20}, {3, 30}}); 346 StdNumMap::value_type std_r1 = *std.find(1); 347 StdNumMap::value_type std_r2 = *std.find(2); 348 StdNumMap::value_type std_r3 = *std.find(3); 349 NumMap d{std_r1, std_r2, std_r3}; 350 NumMap e({std_r1, std_r2, std_r3}); 351 NumMap f = {std_r1, std_r2, std_r3}; 352 353 for (NumMap* map : std::vector<NumMap*>({&a, &b, &c, &d, &e, &f})) { 354 EXPECT_EQ(Get(*map, 1), 10); 355 EXPECT_EQ(Get(*map, 2), 20); 356 EXPECT_EQ(Get(*map, 3), 30); 357 EXPECT_EQ(Contents(*map), NumMapContents({{1, 10}, {2, 20}, {3, 30}})); 358 } 359 } 360 361 TEST(FlatMap, InsertIter) { 362 NumMap a, b; 363 Fill(&a, 1, 10); 364 Fill(&b, 8, 20); 365 b[9] = 10000; // Should not get inserted into a since a already has 9 366 a.insert(b.begin(), b.end()); 367 NumMap expected; 368 Fill(&expected, 1, 20); 369 EXPECT_EQ(Contents(a), Contents(expected)); 370 } 371 372 TEST(FlatMap, Eq) { 373 NumMap empty; 374 375 NumMap elems; 376 Fill(&elems, 0, 5); 377 EXPECT_FALSE(empty == elems); 378 EXPECT_TRUE(empty != elems); 379 380 NumMap copy = elems; 381 EXPECT_TRUE(copy == elems); 382 EXPECT_FALSE(copy != elems); 383 384 NumMap changed = elems; 385 changed[3] = 1; 386 EXPECT_FALSE(changed == elems); 387 EXPECT_TRUE(changed != elems); 388 389 NumMap changed2 = elems; 390 changed2.erase(3); 391 EXPECT_FALSE(changed2 == elems); 392 EXPECT_TRUE(changed2 != elems); 393 } 394 395 TEST(FlatMap, Swap) { 396 NumMap a, b; 397 Fill(&a, 1, 5); 398 Fill(&b, 100, 200); 399 NumMap c = a; 400 NumMap d = b; 401 EXPECT_EQ(c, a); 402 EXPECT_EQ(d, b); 403 c.swap(d); 404 EXPECT_EQ(c, b); 405 EXPECT_EQ(d, a); 406 } 407 408 TEST(FlatMap, Reserve) { 409 NumMap src; 410 Fill(&src, 1, 100); 411 NumMap a = src; 412 a.reserve(10); 413 EXPECT_EQ(a, src); 414 NumMap b = src; 415 b.rehash(1000); 416 EXPECT_EQ(b, src); 417 } 418 419 TEST(FlatMap, EqualRangeMutable) { 420 NumMap map; 421 Fill(&map, 1, 10); 422 423 // Existing element 424 auto p1 = map.equal_range(3); 425 EXPECT_TRUE(p1.first != p1.second); 426 EXPECT_EQ(p1.first->first, 3); 427 EXPECT_EQ(p1.first->second, 300); 428 ++p1.first; 429 EXPECT_TRUE(p1.first == p1.second); 430 431 // Missing element 432 auto p2 = map.equal_range(100); 433 EXPECT_TRUE(p2.first == p2.second); 434 } 435 436 TEST(FlatMap, EqualRangeConst) { 437 NumMap tmp; 438 Fill(&tmp, 1, 10); 439 440 const NumMap map = tmp; 441 442 // Existing element 443 auto p1 = map.equal_range(3); 444 EXPECT_TRUE(p1.first != p1.second); 445 EXPECT_EQ(p1.first->first, 3); 446 EXPECT_EQ(p1.first->second, 300); 447 ++p1.first; 448 EXPECT_TRUE(p1.first == p1.second); 449 450 // Missing element 451 auto p2 = map.equal_range(100); 452 EXPECT_TRUE(p2.first == p2.second); 453 } 454 455 TEST(FlatMap, Prefetch) { 456 NumMap map; 457 Fill(&map, 0, 1000); 458 // Prefetch present and missing keys. 459 for (int i = 0; i < 2000; i++) { 460 map.prefetch_value(i); 461 } 462 } 463 464 // Non-assignable values should work. 465 struct NA { 466 int64 value; 467 NA() : value(-1) {} 468 explicit NA(int64 v) : value(v) {} 469 NA(const NA& x) : value(x.value) {} 470 bool operator==(const NA& x) const { return value == x.value; } 471 }; 472 struct HashNA { 473 size_t operator()(NA x) const { return x.value; } 474 }; 475 476 TEST(FlatMap, NonAssignable) { 477 FlatMap<NA, NA, HashNA> map; 478 for (int i = 0; i < 100; i++) { 479 map[NA(i)] = NA(i * 100); 480 } 481 for (int i = 0; i < 100; i++) { 482 EXPECT_EQ(map.count(NA(i)), 1); 483 auto iter = map.find(NA(i)); 484 EXPECT_NE(iter, map.end()); 485 EXPECT_EQ(iter->first, NA(i)); 486 EXPECT_EQ(iter->second, NA(i * 100)); 487 EXPECT_EQ(map[NA(i)], NA(i * 100)); 488 } 489 map.erase(NA(10)); 490 EXPECT_EQ(map.count(NA(10)), 0); 491 } 492 493 TEST(FlatMap, ForwardIterator) { 494 // Test the requirements of forward iterators 495 typedef FlatMap<NA, NA, HashNA> NAMap; 496 NAMap map({{NA(1), NA(10)}, {NA(2), NA(20)}}); 497 NAMap::iterator it1 = map.find(NA(1)); 498 NAMap::iterator it2 = map.find(NA(2)); 499 500 // Test operator != and == 501 EXPECT_TRUE(it1 != map.end()); 502 EXPECT_TRUE(it2 != map.end()); 503 EXPECT_FALSE(it1 == map.end()); 504 EXPECT_FALSE(it2 == map.end()); 505 EXPECT_TRUE(it1 != it2); 506 EXPECT_FALSE(it1 == it2); 507 508 // Test operator * and -> 509 EXPECT_EQ((*it1).first, NA(1)); 510 EXPECT_EQ((*it1).second, NA(10)); 511 EXPECT_EQ((*it2).first, NA(2)); 512 EXPECT_EQ((*it2).second, NA(20)); 513 EXPECT_EQ(it1->first, NA(1)); 514 EXPECT_EQ(it1->second, NA(10)); 515 EXPECT_EQ(it2->first, NA(2)); 516 EXPECT_EQ(it2->second, NA(20)); 517 518 // Test prefix ++ 519 NAMap::iterator copy_it1 = it1; 520 NAMap::iterator copy_it2 = it2; 521 EXPECT_EQ(copy_it1->first, NA(1)); 522 EXPECT_EQ(copy_it1->second, NA(10)); 523 EXPECT_EQ(copy_it2->first, NA(2)); 524 EXPECT_EQ(copy_it2->second, NA(20)); 525 NAMap::iterator& pp_copy_it1 = ++copy_it1; 526 NAMap::iterator& pp_copy_it2 = ++copy_it2; 527 EXPECT_TRUE(pp_copy_it1 == copy_it1); 528 EXPECT_TRUE(pp_copy_it2 == copy_it2); 529 // Check either possible ordering of the two items 530 EXPECT_TRUE(copy_it1 != it1); 531 EXPECT_TRUE(copy_it2 != it2); 532 if (copy_it1 == map.end()) { 533 EXPECT_TRUE(copy_it2 != map.end()); 534 EXPECT_EQ(copy_it2->first, NA(1)); 535 EXPECT_EQ(copy_it2->second, NA(10)); 536 EXPECT_EQ(pp_copy_it2->first, NA(1)); 537 EXPECT_EQ(pp_copy_it2->second, NA(10)); 538 } else { 539 EXPECT_TRUE(copy_it2 == map.end()); 540 EXPECT_EQ(copy_it1->first, NA(2)); 541 EXPECT_EQ(copy_it1->second, NA(20)); 542 EXPECT_EQ(pp_copy_it1->first, NA(2)); 543 EXPECT_EQ(pp_copy_it1->second, NA(20)); 544 } 545 // Ensure it{1,2} haven't moved 546 EXPECT_EQ(it1->first, NA(1)); 547 EXPECT_EQ(it1->second, NA(10)); 548 EXPECT_EQ(it2->first, NA(2)); 549 EXPECT_EQ(it2->second, NA(20)); 550 551 // Test postfix ++ 552 copy_it1 = it1; 553 copy_it2 = it2; 554 EXPECT_EQ(copy_it1->first, NA(1)); 555 EXPECT_EQ(copy_it1->second, NA(10)); 556 EXPECT_EQ(copy_it2->first, NA(2)); 557 EXPECT_EQ(copy_it2->second, NA(20)); 558 NAMap::iterator copy_it1_pp = copy_it1++; 559 NAMap::iterator copy_it2_pp = copy_it2++; 560 EXPECT_TRUE(copy_it1_pp != copy_it1); 561 EXPECT_TRUE(copy_it2_pp != copy_it2); 562 EXPECT_TRUE(copy_it1_pp == it1); 563 EXPECT_TRUE(copy_it2_pp == it2); 564 EXPECT_EQ(copy_it1_pp->first, NA(1)); 565 EXPECT_EQ(copy_it1_pp->second, NA(10)); 566 EXPECT_EQ(copy_it2_pp->first, NA(2)); 567 EXPECT_EQ(copy_it2_pp->second, NA(20)); 568 // Check either possible ordering of the two items 569 EXPECT_TRUE(copy_it1 != it1); 570 EXPECT_TRUE(copy_it2 != it2); 571 if (copy_it1 == map.end()) { 572 EXPECT_TRUE(copy_it2 != map.end()); 573 EXPECT_EQ(copy_it2->first, NA(1)); 574 EXPECT_EQ(copy_it2->second, NA(10)); 575 } else { 576 EXPECT_TRUE(copy_it2 == map.end()); 577 EXPECT_EQ(copy_it1->first, NA(2)); 578 EXPECT_EQ(copy_it1->second, NA(20)); 579 } 580 // Ensure it{1,2} haven't moved 581 EXPECT_EQ(it1->first, NA(1)); 582 EXPECT_EQ(it1->second, NA(10)); 583 EXPECT_EQ(it2->first, NA(2)); 584 EXPECT_EQ(it2->second, NA(20)); 585 } 586 587 // Test with heap-allocated objects so that mismanaged constructions 588 // or destructions will show up as errors under a sanitizer or 589 // heap checker. 590 TEST(FlatMap, ConstructDestruct) { 591 FlatMap<string, string> map; 592 string k1 = "the quick brown fox jumped over the lazy dog"; 593 string k2 = k1 + k1; 594 string k3 = k1 + k2; 595 map[k1] = k2; 596 map[k3] = k1; 597 EXPECT_EQ(k1, map.find(k1)->first); 598 EXPECT_EQ(k2, map.find(k1)->second); 599 EXPECT_EQ(k1, map[k3]); 600 map.erase(k3); 601 EXPECT_EQ(string(), map[k3]); 602 603 map.clear(); 604 map[k1] = k2; 605 EXPECT_EQ(k2, map[k1]); 606 607 map.reserve(100); 608 EXPECT_EQ(k2, map[k1]); 609 } 610 611 // Type to use to ensure that custom equality operator is used 612 // that ignores extra value. 613 struct CustomCmpKey { 614 int64 a; 615 int64 b; 616 CustomCmpKey(int64 v1, int64 v2) : a(v1), b(v2) {} 617 bool operator==(const CustomCmpKey& x) const { return a == x.a && b == x.b; } 618 }; 619 struct HashA { 620 size_t operator()(CustomCmpKey x) const { return x.a; } 621 }; 622 struct EqA { 623 // Ignore b fields. 624 bool operator()(CustomCmpKey x, CustomCmpKey y) const { return x.a == y.a; } 625 }; 626 TEST(FlatMap, CustomCmp) { 627 FlatMap<CustomCmpKey, int, HashA, EqA> map; 628 map[CustomCmpKey(100, 200)] = 300; 629 EXPECT_EQ(300, map[CustomCmpKey(100, 200)]); 630 EXPECT_EQ(300, map[CustomCmpKey(100, 500)]); // Differences in key.b ignored 631 } 632 633 // Test unique_ptr handling. 634 typedef std::unique_ptr<int> UniqInt; 635 static UniqInt MakeUniq(int i) { return UniqInt(new int(i)); } 636 637 struct HashUniq { 638 size_t operator()(const UniqInt& p) const { return *p; } 639 }; 640 struct EqUniq { 641 bool operator()(const UniqInt& a, const UniqInt& b) const { return *a == *b; } 642 }; 643 typedef FlatMap<UniqInt, UniqInt, HashUniq, EqUniq> UniqMap; 644 645 TEST(FlatMap, UniqueMap) { 646 UniqMap map; 647 648 // Fill map 649 const int N = 10; 650 for (int i = 0; i < N; i++) { 651 if ((i % 2) == 0) { 652 map[MakeUniq(i)] = MakeUniq(i + 100); 653 } else { 654 map.emplace(MakeUniq(i), MakeUniq(i + 100)); 655 } 656 } 657 EXPECT_EQ(map.size(), N); 658 659 // Lookups 660 for (int i = 0; i < N; i++) { 661 EXPECT_EQ(*map.at(MakeUniq(i)), i + 100); 662 } 663 664 // find+erase 665 EXPECT_EQ(map.count(MakeUniq(2)), 1); 666 map.erase(MakeUniq(2)); 667 EXPECT_EQ(map.count(MakeUniq(2)), 0); 668 669 // clear 670 map.clear(); 671 EXPECT_EQ(map.size(), 0); 672 } 673 674 TEST(FlatMap, UniqueMapIter) { 675 UniqMap map; 676 const int kCount = 10; 677 const int kValueDelta = 100; 678 for (int i = 1; i <= kCount; i++) { 679 map[MakeUniq(i)] = MakeUniq(i + kValueDelta); 680 } 681 int key_sum = 0; 682 int val_sum = 0; 683 for (const auto& p : map) { 684 key_sum += *p.first; 685 val_sum += *p.second; 686 } 687 EXPECT_EQ(key_sum, (kCount * (kCount + 1)) / 2); 688 EXPECT_EQ(val_sum, key_sum + (kCount * kValueDelta)); 689 } 690 691 } // namespace 692 } // namespace gtl 693 } // namespace tensorflow 694