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_t, int32> NumMap;
31
32 // If map has an entry for k, return the corresponding value, else return def.
Get(const NumMap & map,int64_t k,int32_t def=-1)33 int32 Get(const NumMap& map, int64_t k, int32_t 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_t, int32>> NumMapContents;
Contents(const NumMap & map)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).
Fill(NumMap * map,int64_t start,int64_t limit)58 void Fill(NumMap* map, int64_t start, int64_t limit) {
59 for (int64_t i = start; i < limit; i++) {
60 map->insert({i, i * 100});
61 }
62 }
63
TEST(FlatMapTest,Find)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
TEST(FlatMapTest,Insert)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
TEST(FlatMapTest,InsertGrowth)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
TEST(FlatMapTest,Emplace)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
TEST(FlatMapTest,EmplaceUniquePtr)145 TEST(FlatMapTest, EmplaceUniquePtr) {
146 FlatMap<int64_t, std::unique_ptr<string>> smap;
147 smap.emplace(1, std::unique_ptr<string>(new string("hello")));
148 }
149
TEST(FlatMapTest,Size)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
TEST(FlatMapTest,Empty)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
TEST(FlatMapTest,ArrayOperator)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
TEST(FlatMapTest,Count)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
TEST(FlatMapTest,Iter)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
TEST(FlatMapTest,Erase)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
TEST(FlatMapTest,EraseIter)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
TEST(FlatMapTest,EraseIterPair)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
TEST(FlatMapTest,EraseLongChains)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
TEST(FlatMap,AlternatingInsertRemove)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
TEST(FlatMap,ClearNoResize)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
TEST(FlatMap,Clear)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
TEST(FlatMap,Copy)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 = *©2; // Self-assignment, avoiding -Wself-assign.
325 EXPECT_EQ(Contents(src), Contents(copy2));
326 }
327 }
328
TEST(FlatMap,InitFromIter)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
TEST(FlatMap,InitializerList)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_t, 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
TEST(FlatMap,InsertIter)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
TEST(FlatMap,Eq)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
TEST(FlatMap,Swap)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
TEST(FlatMap,Reserve)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
TEST(FlatMap,EqualRangeMutable)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
TEST(FlatMap,EqualRangeConst)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
TEST(FlatMap,Prefetch)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_t value;
NAtensorflow::gtl::__anon7420d4170111::NA467 NA() : value(-1) {}
NAtensorflow::gtl::__anon7420d4170111::NA468 explicit NA(int64_t v) : value(v) {}
NAtensorflow::gtl::__anon7420d4170111::NA469 NA(const NA& x) : value(x.value) {}
operator ==tensorflow::gtl::__anon7420d4170111::NA470 bool operator==(const NA& x) const { return value == x.value; }
471 };
472 struct HashNA {
operator ()tensorflow::gtl::__anon7420d4170111::HashNA473 size_t operator()(NA x) const { return x.value; }
474 };
475
TEST(FlatMap,NonAssignable)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
TEST(FlatMap,ForwardIterator)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.
TEST(FlatMap,ConstructDestruct)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_t a;
615 int64_t b;
CustomCmpKeytensorflow::gtl::__anon7420d4170111::CustomCmpKey616 CustomCmpKey(int64_t v1, int64_t v2) : a(v1), b(v2) {}
operator ==tensorflow::gtl::__anon7420d4170111::CustomCmpKey617 bool operator==(const CustomCmpKey& x) const { return a == x.a && b == x.b; }
618 };
619 struct HashA {
operator ()tensorflow::gtl::__anon7420d4170111::HashA620 size_t operator()(CustomCmpKey x) const { return x.a; }
621 };
622 struct EqA {
623 // Ignore b fields.
operator ()tensorflow::gtl::__anon7420d4170111::EqA624 bool operator()(CustomCmpKey x, CustomCmpKey y) const { return x.a == y.a; }
625 };
TEST(FlatMap,CustomCmp)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;
MakeUniq(int i)635 static UniqInt MakeUniq(int i) { return UniqInt(new int(i)); }
636
637 struct HashUniq {
operator ()tensorflow::gtl::__anon7420d4170111::HashUniq638 size_t operator()(const UniqInt& p) const { return *p; }
639 };
640 struct EqUniq {
operator ()tensorflow::gtl::__anon7420d4170111::EqUniq641 bool operator()(const UniqInt& a, const UniqInt& b) const { return *a == *b; }
642 };
643 typedef FlatMap<UniqInt, UniqInt, HashUniq, EqUniq> UniqMap;
644
TEST(FlatMap,UniqueMap)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 // move constructor
660 UniqMap map2(std::move(map));
661
662 // Lookups
663 for (int i = 0; i < N; i++) {
664 EXPECT_EQ(*map2.at(MakeUniq(i)), i + 100);
665 }
666
667 // move assignment
668 UniqMap map3;
669 map3 = std::move(map2);
670
671 // find+erase
672 EXPECT_EQ(map3.count(MakeUniq(2)), 1);
673 map3.erase(MakeUniq(2));
674 EXPECT_EQ(map3.count(MakeUniq(2)), 0);
675
676 // clear
677 map3.clear();
678 EXPECT_EQ(map3.size(), 0);
679
680 // Check that moved-from maps are in a valid (though unspecified) state.
681 EXPECT_GE(map.size(), 0);
682 EXPECT_GE(map2.size(), 0);
683 // This insert should succeed no matter what state `map` is in, because
684 // MakeUniq(-1) is never called above: This key can't possibly exist.
685 EXPECT_TRUE(map.emplace(MakeUniq(-1), MakeUniq(-1)).second);
686 }
687
TEST(FlatMap,UniqueMapIter)688 TEST(FlatMap, UniqueMapIter) {
689 UniqMap map;
690 const int kCount = 10;
691 const int kValueDelta = 100;
692 for (int i = 1; i <= kCount; i++) {
693 map[MakeUniq(i)] = MakeUniq(i + kValueDelta);
694 }
695 int key_sum = 0;
696 int val_sum = 0;
697 for (const auto& p : map) {
698 key_sum += *p.first;
699 val_sum += *p.second;
700 }
701 EXPECT_EQ(key_sum, (kCount * (kCount + 1)) / 2);
702 EXPECT_EQ(val_sum, key_sum + (kCount * kValueDelta));
703 }
704
705 } // namespace
706 } // namespace gtl
707 } // namespace tensorflow
708