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 | |
26 | template <template <typename, typename, typename, typename> class TSet> |
27 | void 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 | |
43 | TEST(F14Set, customSwap) { |
44 | testCustomSwap<folly::F14ValueSet>(); |
45 | testCustomSwap<folly::F14NodeSet>(); |
46 | testCustomSwap<folly::F14VectorSet>(); |
47 | testCustomSwap<folly::F14FastSet>(); |
48 | } |
49 | |
50 | namespace { |
51 | template < |
52 | template <typename, typename, typename, typename> class TSet, |
53 | typename K> |
54 | void 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 | |
108 | template <typename K> |
109 | void 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 | |
117 | TEST(F14Set, getAllocatedMemorySize) { |
118 | runAllocatedMemorySizeTests<bool>(); |
119 | runAllocatedMemorySizeTests<int>(); |
120 | runAllocatedMemorySizeTests<long>(); |
121 | runAllocatedMemorySizeTests<double>(); |
122 | runAllocatedMemorySizeTests<std::string>(); |
123 | runAllocatedMemorySizeTests<folly::fbstring>(); |
124 | } |
125 | |
126 | template <typename S> |
127 | void 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 | |
155 | template <typename S> |
156 | void runVisitContiguousRangesTest() { |
157 | runVisitContiguousRangesTest<S>(0); // empty |
158 | runVisitContiguousRangesTest<S>(5); // single chunk |
159 | runVisitContiguousRangesTest<S>(1000); // many chunks |
160 | } |
161 | |
162 | TEST(F14ValueSet, visitContiguousRanges) { |
163 | runVisitContiguousRangesTest<folly::F14ValueSet<int>>(); |
164 | } |
165 | |
166 | TEST(F14NodeSet, visitContiguousRanges) { |
167 | runVisitContiguousRangesTest<folly::F14NodeSet<int>>(); |
168 | } |
169 | |
170 | TEST(F14VectorSet, visitContiguousRanges) { |
171 | runVisitContiguousRangesTest<folly::F14VectorSet<int>>(); |
172 | } |
173 | |
174 | TEST(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 | |
189 | using namespace folly; |
190 | using namespace folly::f14; |
191 | using namespace folly::string_piece_literals; |
192 | |
193 | namespace { |
194 | std::string s(char const* p) { |
195 | return p; |
196 | } |
197 | } // namespace |
198 | |
199 | template <typename T> |
200 | void 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 | |
315 | template <typename T> |
316 | void 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 |
327 | template <typename T> |
328 | void 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 | |
515 | TEST(F14ValueSet, simple) { |
516 | runSimple<F14ValueSet<std::string>>(); |
517 | } |
518 | |
519 | TEST(F14NodeSet, simple) { |
520 | runSimple<F14NodeSet<std::string>>(); |
521 | } |
522 | |
523 | TEST(F14VectorSet, simple) { |
524 | runSimple<F14VectorSet<std::string>>(); |
525 | } |
526 | |
527 | TEST(F14FastSet, simple) { |
528 | // F14FastSet inherits from a conditional typedef. Verify it compiles. |
529 | runRandom<F14FastSet<uint64_t>>(); |
530 | runSimple<F14FastSet<std::string>>(); |
531 | } |
532 | |
533 | TEST(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 | |
566 | TEST(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 | |
605 | TEST(F14ValueSet, rehash) { |
606 | runRehash<F14ValueSet<std::string>>(); |
607 | } |
608 | |
609 | TEST(F14NodeSet, rehash) { |
610 | runRehash<F14NodeSet<std::string>>(); |
611 | } |
612 | |
613 | TEST(F14VectorSet, rehash) { |
614 | runRehash<F14VectorSet<std::string>>(); |
615 | } |
616 | |
617 | TEST(F14ValueSet, random) { |
618 | runRandom<F14ValueSet<uint64_t>>(); |
619 | } |
620 | |
621 | TEST(F14NodeSet, random) { |
622 | runRandom<F14NodeSet<uint64_t>>(); |
623 | } |
624 | |
625 | TEST(F14VectorSet, random) { |
626 | runRandom<F14VectorSet<uint64_t>>(); |
627 | } |
628 | |
629 | TEST(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 | |
641 | TEST(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 |
669 | template <typename S, typename F> |
670 | void 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 | |
692 | struct 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 | |
699 | struct 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 | |
706 | template <typename S> |
707 | void 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 | |
800 | TEST(F14ValueSet, destructuring) { |
801 | runInsertAndEmplace<F14ValueSet<Tracked<0>>>(); |
802 | } |
803 | |
804 | TEST(F14NodeSet, destructuring) { |
805 | runInsertAndEmplace<F14NodeSet<Tracked<0>>>(); |
806 | } |
807 | |
808 | TEST(F14VectorSet, destructuring) { |
809 | runInsertAndEmplace<F14VectorSet<Tracked<0>>>(); |
810 | } |
811 | |
812 | TEST(F14ValueSet, maxSize) { |
813 | F14ValueSet<int> s; |
814 | EXPECT_EQ( |
815 | s.max_size(), std::numeric_limits<std::size_t>::max() / sizeof(int)); |
816 | } |
817 | |
818 | TEST(F14NodeSet, maxSize) { |
819 | F14NodeSet<int> s; |
820 | EXPECT_EQ( |
821 | s.max_size(), std::numeric_limits<std::size_t>::max() / sizeof(int)); |
822 | } |
823 | |
824 | TEST(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 | |
833 | template <typename S> |
834 | void 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 | |
846 | TEST(F14ValueSet, moveOnly) { |
847 | runMoveOnlyTest<F14ValueSet<f14::MoveOnlyTestInt>>(); |
848 | } |
849 | |
850 | TEST(F14NodeSet, moveOnly) { |
851 | runMoveOnlyTest<F14NodeSet<f14::MoveOnlyTestInt>>(); |
852 | } |
853 | |
854 | TEST(F14VectorSet, moveOnly) { |
855 | runMoveOnlyTest<F14VectorSet<f14::MoveOnlyTestInt>>(); |
856 | } |
857 | |
858 | TEST(F14FastSet, moveOnly) { |
859 | runMoveOnlyTest<F14FastSet<f14::MoveOnlyTestInt>>(); |
860 | } |
861 | |
862 | template <typename S> |
863 | void 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 | |
905 | TEST(F14ValueSet, eraseInto) { |
906 | runEraseIntoTest<F14ValueSet<f14::MoveOnlyTestInt>>(); |
907 | } |
908 | |
909 | TEST(F14NodeSet, eraseInto) { |
910 | runEraseIntoTest<F14NodeSet<f14::MoveOnlyTestInt>>(); |
911 | } |
912 | |
913 | TEST(F14VectorSet, eraseInto) { |
914 | runEraseIntoTest<F14VectorSet<f14::MoveOnlyTestInt>>(); |
915 | } |
916 | |
917 | TEST(F14FastSet, eraseInto) { |
918 | runEraseIntoTest<F14FastSet<f14::MoveOnlyTestInt>>(); |
919 | } |
920 | |
921 | TEST(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 | |
958 | template <typename S> |
959 | void 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 | |
1000 | TEST(F14ValueSet, statefulFunctors) { |
1001 | runStatefulFunctorTest<F14ValueSet< |
1002 | int, |
1003 | GenericHasher<int>, |
1004 | GenericEqual<int>, |
1005 | GenericAlloc<int>>>(); |
1006 | } |
1007 | |
1008 | TEST(F14NodeSet, statefulFunctors) { |
1009 | runStatefulFunctorTest<F14NodeSet< |
1010 | int, |
1011 | GenericHasher<int>, |
1012 | GenericEqual<int>, |
1013 | GenericAlloc<int>>>(); |
1014 | } |
1015 | |
1016 | TEST(F14VectorSet, statefulFunctors) { |
1017 | runStatefulFunctorTest<F14VectorSet< |
1018 | int, |
1019 | GenericHasher<int>, |
1020 | GenericEqual<int>, |
1021 | GenericAlloc<int>>>(); |
1022 | } |
1023 | |
1024 | TEST(F14FastSet, statefulFunctors) { |
1025 | runStatefulFunctorTest<F14FastSet< |
1026 | int, |
1027 | GenericHasher<int>, |
1028 | GenericEqual<int>, |
1029 | GenericAlloc<int>>>(); |
1030 | } |
1031 | |
1032 | template <typename S> |
1033 | void 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 | |
1078 | template <typename S> |
1079 | void 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 | |
1102 | TEST(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 | |
1114 | TEST(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 | |
1126 | TEST(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 | |
1138 | TEST(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 | |
1150 | namespace { |
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 | |
1159 | struct 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 | |
1170 | struct AHasher { |
1171 | std::size_t operator()(A const& v) const { |
1172 | return v.value; |
1173 | } |
1174 | }; |
1175 | |
1176 | template <typename T> |
1177 | struct 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 | |
1189 | struct 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 | |
1199 | TEST(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 | |
1215 | namespace { |
1216 | struct 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 | |
1224 | template < |
1225 | template <typename, typename, typename, typename> class S, |
1226 | std::size_t N> |
1227 | struct 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 | |
1245 | template <template <typename, typename, typename, typename> class S> |
1246 | struct RunAllValueSizeTests<S, 0> { |
1247 | void operator()() const {} |
1248 | }; |
1249 | } // namespace |
1250 | |
1251 | TEST(F14ValueSet, valueSize) { |
1252 | RunAllValueSizeTests<F14ValueSet, 32>{}(); |
1253 | } |
1254 | |
1255 | template <typename S, typename F> |
1256 | void 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 | |
1283 | TEST(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 | |