1/*
2 * Copyright 2017-present Facebook, Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#include <folly/container/F14Map.h>
18
19#include <algorithm>
20#include <unordered_map>
21
22#include <folly/Conv.h>
23#include <folly/FBString.h>
24#include <folly/container/test/F14TestUtil.h>
25#include <folly/portability/GTest.h>
26
27template <template <typename, typename, typename, typename, typename>
28 class TMap>
29void testCustomSwap() {
30 using std::swap;
31
32 TMap<
33 int,
34 int,
35 folly::f14::DefaultHasher<int>,
36 folly::f14::DefaultKeyEqual<int>,
37 folly::f14::SwapTrackingAlloc<std::pair<int const, int>>>
38 m0, m1;
39 folly::f14::resetTracking();
40 swap(m0, m1);
41
42 EXPECT_EQ(
43 0, folly::f14::Tracked<0>::counts.dist(folly::f14::Counts{0, 0, 0, 0}));
44}
45
46TEST(F14Map, customSwap) {
47 testCustomSwap<folly::F14ValueMap>();
48 testCustomSwap<folly::F14NodeMap>();
49 testCustomSwap<folly::F14VectorMap>();
50 testCustomSwap<folly::F14FastMap>();
51}
52
53template <
54 template <typename, typename, typename, typename, typename> class TMap,
55 typename K,
56 typename V>
57void runAllocatedMemorySizeTest() {
58 using namespace folly::f14;
59 using namespace folly::f14::detail;
60 using A = SwapTrackingAlloc<std::pair<const K, V>>;
61
62 resetTracking();
63 {
64 TMap<K, V, DefaultHasher<K>, DefaultKeyEqual<K>, A> m;
65
66 // if F14 intrinsics are not available then we fall back to using
67 // std::unordered_map underneath, but in that case the allocation
68 // info is only best effort
69 bool preciseAllocInfo = getF14IntrinsicsMode() != F14IntrinsicsMode::None;
70
71 if (preciseAllocInfo) {
72 EXPECT_EQ(testAllocatedMemorySize, 0);
73 EXPECT_EQ(m.getAllocatedMemorySize(), 0);
74 }
75 auto emptyMapAllocatedMemorySize = testAllocatedMemorySize;
76 auto emptyMapAllocatedBlockCount = testAllocatedBlockCount;
77
78 for (size_t i = 0; i < 1000; ++i) {
79 m.insert(std::make_pair(folly::to<K>(i), V{}));
80 m.erase(folly::to<K>(i / 10 + 2));
81 if (preciseAllocInfo) {
82 EXPECT_EQ(testAllocatedMemorySize, m.getAllocatedMemorySize());
83 }
84 EXPECT_GE(m.getAllocatedMemorySize(), sizeof(std::pair<K, V>) * m.size());
85 std::size_t size = 0;
86 std::size_t count = 0;
87 m.visitAllocationClasses([&](std::size_t, std::size_t) mutable {});
88 m.visitAllocationClasses([&](std::size_t bytes, std::size_t n) {
89 size += bytes * n;
90 count += n;
91 });
92 if (preciseAllocInfo) {
93 EXPECT_EQ(testAllocatedMemorySize, size);
94 EXPECT_EQ(testAllocatedBlockCount, count);
95 }
96 }
97
98 m = decltype(m){};
99 EXPECT_EQ(testAllocatedMemorySize, emptyMapAllocatedMemorySize);
100 EXPECT_EQ(testAllocatedBlockCount, emptyMapAllocatedBlockCount);
101
102 m.reserve(5);
103 EXPECT_GT(testAllocatedMemorySize, 0);
104 m = {};
105 EXPECT_GT(testAllocatedMemorySize, 0);
106 }
107 EXPECT_EQ(testAllocatedMemorySize, 0);
108 EXPECT_EQ(testAllocatedBlockCount, 0);
109}
110
111template <typename K, typename V>
112void runAllocatedMemorySizeTests() {
113 runAllocatedMemorySizeTest<folly::F14ValueMap, K, V>();
114 runAllocatedMemorySizeTest<folly::F14NodeMap, K, V>();
115 runAllocatedMemorySizeTest<folly::F14VectorMap, K, V>();
116 runAllocatedMemorySizeTest<folly::F14FastMap, K, V>();
117}
118
119TEST(F14Map, getAllocatedMemorySize) {
120 runAllocatedMemorySizeTests<bool, bool>();
121 runAllocatedMemorySizeTests<int, int>();
122 runAllocatedMemorySizeTests<bool, std::string>();
123 runAllocatedMemorySizeTests<double, std::string>();
124 runAllocatedMemorySizeTests<std::string, int>();
125 runAllocatedMemorySizeTests<std::string, std::string>();
126 runAllocatedMemorySizeTests<folly::fbstring, long>();
127}
128
129template <typename M>
130void runVisitContiguousRangesTest(int n) {
131 M map;
132
133 for (int i = 0; i < n; ++i) {
134 map[i] = i;
135 map.erase(i / 2);
136 }
137
138 std::unordered_map<uintptr_t, bool> visited;
139 for (auto& entry : map) {
140 visited[reinterpret_cast<uintptr_t>(&entry)] = false;
141 }
142
143 map.visitContiguousRanges([&](auto b, auto e) {
144 for (auto i = b; i != e; ++i) {
145 auto iter = visited.find(reinterpret_cast<uintptr_t>(i));
146 ASSERT_TRUE(iter != visited.end());
147 EXPECT_FALSE(iter->second);
148 iter->second = true;
149 }
150 });
151
152 // ensure no entries were skipped
153 for (auto& e : visited) {
154 EXPECT_TRUE(e.second);
155 }
156}
157
158template <typename M>
159void runVisitContiguousRangesTest() {
160 runVisitContiguousRangesTest<M>(0); // empty
161 runVisitContiguousRangesTest<M>(5); // single chunk
162 runVisitContiguousRangesTest<M>(1000); // many chunks
163}
164
165TEST(F14ValueMap, visitContiguousRanges) {
166 runVisitContiguousRangesTest<folly::F14ValueMap<int, int>>();
167}
168
169TEST(F14NodeMap, visitContiguousRanges) {
170 runVisitContiguousRangesTest<folly::F14NodeMap<int, int>>();
171}
172
173TEST(F14VectorMap, visitContiguousRanges) {
174 runVisitContiguousRangesTest<folly::F14VectorMap<int, int>>();
175}
176
177TEST(F14FastMap, visitContiguousRanges) {
178 runVisitContiguousRangesTest<folly::F14FastMap<int, int>>();
179}
180
181///////////////////////////////////
182#if FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE
183///////////////////////////////////
184
185#include <chrono>
186#include <random>
187#include <string>
188#include <typeinfo>
189#include <unordered_map>
190
191#include <folly/Range.h>
192#include <folly/hash/Hash.h>
193
194using namespace folly;
195using namespace folly::f14;
196using namespace folly::string_piece_literals;
197
198namespace {
199std::string s(char const* p) {
200 return p;
201}
202} // namespace
203
204template <typename T>
205void runSimple() {
206 T h;
207
208 EXPECT_EQ(h.size(), 0);
209 h.reserve(0);
210 std::vector<std::pair<std::string const, std::string>> v(
211 {{"abc", "first"}, {"abc", "second"}});
212 h.insert(v.begin(), v.begin());
213 EXPECT_EQ(h.size(), 0);
214 EXPECT_EQ(h.bucket_count(), 0);
215 h.insert(v.begin(), v.end());
216 EXPECT_EQ(h.size(), 1);
217 EXPECT_EQ(h["abc"], s("first"));
218 h = T{};
219 EXPECT_EQ(h.bucket_count(), 0);
220
221 h.insert(std::make_pair(s("abc"), s("ABC")));
222 EXPECT_TRUE(h.find(s("def")) == h.end());
223 EXPECT_FALSE(h.find(s("abc")) == h.end());
224 EXPECT_EQ(h[s("abc")], s("ABC"));
225 h[s("ghi")] = s("GHI");
226 EXPECT_EQ(h.size(), 2);
227 h.erase(h.find(s("abc")));
228 EXPECT_EQ(h.size(), 1);
229
230 T h2(std::move(h));
231 EXPECT_EQ(h.size(), 0);
232 EXPECT_TRUE(h.begin() == h.end());
233 EXPECT_EQ(h2.size(), 1);
234
235 EXPECT_TRUE(h2.find(s("abc")) == h2.end());
236 EXPECT_EQ(h2.begin()->first, s("ghi"));
237 {
238 auto i = h2.begin();
239 EXPECT_FALSE(i == h2.end());
240 ++i;
241 EXPECT_TRUE(i == h2.end());
242 }
243
244 T h3;
245 h3.try_emplace(s("xxx"));
246 h3.insert_or_assign(s("yyy"), s("YYY"));
247 h3 = std::move(h2);
248 EXPECT_EQ(h2.size(), 0);
249 EXPECT_EQ(h3.size(), 1);
250 EXPECT_TRUE(h3.find(s("xxx")) == h3.end());
251
252 for (uint64_t i = 0; i < 1000; ++i) {
253 h[to<std::string>(i * i * i)] = s("x");
254 EXPECT_EQ(h.size(), i + 1);
255 }
256 {
257 using std::swap;
258 swap(h, h2);
259 }
260 for (uint64_t i = 0; i < 1000; ++i) {
261 EXPECT_TRUE(h2.find(to<std::string>(i * i * i)) != h2.end());
262 EXPECT_EQ(
263 h2.find(to<std::string>(i * i * i))->first, to<std::string>(i * i * i));
264 EXPECT_TRUE(h2.find(to<std::string>(i * i * i + 2)) == h2.end());
265 }
266
267 T h4{h2};
268 EXPECT_EQ(h2.size(), 1000);
269 EXPECT_EQ(h4.size(), 1000);
270
271 T h5{std::move(h2)};
272 T h6;
273 h6 = h4;
274 T h7 = h4;
275 T h8({{s("abc"), s("ABC")}, {s("def"), s("DEF")}});
276 T h9({{s("abc"), s("ABD")}, {s("def"), s("DEF")}});
277 EXPECT_EQ(h8.size(), 2);
278 EXPECT_EQ(h8.count(s("abc")), 1);
279 EXPECT_EQ(h8.count(s("xyz")), 0);
280
281 EXPECT_TRUE(h7 != h8);
282 EXPECT_TRUE(h8 != h9);
283
284 h8 = std::move(h7);
285 // h2 and h7 are moved from, h4, h5, h6, and h8 should be identical
286
287 EXPECT_TRUE(h4 == h8);
288
289 EXPECT_TRUE(h2.empty());
290 EXPECT_TRUE(h7.empty());
291 for (uint64_t i = 0; i < 1000; ++i) {
292 auto k = to<std::string>(i * i * i);
293 EXPECT_EQ(h4.count(k), 1);
294 EXPECT_EQ(h5.count(k), 1);
295 EXPECT_EQ(h6.count(k), 1);
296 EXPECT_EQ(h8.count(k), 1);
297 }
298
299 EXPECT_TRUE(h2 == h7);
300 EXPECT_TRUE(h4 != h7);
301
302 EXPECT_EQ(h3.at(s("ghi")), s("GHI"));
303 EXPECT_THROW(h3.at(s("abc")), std::out_of_range);
304
305 h8.clear();
306 h8.emplace(s("abc"), s("ABC"));
307 EXPECT_GE(h8.bucket_count(), 1);
308 h8 = {};
309 EXPECT_GE(h8.bucket_count(), 1);
310 h9 = {{s("abc"), s("ABD")}, {s("def"), s("DEF")}};
311 EXPECT_TRUE(h8.empty());
312 EXPECT_EQ(h9.size(), 2);
313
314 auto expectH8 = [&](T& ref) { EXPECT_EQ(&ref, &h8); };
315 expectH8((h8 = h2));
316 expectH8((h8 = std::move(h2)));
317 expectH8((h8 = {}));
318
319 F14TableStats::compute(h);
320 F14TableStats::compute(h2);
321 F14TableStats::compute(h3);
322 F14TableStats::compute(h4);
323 F14TableStats::compute(h5);
324 F14TableStats::compute(h6);
325 F14TableStats::compute(h7);
326 F14TableStats::compute(h8);
327 F14TableStats::compute(h9);
328}
329
330template <typename T>
331void runRehash() {
332 unsigned n = 10000;
333 T h;
334 auto b = h.bucket_count();
335 for (unsigned i = 0; i < n; ++i) {
336 h.insert(std::make_pair(to<std::string>(i), s("")));
337 if (b != h.bucket_count()) {
338 F14TableStats::compute(h);
339 b = h.bucket_count();
340 }
341 }
342 EXPECT_EQ(h.size(), n);
343 F14TableStats::compute(h);
344}
345
346// T should be a map from uint64_t to Tracked<1> that uses SwapTrackingAlloc
347template <typename T>
348void runRandom() {
349 using R = std::unordered_map<uint64_t, Tracked<2>>;
350
351 resetTracking();
352
353 std::mt19937_64 gen(0);
354 std::uniform_int_distribution<> pctDist(0, 100);
355 std::uniform_int_distribution<uint64_t> bitsBitsDist(1, 6);
356 {
357 T t0;
358 T t1;
359 R r0;
360 R r1;
361 std::size_t rollbacks = 0;
362 std::size_t resizingSmallRollbacks = 0;
363 std::size_t resizingLargeRollbacks = 0;
364
365 for (std::size_t reps = 0; reps < 100000 || rollbacks < 10 ||
366 resizingSmallRollbacks < 1 || resizingLargeRollbacks < 1;
367 ++reps) {
368 if (pctDist(gen) < 20) {
369 // 10% chance allocator will fail after 0 to 3 more allocations
370 limitTestAllocations(gen() & 3);
371 } else {
372 unlimitTestAllocations();
373 }
374 bool leakCheckOnly = false;
375
376 // discardBits will be from 0 to 62
377 auto discardBits = (uint64_t{1} << bitsBitsDist(gen)) - 2;
378 auto k = gen() >> discardBits;
379 auto v = gen();
380 auto pct = pctDist(gen);
381
382 try {
383 EXPECT_EQ(t0.empty(), r0.empty());
384 EXPECT_EQ(t0.size(), r0.size());
385 EXPECT_EQ(2, Tracked<0>::counts.liveCount());
386 EXPECT_EQ(t0.size() + t1.size(), Tracked<1>::counts.liveCount());
387 EXPECT_EQ(r0.size() + r1.size(), Tracked<2>::counts.liveCount());
388 if (pct < 15) {
389 // insert
390 auto t = t0.insert(std::make_pair(k, v));
391 auto r = r0.insert(std::make_pair(k, v));
392 EXPECT_EQ(t.first->first, r.first->first);
393 EXPECT_EQ(t.first->second.val_, r.first->second.val_);
394 EXPECT_EQ(t.second, r.second);
395 } else if (pct < 25) {
396 // emplace
397 auto t = t0.emplace(k, v);
398 auto r = r0.emplace(k, v);
399 EXPECT_EQ(t.first->first, r.first->first);
400 EXPECT_EQ(t.first->second.val_, r.first->second.val_);
401 EXPECT_EQ(t.second, r.second);
402 } else if (pct < 30) {
403 // bulk insert
404 leakCheckOnly = true;
405 t0.insert(t1.begin(), t1.end());
406 r0.insert(r1.begin(), r1.end());
407 } else if (pct < 40) {
408 // erase by key
409 auto t = t0.erase(k);
410 auto r = r0.erase(k);
411 EXPECT_EQ(t, r);
412 } else if (pct < 47) {
413 // erase by iterator
414 if (t0.size() > 0) {
415 auto r = r0.find(k);
416 if (r == r0.end()) {
417 r = r0.begin();
418 }
419 k = r->first;
420 auto t = t0.find(k);
421 t = t0.erase(t);
422 if (t != t0.end()) {
423 EXPECT_NE(t->first, k);
424 }
425 r = r0.erase(r);
426 if (r != r0.end()) {
427 EXPECT_NE(r->first, k);
428 }
429 }
430 } else if (pct < 50) {
431 // bulk erase
432 if (t0.size() > 0) {
433 auto r = r0.find(k);
434 if (r == r0.end()) {
435 r = r0.begin();
436 }
437 k = r->first;
438 auto t = t0.find(k);
439 auto firstt = t;
440 auto lastt = ++t;
441 t = t0.erase(firstt, lastt);
442 if (t != t0.end()) {
443 EXPECT_NE(t->first, k);
444 }
445 auto firstr = r;
446 auto lastr = ++r;
447 r = r0.erase(firstr, lastr);
448 if (r != r0.end()) {
449 EXPECT_NE(r->first, k);
450 }
451 }
452 } else if (pct < 58) {
453 // find
454 auto t = t0.find(k);
455 auto r = r0.find(k);
456 EXPECT_EQ((t == t0.end()), (r == r0.end()));
457 if (t != t0.end() && r != r0.end()) {
458 EXPECT_EQ(t->first, r->first);
459 EXPECT_EQ(t->second.val_, r->second.val_);
460 }
461 EXPECT_EQ(t0.count(k), r0.count(k));
462 } else if (pct < 60) {
463 // equal_range
464 auto t = t0.equal_range(k);
465 auto r = r0.equal_range(k);
466 EXPECT_EQ((t.first == t.second), (r.first == r.second));
467 if (t.first != t.second && r.first != r.second) {
468 EXPECT_EQ(t.first->first, r.first->first);
469 EXPECT_EQ(t.first->second.val_, r.first->second.val_);
470 t.first++;
471 r.first++;
472 EXPECT_TRUE(t.first == t.second);
473 EXPECT_TRUE(r.first == r.second);
474 }
475 } else if (pct < 65) {
476 // iterate
477 uint64_t t = 0;
478 for (auto& e : t0) {
479 t += e.first * 37 + e.second.val_ + 1000;
480 }
481 uint64_t r = 0;
482 for (auto& e : r0) {
483 r += e.first * 37 + e.second.val_ + 1000;
484 }
485 EXPECT_EQ(t, r);
486 } else if (pct < 69) {
487 // swap
488 using std::swap;
489 swap(t0, t1);
490 swap(r0, r1);
491 } else if (pct < 70) {
492 // swap
493 t0.swap(t1);
494 r0.swap(r1);
495 } else if (pct < 72) {
496 // default construct
497 t0.~T();
498 new (&t0) T();
499 r0.~R();
500 new (&r0) R();
501 } else if (pct < 74) {
502 // default construct with capacity
503 std::size_t capacity = k & 0xffff;
504 T t(capacity);
505 t0 = std::move(t);
506 R r(capacity);
507 r0 = std::move(r);
508 } else if (pct < 80) {
509 // bulk iterator construct
510 t0 = T{t1.begin(), t1.end()};
511 r0 = R{r1.begin(), r1.end()};
512 } else if (pct < 82) {
513 // initializer list construct
514 auto k2 = gen() >> discardBits;
515 auto v2 = gen();
516 T t({{k, v}, {k2, v}, {k2, v2}});
517 t0 = std::move(t);
518 R r({{k, v}, {k2, v}, {k2, v2}});
519 r0 = std::move(r);
520 } else if (pct < 85) {
521 // copy construct
522 T t(t1);
523 t0 = std::move(t);
524 R r(r1);
525 r0 = std::move(r);
526 } else if (pct < 88) {
527 // copy construct
528 T t(t1, t1.get_allocator());
529 t0 = std::move(t);
530 R r(r1, r1.get_allocator());
531 r0 = std::move(r);
532 } else if (pct < 89) {
533 // move construct
534 t0.~T();
535 new (&t0) T(std::move(t1));
536 r0.~R();
537 new (&r0) R(std::move(r1));
538 } else if (pct < 90) {
539 // move construct
540 t0.~T();
541 auto ta = t1.get_allocator();
542 new (&t0) T(std::move(t1), ta);
543 r0.~R();
544 auto ra = r1.get_allocator();
545 new (&r0) R(std::move(r1), ra);
546 } else if (pct < 94) {
547 // copy assign
548 leakCheckOnly = true;
549 t0 = t1;
550 r0 = r1;
551 } else if (pct < 96) {
552 // move assign
553 t0 = std::move(t1);
554 r0 = std::move(r1);
555 } else if (pct < 98) {
556 // operator==
557 EXPECT_EQ((t0 == t1), (r0 == r1));
558 } else if (pct < 99) {
559 // clear
560 F14TableStats::compute(t0);
561 t0.clear();
562 r0.clear();
563 } else if (pct < 100) {
564 // reserve
565 auto scale = std::uniform_int_distribution<>(0, 8)(gen);
566 auto delta = std::uniform_int_distribution<>(-2, 2)(gen);
567 std::ptrdiff_t target = (t0.size() * scale) / 4 + delta;
568 if (target >= 0) {
569 t0.reserve(static_cast<std::size_t>(target));
570 r0.reserve(static_cast<std::size_t>(target));
571 }
572 }
573 } catch (std::bad_alloc const&) {
574 ++rollbacks;
575
576 F14TableStats::compute(t0);
577
578 if (leakCheckOnly) {
579 unlimitTestAllocations();
580 t0.clear();
581 for (auto&& kv : r0) {
582 t0[kv.first] = kv.second.val_;
583 }
584 }
585
586 if (t0.bucket_count() == t0.size() && t0.size() > 0) {
587 if (t0.size() < 10) {
588 ++resizingSmallRollbacks;
589 } else {
590 ++resizingLargeRollbacks;
591 }
592 }
593
594 assert(t0.size() == r0.size());
595 for (auto&& kv : r0) {
596 auto t = t0.find(kv.first);
597 EXPECT_TRUE(
598 t != t0.end() && t->first == kv.first &&
599 t->second.val_ == kv.second.val_);
600 }
601 }
602 }
603 }
604
605 EXPECT_EQ(testAllocatedMemorySize, 0);
606}
607
608template <typename T>
609void runPrehash() {
610 T h;
611
612 EXPECT_EQ(h.size(), 0);
613
614 h.insert(std::make_pair(s("abc"), s("ABC")));
615 EXPECT_TRUE(h.find(s("def")) == h.end());
616 EXPECT_FALSE(h.find(s("abc")) == h.end());
617
618 auto t1 = h.prehash(s("def"));
619 F14HashToken t2;
620 t2 = h.prehash(s("abc"));
621 EXPECT_TRUE(h.find(t1, s("def")) == h.end());
622 EXPECT_FALSE(h.find(t2, s("abc")) == h.end());
623}
624
625TEST(F14ValueMap, simple) {
626 runSimple<F14ValueMap<std::string, std::string>>();
627}
628
629TEST(F14NodeMap, simple) {
630 runSimple<F14NodeMap<std::string, std::string>>();
631}
632
633TEST(F14VectorMap, simple) {
634 runSimple<F14VectorMap<std::string, std::string>>();
635}
636
637TEST(F14FastMap, simple) {
638 runSimple<F14FastMap<std::string, std::string>>();
639}
640
641TEST(F14VectorMap, reverse_iterator) {
642 using TMap = F14VectorMap<uint64_t, uint64_t>;
643 auto populate = [](TMap& h, uint64_t lo, uint64_t hi) {
644 for (auto i = lo; i < hi; ++i) {
645 h.emplace(i, i);
646 }
647 };
648 auto verify = [](TMap const& h, uint64_t lo, uint64_t hi) {
649 auto loIt = h.find(lo);
650 EXPECT_NE(h.end(), loIt);
651 uint64_t val = lo;
652 for (auto rit = h.riter(loIt); rit != h.rend(); ++rit) {
653 EXPECT_EQ(val, rit->first);
654 EXPECT_EQ(val, rit->second);
655 TMap::const_iterator it = h.iter(rit);
656 EXPECT_EQ(val, it->first);
657 EXPECT_EQ(val, it->second);
658 val++;
659 }
660 EXPECT_EQ(hi, val);
661 };
662 TMap h;
663 size_t prevSize = 0;
664 size_t newSize = 1;
665 // verify iteration order across rehashes, copies, and moves
666 while (newSize < 10'000) {
667 populate(h, prevSize, newSize);
668 verify(h, 0, newSize);
669 verify(h, newSize / 2, newSize);
670
671 TMap h2{h};
672 verify(h2, 0, newSize);
673
674 h = std::move(h2);
675 verify(h, 0, newSize);
676 prevSize = newSize;
677 newSize *= 10;
678 }
679}
680
681TEST(F14ValueMap, rehash) {
682 runRehash<F14ValueMap<std::string, std::string>>();
683}
684
685TEST(F14NodeMap, rehash) {
686 runRehash<F14NodeMap<std::string, std::string>>();
687}
688
689TEST(F14VectorMap, rehash) {
690 runRehash<F14VectorMap<std::string, std::string>>();
691}
692
693TEST(F14ValueMap, prehash) {
694 runPrehash<F14ValueMap<std::string, std::string>>();
695}
696
697TEST(F14NodeMap, prehash) {
698 runPrehash<F14NodeMap<std::string, std::string>>();
699}
700
701TEST(F14ValueMap, random) {
702 runRandom<F14ValueMap<
703 uint64_t,
704 Tracked<1>,
705 std::hash<uint64_t>,
706 std::equal_to<uint64_t>,
707 SwapTrackingAlloc<std::pair<uint64_t const, Tracked<1>>>>>();
708}
709
710TEST(F14NodeMap, random) {
711 runRandom<F14NodeMap<
712 uint64_t,
713 Tracked<1>,
714 std::hash<uint64_t>,
715 std::equal_to<uint64_t>,
716 SwapTrackingAlloc<std::pair<uint64_t const, Tracked<1>>>>>();
717}
718
719TEST(F14VectorMap, random) {
720 runRandom<F14VectorMap<
721 uint64_t,
722 Tracked<1>,
723 std::hash<uint64_t>,
724 std::equal_to<uint64_t>,
725 SwapTrackingAlloc<std::pair<uint64_t const, Tracked<1>>>>>();
726}
727
728TEST(F14FastMap, random) {
729 runRandom<F14FastMap<
730 uint64_t,
731 Tracked<1>,
732 std::hash<uint64_t>,
733 std::equal_to<uint64_t>,
734 SwapTrackingAlloc<std::pair<uint64_t const, Tracked<1>>>>>();
735}
736
737TEST(F14ValueMap, grow_stats) {
738 F14ValueMap<uint64_t, uint64_t> h;
739 for (unsigned i = 1; i <= 3072; ++i) {
740 h[i]++;
741 }
742 // F14ValueMap just before rehash
743 F14TableStats::compute(h);
744 h[0]++;
745 // F14ValueMap just after rehash
746 F14TableStats::compute(h);
747}
748
749TEST(F14ValueMap, steady_state_stats) {
750 // 10k keys, 14% probability of insert, 90% chance of erase, so the
751 // table should converge to 1400 size without triggering the rehash
752 // that would occur at 1536.
753 F14ValueMap<uint64_t, uint64_t> h;
754 std::mt19937_64 gen(0);
755 std::uniform_int_distribution<> dist(0, 10000);
756 for (std::size_t i = 0; i < 100000; ++i) {
757 auto key = dist(gen);
758 if (dist(gen) < 1400) {
759 h.insert_or_assign(key, i);
760 } else {
761 h.erase(key);
762 }
763 if (((i + 1) % 10000) == 0) {
764 auto stats = F14TableStats::compute(h);
765 // Verify that average miss probe length is bounded despite continued
766 // erase + reuse. p99 of the average across 10M random steps is 4.69,
767 // average is 2.96.
768 EXPECT_LT(f14::expectedProbe(stats.missProbeLengthHisto), 10.0);
769 }
770 }
771 // F14ValueMap at steady state
772 F14TableStats::compute(h);
773}
774
775TEST(F14VectorMap, steady_state_stats) {
776 // 10k keys, 14% probability of insert, 90% chance of erase, so the
777 // table should converge to 1400 size without triggering the rehash
778 // that would occur at 1536.
779 F14VectorMap<std::string, uint64_t> h;
780 std::mt19937_64 gen(0);
781 std::uniform_int_distribution<> dist(0, 10000);
782 for (std::size_t i = 0; i < 100000; ++i) {
783 auto key = "0123456789ABCDEFGHIJKLMNOPQ" + to<std::string>(dist(gen));
784 if (dist(gen) < 1400) {
785 h.insert_or_assign(key, i);
786 } else {
787 h.erase(key);
788 }
789 if (((i + 1) % 10000) == 0) {
790 auto stats = F14TableStats::compute(h);
791 // Verify that average miss probe length is bounded despite continued
792 // erase + reuse. p99 of the average across 10M random steps is 4.69,
793 // average is 2.96.
794 EXPECT_LT(f14::expectedProbe(stats.missProbeLengthHisto), 10.0);
795 }
796 }
797 // F14ValueMap at steady state
798 F14TableStats::compute(h);
799}
800
801TEST(Tracked, baseline) {
802 Tracked<0> a0;
803
804 {
805 resetTracking();
806 Tracked<0> b0{a0};
807 EXPECT_EQ(a0.val_, b0.val_);
808 EXPECT_EQ(sumCounts, (Counts{1, 0, 0, 0}));
809 EXPECT_EQ(Tracked<0>::counts, (Counts{1, 0, 0, 0}));
810 }
811 {
812 resetTracking();
813 Tracked<0> b0{std::move(a0)};
814 EXPECT_EQ(a0.val_, b0.val_);
815 EXPECT_EQ(sumCounts, (Counts{0, 1, 0, 0}));
816 EXPECT_EQ(Tracked<0>::counts, (Counts{0, 1, 0, 0}));
817 }
818 {
819 resetTracking();
820 Tracked<1> b1{a0};
821 EXPECT_EQ(a0.val_, b1.val_);
822 EXPECT_EQ(sumCounts, (Counts{0, 0, 1, 0}));
823 EXPECT_EQ(Tracked<1>::counts, (Counts{0, 0, 1, 0}));
824 }
825 {
826 resetTracking();
827 Tracked<1> b1{std::move(a0)};
828 EXPECT_EQ(a0.val_, b1.val_);
829 EXPECT_EQ(sumCounts, (Counts{0, 0, 0, 1}));
830 EXPECT_EQ(Tracked<1>::counts, (Counts{0, 0, 0, 1}));
831 }
832 {
833 Tracked<0> b0;
834 resetTracking();
835 b0 = a0;
836 EXPECT_EQ(a0.val_, b0.val_);
837 EXPECT_EQ(sumCounts, (Counts{0, 0, 0, 0, 1, 0}));
838 EXPECT_EQ(Tracked<0>::counts, (Counts{0, 0, 0, 0, 1, 0}));
839 }
840 {
841 Tracked<0> b0;
842 resetTracking();
843 b0 = std::move(a0);
844 EXPECT_EQ(a0.val_, b0.val_);
845 EXPECT_EQ(sumCounts, (Counts{0, 0, 0, 0, 0, 1}));
846 EXPECT_EQ(Tracked<0>::counts, (Counts{0, 0, 0, 0, 0, 1}));
847 }
848 {
849 Tracked<1> b1;
850 resetTracking();
851 b1 = a0;
852 EXPECT_EQ(a0.val_, b1.val_);
853 EXPECT_EQ(sumCounts, (Counts{0, 0, 1, 0, 0, 1, 0, 1}));
854 EXPECT_EQ(Tracked<1>::counts, (Counts{0, 0, 1, 0, 0, 1, 0, 1}));
855 }
856 {
857 Tracked<1> b1;
858 resetTracking();
859 b1 = std::move(a0);
860 EXPECT_EQ(a0.val_, b1.val_);
861 EXPECT_EQ(sumCounts, (Counts{0, 0, 0, 1, 0, 1, 0, 1}));
862 EXPECT_EQ(Tracked<1>::counts, (Counts{0, 0, 0, 1, 0, 1, 0, 1}));
863 }
864}
865
866// M should be a map from Tracked<0> to Tracked<1>. F should take a map
867// and a pair const& or pair&& and cause it to be inserted
868template <typename M, typename F>
869void runInsertCases(
870 std::string const& name,
871 F const& insertFunc,
872 uint64_t expectedDist = 0) {
873 static_assert(std::is_same<typename M::key_type, Tracked<0>>::value, "");
874 static_assert(std::is_same<typename M::mapped_type, Tracked<1>>::value, "");
875 {
876 typename M::value_type p{0, 0};
877 M m;
878 resetTracking();
879 insertFunc(m, p);
880 // fresh key, value_type const& ->
881 // copy is expected
882 EXPECT_EQ(
883 Tracked<0>::counts.dist(Counts{1, 0, 0, 0}) +
884 Tracked<1>::counts.dist(Counts{1, 0, 0, 0}),
885 expectedDist)
886 << name << "\n0 -> " << Tracked<0>::counts << "\n1 -> "
887 << Tracked<1>::counts;
888 }
889 {
890 typename M::value_type p{0, 0};
891 M m;
892 resetTracking();
893 insertFunc(m, std::move(p));
894 // fresh key, value_type&& ->
895 // key copy is unfortunate but required
896 EXPECT_EQ(
897 Tracked<0>::counts.dist(Counts{1, 0, 0, 0}) +
898 Tracked<1>::counts.dist(Counts{0, 1, 0, 0}),
899 expectedDist)
900 << name << "\n0 -> " << Tracked<0>::counts << "\n1 -> "
901 << Tracked<1>::counts;
902 }
903 {
904 std::pair<Tracked<0>, Tracked<1>> p{0, 0};
905 M m;
906 resetTracking();
907 insertFunc(m, p);
908 // fresh key, pair<key_type,mapped_type> const& ->
909 // 1 copy is required
910 EXPECT_EQ(
911 Tracked<0>::counts.dist(Counts{1, 0, 0, 0}) +
912 Tracked<1>::counts.dist(Counts{1, 0, 0, 0}),
913 expectedDist)
914 << name << "\n0 -> " << Tracked<0>::counts << "\n1 -> "
915 << Tracked<1>::counts;
916 }
917 {
918 std::pair<Tracked<0>, Tracked<1>> p{0, 0};
919 M m;
920 resetTracking();
921 insertFunc(m, std::move(p));
922 // fresh key, pair<key_type,mapped_type>&& ->
923 // this is the happy path for insert(make_pair(.., ..))
924 EXPECT_EQ(
925 Tracked<0>::counts.dist(Counts{0, 1, 0, 0}) +
926 Tracked<1>::counts.dist(Counts{0, 1, 0, 0}),
927 expectedDist)
928 << name << "\n0 -> " << Tracked<0>::counts << "\n1 -> "
929 << Tracked<1>::counts;
930 }
931 {
932 std::pair<Tracked<2>, Tracked<3>> p{0, 0};
933 M m;
934 resetTracking();
935 insertFunc(m, p);
936 // fresh key, convertible const& ->
937 // key_type ops: Tracked<0>::counts
938 // mapped_type ops: Tracked<1>::counts
939 // key_src ops: Tracked<2>::counts
940 // mapped_src ops: Tracked<3>::counts;
941
942 // There are three strategies that could be optimal for particular
943 // ratios of cost:
944 //
945 // - convert key and value in place to final position, destroy if
946 // insert fails. This is the strategy used by std::unordered_map
947 // and FBHashMap
948 //
949 // - convert key and default value in place to final position,
950 // convert value only if insert succeeds. Nobody uses this strategy
951 //
952 // - convert key to a temporary, move key and convert value if
953 // insert succeeds. This is the strategy used by F14 and what is
954 // EXPECT_EQ here.
955
956 // The expectedDist * 3 is just a hack for the emplace-pieces-by-value
957 // test, whose test harness copies the original pair and then uses
958 // move conversion instead of copy conversion.
959 EXPECT_EQ(
960 Tracked<0>::counts.dist(Counts{0, 1, 1, 0}) +
961 Tracked<1>::counts.dist(Counts{0, 0, 1, 0}) +
962 Tracked<2>::counts.dist(Counts{0, 0, 0, 0}) +
963 Tracked<3>::counts.dist(Counts{0, 0, 0, 0}),
964 expectedDist * 3);
965 }
966 {
967 std::pair<Tracked<2>, Tracked<3>> p{0, 0};
968 M m;
969 resetTracking();
970 insertFunc(m, std::move(p));
971 // fresh key, convertible&& ->
972 // key_type ops: Tracked<0>::counts
973 // mapped_type ops: Tracked<1>::counts
974 // key_src ops: Tracked<2>::counts
975 // mapped_src ops: Tracked<3>::counts;
976 EXPECT_EQ(
977 Tracked<0>::counts.dist(Counts{0, 1, 0, 1}) +
978 Tracked<1>::counts.dist(Counts{0, 0, 0, 1}) +
979 Tracked<2>::counts.dist(Counts{0, 0, 0, 0}) +
980 Tracked<3>::counts.dist(Counts{0, 0, 0, 0}),
981 expectedDist);
982 }
983 {
984 typename M::value_type p{0, 0};
985 M m;
986 m[0] = 0;
987 resetTracking();
988 insertFunc(m, p);
989 // duplicate key, value_type const&
990 EXPECT_EQ(
991 Tracked<0>::counts.dist(Counts{0, 0, 0, 0}) +
992 Tracked<1>::counts.dist(Counts{0, 0, 0, 0}),
993 expectedDist);
994 }
995 {
996 typename M::value_type p{0, 0};
997 M m;
998 m[0] = 0;
999 resetTracking();
1000 insertFunc(m, std::move(p));
1001 // duplicate key, value_type&&
1002 EXPECT_EQ(
1003 Tracked<0>::counts.dist(Counts{0, 0, 0, 0}) +
1004 Tracked<1>::counts.dist(Counts{0, 0, 0, 0}),
1005 expectedDist);
1006 }
1007 {
1008 std::pair<Tracked<0>, Tracked<1>> p{0, 0};
1009 M m;
1010 m[0] = 0;
1011 resetTracking();
1012 insertFunc(m, p);
1013 // duplicate key, pair<key_type,mapped_type> const&
1014 EXPECT_EQ(
1015 Tracked<0>::counts.dist(Counts{0, 0, 0, 0}) +
1016 Tracked<1>::counts.dist(Counts{0, 0, 0, 0}),
1017 expectedDist);
1018 }
1019 {
1020 std::pair<Tracked<0>, Tracked<1>> p{0, 0};
1021 M m;
1022 m[0] = 0;
1023 resetTracking();
1024 insertFunc(m, std::move(p));
1025 // duplicate key, pair<key_type,mapped_type>&&
1026 EXPECT_EQ(
1027 Tracked<0>::counts.dist(Counts{0, 0, 0, 0}) +
1028 Tracked<1>::counts.dist(Counts{0, 0, 0, 0}),
1029 expectedDist);
1030 }
1031 {
1032 std::pair<Tracked<2>, Tracked<3>> p{0, 0};
1033 M m;
1034 m[0] = 0;
1035 resetTracking();
1036 insertFunc(m, p);
1037 // duplicate key, convertible const& ->
1038 // key_type ops: Tracked<0>::counts
1039 // mapped_type ops: Tracked<1>::counts
1040 // key_src ops: Tracked<2>::counts
1041 // mapped_src ops: Tracked<3>::counts;
1042 EXPECT_EQ(
1043 Tracked<0>::counts.dist(Counts{0, 0, 1, 0}) +
1044 Tracked<1>::counts.dist(Counts{0, 0, 0, 0}) +
1045 Tracked<2>::counts.dist(Counts{0, 0, 0, 0}) +
1046 Tracked<3>::counts.dist(Counts{0, 0, 0, 0}),
1047 expectedDist * 2);
1048 }
1049 {
1050 std::pair<Tracked<2>, Tracked<3>> p{0, 0};
1051 M m;
1052 m[0] = 0;
1053 resetTracking();
1054 insertFunc(m, std::move(p));
1055 // duplicate key, convertible&& ->
1056 // key_type ops: Tracked<0>::counts
1057 // mapped_type ops: Tracked<1>::counts
1058 // key_src ops: Tracked<2>::counts
1059 // mapped_src ops: Tracked<3>::counts;
1060 EXPECT_EQ(
1061 Tracked<0>::counts.dist(Counts{0, 0, 0, 1}) +
1062 Tracked<1>::counts.dist(Counts{0, 0, 0, 0}) +
1063 Tracked<2>::counts.dist(Counts{0, 0, 0, 0}) +
1064 Tracked<3>::counts.dist(Counts{0, 0, 0, 0}),
1065 expectedDist);
1066 }
1067}
1068
1069struct DoInsert {
1070 template <typename M, typename P>
1071 void operator()(M& m, P&& p) const {
1072 m.insert(std::forward<P>(p));
1073 }
1074};
1075
1076struct DoEmplace1 {
1077 template <typename M, typename P>
1078 void operator()(M& m, P&& p) const {
1079 m.emplace(std::forward<P>(p));
1080 }
1081};
1082
1083struct DoEmplace2 {
1084 template <typename M, typename U1, typename U2>
1085 void operator()(M& m, std::pair<U1, U2> const& p) const {
1086 m.emplace(p.first, p.second);
1087 }
1088
1089 template <typename M, typename U1, typename U2>
1090 void operator()(M& m, std::pair<U1, U2>&& p) const {
1091 m.emplace(std::move(p.first), std::move(p.second));
1092 }
1093};
1094
1095struct DoEmplace3 {
1096 template <typename M, typename U1, typename U2>
1097 void operator()(M& m, std::pair<U1, U2> const& p) const {
1098 m.emplace(
1099 std::piecewise_construct,
1100 std::forward_as_tuple(p.first),
1101 std::forward_as_tuple(p.second));
1102 }
1103
1104 template <typename M, typename U1, typename U2>
1105 void operator()(M& m, std::pair<U1, U2>&& p) const {
1106 m.emplace(
1107 std::piecewise_construct,
1108 std::forward_as_tuple(std::move(p.first)),
1109 std::forward_as_tuple(std::move(p.second)));
1110 }
1111};
1112
1113// Simulates use of piecewise_construct without proper use of
1114// forward_as_tuple. This code doesn't yield the normal pattern, but
1115// it should have exactly 1 additional move or copy of the key and 1
1116// additional move or copy of the mapped value.
1117struct DoEmplace3Value {
1118 template <typename M, typename U1, typename U2>
1119 void operator()(M& m, std::pair<U1, U2> const& p) const {
1120 m.emplace(
1121 std::piecewise_construct,
1122 std::tuple<U1>{p.first},
1123 std::tuple<U2>{p.second});
1124 }
1125
1126 template <typename M, typename U1, typename U2>
1127 void operator()(M& m, std::pair<U1, U2>&& p) const {
1128 m.emplace(
1129 std::piecewise_construct,
1130 std::tuple<U1>{std::move(p.first)},
1131 std::tuple<U2>{std::move(p.second)});
1132 }
1133};
1134
1135template <typename M>
1136void runInsertAndEmplace(std::string const& name) {
1137 runInsertCases<M>(name + " insert", DoInsert{});
1138 runInsertCases<M>(name + " emplace pair", DoEmplace1{});
1139 runInsertCases<M>(name + " emplace k,v", DoEmplace2{});
1140 runInsertCases<M>(name + " emplace pieces", DoEmplace3{});
1141 runInsertCases<M>(name + " emplace pieces by value", DoEmplace3Value{}, 2);
1142
1143 // Calling the default pair constructor via emplace is valid, but not
1144 // very useful in real life. Verify that it works.
1145 M m;
1146 typename M::key_type k;
1147 EXPECT_EQ(m.count(k), 0);
1148 m.emplace();
1149 EXPECT_EQ(m.count(k), 1);
1150 m.emplace();
1151 EXPECT_EQ(m.count(k), 1);
1152}
1153
1154TEST(F14ValueMap, destructuring) {
1155 runInsertAndEmplace<F14ValueMap<Tracked<0>, Tracked<1>>>("f14value");
1156}
1157
1158TEST(F14NodeMap, destructuring) {
1159 runInsertAndEmplace<F14NodeMap<Tracked<0>, Tracked<1>>>("f14node");
1160}
1161
1162TEST(F14VectorMap, destructuring) {
1163 runInsertAndEmplace<F14VectorMap<Tracked<0>, Tracked<1>>>("f14vector");
1164}
1165
1166TEST(F14VectorMap, destructuringErase) {
1167 using M = F14VectorMap<Tracked<0>, Tracked<1>>;
1168 typename M::value_type p1{0, 0};
1169 typename M::value_type p2{2, 2};
1170 M m;
1171 m.insert(p1);
1172 m.insert(p2);
1173
1174 resetTracking();
1175 m.erase(p1.first);
1176 LOG(INFO) << "erase -> "
1177 << "key_type ops " << Tracked<0>::counts << ", mapped_type ops "
1178 << Tracked<1>::counts;
1179 // deleting p1 will cause p2 to be moved to the front of the values array
1180 EXPECT_EQ(
1181 Tracked<0>::counts.dist(Counts{0, 1, 0, 0}) +
1182 Tracked<1>::counts.dist(Counts{0, 1, 0, 0}),
1183 0);
1184}
1185
1186TEST(F14ValueMap, maxSize) {
1187 F14ValueMap<int, int> m;
1188 EXPECT_EQ(
1189 m.max_size(),
1190 std::numeric_limits<std::size_t>::max() / sizeof(std::pair<int, int>));
1191}
1192
1193TEST(F14NodeMap, maxSize) {
1194 F14NodeMap<int, int> m;
1195 EXPECT_EQ(
1196 m.max_size(),
1197 std::numeric_limits<std::size_t>::max() / sizeof(std::pair<int, int>));
1198}
1199
1200TEST(F14VectorMap, vectorMaxSize) {
1201 F14VectorMap<int, int> m;
1202 EXPECT_EQ(
1203 m.max_size(),
1204 std::min(
1205 std::size_t{std::numeric_limits<uint32_t>::max()},
1206 std::numeric_limits<std::size_t>::max() /
1207 sizeof(std::pair<int, int>)));
1208}
1209
1210template <typename M>
1211void runMoveOnlyTest() {
1212 M t0;
1213 t0[10] = 20;
1214 t0.emplace(30, 40);
1215 t0.insert(std::make_pair(50, 60));
1216 M t1{std::move(t0)};
1217 EXPECT_TRUE(t0.empty());
1218 M t2;
1219 EXPECT_TRUE(t2.empty());
1220 t2 = std::move(t1);
1221 EXPECT_EQ(t2.size(), 3);
1222}
1223
1224TEST(F14ValueMap, moveOnly) {
1225 runMoveOnlyTest<F14ValueMap<f14::MoveOnlyTestInt, int>>();
1226 runMoveOnlyTest<F14ValueMap<int, f14::MoveOnlyTestInt>>();
1227 runMoveOnlyTest<F14ValueMap<f14::MoveOnlyTestInt, f14::MoveOnlyTestInt>>();
1228}
1229
1230TEST(F14NodeMap, moveOnly) {
1231 runMoveOnlyTest<F14NodeMap<f14::MoveOnlyTestInt, int>>();
1232 runMoveOnlyTest<F14NodeMap<int, f14::MoveOnlyTestInt>>();
1233 runMoveOnlyTest<F14NodeMap<f14::MoveOnlyTestInt, f14::MoveOnlyTestInt>>();
1234}
1235
1236TEST(F14VectorMap, moveOnly) {
1237 runMoveOnlyTest<F14VectorMap<f14::MoveOnlyTestInt, int>>();
1238 runMoveOnlyTest<F14VectorMap<int, f14::MoveOnlyTestInt>>();
1239 runMoveOnlyTest<F14VectorMap<f14::MoveOnlyTestInt, f14::MoveOnlyTestInt>>();
1240}
1241
1242TEST(F14FastMap, moveOnly) {
1243 runMoveOnlyTest<F14FastMap<f14::MoveOnlyTestInt, int>>();
1244 runMoveOnlyTest<F14FastMap<int, f14::MoveOnlyTestInt>>();
1245 runMoveOnlyTest<F14FastMap<f14::MoveOnlyTestInt, f14::MoveOnlyTestInt>>();
1246}
1247
1248TEST(F14ValueMap, heterogeneousLookup) {
1249 using Hasher = folly::transparent<folly::hasher<folly::StringPiece>>;
1250 using KeyEqual = folly::transparent<std::equal_to<folly::StringPiece>>;
1251
1252 constexpr auto hello = "hello"_sp;
1253 constexpr auto buddy = "buddy"_sp;
1254 constexpr auto world = "world"_sp;
1255
1256 F14ValueMap<std::string, bool, Hasher, KeyEqual> map;
1257 map.emplace(hello, true);
1258 map.emplace(world, false);
1259
1260 auto checks = [hello, buddy](auto& ref) {
1261 // count
1262 EXPECT_EQ(0, ref.count(buddy));
1263 EXPECT_EQ(1, ref.count(hello));
1264
1265 // find
1266 EXPECT_TRUE(ref.end() == ref.find(buddy));
1267 EXPECT_EQ(hello, ref.find(hello)->first);
1268
1269 // prehash + find
1270 EXPECT_TRUE(ref.end() == ref.find(ref.prehash(buddy), buddy));
1271 EXPECT_EQ(hello, ref.find(ref.prehash(hello), hello)->first);
1272
1273 // equal_range
1274 EXPECT_TRUE(std::make_pair(ref.end(), ref.end()) == ref.equal_range(buddy));
1275 EXPECT_TRUE(
1276 std::make_pair(ref.find(hello), ++ref.find(hello)) ==
1277 ref.equal_range(hello));
1278 };
1279
1280 checks(map);
1281 checks(folly::as_const(map));
1282}
1283
1284template <typename M>
1285void runStatefulFunctorTest() {
1286 bool ranHasher = false;
1287 bool ranEqual = false;
1288 bool ranAlloc = false;
1289 bool ranDealloc = false;
1290
1291 auto hasher = [&](int x) {
1292 ranHasher = true;
1293 return x;
1294 };
1295 auto equal = [&](int x, int y) {
1296 ranEqual = true;
1297 return x == y;
1298 };
1299 auto alloc = [&](std::size_t n) {
1300 ranAlloc = true;
1301 return std::malloc(n);
1302 };
1303 auto dealloc = [&](void* p, std::size_t) {
1304 ranDealloc = true;
1305 std::free(p);
1306 };
1307
1308 {
1309 M map(0, hasher, equal, {alloc, dealloc});
1310 map[10]++;
1311 map[10]++;
1312 EXPECT_EQ(map[10], 2);
1313
1314 M map2(map);
1315 M map3(std::move(map));
1316 map = map2;
1317 map2.clear();
1318 map2 = std::move(map3);
1319 }
1320 EXPECT_TRUE(ranHasher);
1321 EXPECT_TRUE(ranEqual);
1322 EXPECT_TRUE(ranAlloc);
1323 EXPECT_TRUE(ranDealloc);
1324}
1325
1326TEST(F14ValueMap, statefulFunctors) {
1327 runStatefulFunctorTest<F14ValueMap<
1328 int,
1329 int,
1330 GenericHasher<int>,
1331 GenericEqual<int>,
1332 GenericAlloc<std::pair<int const, int>>>>();
1333}
1334
1335TEST(F14NodeMap, statefulFunctors) {
1336 runStatefulFunctorTest<F14NodeMap<
1337 int,
1338 int,
1339 GenericHasher<int>,
1340 GenericEqual<int>,
1341 GenericAlloc<std::pair<int const, int>>>>();
1342}
1343
1344TEST(F14VectorMap, statefulFunctors) {
1345 runStatefulFunctorTest<F14VectorMap<
1346 int,
1347 int,
1348 GenericHasher<int>,
1349 GenericEqual<int>,
1350 GenericAlloc<std::pair<int const, int>>>>();
1351}
1352
1353TEST(F14FastMap, statefulFunctors) {
1354 runStatefulFunctorTest<F14FastMap<
1355 int,
1356 int,
1357 GenericHasher<int>,
1358 GenericEqual<int>,
1359 GenericAlloc<std::pair<int const, int>>>>();
1360}
1361
1362template <typename M>
1363void runHeterogeneousInsertTest() {
1364 M map;
1365
1366 resetTracking();
1367 EXPECT_EQ(map.count(10), 0);
1368 EXPECT_EQ(Tracked<1>::counts.dist(Counts{0, 0, 0, 0}), 0)
1369 << Tracked<1>::counts;
1370
1371 resetTracking();
1372 map[10] = 20;
1373 EXPECT_EQ(Tracked<1>::counts.dist(Counts{0, 0, 0, 1}), 0)
1374 << Tracked<1>::counts;
1375
1376 resetTracking();
1377 std::pair<int, int> p(10, 30);
1378 std::vector<std::pair<int, int>> v({p});
1379 map[10] = 30;
1380 map.insert(std::pair<int, int>(10, 30));
1381 map.insert(std::pair<int const, int>(10, 30));
1382 map.insert(p);
1383 map.insert(v.begin(), v.end());
1384 map.insert(
1385 std::make_move_iterator(v.begin()), std::make_move_iterator(v.end()));
1386 map.insert_or_assign(10, 40);
1387 EXPECT_EQ(Tracked<1>::counts.dist(Counts{0, 0, 0, 0}), 0)
1388 << Tracked<1>::counts;
1389
1390 resetTracking();
1391 map.emplace(10, 30);
1392 map.emplace(
1393 std::piecewise_construct,
1394 std::forward_as_tuple(10),
1395 std::forward_as_tuple(30));
1396 map.emplace(p);
1397 map.try_emplace(10, 30);
1398 map.try_emplace(10);
1399 EXPECT_EQ(Tracked<1>::counts.dist(Counts{0, 0, 0, 0}), 0)
1400 << Tracked<1>::counts;
1401
1402 resetTracking();
1403 map.erase(10);
1404 EXPECT_EQ(map.size(), 0);
1405 EXPECT_EQ(Tracked<1>::counts.dist(Counts{0, 0, 0, 0}), 0)
1406 << Tracked<1>::counts;
1407}
1408
1409template <typename M>
1410void runHeterogeneousInsertStringTest() {
1411 using P = std::pair<StringPiece, std::string>;
1412 using CP = std::pair<const StringPiece, std::string>;
1413
1414 M map;
1415 P p{"foo", "hello"};
1416 std::vector<P> v{p};
1417 StringPiece foo{"foo"};
1418
1419 map.insert(P("foo", "hello"));
1420 // TODO(T31574848): the list-initialization below does not work on libstdc++
1421 // versions (e.g., GCC < 6) with no implementation of N4387 ("perfect
1422 // initialization" for pairs and tuples).
1423 // StringPiece sp{"foo"};
1424 // map.insert({sp, "hello"});
1425 map.insert({"foo", "hello"});
1426 map.insert(CP("foo", "hello"));
1427 map.insert(p);
1428 map.insert(v.begin(), v.end());
1429 map.insert(
1430 std::make_move_iterator(v.begin()), std::make_move_iterator(v.end()));
1431 map.insert_or_assign("foo", "hello");
1432 map.insert_or_assign(StringPiece{"foo"}, "hello");
1433 EXPECT_EQ(map["foo"], "hello");
1434
1435 map.emplace(StringPiece{"foo"}, "hello");
1436 map.emplace("foo", "hello");
1437 map.emplace(p);
1438 map.emplace();
1439 map.emplace(
1440 std::piecewise_construct,
1441 std::forward_as_tuple(StringPiece{"foo"}),
1442 std::forward_as_tuple(/* count */ 20, 'x'));
1443 map.try_emplace(StringPiece{"foo"}, "hello");
1444 map.try_emplace(foo, "hello");
1445 map.try_emplace(foo);
1446 map.try_emplace("foo");
1447 map.try_emplace("foo", "hello");
1448 map.try_emplace("foo", /* count */ 20, 'x');
1449
1450 map.erase(StringPiece{"foo"});
1451 map.erase(foo);
1452 map.erase("");
1453 EXPECT_TRUE(map.empty());
1454}
1455
1456TEST(F14ValueMap, heterogeneousInsert) {
1457 runHeterogeneousInsertTest<F14ValueMap<
1458 Tracked<1>,
1459 int,
1460 TransparentTrackedHash<1>,
1461 TransparentTrackedEqual<1>>>();
1462 runHeterogeneousInsertStringTest<F14ValueMap<
1463 std::string,
1464 std::string,
1465 transparent<hasher<StringPiece>>,
1466 transparent<DefaultKeyEqual<StringPiece>>>>();
1467 runHeterogeneousInsertStringTest<F14ValueMap<std::string, std::string>>();
1468}
1469
1470TEST(F14NodeMap, heterogeneousInsert) {
1471 runHeterogeneousInsertTest<F14NodeMap<
1472 Tracked<1>,
1473 int,
1474 TransparentTrackedHash<1>,
1475 TransparentTrackedEqual<1>>>();
1476 runHeterogeneousInsertStringTest<F14NodeMap<
1477 std::string,
1478 std::string,
1479 transparent<hasher<StringPiece>>,
1480 transparent<DefaultKeyEqual<StringPiece>>>>();
1481 runHeterogeneousInsertStringTest<F14NodeMap<std::string, std::string>>();
1482}
1483
1484TEST(F14VectorMap, heterogeneousInsert) {
1485 runHeterogeneousInsertTest<F14VectorMap<
1486 Tracked<1>,
1487 int,
1488 TransparentTrackedHash<1>,
1489 TransparentTrackedEqual<1>>>();
1490 runHeterogeneousInsertStringTest<F14VectorMap<
1491 std::string,
1492 std::string,
1493 transparent<hasher<StringPiece>>,
1494 transparent<DefaultKeyEqual<StringPiece>>>>();
1495 runHeterogeneousInsertStringTest<F14VectorMap<std::string, std::string>>();
1496}
1497
1498TEST(F14FastMap, heterogeneousInsert) {
1499 runHeterogeneousInsertTest<F14FastMap<
1500 Tracked<1>,
1501 int,
1502 TransparentTrackedHash<1>,
1503 TransparentTrackedEqual<1>>>();
1504 runHeterogeneousInsertStringTest<F14FastMap<
1505 std::string,
1506 std::string,
1507 transparent<hasher<StringPiece>>,
1508 transparent<DefaultKeyEqual<StringPiece>>>>();
1509 runHeterogeneousInsertStringTest<F14FastMap<std::string, std::string>>();
1510}
1511
1512namespace {
1513
1514// std::is_convertible is not transitive :( Problem scenario: B<T> is
1515// implicitly convertible to A, so hasher that takes A can be used as a
1516// transparent hasher for a map with key of type B<T>. C is implicitly
1517// convertible to any B<T>, but we have to disable heterogeneous find
1518// for C. There is no way to infer the T of the intermediate type so C
1519// can't be used to explicitly construct A.
1520
1521struct A {
1522 int value;
1523
1524 bool operator==(A const& rhs) const {
1525 return value == rhs.value;
1526 }
1527 bool operator!=(A const& rhs) const {
1528 return !(*this == rhs);
1529 }
1530};
1531
1532struct AHasher {
1533 std::size_t operator()(A const& v) const {
1534 return v.value;
1535 }
1536};
1537
1538template <typename T>
1539struct B {
1540 int value;
1541
1542 explicit B(int v) : value(v) {}
1543
1544 /* implicit */ B(A const& v) : value(v.value) {}
1545
1546 /* implicit */ operator A() const {
1547 return A{value};
1548 }
1549};
1550
1551struct C {
1552 int value;
1553
1554 template <typename T>
1555 /* implicit */ operator B<T>() const {
1556 return B<T>{value};
1557 }
1558};
1559} // namespace
1560
1561TEST(F14FastMap, disabledDoubleTransparent) {
1562 static_assert(std::is_convertible<B<char>, A>::value, "");
1563 static_assert(std::is_convertible<C, B<char>>::value, "");
1564 static_assert(!std::is_convertible<C, A>::value, "");
1565
1566 F14FastMap<
1567 B<char>,
1568 int,
1569 folly::transparent<AHasher>,
1570 folly::transparent<std::equal_to<A>>>
1571 map;
1572 map[A{10}] = 10;
1573
1574 EXPECT_TRUE(map.find(C{10}) != map.end());
1575 EXPECT_TRUE(map.find(C{20}) == map.end());
1576}
1577
1578template <typename M>
1579void runRandomInsertOrderTest() {
1580 if (FOLLY_F14_PERTURB_INSERTION_ORDER) {
1581 std::string prev;
1582 bool diffFound = false;
1583 for (int tries = 0; tries < 100; ++tries) {
1584 M m;
1585 for (char x = '0'; x <= '7'; ++x) {
1586 m.try_emplace(x);
1587 }
1588 m.reserve(10);
1589 auto it = m.try_emplace('8').first;
1590 auto addr = &*it;
1591 m.try_emplace('9');
1592 EXPECT_TRUE(it == m.find('8'));
1593 EXPECT_TRUE(addr = &*m.find('8'));
1594 std::string s;
1595 for (auto&& e : m) {
1596 s.push_back(e.first);
1597 }
1598 LOG(INFO) << s << "\n";
1599 if (prev.empty()) {
1600 prev = s;
1601 continue;
1602 }
1603 if (prev != s) {
1604 diffFound = true;
1605 break;
1606 }
1607 }
1608 EXPECT_TRUE(diffFound) << "no randomness found in insert order";
1609 }
1610}
1611
1612TEST(F14Map, randomInsertOrder) {
1613 runRandomInsertOrderTest<F14ValueMap<char, char>>();
1614 runRandomInsertOrderTest<F14FastMap<char, char>>();
1615 runRandomInsertOrderTest<F14FastMap<char, std::string>>();
1616}
1617
1618template <typename M>
1619void runContinuousCapacityTest(std::size_t minSize, std::size_t maxSize) {
1620 using K = typename M::key_type;
1621 for (std::size_t n = minSize; n <= maxSize; ++n) {
1622 M m1;
1623 m1.reserve(n);
1624 auto cap = m1.bucket_count();
1625 double ratio = cap * 1.0 / n;
1626 // worst case scenario is that rehash just occurred and capacityScale
1627 // is 5*2^12
1628 EXPECT_TRUE(ratio < 1 + 1.0 / (5 << 12))
1629 << ratio << ", " << cap << ", " << n;
1630 m1[0];
1631 M m2;
1632 m2 = m1;
1633 EXPECT_LE(m2.bucket_count(), 2);
1634 for (K i = 1; i < n; ++i) {
1635 m1[i];
1636 }
1637 EXPECT_EQ(m1.bucket_count(), cap);
1638 M m3 = m1;
1639 EXPECT_EQ(m3.bucket_count(), cap);
1640 for (K i = n; i <= cap; ++i) {
1641 m1[i];
1642 }
1643 EXPECT_GT(m1.bucket_count(), cap);
1644 EXPECT_LE(m1.bucket_count(), 3 * cap);
1645
1646 M m4;
1647 for (K i = 0; i < n; ++i) {
1648 m4[i];
1649 }
1650 // reserve(0) works like shrink_to_fit. Note that tight fit (1/8
1651 // waste bound) only applies for vector policy or single-chunk, which
1652 // might not apply to m1. m3 should already have been optimally sized.
1653 m1.reserve(0);
1654 m3.reserve(0);
1655 m4.reserve(0);
1656 EXPECT_GT(m1.load_factor(), 0.5);
1657 EXPECT_GE(m3.load_factor(), 0.875);
1658 EXPECT_EQ(m3.bucket_count(), cap);
1659 EXPECT_GE(m4.load_factor(), 0.875);
1660 }
1661}
1662
1663TEST(F14Map, continuousCapacitySmall) {
1664 runContinuousCapacityTest<folly::F14NodeMap<std::size_t, std::string>>(1, 14);
1665 runContinuousCapacityTest<folly::F14ValueMap<std::size_t, std::string>>(
1666 1, 14);
1667 runContinuousCapacityTest<folly::F14VectorMap<std::size_t, std::string>>(
1668 1, 100);
1669 runContinuousCapacityTest<folly::F14FastMap<std::size_t, std::string>>(
1670 1, 100);
1671}
1672
1673TEST(F14Map, continuousCapacityBig0) {
1674 runContinuousCapacityTest<folly::F14VectorMap<std::size_t, std::string>>(
1675 1000000 - 1, 1000000 - 1);
1676}
1677
1678TEST(F14Map, continuousCapacityBig1) {
1679 runContinuousCapacityTest<folly::F14VectorMap<std::size_t, std::string>>(
1680 1000000, 1000000);
1681}
1682
1683TEST(F14Map, continuousCapacityBig2) {
1684 runContinuousCapacityTest<folly::F14VectorMap<std::size_t, std::string>>(
1685 1000000 + 1, 1000000 + 1);
1686}
1687
1688TEST(F14Map, continuousCapacityBig3) {
1689 runContinuousCapacityTest<folly::F14VectorMap<std::size_t, std::string>>(
1690 1000000 + 2, 1000000 + 2);
1691}
1692
1693TEST(F14Map, continuousCapacityF12) {
1694 runContinuousCapacityTest<folly::F14VectorMap<uint16_t, uint16_t>>(
1695 0xfff0, 0xfffe);
1696}
1697
1698///////////////////////////////////
1699#endif // FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE
1700///////////////////////////////////
1701