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 | |
27 | template <template <typename, typename, typename, typename, typename> |
28 | class TMap> |
29 | void 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 | |
46 | TEST(F14Map, customSwap) { |
47 | testCustomSwap<folly::F14ValueMap>(); |
48 | testCustomSwap<folly::F14NodeMap>(); |
49 | testCustomSwap<folly::F14VectorMap>(); |
50 | testCustomSwap<folly::F14FastMap>(); |
51 | } |
52 | |
53 | template < |
54 | template <typename, typename, typename, typename, typename> class TMap, |
55 | typename K, |
56 | typename V> |
57 | void 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 | |
111 | template <typename K, typename V> |
112 | void 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 | |
119 | TEST(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 | |
129 | template <typename M> |
130 | void 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 | |
158 | template <typename M> |
159 | void runVisitContiguousRangesTest() { |
160 | runVisitContiguousRangesTest<M>(0); // empty |
161 | runVisitContiguousRangesTest<M>(5); // single chunk |
162 | runVisitContiguousRangesTest<M>(1000); // many chunks |
163 | } |
164 | |
165 | TEST(F14ValueMap, visitContiguousRanges) { |
166 | runVisitContiguousRangesTest<folly::F14ValueMap<int, int>>(); |
167 | } |
168 | |
169 | TEST(F14NodeMap, visitContiguousRanges) { |
170 | runVisitContiguousRangesTest<folly::F14NodeMap<int, int>>(); |
171 | } |
172 | |
173 | TEST(F14VectorMap, visitContiguousRanges) { |
174 | runVisitContiguousRangesTest<folly::F14VectorMap<int, int>>(); |
175 | } |
176 | |
177 | TEST(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 | |
194 | using namespace folly; |
195 | using namespace folly::f14; |
196 | using namespace folly::string_piece_literals; |
197 | |
198 | namespace { |
199 | std::string s(char const* p) { |
200 | return p; |
201 | } |
202 | } // namespace |
203 | |
204 | template <typename T> |
205 | void 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 | |
330 | template <typename T> |
331 | void 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 |
347 | template <typename T> |
348 | void 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 | |
608 | template <typename T> |
609 | void 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 | |
625 | TEST(F14ValueMap, simple) { |
626 | runSimple<F14ValueMap<std::string, std::string>>(); |
627 | } |
628 | |
629 | TEST(F14NodeMap, simple) { |
630 | runSimple<F14NodeMap<std::string, std::string>>(); |
631 | } |
632 | |
633 | TEST(F14VectorMap, simple) { |
634 | runSimple<F14VectorMap<std::string, std::string>>(); |
635 | } |
636 | |
637 | TEST(F14FastMap, simple) { |
638 | runSimple<F14FastMap<std::string, std::string>>(); |
639 | } |
640 | |
641 | TEST(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 | |
681 | TEST(F14ValueMap, rehash) { |
682 | runRehash<F14ValueMap<std::string, std::string>>(); |
683 | } |
684 | |
685 | TEST(F14NodeMap, rehash) { |
686 | runRehash<F14NodeMap<std::string, std::string>>(); |
687 | } |
688 | |
689 | TEST(F14VectorMap, rehash) { |
690 | runRehash<F14VectorMap<std::string, std::string>>(); |
691 | } |
692 | |
693 | TEST(F14ValueMap, prehash) { |
694 | runPrehash<F14ValueMap<std::string, std::string>>(); |
695 | } |
696 | |
697 | TEST(F14NodeMap, prehash) { |
698 | runPrehash<F14NodeMap<std::string, std::string>>(); |
699 | } |
700 | |
701 | TEST(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 | |
710 | TEST(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 | |
719 | TEST(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 | |
728 | TEST(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 | |
737 | TEST(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 | |
749 | TEST(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 | |
775 | TEST(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 | |
801 | TEST(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 |
868 | template <typename M, typename F> |
869 | void 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 | |
1069 | struct 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 | |
1076 | struct 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 | |
1083 | struct 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 | |
1095 | struct 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. |
1117 | struct 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 | |
1135 | template <typename M> |
1136 | void 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 | |
1154 | TEST(F14ValueMap, destructuring) { |
1155 | runInsertAndEmplace<F14ValueMap<Tracked<0>, Tracked<1>>>("f14value" ); |
1156 | } |
1157 | |
1158 | TEST(F14NodeMap, destructuring) { |
1159 | runInsertAndEmplace<F14NodeMap<Tracked<0>, Tracked<1>>>("f14node" ); |
1160 | } |
1161 | |
1162 | TEST(F14VectorMap, destructuring) { |
1163 | runInsertAndEmplace<F14VectorMap<Tracked<0>, Tracked<1>>>("f14vector" ); |
1164 | } |
1165 | |
1166 | TEST(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 | |
1186 | TEST(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 | |
1193 | TEST(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 | |
1200 | TEST(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 | |
1210 | template <typename M> |
1211 | void 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 | |
1224 | TEST(F14ValueMap, moveOnly) { |
1225 | runMoveOnlyTest<F14ValueMap<f14::MoveOnlyTestInt, int>>(); |
1226 | runMoveOnlyTest<F14ValueMap<int, f14::MoveOnlyTestInt>>(); |
1227 | runMoveOnlyTest<F14ValueMap<f14::MoveOnlyTestInt, f14::MoveOnlyTestInt>>(); |
1228 | } |
1229 | |
1230 | TEST(F14NodeMap, moveOnly) { |
1231 | runMoveOnlyTest<F14NodeMap<f14::MoveOnlyTestInt, int>>(); |
1232 | runMoveOnlyTest<F14NodeMap<int, f14::MoveOnlyTestInt>>(); |
1233 | runMoveOnlyTest<F14NodeMap<f14::MoveOnlyTestInt, f14::MoveOnlyTestInt>>(); |
1234 | } |
1235 | |
1236 | TEST(F14VectorMap, moveOnly) { |
1237 | runMoveOnlyTest<F14VectorMap<f14::MoveOnlyTestInt, int>>(); |
1238 | runMoveOnlyTest<F14VectorMap<int, f14::MoveOnlyTestInt>>(); |
1239 | runMoveOnlyTest<F14VectorMap<f14::MoveOnlyTestInt, f14::MoveOnlyTestInt>>(); |
1240 | } |
1241 | |
1242 | TEST(F14FastMap, moveOnly) { |
1243 | runMoveOnlyTest<F14FastMap<f14::MoveOnlyTestInt, int>>(); |
1244 | runMoveOnlyTest<F14FastMap<int, f14::MoveOnlyTestInt>>(); |
1245 | runMoveOnlyTest<F14FastMap<f14::MoveOnlyTestInt, f14::MoveOnlyTestInt>>(); |
1246 | } |
1247 | |
1248 | TEST(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 | |
1284 | template <typename M> |
1285 | void 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 | |
1326 | TEST(F14ValueMap, statefulFunctors) { |
1327 | runStatefulFunctorTest<F14ValueMap< |
1328 | int, |
1329 | int, |
1330 | GenericHasher<int>, |
1331 | GenericEqual<int>, |
1332 | GenericAlloc<std::pair<int const, int>>>>(); |
1333 | } |
1334 | |
1335 | TEST(F14NodeMap, statefulFunctors) { |
1336 | runStatefulFunctorTest<F14NodeMap< |
1337 | int, |
1338 | int, |
1339 | GenericHasher<int>, |
1340 | GenericEqual<int>, |
1341 | GenericAlloc<std::pair<int const, int>>>>(); |
1342 | } |
1343 | |
1344 | TEST(F14VectorMap, statefulFunctors) { |
1345 | runStatefulFunctorTest<F14VectorMap< |
1346 | int, |
1347 | int, |
1348 | GenericHasher<int>, |
1349 | GenericEqual<int>, |
1350 | GenericAlloc<std::pair<int const, int>>>>(); |
1351 | } |
1352 | |
1353 | TEST(F14FastMap, statefulFunctors) { |
1354 | runStatefulFunctorTest<F14FastMap< |
1355 | int, |
1356 | int, |
1357 | GenericHasher<int>, |
1358 | GenericEqual<int>, |
1359 | GenericAlloc<std::pair<int const, int>>>>(); |
1360 | } |
1361 | |
1362 | template <typename M> |
1363 | void 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 | |
1409 | template <typename M> |
1410 | void 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 | |
1456 | TEST(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 | |
1470 | TEST(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 | |
1484 | TEST(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 | |
1498 | TEST(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 | |
1512 | namespace { |
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 | |
1521 | struct 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 | |
1532 | struct AHasher { |
1533 | std::size_t operator()(A const& v) const { |
1534 | return v.value; |
1535 | } |
1536 | }; |
1537 | |
1538 | template <typename T> |
1539 | struct 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 | |
1551 | struct 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 | |
1561 | TEST(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 | |
1578 | template <typename M> |
1579 | void 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 | |
1612 | TEST(F14Map, randomInsertOrder) { |
1613 | runRandomInsertOrderTest<F14ValueMap<char, char>>(); |
1614 | runRandomInsertOrderTest<F14FastMap<char, char>>(); |
1615 | runRandomInsertOrderTest<F14FastMap<char, std::string>>(); |
1616 | } |
1617 | |
1618 | template <typename M> |
1619 | void 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 | |
1663 | TEST(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 | |
1673 | TEST(F14Map, continuousCapacityBig0) { |
1674 | runContinuousCapacityTest<folly::F14VectorMap<std::size_t, std::string>>( |
1675 | 1000000 - 1, 1000000 - 1); |
1676 | } |
1677 | |
1678 | TEST(F14Map, continuousCapacityBig1) { |
1679 | runContinuousCapacityTest<folly::F14VectorMap<std::size_t, std::string>>( |
1680 | 1000000, 1000000); |
1681 | } |
1682 | |
1683 | TEST(F14Map, continuousCapacityBig2) { |
1684 | runContinuousCapacityTest<folly::F14VectorMap<std::size_t, std::string>>( |
1685 | 1000000 + 1, 1000000 + 1); |
1686 | } |
1687 | |
1688 | TEST(F14Map, continuousCapacityBig3) { |
1689 | runContinuousCapacityTest<folly::F14VectorMap<std::size_t, std::string>>( |
1690 | 1000000 + 2, 1000000 + 2); |
1691 | } |
1692 | |
1693 | TEST(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 | |