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/F14Set.h>
18
19#include <unordered_map>
20
21#include <folly/Conv.h>
22#include <folly/FBString.h>
23#include <folly/container/test/F14TestUtil.h>
24#include <folly/portability/GTest.h>
25
26template <template <typename, typename, typename, typename> class TSet>
27void testCustomSwap() {
28 using std::swap;
29
30 TSet<
31 int,
32 folly::f14::DefaultHasher<int>,
33 folly::f14::DefaultKeyEqual<int>,
34 folly::f14::SwapTrackingAlloc<int>>
35 m0, m1;
36 folly::f14::resetTracking();
37 swap(m0, m1);
38
39 EXPECT_EQ(
40 0, folly::f14::Tracked<0>::counts.dist(folly::f14::Counts{0, 0, 0, 0}));
41}
42
43TEST(F14Set, customSwap) {
44 testCustomSwap<folly::F14ValueSet>();
45 testCustomSwap<folly::F14NodeSet>();
46 testCustomSwap<folly::F14VectorSet>();
47 testCustomSwap<folly::F14FastSet>();
48}
49
50namespace {
51template <
52 template <typename, typename, typename, typename> class TSet,
53 typename K>
54void runAllocatedMemorySizeTest() {
55 using namespace folly::f14;
56 using namespace folly::f14::detail;
57 using A = SwapTrackingAlloc<K>;
58
59 resetTracking();
60 {
61 TSet<K, DefaultHasher<K>, DefaultKeyEqual<K>, A> s;
62
63 // if F14 intrinsics are not available then we fall back to using
64 // std::unordered_set underneath, but in that case the allocation
65 // info is only best effort
66 bool preciseAllocInfo = getF14IntrinsicsMode() != F14IntrinsicsMode::None;
67
68 if (preciseAllocInfo) {
69 EXPECT_EQ(testAllocatedMemorySize, 0);
70 EXPECT_EQ(s.getAllocatedMemorySize(), 0);
71 }
72 auto emptySetAllocatedMemorySize = testAllocatedMemorySize;
73 auto emptySetAllocatedBlockCount = testAllocatedBlockCount;
74
75 for (size_t i = 0; i < 1000; ++i) {
76 s.insert(folly::to<K>(i));
77 s.erase(folly::to<K>(i / 10 + 2));
78 if (preciseAllocInfo) {
79 EXPECT_EQ(testAllocatedMemorySize, s.getAllocatedMemorySize());
80 }
81 EXPECT_GE(s.getAllocatedMemorySize(), sizeof(K) * s.size());
82 std::size_t size = 0;
83 std::size_t count = 0;
84 s.visitAllocationClasses([&](std::size_t, std::size_t) mutable {});
85 s.visitAllocationClasses([&](std::size_t bytes, std::size_t n) {
86 size += bytes * n;
87 count += n;
88 });
89 if (preciseAllocInfo) {
90 EXPECT_EQ(testAllocatedMemorySize, size);
91 EXPECT_EQ(testAllocatedBlockCount, count);
92 }
93 }
94
95 s = decltype(s){};
96 EXPECT_EQ(testAllocatedMemorySize, emptySetAllocatedMemorySize);
97 EXPECT_EQ(testAllocatedBlockCount, emptySetAllocatedBlockCount);
98
99 s.reserve(5);
100 EXPECT_GT(testAllocatedMemorySize, 0);
101 s = {};
102 EXPECT_GT(testAllocatedMemorySize, 0);
103 }
104 EXPECT_EQ(testAllocatedMemorySize, 0);
105 EXPECT_EQ(testAllocatedBlockCount, 0);
106}
107
108template <typename K>
109void runAllocatedMemorySizeTests() {
110 runAllocatedMemorySizeTest<folly::F14ValueSet, K>();
111 runAllocatedMemorySizeTest<folly::F14NodeSet, K>();
112 runAllocatedMemorySizeTest<folly::F14VectorSet, K>();
113 runAllocatedMemorySizeTest<folly::F14FastSet, K>();
114}
115} // namespace
116
117TEST(F14Set, getAllocatedMemorySize) {
118 runAllocatedMemorySizeTests<bool>();
119 runAllocatedMemorySizeTests<int>();
120 runAllocatedMemorySizeTests<long>();
121 runAllocatedMemorySizeTests<double>();
122 runAllocatedMemorySizeTests<std::string>();
123 runAllocatedMemorySizeTests<folly::fbstring>();
124}
125
126template <typename S>
127void runVisitContiguousRangesTest(int n) {
128 S set;
129
130 for (int i = 0; i < n; ++i) {
131 set.insert(i);
132 set.erase(i / 2);
133 }
134
135 std::unordered_map<uintptr_t, bool> visited;
136 for (auto& entry : set) {
137 visited[reinterpret_cast<uintptr_t>(&entry)] = false;
138 }
139
140 set.visitContiguousRanges([&](auto b, auto e) {
141 for (auto i = b; i != e; ++i) {
142 auto iter = visited.find(reinterpret_cast<uintptr_t>(i));
143 ASSERT_TRUE(iter != visited.end());
144 EXPECT_FALSE(iter->second);
145 iter->second = true;
146 }
147 });
148
149 // ensure no entries were skipped
150 for (auto& e : visited) {
151 EXPECT_TRUE(e.second);
152 }
153}
154
155template <typename S>
156void runVisitContiguousRangesTest() {
157 runVisitContiguousRangesTest<S>(0); // empty
158 runVisitContiguousRangesTest<S>(5); // single chunk
159 runVisitContiguousRangesTest<S>(1000); // many chunks
160}
161
162TEST(F14ValueSet, visitContiguousRanges) {
163 runVisitContiguousRangesTest<folly::F14ValueSet<int>>();
164}
165
166TEST(F14NodeSet, visitContiguousRanges) {
167 runVisitContiguousRangesTest<folly::F14NodeSet<int>>();
168}
169
170TEST(F14VectorSet, visitContiguousRanges) {
171 runVisitContiguousRangesTest<folly::F14VectorSet<int>>();
172}
173
174TEST(F14FastSet, visitContiguousRanges) {
175 runVisitContiguousRangesTest<folly::F14FastSet<int>>();
176}
177
178///////////////////////////////////
179#if FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE
180///////////////////////////////////
181
182#include <chrono>
183#include <random>
184#include <string>
185#include <unordered_set>
186
187#include <folly/Range.h>
188
189using namespace folly;
190using namespace folly::f14;
191using namespace folly::string_piece_literals;
192
193namespace {
194std::string s(char const* p) {
195 return p;
196}
197} // namespace
198
199template <typename T>
200void runSimple() {
201 T h;
202
203 EXPECT_EQ(h.size(), 0);
204 h.reserve(0);
205 std::vector<std::string> v({"abc", "abc"});
206 h.insert(v.begin(), v.begin());
207 EXPECT_EQ(h.size(), 0);
208 EXPECT_EQ(h.bucket_count(), 0);
209 h.insert(v.begin(), v.end());
210 EXPECT_EQ(h.size(), 1);
211 h = T{};
212 EXPECT_EQ(h.bucket_count(), 0);
213
214 h.insert(s("abc"));
215 EXPECT_TRUE(h.find(s("def")) == h.end());
216 EXPECT_FALSE(h.find(s("abc")) == h.end());
217 h.insert(s("ghi"));
218 EXPECT_EQ(h.size(), 2);
219 h.erase(h.find(s("abc")));
220 EXPECT_EQ(h.size(), 1);
221
222 T h2(std::move(h));
223 EXPECT_EQ(h.size(), 0);
224 EXPECT_TRUE(h.begin() == h.end());
225 EXPECT_EQ(h2.size(), 1);
226
227 EXPECT_TRUE(h2.find(s("abc")) == h2.end());
228 EXPECT_EQ(*h2.begin(), s("ghi"));
229 {
230 auto i = h2.begin();
231 EXPECT_FALSE(i == h2.end());
232 ++i;
233 EXPECT_TRUE(i == h2.end());
234 }
235
236 T h3;
237 h3.insert(s("xxx"));
238 h3.insert(s("yyy"));
239 h3 = std::move(h2);
240 EXPECT_EQ(h2.size(), 0);
241 EXPECT_EQ(h3.size(), 1);
242 EXPECT_TRUE(h3.find(s("xxx")) == h3.end());
243
244 for (uint64_t i = 0; i < 1000; ++i) {
245 h.insert(std::move(to<std::string>(i * i * i)));
246 EXPECT_EQ(h.size(), i + 1);
247 }
248 {
249 using std::swap;
250 swap(h, h2);
251 }
252 for (uint64_t i = 0; i < 1000; ++i) {
253 EXPECT_TRUE(h2.find(to<std::string>(i * i * i)) != h2.end());
254 EXPECT_EQ(*h2.find(to<std::string>(i * i * i)), to<std::string>(i * i * i));
255 EXPECT_TRUE(h2.find(to<std::string>(i * i * i + 2)) == h2.end());
256 }
257
258 T h4{h2};
259 EXPECT_EQ(h2.size(), 1000);
260 EXPECT_EQ(h4.size(), 1000);
261
262 T h5{std::move(h2)};
263 T h6;
264 h6 = h4;
265 T h7 = h4;
266
267 T h8({s("abc"), s("def")});
268 T h9({s("abd"), s("def")});
269 EXPECT_EQ(h8.size(), 2);
270 EXPECT_EQ(h8.count(s("abc")), 1);
271 EXPECT_EQ(h8.count(s("xyz")), 0);
272
273 EXPECT_TRUE(h7 != h8);
274 EXPECT_TRUE(h8 != h9);
275
276 h8 = std::move(h7);
277 // h2 and h7 are moved from, h4, h5, h6, and h8 should be identical
278
279 EXPECT_TRUE(h4 == h8);
280
281 EXPECT_TRUE(h2.empty());
282 EXPECT_TRUE(h7.empty());
283 for (uint64_t i = 0; i < 1000; ++i) {
284 auto k = to<std::string>(i * i * i);
285 EXPECT_EQ(h4.count(k), 1);
286 EXPECT_EQ(h5.count(k), 1);
287 EXPECT_EQ(h6.count(k), 1);
288 EXPECT_EQ(h8.count(k), 1);
289 }
290
291 h8.clear();
292 h8.emplace(s("abc"));
293 EXPECT_GT(h8.bucket_count(), 1);
294 h8 = {};
295 EXPECT_GT(h8.bucket_count(), 1);
296 h9 = {s("abc"), s("def")};
297 EXPECT_TRUE(h8.empty());
298 EXPECT_EQ(h9.size(), 2);
299
300 auto expectH8 = [&](T& ref) { EXPECT_EQ(&ref, &h8); };
301 expectH8((h8 = h2));
302 expectH8((h8 = std::move(h2)));
303 expectH8((h8 = {}));
304
305 F14TableStats::compute(h);
306 F14TableStats::compute(h2);
307 F14TableStats::compute(h3);
308 F14TableStats::compute(h4);
309 F14TableStats::compute(h5);
310 F14TableStats::compute(h6);
311 F14TableStats::compute(h7);
312 F14TableStats::compute(h8);
313}
314
315template <typename T>
316void runRehash() {
317 unsigned n = 10000;
318 T h;
319 for (unsigned i = 0; i < n; ++i) {
320 h.insert(to<std::string>(i));
321 }
322 EXPECT_EQ(h.size(), n);
323 F14TableStats::compute(h);
324}
325
326// T should be a set of uint64_t
327template <typename T>
328void runRandom() {
329 using R = std::unordered_set<uint64_t>;
330
331 std::mt19937_64 gen(0);
332 std::uniform_int_distribution<> pctDist(0, 100);
333 std::uniform_int_distribution<uint64_t> bitsBitsDist(1, 6);
334 T t0;
335 T t1;
336 R r0;
337 R r1;
338
339 for (std::size_t reps = 0; reps < 100000; ++reps) {
340 // discardBits will be from 0 to 62
341 auto discardBits = (uint64_t{1} << bitsBitsDist(gen)) - 2;
342 auto k = gen() >> discardBits;
343 auto pct = pctDist(gen);
344
345 EXPECT_EQ(t0.size(), r0.size());
346 if (pct < 15) {
347 // insert
348 auto t = t0.insert(k);
349 auto r = r0.insert(k);
350 EXPECT_EQ(t.second, r.second);
351 EXPECT_EQ(*t.first, *r.first);
352 } else if (pct < 25) {
353 // emplace
354 auto t = t0.emplace(k);
355 auto r = r0.emplace(k);
356 EXPECT_EQ(t.second, r.second);
357 EXPECT_EQ(*t.first, *r.first);
358 } else if (pct < 30) {
359 // bulk insert
360 t0.insert(t1.begin(), t1.end());
361 r0.insert(r1.begin(), r1.end());
362 } else if (pct < 40) {
363 // erase by key
364 auto t = t0.erase(k);
365 auto r = r0.erase(k);
366 EXPECT_EQ(t, r);
367 } else if (pct < 47) {
368 // erase by iterator
369 if (t0.size() > 0) {
370 auto r = r0.find(k);
371 if (r == r0.end()) {
372 r = r0.begin();
373 }
374 k = *r;
375 auto t = t0.find(k);
376 t = t0.erase(t);
377 if (t != t0.end()) {
378 EXPECT_NE(*t, k);
379 }
380 r = r0.erase(r);
381 if (r != r0.end()) {
382 EXPECT_NE(*r, k);
383 }
384 }
385 } else if (pct < 50) {
386 // bulk erase
387 if (t0.size() > 0) {
388 auto r = r0.find(k);
389 if (r == r0.end()) {
390 r = r0.begin();
391 }
392 k = *r;
393 auto t = t0.find(k);
394 auto firstt = t;
395 auto lastt = ++t;
396 t = t0.erase(firstt, lastt);
397 if (t != t0.end()) {
398 EXPECT_NE(*t, k);
399 }
400 auto firstr = r;
401 auto lastr = ++r;
402 r = r0.erase(firstr, lastr);
403 if (r != r0.end()) {
404 EXPECT_NE(*r, k);
405 }
406 }
407 } else if (pct < 58) {
408 // find
409 auto t = t0.find(k);
410 auto r = r0.find(k);
411 EXPECT_EQ((t == t0.end()), (r == r0.end()));
412 if (t != t0.end() && r != r0.end()) {
413 EXPECT_EQ(*t, *r);
414 }
415 EXPECT_EQ(t0.count(k), r0.count(k));
416 } else if (pct < 60) {
417 // equal_range
418 auto t = t0.equal_range(k);
419 auto r = r0.equal_range(k);
420 EXPECT_EQ((t.first == t.second), (r.first == r.second));
421 if (t.first != t.second && r.first != r.second) {
422 EXPECT_EQ(*t.first, *r.first);
423 t.first++;
424 r.first++;
425 EXPECT_TRUE(t.first == t.second);
426 EXPECT_TRUE(r.first == r.second);
427 }
428 } else if (pct < 65) {
429 // iterate
430 uint64_t t = 0;
431 for (auto& e : t0) {
432 t += e + 1000;
433 }
434 uint64_t r = 0;
435 for (auto& e : r0) {
436 r += e + 1000;
437 }
438 EXPECT_EQ(t, r);
439 } else if (pct < 69) {
440 // swap
441 using std::swap;
442 swap(t0, t1);
443 swap(r0, r1);
444 } else if (pct < 70) {
445 // swap
446 t0.swap(t1);
447 r0.swap(r1);
448 } else if (pct < 72) {
449 // default construct
450 t0.~T();
451 new (&t0) T();
452 r0.~R();
453 new (&r0) R();
454 } else if (pct < 74) {
455 // default construct with capacity
456 std::size_t capacity = k & 0xffff;
457 t0.~T();
458 new (&t0) T(capacity);
459 r0.~R();
460 new (&r0) R(capacity);
461 } else if (pct < 80) {
462 // bulk iterator construct
463 t0.~T();
464 new (&t0) T(r1.begin(), r1.end());
465 r0.~R();
466 new (&r0) R(r1.begin(), r1.end());
467 } else if (pct < 82) {
468 // initializer list construct
469 auto k2 = gen() >> discardBits;
470 t0.~T();
471 new (&t0) T({k, k, k2});
472 r0.~R();
473 new (&r0) R({k, k, k2});
474 } else if (pct < 88) {
475 // copy construct
476 t0.~T();
477 new (&t0) T(t1);
478 r0.~R();
479 new (&r0) R(r1);
480 } else if (pct < 90) {
481 // move construct
482 t0.~T();
483 new (&t0) T(std::move(t1));
484 r0.~R();
485 new (&r0) R(std::move(r1));
486 } else if (pct < 94) {
487 // copy assign
488 t0 = t1;
489 r0 = r1;
490 } else if (pct < 96) {
491 // move assign
492 t0 = std::move(t1);
493 r0 = std::move(r1);
494 } else if (pct < 98) {
495 // operator==
496 EXPECT_EQ((t0 == t1), (r0 == r1));
497 } else if (pct < 99) {
498 // clear
499 t0.computeStats();
500 t0.clear();
501 r0.clear();
502 } else if (pct < 100) {
503 // reserve
504 auto scale = std::uniform_int_distribution<>(0, 8)(gen);
505 auto delta = std::uniform_int_distribution<>(-2, 2)(gen);
506 std::ptrdiff_t target = (t0.size() * scale) / 4 + delta;
507 if (target >= 0) {
508 t0.reserve(static_cast<std::size_t>(target));
509 r0.reserve(static_cast<std::size_t>(target));
510 }
511 }
512 }
513}
514
515TEST(F14ValueSet, simple) {
516 runSimple<F14ValueSet<std::string>>();
517}
518
519TEST(F14NodeSet, simple) {
520 runSimple<F14NodeSet<std::string>>();
521}
522
523TEST(F14VectorSet, simple) {
524 runSimple<F14VectorSet<std::string>>();
525}
526
527TEST(F14FastSet, simple) {
528 // F14FastSet inherits from a conditional typedef. Verify it compiles.
529 runRandom<F14FastSet<uint64_t>>();
530 runSimple<F14FastSet<std::string>>();
531}
532
533TEST(F14Set, ContainerSize) {
534 {
535 folly::F14ValueSet<int> set;
536 set.insert(10);
537 EXPECT_EQ(sizeof(set), 4 * sizeof(void*));
538 if (alignof(folly::max_align_t) == 16) {
539 // chunks will be allocated as 2 max_align_t-s
540 EXPECT_EQ(set.getAllocatedMemorySize(), 32);
541 } else {
542 // chunks will be allocated using aligned_malloc with the true size
543 EXPECT_EQ(set.getAllocatedMemorySize(), 24);
544 }
545 }
546 {
547 folly::F14NodeSet<int> set;
548 set.insert(10);
549 EXPECT_EQ(sizeof(set), 4 * sizeof(void*));
550 if (alignof(folly::max_align_t) == 16) {
551 // chunks will be allocated as 2 max_align_t-s
552 EXPECT_EQ(set.getAllocatedMemorySize(), 36);
553 } else {
554 // chunks will be allocated using aligned_malloc with the true size
555 EXPECT_EQ(set.getAllocatedMemorySize(), 20 + 2 * sizeof(void*));
556 }
557 }
558 {
559 folly::F14VectorSet<int> set;
560 set.insert(10);
561 EXPECT_EQ(sizeof(set), 8 + 2 * sizeof(void*));
562 EXPECT_EQ(set.getAllocatedMemorySize(), 32);
563 }
564}
565
566TEST(F14VectorMap, reverse_iterator) {
567 using TSet = F14VectorSet<uint64_t>;
568 auto populate = [](TSet& h, uint64_t lo, uint64_t hi) {
569 for (auto i = lo; i < hi; ++i) {
570 h.insert(i);
571 }
572 };
573 auto verify = [](TSet const& h, uint64_t lo, uint64_t hi) {
574 auto loIt = h.find(lo);
575 EXPECT_NE(h.end(), loIt);
576 uint64_t val = lo;
577 for (auto rit = h.riter(loIt); rit != h.rend(); ++rit) {
578 EXPECT_EQ(val, *rit);
579 TSet::const_iterator it = h.iter(rit);
580 EXPECT_EQ(val, *it);
581 val++;
582 }
583 EXPECT_EQ(hi, val);
584 };
585
586 TSet h;
587 size_t prevSize = 0;
588 size_t newSize = 1;
589 // verify iteration order across rehashes, copies, and moves
590 while (newSize < 10'000) {
591 populate(h, prevSize, newSize);
592 verify(h, 0, newSize);
593 verify(h, newSize / 2, newSize);
594
595 TSet h2{h};
596 verify(h2, 0, newSize);
597
598 h = std::move(h2);
599 verify(h, 0, newSize);
600 prevSize = newSize;
601 newSize *= 10;
602 }
603}
604
605TEST(F14ValueSet, rehash) {
606 runRehash<F14ValueSet<std::string>>();
607}
608
609TEST(F14NodeSet, rehash) {
610 runRehash<F14NodeSet<std::string>>();
611}
612
613TEST(F14VectorSet, rehash) {
614 runRehash<F14VectorSet<std::string>>();
615}
616
617TEST(F14ValueSet, random) {
618 runRandom<F14ValueSet<uint64_t>>();
619}
620
621TEST(F14NodeSet, random) {
622 runRandom<F14NodeSet<uint64_t>>();
623}
624
625TEST(F14VectorSet, random) {
626 runRandom<F14VectorSet<uint64_t>>();
627}
628
629TEST(F14ValueSet, grow_stats) {
630 F14ValueSet<uint64_t> h;
631 for (unsigned i = 1; i <= 3072; ++i) {
632 h.insert(i);
633 }
634 // F14ValueSet just before rehash
635 F14TableStats::compute(h);
636 h.insert(0);
637 // F14ValueSet just after rehash
638 F14TableStats::compute(h);
639}
640
641TEST(F14ValueSet, steady_state_stats) {
642 // 10k keys, 14% probability of insert, 90% chance of erase, so the
643 // table should converge to 1400 size without triggering the rehash
644 // that would occur at 1536.
645 F14ValueSet<uint64_t> h;
646 std::mt19937 gen(0);
647 std::uniform_int_distribution<> dist(0, 10000);
648 for (std::size_t i = 0; i < 100000; ++i) {
649 auto key = dist(gen);
650 if (dist(gen) < 1400) {
651 h.insert(key);
652 } else {
653 h.erase(key);
654 }
655 if (((i + 1) % 10000) == 0) {
656 auto stats = F14TableStats::compute(h);
657 // Verify that average miss probe length is bounded despite continued
658 // erase + reuse. p99 of the average across 10M random steps is 4.69,
659 // average is 2.96.
660 EXPECT_LT(f14::expectedProbe(stats.missProbeLengthHisto), 10.0);
661 }
662 }
663 // F14ValueSet at steady state
664 F14TableStats::compute(h);
665}
666
667// S should be a set of Tracked<0>. F should take a set
668// and a key_type const& or key_type&& and cause it to be inserted
669template <typename S, typename F>
670void runInsertCases(std::string const& /* name */, F const& insertFunc) {
671 static_assert(std::is_same<typename S::value_type, Tracked<0>>::value, "");
672 {
673 typename S::value_type k{0};
674 S s;
675 resetTracking();
676 insertFunc(s, k);
677 // fresh key, value_type const& ->
678 // copy is expected
679 EXPECT_EQ(Tracked<0>::counts.dist(Counts{1, 0, 0, 0}), 0);
680 }
681 {
682 typename S::value_type k{0};
683 S s;
684 resetTracking();
685 insertFunc(s, std::move(k));
686 // fresh key, value_type&& ->
687 // move is expected
688 EXPECT_EQ(Tracked<0>::counts.dist(Counts{0, 1, 0, 0}), 0);
689 }
690}
691
692struct DoInsert {
693 template <typename M, typename P>
694 void operator()(M& m, P&& p) const {
695 m.insert(std::forward<P>(p));
696 }
697};
698
699struct DoEmplace1 {
700 template <typename M, typename P>
701 void operator()(M& m, P&& p) const {
702 m.emplace(std::forward<P>(p));
703 }
704};
705
706template <typename S>
707void runInsertAndEmplace() {
708 {
709 typename S::value_type k1{0};
710 typename S::value_type k2{0};
711 S s;
712 resetTracking();
713 EXPECT_TRUE(s.insert(k1).second);
714 // copy is expected on successful insert
715 EXPECT_EQ(Tracked<0>::counts.dist(Counts{1, 0, 0, 0}), 0);
716
717 resetTracking();
718 EXPECT_FALSE(s.insert(k2).second);
719 // no copies or moves on failing insert
720 EXPECT_EQ(Tracked<0>::counts.dist(Counts{0, 0, 0, 0}), 0);
721 }
722 {
723 typename S::value_type k1{0};
724 typename S::value_type k2{0};
725 S s;
726 resetTracking();
727 EXPECT_TRUE(s.insert(std::move(k1)).second);
728 // move is expected on successful insert
729 EXPECT_EQ(Tracked<0>::counts.dist(Counts{0, 1, 0, 0}), 0);
730
731 resetTracking();
732 EXPECT_FALSE(s.insert(std::move(k2)).second);
733 // no copies or moves on failing insert
734 EXPECT_EQ(Tracked<0>::counts.dist(Counts{0, 0, 0, 0}), 0);
735 }
736 {
737 typename S::value_type k1{0};
738 typename S::value_type k2{0};
739 uint64_t k3 = 0;
740 S s;
741 resetTracking();
742 EXPECT_TRUE(s.emplace(k1).second);
743 // copy is expected on successful emplace
744 EXPECT_EQ(Tracked<0>::counts.dist(Counts{1, 0, 0, 0}), 0);
745
746 resetTracking();
747 EXPECT_FALSE(s.emplace(k2).second);
748 // no copies or moves on failing emplace with value_type
749 EXPECT_EQ(Tracked<0>::counts.dist(Counts{0, 0, 0, 0}), 0);
750
751 resetTracking();
752 EXPECT_FALSE(s.emplace(k3).second);
753 // copy convert expected for failing emplace with wrong type
754 EXPECT_EQ(Tracked<0>::counts.dist(Counts{0, 0, 1, 0}), 0);
755
756 s.clear();
757 resetTracking();
758 EXPECT_TRUE(s.emplace(k3).second);
759 // copy convert + move expected for successful emplace with wrong type
760 EXPECT_EQ(Tracked<0>::counts.dist(Counts{0, 1, 1, 0}), 0);
761 }
762 {
763 typename S::value_type k1{0};
764 typename S::value_type k2{0};
765 uint64_t k3 = 0;
766 S s;
767 resetTracking();
768 EXPECT_TRUE(s.emplace(std::move(k1)).second);
769 // move is expected on successful emplace
770 EXPECT_EQ(Tracked<0>::counts.dist(Counts{0, 1, 0, 0}), 0);
771
772 resetTracking();
773 EXPECT_FALSE(s.emplace(std::move(k2)).second);
774 // no copies or moves on failing emplace with value_type
775 EXPECT_EQ(Tracked<0>::counts.dist(Counts{0, 0, 0, 0}), 0);
776
777 resetTracking();
778 EXPECT_FALSE(s.emplace(std::move(k3)).second);
779 // move convert expected for failing emplace with wrong type
780 EXPECT_EQ(Tracked<0>::counts.dist(Counts{0, 0, 0, 1}), 0);
781
782 s.clear();
783 resetTracking();
784 EXPECT_TRUE(s.emplace(std::move(k3)).second);
785 // move convert + move expected for successful emplace with wrong type
786 EXPECT_EQ(Tracked<0>::counts.dist(Counts{0, 1, 0, 1}), 0);
787 }
788
789 // Calling the default pair constructor via emplace is valid, but not
790 // very useful in real life. Verify that it works.
791 S s;
792 typename S::value_type k;
793 EXPECT_EQ(s.count(k), 0);
794 s.emplace();
795 EXPECT_EQ(s.count(k), 1);
796 s.emplace();
797 EXPECT_EQ(s.count(k), 1);
798}
799
800TEST(F14ValueSet, destructuring) {
801 runInsertAndEmplace<F14ValueSet<Tracked<0>>>();
802}
803
804TEST(F14NodeSet, destructuring) {
805 runInsertAndEmplace<F14NodeSet<Tracked<0>>>();
806}
807
808TEST(F14VectorSet, destructuring) {
809 runInsertAndEmplace<F14VectorSet<Tracked<0>>>();
810}
811
812TEST(F14ValueSet, maxSize) {
813 F14ValueSet<int> s;
814 EXPECT_EQ(
815 s.max_size(), std::numeric_limits<std::size_t>::max() / sizeof(int));
816}
817
818TEST(F14NodeSet, maxSize) {
819 F14NodeSet<int> s;
820 EXPECT_EQ(
821 s.max_size(), std::numeric_limits<std::size_t>::max() / sizeof(int));
822}
823
824TEST(F14VectorSet, maxSize) {
825 F14VectorSet<int> s;
826 EXPECT_EQ(
827 s.max_size(),
828 std::min(
829 std::size_t{std::numeric_limits<uint32_t>::max()},
830 std::numeric_limits<std::size_t>::max() / sizeof(int)));
831}
832
833template <typename S>
834void runMoveOnlyTest() {
835 S t0;
836 t0.emplace(10);
837 t0.insert(20);
838 S t1{std::move(t0)};
839 EXPECT_TRUE(t0.empty());
840 S t2;
841 EXPECT_TRUE(t2.empty());
842 t2 = std::move(t1);
843 EXPECT_EQ(t2.size(), 2);
844}
845
846TEST(F14ValueSet, moveOnly) {
847 runMoveOnlyTest<F14ValueSet<f14::MoveOnlyTestInt>>();
848}
849
850TEST(F14NodeSet, moveOnly) {
851 runMoveOnlyTest<F14NodeSet<f14::MoveOnlyTestInt>>();
852}
853
854TEST(F14VectorSet, moveOnly) {
855 runMoveOnlyTest<F14VectorSet<f14::MoveOnlyTestInt>>();
856}
857
858TEST(F14FastSet, moveOnly) {
859 runMoveOnlyTest<F14FastSet<f14::MoveOnlyTestInt>>();
860}
861
862template <typename S>
863void runEraseIntoTest() {
864 S t0;
865 S t1;
866
867 auto insertIntoT0 = [&t0](auto&& value) {
868 EXPECT_FALSE(value.destroyed);
869 t0.emplace(std::move(value));
870 };
871 auto insertIntoT0Mut = [&](typename S::value_type&& value) mutable {
872 insertIntoT0(std::move(value));
873 };
874
875 t0.insert(10);
876 t1.insert(20);
877 t1.eraseInto(t1.begin(), insertIntoT0);
878 EXPECT_TRUE(t1.empty());
879 EXPECT_EQ(t0.size(), 2);
880 EXPECT_TRUE(t0.find(10) != t0.end());
881 EXPECT_TRUE(t0.find(20) != t0.end());
882
883 t1.insert(20);
884 t1.insert(30);
885 t1.insert(40);
886 t1.eraseInto(t1.begin(), t1.end(), insertIntoT0Mut);
887 EXPECT_TRUE(t1.empty());
888 EXPECT_EQ(t0.size(), 4);
889 EXPECT_TRUE(t0.find(30) != t0.end());
890 EXPECT_TRUE(t0.find(40) != t0.end());
891
892 t1.insert(50);
893 size_t erased = t1.eraseInto(*t1.find(50), insertIntoT0);
894 EXPECT_EQ(erased, 1);
895 EXPECT_TRUE(t1.empty());
896 EXPECT_EQ(t0.size(), 5);
897 EXPECT_TRUE(t0.find(50) != t0.end());
898
899 typename S::value_type key{60};
900 erased = t1.eraseInto(key, insertIntoT0Mut);
901 EXPECT_EQ(erased, 0);
902 EXPECT_EQ(t0.size(), 5);
903}
904
905TEST(F14ValueSet, eraseInto) {
906 runEraseIntoTest<F14ValueSet<f14::MoveOnlyTestInt>>();
907}
908
909TEST(F14NodeSet, eraseInto) {
910 runEraseIntoTest<F14NodeSet<f14::MoveOnlyTestInt>>();
911}
912
913TEST(F14VectorSet, eraseInto) {
914 runEraseIntoTest<F14VectorSet<f14::MoveOnlyTestInt>>();
915}
916
917TEST(F14FastSet, eraseInto) {
918 runEraseIntoTest<F14FastSet<f14::MoveOnlyTestInt>>();
919}
920
921TEST(F14ValueSet, heterogeneous) {
922 // note: std::string is implicitly convertible to but not from StringPiece
923 using Hasher = folly::transparent<folly::hasher<folly::StringPiece>>;
924 using KeyEqual = folly::transparent<std::equal_to<folly::StringPiece>>;
925
926 constexpr auto hello = "hello"_sp;
927 constexpr auto buddy = "buddy"_sp;
928 constexpr auto world = "world"_sp;
929
930 F14ValueSet<std::string, Hasher, KeyEqual> set;
931 set.emplace(hello);
932 set.emplace(world);
933
934 auto checks = [hello, buddy](auto& ref) {
935 // count
936 EXPECT_EQ(0, ref.count(buddy));
937 EXPECT_EQ(1, ref.count(hello));
938
939 // find
940 EXPECT_TRUE(ref.end() == ref.find(buddy));
941 EXPECT_EQ(hello, *ref.find(hello));
942
943 // prehash + find
944 EXPECT_TRUE(ref.end() == ref.find(ref.prehash(buddy), buddy));
945 EXPECT_EQ(hello, *ref.find(ref.prehash(hello), hello));
946
947 // equal_range
948 EXPECT_TRUE(std::make_pair(ref.end(), ref.end()) == ref.equal_range(buddy));
949 EXPECT_TRUE(
950 std::make_pair(ref.find(hello), ++ref.find(hello)) ==
951 ref.equal_range(hello));
952 };
953
954 checks(set);
955 checks(folly::as_const(set));
956}
957
958template <typename S>
959void runStatefulFunctorTest() {
960 bool ranHasher = false;
961 bool ranEqual = false;
962 bool ranAlloc = false;
963 bool ranDealloc = false;
964
965 auto hasher = [&](int x) {
966 ranHasher = true;
967 return x;
968 };
969 auto equal = [&](int x, int y) {
970 ranEqual = true;
971 return x == y;
972 };
973 auto alloc = [&](std::size_t n) {
974 ranAlloc = true;
975 return std::malloc(n);
976 };
977 auto dealloc = [&](void* p, std::size_t) {
978 ranDealloc = true;
979 std::free(p);
980 };
981
982 {
983 S set(0, hasher, equal, {alloc, dealloc});
984 set.insert(10);
985 set.insert(10);
986 EXPECT_EQ(set.size(), 1);
987
988 S set2(set);
989 S set3(std::move(set));
990 set = set2;
991 set2.clear();
992 set2 = std::move(set3);
993 }
994 EXPECT_TRUE(ranHasher);
995 EXPECT_TRUE(ranEqual);
996 EXPECT_TRUE(ranAlloc);
997 EXPECT_TRUE(ranDealloc);
998}
999
1000TEST(F14ValueSet, statefulFunctors) {
1001 runStatefulFunctorTest<F14ValueSet<
1002 int,
1003 GenericHasher<int>,
1004 GenericEqual<int>,
1005 GenericAlloc<int>>>();
1006}
1007
1008TEST(F14NodeSet, statefulFunctors) {
1009 runStatefulFunctorTest<F14NodeSet<
1010 int,
1011 GenericHasher<int>,
1012 GenericEqual<int>,
1013 GenericAlloc<int>>>();
1014}
1015
1016TEST(F14VectorSet, statefulFunctors) {
1017 runStatefulFunctorTest<F14VectorSet<
1018 int,
1019 GenericHasher<int>,
1020 GenericEqual<int>,
1021 GenericAlloc<int>>>();
1022}
1023
1024TEST(F14FastSet, statefulFunctors) {
1025 runStatefulFunctorTest<F14FastSet<
1026 int,
1027 GenericHasher<int>,
1028 GenericEqual<int>,
1029 GenericAlloc<int>>>();
1030}
1031
1032template <typename S>
1033void runHeterogeneousInsertTest() {
1034 S set;
1035
1036 resetTracking();
1037 EXPECT_EQ(set.count(10), 0);
1038 EXPECT_EQ(Tracked<1>::counts.dist(Counts{0, 0, 0, 0}), 0)
1039 << Tracked<1>::counts;
1040
1041 resetTracking();
1042 set.insert(10);
1043 EXPECT_EQ(Tracked<1>::counts.dist(Counts{0, 0, 0, 1}), 0)
1044 << Tracked<1>::counts;
1045
1046 resetTracking();
1047 int k = 10;
1048 std::vector<int> v({10});
1049 set.insert(10);
1050 set.insert(k);
1051 set.insert(v.begin(), v.end());
1052 set.insert(
1053 std::make_move_iterator(v.begin()), std::make_move_iterator(v.end()));
1054 set.emplace(10);
1055 set.emplace(k);
1056 EXPECT_EQ(Tracked<1>::counts.dist(Counts{0, 0, 0, 0}), 0)
1057 << Tracked<1>::counts;
1058
1059 resetTracking();
1060 set.erase(20);
1061 EXPECT_EQ(set.size(), 1);
1062 EXPECT_EQ(Tracked<1>::counts.dist(Counts{0, 0, 0, 0}), 0)
1063 << Tracked<1>::counts;
1064
1065 resetTracking();
1066 set.erase(10);
1067 EXPECT_EQ(set.size(), 0);
1068 EXPECT_EQ(Tracked<1>::counts.dist(Counts{0, 0, 0, 0}), 0)
1069 << Tracked<1>::counts;
1070
1071 set.insert(10);
1072 resetTracking();
1073 set.eraseInto(10, [](auto&&) {});
1074 EXPECT_EQ(Tracked<1>::counts.dist(Counts{0, 0, 0, 0}), 0)
1075 << Tracked<1>::counts;
1076}
1077
1078template <typename S>
1079void runHeterogeneousInsertStringTest() {
1080 S set;
1081 StringPiece k{"foo"};
1082 std::vector<StringPiece> v{k};
1083
1084 set.insert(k);
1085 set.insert("foo");
1086 set.insert(StringPiece{"foo"});
1087 set.insert(v.begin(), v.end());
1088 set.insert(
1089 std::make_move_iterator(v.begin()), std::make_move_iterator(v.end()));
1090
1091 set.emplace();
1092 set.emplace(k);
1093 set.emplace("foo");
1094 set.emplace(StringPiece("foo"));
1095
1096 set.erase("");
1097 set.erase(k);
1098 set.erase(StringPiece{"foo"});
1099 EXPECT_TRUE(set.empty());
1100}
1101
1102TEST(F14ValueSet, heterogeneousInsert) {
1103 runHeterogeneousInsertTest<F14ValueSet<
1104 Tracked<1>,
1105 TransparentTrackedHash<1>,
1106 TransparentTrackedEqual<1>>>();
1107 runHeterogeneousInsertStringTest<F14ValueSet<
1108 std::string,
1109 transparent<hasher<StringPiece>>,
1110 transparent<DefaultKeyEqual<StringPiece>>>>();
1111 runHeterogeneousInsertStringTest<F14ValueSet<std::string>>();
1112}
1113
1114TEST(F14NodeSet, heterogeneousInsert) {
1115 runHeterogeneousInsertTest<F14NodeSet<
1116 Tracked<1>,
1117 TransparentTrackedHash<1>,
1118 TransparentTrackedEqual<1>>>();
1119 runHeterogeneousInsertStringTest<F14NodeSet<
1120 std::string,
1121 transparent<hasher<StringPiece>>,
1122 transparent<DefaultKeyEqual<StringPiece>>>>();
1123 runHeterogeneousInsertStringTest<F14NodeSet<std::string>>();
1124}
1125
1126TEST(F14VectorSet, heterogeneousInsert) {
1127 runHeterogeneousInsertTest<F14VectorSet<
1128 Tracked<1>,
1129 TransparentTrackedHash<1>,
1130 TransparentTrackedEqual<1>>>();
1131 runHeterogeneousInsertStringTest<F14VectorSet<
1132 std::string,
1133 transparent<hasher<StringPiece>>,
1134 transparent<DefaultKeyEqual<StringPiece>>>>();
1135 runHeterogeneousInsertStringTest<F14VectorSet<std::string>>();
1136}
1137
1138TEST(F14FastSet, heterogeneousInsert) {
1139 runHeterogeneousInsertTest<F14FastSet<
1140 Tracked<1>,
1141 TransparentTrackedHash<1>,
1142 TransparentTrackedEqual<1>>>();
1143 runHeterogeneousInsertStringTest<F14FastSet<
1144 std::string,
1145 transparent<hasher<StringPiece>>,
1146 transparent<DefaultKeyEqual<StringPiece>>>>();
1147 runHeterogeneousInsertStringTest<F14FastSet<std::string>>();
1148}
1149
1150namespace {
1151
1152// std::is_convertible is not transitive :( Problem scenario: B<T> is
1153// implicitly convertible to A, so hasher that takes A can be used as a
1154// transparent hasher for a map with key of type B<T>. C is implicitly
1155// convertible to any B<T>, but we have to disable heterogeneous find
1156// for C. There is no way to infer the T of the intermediate type so C
1157// can't be used to explicitly construct A.
1158
1159struct A {
1160 int value;
1161
1162 bool operator==(A const& rhs) const {
1163 return value == rhs.value;
1164 }
1165 bool operator!=(A const& rhs) const {
1166 return !(*this == rhs);
1167 }
1168};
1169
1170struct AHasher {
1171 std::size_t operator()(A const& v) const {
1172 return v.value;
1173 }
1174};
1175
1176template <typename T>
1177struct B {
1178 int value;
1179
1180 explicit B(int v) : value(v) {}
1181
1182 /* implicit */ B(A const& v) : value(v.value) {}
1183
1184 /* implicit */ operator A() const {
1185 return A{value};
1186 }
1187};
1188
1189struct C {
1190 int value;
1191
1192 template <typename T>
1193 /* implicit */ operator B<T>() const {
1194 return B<T>{value};
1195 }
1196};
1197} // namespace
1198
1199TEST(F14FastSet, disabledDoubleTransparent) {
1200 static_assert(std::is_convertible<B<char>, A>::value, "");
1201 static_assert(std::is_convertible<C, B<char>>::value, "");
1202 static_assert(!std::is_convertible<C, A>::value, "");
1203
1204 F14FastSet<
1205 B<char>,
1206 folly::transparent<AHasher>,
1207 folly::transparent<std::equal_to<A>>>
1208 set;
1209 set.emplace(A{10});
1210
1211 EXPECT_TRUE(set.find(C{10}) != set.end());
1212 EXPECT_TRUE(set.find(C{20}) == set.end());
1213}
1214
1215namespace {
1216struct CharArrayHasher {
1217 template <std::size_t N>
1218 std::size_t operator()(std::array<char, N> const& value) const {
1219 return folly::Hash{}(
1220 StringPiece{value.data(), &value.data()[value.size()]});
1221 }
1222};
1223
1224template <
1225 template <typename, typename, typename, typename> class S,
1226 std::size_t N>
1227struct RunAllValueSizeTests {
1228 void operator()() const {
1229 using Key = std::array<char, N>;
1230 static_assert(sizeof(Key) == N, "");
1231 S<Key, CharArrayHasher, std::equal_to<Key>, std::allocator<Key>> set;
1232
1233 for (int i = 0; i < 100; ++i) {
1234 Key key{{static_cast<char>(i)}};
1235 set.insert(key);
1236 }
1237 while (!set.empty()) {
1238 set.erase(set.begin());
1239 }
1240
1241 RunAllValueSizeTests<S, N - 1>{}();
1242 }
1243};
1244
1245template <template <typename, typename, typename, typename> class S>
1246struct RunAllValueSizeTests<S, 0> {
1247 void operator()() const {}
1248};
1249} // namespace
1250
1251TEST(F14ValueSet, valueSize) {
1252 RunAllValueSizeTests<F14ValueSet, 32>{}();
1253}
1254
1255template <typename S, typename F>
1256void runRandomInsertOrderTest(F&& func) {
1257 if (FOLLY_F14_PERTURB_INSERTION_ORDER) {
1258 std::string prev;
1259 bool diffFound = false;
1260 for (int tries = 0; tries < 100; ++tries) {
1261 S set;
1262 for (char x = '0'; x <= '9'; ++x) {
1263 set.emplace(func(x));
1264 }
1265 std::string s;
1266 for (auto&& e : set) {
1267 s += e;
1268 }
1269 LOG(INFO) << s << "\n";
1270 if (prev.empty()) {
1271 prev = s;
1272 continue;
1273 }
1274 if (prev != s) {
1275 diffFound = true;
1276 break;
1277 }
1278 }
1279 EXPECT_TRUE(diffFound) << "no randomness found in insert order";
1280 }
1281}
1282
1283TEST(F14Set, randomInsertOrder) {
1284 runRandomInsertOrderTest<F14ValueSet<char>>([](char x) { return x; });
1285 runRandomInsertOrderTest<F14FastSet<char>>([](char x) { return x; });
1286 runRandomInsertOrderTest<F14FastSet<std::string>>([](char x) {
1287 return std::string{std::size_t{1}, x};
1288 });
1289}
1290
1291///////////////////////////////////
1292#endif // FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE
1293///////////////////////////////////
1294