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 | #pragma once |
18 | |
19 | /** |
20 | * F14NodeSet, F14ValueSet, and F14VectorSet |
21 | * |
22 | * F14FastSet conditionally inherits from F14ValueSet or F14VectorSet |
23 | * |
24 | * See F14.md |
25 | * |
26 | * @author Nathan Bronson <ngbronson@fb.com> |
27 | * @author Xiao Shi <xshi@fb.com> |
28 | */ |
29 | |
30 | #include <tuple> |
31 | |
32 | #include <folly/lang/SafeAssert.h> |
33 | |
34 | #include <folly/container/F14Set-fwd.h> |
35 | #include <folly/container/detail/F14Policy.h> |
36 | #include <folly/container/detail/F14Table.h> |
37 | |
38 | #if !FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE |
39 | |
40 | //////// Compatibility for unsupported platforms (not x86_64 and not aarch64) |
41 | |
42 | #include <unordered_set> |
43 | |
44 | namespace folly { |
45 | |
46 | namespace f14 { |
47 | namespace detail { |
48 | template <typename K, typename H, typename E, typename A> |
49 | class F14BasicSet : public std::unordered_set<K, H, E, A> { |
50 | using Super = std::unordered_set<K, H, E, A>; |
51 | |
52 | public: |
53 | using typename Super::pointer; |
54 | using typename Super::value_type; |
55 | |
56 | F14BasicSet() = default; |
57 | |
58 | using Super::Super; |
59 | |
60 | //// PUBLIC - F14 Extensions |
61 | |
62 | // exact for libstdc++, approximate for others |
63 | std::size_t getAllocatedMemorySize() const { |
64 | std::size_t rv = 0; |
65 | visitAllocationClasses( |
66 | [&](std::size_t bytes, std::size_t n) { rv += bytes * n; }); |
67 | return rv; |
68 | } |
69 | |
70 | // exact for libstdc++, approximate for others |
71 | template <typename V> |
72 | void visitAllocationClasses(V&& visitor) const { |
73 | auto bc = this->bucket_count(); |
74 | if (bc > 1) { |
75 | visitor(bc * sizeof(pointer), 1); |
76 | } |
77 | if (this->size() > 0) { |
78 | visitor(sizeof(StdNodeReplica<K, value_type, H>), this->size()); |
79 | } |
80 | } |
81 | |
82 | template <typename V> |
83 | void visitContiguousRanges(V&& visitor) const { |
84 | for (value_type const& entry : *this) { |
85 | value_type const* b = std::addressof(entry); |
86 | visitor(b, b + 1); |
87 | } |
88 | } |
89 | }; |
90 | } // namespace detail |
91 | } // namespace f14 |
92 | |
93 | template <typename Key, typename Hasher, typename KeyEqual, typename Alloc> |
94 | class F14NodeSet |
95 | : public f14::detail::F14BasicSet<Key, Hasher, KeyEqual, Alloc> { |
96 | using Super = f14::detail::F14BasicSet<Key, Hasher, KeyEqual, Alloc>; |
97 | |
98 | public: |
99 | using typename Super::value_type; |
100 | |
101 | F14NodeSet() = default; |
102 | |
103 | using Super::Super; |
104 | |
105 | F14NodeSet& operator=(std::initializer_list<value_type> ilist) { |
106 | Super::operator=(ilist); |
107 | return *this; |
108 | } |
109 | }; |
110 | |
111 | template <typename Key, typename Hasher, typename KeyEqual, typename Alloc> |
112 | class F14ValueSet |
113 | : public f14::detail::F14BasicSet<Key, Hasher, KeyEqual, Alloc> { |
114 | using Super = f14::detail::F14BasicSet<Key, Hasher, KeyEqual, Alloc>; |
115 | |
116 | public: |
117 | using typename Super::value_type; |
118 | |
119 | F14ValueSet() : Super() {} |
120 | |
121 | using Super::Super; |
122 | |
123 | F14ValueSet& operator=(std::initializer_list<value_type> ilist) { |
124 | Super::operator=(ilist); |
125 | return *this; |
126 | } |
127 | }; |
128 | |
129 | template <typename Key, typename Hasher, typename KeyEqual, typename Alloc> |
130 | class F14VectorSet |
131 | : public f14::detail::F14BasicSet<Key, Hasher, KeyEqual, Alloc> { |
132 | using Super = f14::detail::F14BasicSet<Key, Hasher, KeyEqual, Alloc>; |
133 | |
134 | public: |
135 | using typename Super::value_type; |
136 | |
137 | F14VectorSet() = default; |
138 | |
139 | using Super::Super; |
140 | |
141 | F14VectorSet& operator=(std::initializer_list<value_type> ilist) { |
142 | Super::operator=(ilist); |
143 | return *this; |
144 | } |
145 | }; |
146 | |
147 | template <typename Key, typename Hasher, typename KeyEqual, typename Alloc> |
148 | class F14FastSet |
149 | : public f14::detail::F14BasicSet<Key, Hasher, KeyEqual, Alloc> { |
150 | using Super = f14::detail::F14BasicSet<Key, Hasher, KeyEqual, Alloc>; |
151 | |
152 | public: |
153 | using typename Super::value_type; |
154 | |
155 | F14FastSet() = default; |
156 | |
157 | using Super::Super; |
158 | |
159 | F14FastSet& operator=(std::initializer_list<value_type> ilist) { |
160 | Super::operator=(ilist); |
161 | return *this; |
162 | } |
163 | }; |
164 | } // namespace folly |
165 | |
166 | #else // FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE |
167 | |
168 | //////// Common case for supported platforms |
169 | |
170 | namespace folly { |
171 | namespace f14 { |
172 | namespace detail { |
173 | |
174 | template <typename Policy> |
175 | class F14BasicSet { |
176 | template <typename K, typename T> |
177 | using EnableHeterogeneousFind = std::enable_if_t< |
178 | EligibleForHeterogeneousFind< |
179 | typename Policy::Value, |
180 | typename Policy::Hasher, |
181 | typename Policy::KeyEqual, |
182 | K>::value, |
183 | T>; |
184 | |
185 | template <typename K, typename T> |
186 | using EnableHeterogeneousInsert = std::enable_if_t< |
187 | EligibleForHeterogeneousInsert< |
188 | typename Policy::Value, |
189 | typename Policy::Hasher, |
190 | typename Policy::KeyEqual, |
191 | K>::value, |
192 | T>; |
193 | |
194 | template <typename K, typename T> |
195 | using EnableHeterogeneousErase = std::enable_if_t< |
196 | EligibleForHeterogeneousFind< |
197 | typename Policy::Value, |
198 | typename Policy::Hasher, |
199 | typename Policy::KeyEqual, |
200 | K>::value && |
201 | !std::is_same<typename Policy::Iter, remove_cvref_t<K>>::value, |
202 | T>; |
203 | |
204 | public: |
205 | //// PUBLIC - Member types |
206 | |
207 | using key_type = typename Policy::Value; |
208 | using value_type = key_type; |
209 | using size_type = std::size_t; |
210 | using difference_type = std::ptrdiff_t; |
211 | using hasher = typename Policy::Hasher; |
212 | using key_equal = typename Policy::KeyEqual; |
213 | using allocator_type = typename Policy::Alloc; |
214 | using reference = value_type&; |
215 | using const_reference = value_type const&; |
216 | using pointer = typename Policy::AllocTraits::pointer; |
217 | using const_pointer = typename Policy::AllocTraits::const_pointer; |
218 | using iterator = typename Policy::Iter; |
219 | using const_iterator = iterator; |
220 | |
221 | private: |
222 | using ItemIter = typename Policy::ItemIter; |
223 | |
224 | public: |
225 | //// PUBLIC - Member functions |
226 | |
227 | F14BasicSet() noexcept(Policy::kDefaultConstructIsNoexcept) |
228 | : F14BasicSet(0) {} |
229 | |
230 | explicit F14BasicSet( |
231 | std::size_t initialCapacity, |
232 | hasher const& hash = hasher{}, |
233 | key_equal const& eq = key_equal{}, |
234 | allocator_type const& alloc = allocator_type{}) |
235 | : table_{initialCapacity, hash, eq, alloc} {} |
236 | |
237 | explicit F14BasicSet(std::size_t initialCapacity, allocator_type const& alloc) |
238 | : F14BasicSet(initialCapacity, hasher{}, key_equal{}, alloc) {} |
239 | |
240 | explicit F14BasicSet( |
241 | std::size_t initialCapacity, |
242 | hasher const& hash, |
243 | allocator_type const& alloc) |
244 | : F14BasicSet(initialCapacity, hash, key_equal{}, alloc) {} |
245 | |
246 | explicit F14BasicSet(allocator_type const& alloc) |
247 | : F14BasicSet(0, hasher{}, key_equal{}, alloc) {} |
248 | |
249 | template <typename InputIt> |
250 | F14BasicSet( |
251 | InputIt first, |
252 | InputIt last, |
253 | std::size_t initialCapacity = 0, |
254 | hasher const& hash = hasher{}, |
255 | key_equal const& eq = key_equal{}, |
256 | allocator_type const& alloc = allocator_type{}) |
257 | : table_{initialCapacity, hash, eq, alloc} { |
258 | initialInsert(first, last, initialCapacity); |
259 | } |
260 | |
261 | template <typename InputIt> |
262 | F14BasicSet( |
263 | InputIt first, |
264 | InputIt last, |
265 | std::size_t initialCapacity, |
266 | allocator_type const& alloc) |
267 | : table_{initialCapacity, hasher{}, key_equal{}, alloc} { |
268 | initialInsert(first, last, initialCapacity); |
269 | } |
270 | |
271 | template <typename InputIt> |
272 | F14BasicSet( |
273 | InputIt first, |
274 | InputIt last, |
275 | std::size_t initialCapacity, |
276 | hasher const& hash, |
277 | allocator_type const& alloc) |
278 | : table_{initialCapacity, hash, key_equal{}, alloc} { |
279 | initialInsert(first, last, initialCapacity); |
280 | } |
281 | |
282 | F14BasicSet(F14BasicSet const& rhs) = default; |
283 | |
284 | F14BasicSet(F14BasicSet const& rhs, allocator_type const& alloc) |
285 | : table_(rhs.table_, alloc) {} |
286 | |
287 | F14BasicSet(F14BasicSet&& rhs) = default; |
288 | |
289 | F14BasicSet(F14BasicSet&& rhs, allocator_type const& alloc) noexcept( |
290 | Policy::kAllocIsAlwaysEqual) |
291 | : table_{std::move(rhs.table_), alloc} {} |
292 | |
293 | F14BasicSet( |
294 | std::initializer_list<value_type> init, |
295 | std::size_t initialCapacity = 0, |
296 | hasher const& hash = hasher{}, |
297 | key_equal const& eq = key_equal{}, |
298 | allocator_type const& alloc = allocator_type{}) |
299 | : table_{initialCapacity, hash, eq, alloc} { |
300 | initialInsert(init.begin(), init.end(), initialCapacity); |
301 | } |
302 | |
303 | F14BasicSet( |
304 | std::initializer_list<value_type> init, |
305 | std::size_t initialCapacity, |
306 | allocator_type const& alloc) |
307 | : table_{initialCapacity, hasher{}, key_equal{}, alloc} { |
308 | initialInsert(init.begin(), init.end(), initialCapacity); |
309 | } |
310 | |
311 | F14BasicSet( |
312 | std::initializer_list<value_type> init, |
313 | std::size_t initialCapacity, |
314 | hasher const& hash, |
315 | allocator_type const& alloc) |
316 | : table_{initialCapacity, hash, key_equal{}, alloc} { |
317 | initialInsert(init.begin(), init.end(), initialCapacity); |
318 | } |
319 | |
320 | F14BasicSet& operator=(F14BasicSet const&) = default; |
321 | |
322 | F14BasicSet& operator=(F14BasicSet&&) = default; |
323 | |
324 | F14BasicSet& operator=(std::initializer_list<value_type> ilist) { |
325 | clear(); |
326 | bulkInsert(ilist.begin(), ilist.end(), false); |
327 | return *this; |
328 | } |
329 | |
330 | allocator_type get_allocator() const noexcept { |
331 | return table_.alloc(); |
332 | } |
333 | |
334 | //// PUBLIC - Iterators |
335 | |
336 | iterator begin() noexcept { |
337 | return cbegin(); |
338 | } |
339 | const_iterator begin() const noexcept { |
340 | return cbegin(); |
341 | } |
342 | const_iterator cbegin() const noexcept { |
343 | return table_.makeIter(table_.begin()); |
344 | } |
345 | |
346 | iterator end() noexcept { |
347 | return cend(); |
348 | } |
349 | const_iterator end() const noexcept { |
350 | return cend(); |
351 | } |
352 | const_iterator cend() const noexcept { |
353 | return table_.makeIter(table_.end()); |
354 | } |
355 | |
356 | //// PUBLIC - Capacity |
357 | |
358 | bool empty() const noexcept { |
359 | return table_.empty(); |
360 | } |
361 | |
362 | std::size_t size() const noexcept { |
363 | return table_.size(); |
364 | } |
365 | |
366 | std::size_t max_size() const noexcept { |
367 | return table_.max_size(); |
368 | } |
369 | |
370 | //// PUBLIC - Modifiers |
371 | |
372 | void clear() noexcept { |
373 | table_.clear(); |
374 | } |
375 | |
376 | std::pair<iterator, bool> insert(value_type const& value) { |
377 | return emplace(value); |
378 | } |
379 | |
380 | std::pair<iterator, bool> insert(value_type&& value) { |
381 | return emplace(std::move(value)); |
382 | } |
383 | |
384 | // std::unordered_set's hinted insertion API is misleading. No |
385 | // implementation I've seen actually uses the hint. Code restructuring |
386 | // by the caller to use the hinted API is at best unnecessary, and at |
387 | // worst a pessimization. It is used, however, so we provide it. |
388 | |
389 | iterator insert(const_iterator /*hint*/, value_type const& value) { |
390 | return insert(value).first; |
391 | } |
392 | |
393 | iterator insert(const_iterator /*hint*/, value_type&& value) { |
394 | return insert(std::move(value)).first; |
395 | } |
396 | |
397 | template <typename K> |
398 | EnableHeterogeneousInsert<K, std::pair<iterator, bool>> insert(K&& value) { |
399 | return emplace(std::forward<K>(value)); |
400 | } |
401 | |
402 | private: |
403 | template <class InputIt> |
404 | FOLLY_ALWAYS_INLINE void |
405 | bulkInsert(InputIt first, InputIt last, bool autoReserve) { |
406 | if (autoReserve) { |
407 | auto n = std::distance(first, last); |
408 | if (n == 0) { |
409 | return; |
410 | } |
411 | table_.reserveForInsert(n); |
412 | } |
413 | while (first != last) { |
414 | insert(*first); |
415 | ++first; |
416 | } |
417 | } |
418 | |
419 | template <class InputIt> |
420 | void initialInsert(InputIt first, InputIt last, std::size_t initialCapacity) { |
421 | FOLLY_SAFE_DCHECK(empty() && bucket_count() >= initialCapacity, "" ); |
422 | |
423 | // It's possible that there are a lot of duplicates in first..last and |
424 | // so we will oversize ourself. The common case, however, is that |
425 | // we can avoid a lot of rehashing if we pre-expand. The behavior |
426 | // is easy to disable at a particular call site by asking for an |
427 | // initialCapacity of 1. |
428 | bool autoReserve = |
429 | std::is_same< |
430 | typename std::iterator_traits<InputIt>::iterator_category, |
431 | std::random_access_iterator_tag>::value && |
432 | initialCapacity == 0; |
433 | bulkInsert(first, last, autoReserve); |
434 | } |
435 | |
436 | public: |
437 | template <class InputIt> |
438 | void insert(InputIt first, InputIt last) { |
439 | // Bulk reserve is a heuristic choice, so it can backfire. We restrict |
440 | // ourself to situations that mimic bulk construction without an |
441 | // explicit initialCapacity. |
442 | bool autoReserve = |
443 | std::is_same< |
444 | typename std::iterator_traits<InputIt>::iterator_category, |
445 | std::random_access_iterator_tag>::value && |
446 | bucket_count() == 0; |
447 | bulkInsert(first, last, autoReserve); |
448 | } |
449 | |
450 | void insert(std::initializer_list<value_type> ilist) { |
451 | insert(ilist.begin(), ilist.end()); |
452 | } |
453 | |
454 | template <class... Args> |
455 | std::pair<iterator, bool> emplace(Args&&... args) { |
456 | using K = KeyTypeForEmplace<key_type, hasher, key_equal, Args...>; |
457 | |
458 | // If args is a single arg that can be emplaced directly (either |
459 | // key_type or a heterogeneous find + conversion to key_type) key will |
460 | // just be a reference to that arg, otherwise this will construct an |
461 | // intermediate key. |
462 | K key(std::forward<Args>(args)...); |
463 | |
464 | auto rv = table_.tryEmplaceValue(key, std::forward<K>(key)); |
465 | |
466 | return std::make_pair(table_.makeIter(rv.first), rv.second); |
467 | } |
468 | |
469 | template <class... Args> |
470 | iterator emplace_hint(const_iterator /*hint*/, Args&&... args) { |
471 | return emplace(std::forward<Args>(args)...).first; |
472 | } |
473 | |
474 | FOLLY_ALWAYS_INLINE iterator erase(const_iterator pos) { |
475 | return eraseInto(pos, [](value_type&&) {}); |
476 | } |
477 | |
478 | iterator erase(const_iterator first, const_iterator last) { |
479 | return eraseInto(first, last, [](value_type&&) {}); |
480 | } |
481 | |
482 | size_type erase(key_type const& key) { |
483 | return eraseInto(key, [](value_type&&) {}); |
484 | } |
485 | |
486 | template <typename K> |
487 | EnableHeterogeneousErase<K, size_type> erase(K const& key) { |
488 | return eraseInto(key, [](value_type&&) {}); |
489 | } |
490 | |
491 | // eraseInto contains the same overloads as erase but provides |
492 | // an additional callback argument which is called with an rvalue |
493 | // reference to the item directly before it is destroyed. This can be |
494 | // used to extract an item out of a F14Set while avoiding a copy. |
495 | template <typename BeforeDestroy> |
496 | FOLLY_ALWAYS_INLINE iterator |
497 | eraseInto(const_iterator pos, BeforeDestroy&& beforeDestroy) { |
498 | auto itemPos = table_.unwrapIter(pos); |
499 | table_.eraseIterInto(itemPos, beforeDestroy); |
500 | |
501 | // If we are inlined then gcc and clang can optimize away all of the |
502 | // work of ++pos if the caller discards it. |
503 | itemPos.advanceLikelyDead(); |
504 | return table_.makeIter(itemPos); |
505 | } |
506 | |
507 | template <typename BeforeDestroy> |
508 | iterator eraseInto( |
509 | const_iterator first, |
510 | const_iterator last, |
511 | BeforeDestroy&& beforeDestroy) { |
512 | while (first != last) { |
513 | first = eraseInto(first, beforeDestroy); |
514 | } |
515 | return first; |
516 | } |
517 | |
518 | template <typename BeforeDestroy> |
519 | size_type eraseInto(key_type const& key, BeforeDestroy&& beforeDestroy) { |
520 | return table_.eraseKeyInto(key, beforeDestroy); |
521 | } |
522 | |
523 | template <typename K, typename BeforeDestroy> |
524 | EnableHeterogeneousErase<K, size_type> eraseInto( |
525 | K const& key, |
526 | BeforeDestroy&& beforeDestroy) { |
527 | return table_.eraseKeyInto(key, beforeDestroy); |
528 | } |
529 | |
530 | //// PUBLIC - Lookup |
531 | |
532 | FOLLY_ALWAYS_INLINE std::size_t count(key_type const& key) const { |
533 | return table_.find(key).atEnd() ? 0 : 1; |
534 | } |
535 | |
536 | template <typename K> |
537 | FOLLY_ALWAYS_INLINE EnableHeterogeneousFind<K, size_type> count( |
538 | K const& key) const { |
539 | return table_.find(key).atEnd() ? 0 : 1; |
540 | } |
541 | |
542 | // prehash(key) does the work of evaluating hash_function()(key) |
543 | // (including additional bit-mixing for non-avalanching hash functions), |
544 | // wraps the result of that work in a token for later reuse, and |
545 | // begins prefetching of the first steps of looking for key into the |
546 | // local CPU cache. |
547 | // |
548 | // The returned token may be used at any time, may be used more than |
549 | // once, and may be used in other F14 sets and maps. Tokens are |
550 | // transferrable between any F14 containers (maps and sets) with the |
551 | // same key_type and equal hash_function()s. |
552 | // |
553 | // Hash tokens are not hints -- it is a bug to call any method on this |
554 | // class with a token t and key k where t isn't the result of a call |
555 | // to prehash(k2) with k2 == k. |
556 | F14HashToken prehash(key_type const& key) const { |
557 | return table_.prehash(key); |
558 | } |
559 | |
560 | template <typename K> |
561 | EnableHeterogeneousFind<K, F14HashToken> prehash(K const& key) const { |
562 | return table_.prehash(key); |
563 | } |
564 | |
565 | FOLLY_ALWAYS_INLINE iterator find(key_type const& key) { |
566 | return const_cast<F14BasicSet const*>(this)->find(key); |
567 | } |
568 | |
569 | FOLLY_ALWAYS_INLINE const_iterator find(key_type const& key) const { |
570 | return table_.makeIter(table_.find(key)); |
571 | } |
572 | |
573 | FOLLY_ALWAYS_INLINE iterator |
574 | find(F14HashToken const& token, key_type const& key) { |
575 | return const_cast<F14BasicSet const*>(this)->find(token, key); |
576 | } |
577 | |
578 | FOLLY_ALWAYS_INLINE const_iterator |
579 | find(F14HashToken const& token, key_type const& key) const { |
580 | return table_.makeIter(table_.find(token, key)); |
581 | } |
582 | |
583 | template <typename K> |
584 | FOLLY_ALWAYS_INLINE EnableHeterogeneousFind<K, iterator> find(K const& key) { |
585 | return const_cast<F14BasicSet const*>(this)->find(key); |
586 | } |
587 | |
588 | template <typename K> |
589 | FOLLY_ALWAYS_INLINE EnableHeterogeneousFind<K, const_iterator> find( |
590 | K const& key) const { |
591 | return table_.makeIter(table_.find(key)); |
592 | } |
593 | |
594 | template <typename K> |
595 | FOLLY_ALWAYS_INLINE EnableHeterogeneousFind<K, iterator> find( |
596 | F14HashToken const& token, |
597 | K const& key) { |
598 | return const_cast<F14BasicSet const*>(this)->find(token, key); |
599 | } |
600 | |
601 | template <typename K> |
602 | FOLLY_ALWAYS_INLINE EnableHeterogeneousFind<K, const_iterator> find( |
603 | F14HashToken const& token, |
604 | K const& key) const { |
605 | return table_.makeIter(table_.find(token, key)); |
606 | } |
607 | |
608 | std::pair<iterator, iterator> equal_range(key_type const& key) { |
609 | return equal_range(*this, key); |
610 | } |
611 | |
612 | std::pair<const_iterator, const_iterator> equal_range( |
613 | key_type const& key) const { |
614 | return equal_range(*this, key); |
615 | } |
616 | |
617 | template <typename K> |
618 | EnableHeterogeneousFind<K, std::pair<iterator, iterator>> equal_range( |
619 | K const& key) { |
620 | return equal_range(*this, key); |
621 | } |
622 | |
623 | template <typename K> |
624 | EnableHeterogeneousFind<K, std::pair<const_iterator, const_iterator>> |
625 | equal_range(K const& key) const { |
626 | return equal_range(*this, key); |
627 | } |
628 | |
629 | //// PUBLIC - Bucket interface |
630 | |
631 | std::size_t bucket_count() const noexcept { |
632 | return table_.bucket_count(); |
633 | } |
634 | |
635 | std::size_t max_bucket_count() const noexcept { |
636 | return table_.max_bucket_count(); |
637 | } |
638 | |
639 | //// PUBLIC - Hash policy |
640 | |
641 | float load_factor() const noexcept { |
642 | return table_.load_factor(); |
643 | } |
644 | |
645 | float max_load_factor() const noexcept { |
646 | return table_.max_load_factor(); |
647 | } |
648 | |
649 | void max_load_factor(float v) { |
650 | table_.max_load_factor(v); |
651 | } |
652 | |
653 | void rehash(std::size_t bucketCapacity) { |
654 | // The standard's rehash() requires understanding the max load factor, |
655 | // which is easy to get wrong. Since we don't actually allow adjustment |
656 | // of max_load_factor there is no difference. |
657 | reserve(bucketCapacity); |
658 | } |
659 | |
660 | void reserve(std::size_t capacity) { |
661 | table_.reserve(capacity); |
662 | } |
663 | |
664 | //// PUBLIC - Observers |
665 | |
666 | hasher hash_function() const { |
667 | return table_.hasher(); |
668 | } |
669 | |
670 | key_equal key_eq() const { |
671 | return table_.keyEqual(); |
672 | } |
673 | |
674 | //// PUBLIC - F14 Extensions |
675 | |
676 | // Get memory footprint, not including sizeof(*this). |
677 | std::size_t getAllocatedMemorySize() const { |
678 | return table_.getAllocatedMemorySize(); |
679 | } |
680 | |
681 | // Enumerates classes of allocated memory blocks currently owned |
682 | // by this table, calling visitor(allocationSize, allocationCount). |
683 | // This can be used to get a more accurate indication of memory footprint |
684 | // than getAllocatedMemorySize() if you have some way of computing the |
685 | // internal fragmentation of the allocator, such as JEMalloc's nallocx. |
686 | // The visitor might be called twice with the same allocationSize. The |
687 | // visitor's computation should produce the same result for visitor(8, |
688 | // 2) as for two calls to visitor(8, 1), for example. The visitor may |
689 | // be called with a zero allocationCount. |
690 | template <typename V> |
691 | void visitAllocationClasses(V&& visitor) const { |
692 | return table_.visitAllocationClasses(visitor); |
693 | } |
694 | |
695 | // Calls visitor with two value_type const*, b and e, such that every |
696 | // entry in the table is included in exactly one of the ranges [b,e). |
697 | // This can be used to efficiently iterate elements in bulk when crossing |
698 | // an API boundary that supports contiguous blocks of items. |
699 | template <typename V> |
700 | void visitContiguousRanges(V&& visitor) const; |
701 | |
702 | F14TableStats computeStats() const noexcept { |
703 | return table_.computeStats(); |
704 | } |
705 | |
706 | private: |
707 | template <typename Self, typename K> |
708 | static auto equal_range(Self& self, K const& key) { |
709 | auto first = self.find(key); |
710 | auto last = first; |
711 | if (last != self.end()) { |
712 | ++last; |
713 | } |
714 | return std::make_pair(first, last); |
715 | } |
716 | |
717 | protected: |
718 | F14Table<Policy> table_; |
719 | }; |
720 | |
721 | template <typename S> |
722 | bool setsEqual(S const& lhs, S const& rhs) { |
723 | if (lhs.size() != rhs.size()) { |
724 | return false; |
725 | } |
726 | for (auto& k : lhs) { |
727 | auto iter = rhs.find(k); |
728 | if (iter == rhs.end()) { |
729 | return false; |
730 | } |
731 | if (!std::is_same< |
732 | typename S::key_equal, |
733 | std::equal_to<typename S::value_type>>::value) { |
734 | // spec says we compare key with == as well as with key_eq() |
735 | if (!(k == *iter)) { |
736 | return false; |
737 | } |
738 | } |
739 | } |
740 | return true; |
741 | } |
742 | } // namespace detail |
743 | } // namespace f14 |
744 | |
745 | template <typename Key, typename Hasher, typename KeyEqual, typename Alloc> |
746 | class F14ValueSet |
747 | : public f14::detail::F14BasicSet<f14::detail::SetPolicyWithDefaults< |
748 | f14::detail::ValueContainerPolicy, |
749 | Key, |
750 | Hasher, |
751 | KeyEqual, |
752 | Alloc>> { |
753 | protected: |
754 | using Policy = f14::detail::SetPolicyWithDefaults< |
755 | f14::detail::ValueContainerPolicy, |
756 | Key, |
757 | Hasher, |
758 | KeyEqual, |
759 | Alloc>; |
760 | |
761 | private: |
762 | using Super = f14::detail::F14BasicSet<Policy>; |
763 | |
764 | public: |
765 | using typename Super::value_type; |
766 | |
767 | F14ValueSet() = default; |
768 | |
769 | using Super::Super; |
770 | |
771 | F14ValueSet& operator=(std::initializer_list<value_type> ilist) { |
772 | Super::operator=(ilist); |
773 | return *this; |
774 | } |
775 | |
776 | void swap(F14ValueSet& rhs) noexcept(Policy::kSwapIsNoexcept) { |
777 | this->table_.swap(rhs.table_); |
778 | } |
779 | |
780 | template <typename V> |
781 | void visitContiguousRanges(V&& visitor) const { |
782 | this->table_.visitContiguousItemRanges(std::forward<V>(visitor)); |
783 | } |
784 | }; |
785 | |
786 | template <typename K, typename H, typename E, typename A> |
787 | bool operator==( |
788 | F14ValueSet<K, H, E, A> const& lhs, |
789 | F14ValueSet<K, H, E, A> const& rhs) { |
790 | return setsEqual(lhs, rhs); |
791 | } |
792 | |
793 | template <typename K, typename H, typename E, typename A> |
794 | bool operator!=( |
795 | F14ValueSet<K, H, E, A> const& lhs, |
796 | F14ValueSet<K, H, E, A> const& rhs) { |
797 | return !(lhs == rhs); |
798 | } |
799 | |
800 | template <typename Key, typename Hasher, typename KeyEqual, typename Alloc> |
801 | class F14NodeSet |
802 | : public f14::detail::F14BasicSet<f14::detail::SetPolicyWithDefaults< |
803 | f14::detail::NodeContainerPolicy, |
804 | Key, |
805 | Hasher, |
806 | KeyEqual, |
807 | Alloc>> { |
808 | protected: |
809 | using Policy = f14::detail::SetPolicyWithDefaults< |
810 | f14::detail::NodeContainerPolicy, |
811 | Key, |
812 | Hasher, |
813 | KeyEqual, |
814 | Alloc>; |
815 | |
816 | private: |
817 | using Super = f14::detail::F14BasicSet<Policy>; |
818 | |
819 | public: |
820 | using typename Super::value_type; |
821 | |
822 | F14NodeSet() = default; |
823 | |
824 | using Super::Super; |
825 | |
826 | F14NodeSet& operator=(std::initializer_list<value_type> ilist) { |
827 | Super::operator=(ilist); |
828 | return *this; |
829 | } |
830 | |
831 | void swap(F14NodeSet& rhs) noexcept(Policy::kSwapIsNoexcept) { |
832 | this->table_.swap(rhs.table_); |
833 | } |
834 | |
835 | template <typename V> |
836 | void visitContiguousRanges(V&& visitor) const { |
837 | this->table_.visitItems([&](typename Policy::Item ptr) { |
838 | value_type const* b = std::addressof(*ptr); |
839 | visitor(b, b + 1); |
840 | }); |
841 | } |
842 | }; |
843 | |
844 | template <typename K, typename H, typename E, typename A> |
845 | bool operator==( |
846 | F14NodeSet<K, H, E, A> const& lhs, |
847 | F14NodeSet<K, H, E, A> const& rhs) { |
848 | return setsEqual(lhs, rhs); |
849 | } |
850 | |
851 | template <typename K, typename H, typename E, typename A> |
852 | bool operator!=( |
853 | F14NodeSet<K, H, E, A> const& lhs, |
854 | F14NodeSet<K, H, E, A> const& rhs) { |
855 | return !(lhs == rhs); |
856 | } |
857 | |
858 | namespace f14 { |
859 | namespace detail { |
860 | template < |
861 | typename Key, |
862 | typename Hasher, |
863 | typename KeyEqual, |
864 | typename Alloc, |
865 | typename EligibleForPerturbedInsertionOrder> |
866 | class F14VectorSetImpl : public F14BasicSet<SetPolicyWithDefaults< |
867 | VectorContainerPolicy, |
868 | Key, |
869 | Hasher, |
870 | KeyEqual, |
871 | Alloc, |
872 | EligibleForPerturbedInsertionOrder>> { |
873 | protected: |
874 | using Policy = SetPolicyWithDefaults< |
875 | VectorContainerPolicy, |
876 | Key, |
877 | Hasher, |
878 | KeyEqual, |
879 | Alloc, |
880 | EligibleForPerturbedInsertionOrder>; |
881 | |
882 | private: |
883 | using Super = F14BasicSet<Policy>; |
884 | |
885 | template <typename K, typename T> |
886 | using EnableHeterogeneousVectorErase = std::enable_if_t< |
887 | EligibleForHeterogeneousFind< |
888 | typename Policy::Value, |
889 | typename Policy::Hasher, |
890 | typename Policy::KeyEqual, |
891 | K>::value && |
892 | !std::is_same<typename Policy::Iter, remove_cvref_t<K>>::value && |
893 | !std::is_same<typename Policy::ReverseIter, remove_cvref_t<K>>::value, |
894 | T>; |
895 | |
896 | public: |
897 | using typename Super::const_iterator; |
898 | using typename Super::iterator; |
899 | using typename Super::key_type; |
900 | using typename Super::value_type; |
901 | |
902 | F14VectorSetImpl() = default; |
903 | |
904 | using Super::Super; |
905 | |
906 | F14VectorSetImpl& operator=(std::initializer_list<value_type> ilist) { |
907 | Super::operator=(ilist); |
908 | return *this; |
909 | } |
910 | |
911 | iterator begin() { |
912 | return cbegin(); |
913 | } |
914 | const_iterator begin() const { |
915 | return cbegin(); |
916 | } |
917 | const_iterator cbegin() const { |
918 | return this->table_.linearBegin(this->size()); |
919 | } |
920 | |
921 | iterator end() { |
922 | return cend(); |
923 | } |
924 | const_iterator end() const { |
925 | return cend(); |
926 | } |
927 | const_iterator cend() const { |
928 | return this->table_.linearEnd(); |
929 | } |
930 | |
931 | private: |
932 | template <typename BeforeDestroy> |
933 | void eraseUnderlying( |
934 | typename Policy::ItemIter underlying, |
935 | BeforeDestroy&& beforeDestroy) { |
936 | Alloc& a = this->table_.alloc(); |
937 | auto values = this->table_.values_; |
938 | |
939 | // destroy the value and remove the ptr from the base table |
940 | auto index = underlying.item(); |
941 | this->table_.eraseIterInto(underlying, beforeDestroy); |
942 | Policy::AllocTraits::destroy(a, std::addressof(values[index])); |
943 | |
944 | // move the last element in values_ down and fix up the inbound index |
945 | auto tailIndex = this->size(); |
946 | if (tailIndex != index) { |
947 | auto tail = this->table_.find( |
948 | VectorContainerIndexSearch{static_cast<uint32_t>(tailIndex)}); |
949 | tail.item() = index; |
950 | auto p = std::addressof(values[index]); |
951 | assume(p != nullptr); |
952 | this->table_.transfer(a, std::addressof(values[tailIndex]), p, 1); |
953 | } |
954 | } |
955 | |
956 | template <typename K, typename BeforeDestroy> |
957 | std::size_t eraseUnderlyingKey(K const& key, BeforeDestroy&& beforeDestroy) { |
958 | auto underlying = this->table_.find(key); |
959 | if (underlying.atEnd()) { |
960 | return 0; |
961 | } else { |
962 | eraseUnderlying(underlying, beforeDestroy); |
963 | return 1; |
964 | } |
965 | } |
966 | |
967 | public: |
968 | FOLLY_ALWAYS_INLINE iterator erase(const_iterator pos) { |
969 | return eraseInto(pos, [](value_type&&) {}); |
970 | } |
971 | |
972 | iterator erase(const_iterator first, const_iterator last) { |
973 | return eraseInto(first, last, [](value_type&&) {}); |
974 | } |
975 | |
976 | std::size_t erase(key_type const& key) { |
977 | return eraseInto(key, [](value_type&&) {}); |
978 | } |
979 | |
980 | template <typename K> |
981 | EnableHeterogeneousVectorErase<K, std::size_t> erase(K const& key) { |
982 | return eraseInto(key, [](value_type&&) {}); |
983 | } |
984 | |
985 | template <typename BeforeDestroy> |
986 | FOLLY_ALWAYS_INLINE iterator |
987 | eraseInto(const_iterator pos, BeforeDestroy&& beforeDestroy) { |
988 | auto underlying = this->table_.find( |
989 | VectorContainerIndexSearch{this->table_.iterToIndex(pos)}); |
990 | eraseUnderlying(underlying, beforeDestroy); |
991 | return ++pos; |
992 | } |
993 | |
994 | template <typename BeforeDestroy> |
995 | iterator eraseInto( |
996 | const_iterator first, |
997 | const_iterator last, |
998 | BeforeDestroy&& beforeDestroy) { |
999 | while (first != last) { |
1000 | first = eraseInto(first, beforeDestroy); |
1001 | } |
1002 | return first; |
1003 | } |
1004 | |
1005 | template <typename BeforeDestroy> |
1006 | std::size_t eraseInto(key_type const& key, BeforeDestroy&& beforeDestroy) { |
1007 | return eraseUnderlyingKey(key, beforeDestroy); |
1008 | } |
1009 | |
1010 | template <typename K, typename BeforeDestroy> |
1011 | EnableHeterogeneousVectorErase<K, std::size_t> eraseInto( |
1012 | K const& key, |
1013 | BeforeDestroy&& beforeDestroy) { |
1014 | return eraseUnderlyingKey(key, beforeDestroy); |
1015 | } |
1016 | |
1017 | template <typename V> |
1018 | void visitContiguousRanges(V&& visitor) const { |
1019 | auto n = this->table_.size(); |
1020 | if (n > 0) { |
1021 | value_type const* b = std::addressof(this->table_.values_[0]); |
1022 | visitor(b, b + n); |
1023 | } |
1024 | } |
1025 | }; |
1026 | } // namespace detail |
1027 | } // namespace f14 |
1028 | |
1029 | template <typename Key, typename Hasher, typename KeyEqual, typename Alloc> |
1030 | class F14VectorSet |
1031 | : public f14::detail:: |
1032 | F14VectorSetImpl<Key, Hasher, KeyEqual, Alloc, std::false_type> { |
1033 | using Super = f14::detail:: |
1034 | F14VectorSetImpl<Key, Hasher, KeyEqual, Alloc, std::false_type>; |
1035 | |
1036 | public: |
1037 | using typename Super::const_iterator; |
1038 | using typename Super::iterator; |
1039 | using typename Super::value_type; |
1040 | using reverse_iterator = typename Super::Policy::ReverseIter; |
1041 | using const_reverse_iterator = reverse_iterator; |
1042 | |
1043 | F14VectorSet() = default; |
1044 | |
1045 | using Super::Super; |
1046 | |
1047 | F14VectorSet& operator=(std::initializer_list<value_type> ilist) { |
1048 | Super::operator=(ilist); |
1049 | return *this; |
1050 | } |
1051 | |
1052 | void swap(F14VectorSet& rhs) noexcept(Super::Policy::kSwapIsNoexcept) { |
1053 | this->table_.swap(rhs.table_); |
1054 | } |
1055 | |
1056 | // ITERATION ORDER |
1057 | // |
1058 | // Deterministic iteration order for insert-only workloads is part of |
1059 | // F14VectorSet's supported API: iterator is LIFO and reverse_iterator |
1060 | // is FIFO. |
1061 | // |
1062 | // If there have been no calls to erase() then iterator and |
1063 | // const_iterator enumerate entries in the opposite of insertion order. |
1064 | // begin()->first is the key most recently inserted. reverse_iterator |
1065 | // and reverse_const_iterator, therefore, enumerate in LIFO (insertion) |
1066 | // order for insert-only workloads. Deterministic iteration order is |
1067 | // only guaranteed if no keys were removed since the last time the |
1068 | // set was empty. Iteration order is preserved across rehashes and |
1069 | // F14VectorSet copies and moves. |
1070 | // |
1071 | // iterator uses LIFO order so that erasing while iterating with begin() |
1072 | // and end() is safe using the erase(it++) idiom, which is supported |
1073 | // by std::set and std::unordered_set. erase(iter) invalidates iter |
1074 | // and all iterators before iter in the non-reverse iteration order. |
1075 | // Every successful erase invalidates all reverse iterators. |
1076 | // |
1077 | // No erase is provided for reverse_iterator (AKA const_reverse_iterator) |
1078 | // to make it harder to shoot yourself in the foot by erasing while |
1079 | // reverse-iterating. You can write that as set.erase(set.iter(riter)) |
1080 | // if you need it. |
1081 | |
1082 | reverse_iterator rbegin() { |
1083 | return this->table_.values_; |
1084 | } |
1085 | const_reverse_iterator rbegin() const { |
1086 | return crbegin(); |
1087 | } |
1088 | const_reverse_iterator crbegin() const { |
1089 | return this->table_.values_; |
1090 | } |
1091 | |
1092 | reverse_iterator rend() { |
1093 | return this->table_.values_ + this->table_.size(); |
1094 | } |
1095 | const_reverse_iterator rend() const { |
1096 | return crend(); |
1097 | } |
1098 | const_reverse_iterator crend() const { |
1099 | return this->table_.values_ + this->table_.size(); |
1100 | } |
1101 | |
1102 | // explicit conversions between iterator and reverse_iterator |
1103 | iterator iter(reverse_iterator riter) { |
1104 | return this->table_.iter(riter); |
1105 | } |
1106 | const_iterator iter(const_reverse_iterator riter) const { |
1107 | return this->table_.iter(riter); |
1108 | } |
1109 | |
1110 | reverse_iterator riter(iterator it) { |
1111 | return this->table_.riter(it); |
1112 | } |
1113 | const_reverse_iterator riter(const_iterator it) const { |
1114 | return this->table_.riter(it); |
1115 | } |
1116 | }; |
1117 | |
1118 | template <typename K, typename H, typename E, typename A> |
1119 | bool operator==( |
1120 | F14VectorSet<K, H, E, A> const& lhs, |
1121 | F14VectorSet<K, H, E, A> const& rhs) { |
1122 | return setsEqual(lhs, rhs); |
1123 | } |
1124 | |
1125 | template <typename K, typename H, typename E, typename A> |
1126 | bool operator!=( |
1127 | F14VectorSet<K, H, E, A> const& lhs, |
1128 | F14VectorSet<K, H, E, A> const& rhs) { |
1129 | return !(lhs == rhs); |
1130 | } |
1131 | |
1132 | template <typename Key, typename Hasher, typename KeyEqual, typename Alloc> |
1133 | class F14FastSet |
1134 | : public std::conditional_t< |
1135 | sizeof(Key) < 24, |
1136 | F14ValueSet<Key, Hasher, KeyEqual, Alloc>, |
1137 | f14::detail:: |
1138 | F14VectorSetImpl<Key, Hasher, KeyEqual, Alloc, std::true_type>> { |
1139 | using Super = std::conditional_t< |
1140 | sizeof(Key) < 24, |
1141 | F14ValueSet<Key, Hasher, KeyEqual, Alloc>, |
1142 | f14::detail:: |
1143 | F14VectorSetImpl<Key, Hasher, KeyEqual, Alloc, std::true_type>>; |
1144 | |
1145 | public: |
1146 | using typename Super::value_type; |
1147 | |
1148 | F14FastSet() = default; |
1149 | |
1150 | using Super::Super; |
1151 | |
1152 | F14FastSet& operator=(std::initializer_list<value_type> ilist) { |
1153 | Super::operator=(ilist); |
1154 | return *this; |
1155 | } |
1156 | |
1157 | void swap(F14FastSet& rhs) noexcept(Super::Policy::kSwapIsNoexcept) { |
1158 | this->table_.swap(rhs.table_); |
1159 | } |
1160 | }; |
1161 | |
1162 | template <typename K, typename H, typename E, typename A> |
1163 | bool operator==( |
1164 | F14FastSet<K, H, E, A> const& lhs, |
1165 | F14FastSet<K, H, E, A> const& rhs) { |
1166 | return setsEqual(lhs, rhs); |
1167 | } |
1168 | |
1169 | template <typename K, typename H, typename E, typename A> |
1170 | bool operator!=( |
1171 | F14FastSet<K, H, E, A> const& lhs, |
1172 | F14FastSet<K, H, E, A> const& rhs) { |
1173 | return !(lhs == rhs); |
1174 | } |
1175 | } // namespace folly |
1176 | |
1177 | #endif // FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE |
1178 | |
1179 | namespace folly { |
1180 | |
1181 | template <typename K, typename H, typename E, typename A> |
1182 | void swap(F14ValueSet<K, H, E, A>& lhs, F14ValueSet<K, H, E, A>& rhs) noexcept( |
1183 | noexcept(lhs.swap(rhs))) { |
1184 | lhs.swap(rhs); |
1185 | } |
1186 | |
1187 | template <typename K, typename H, typename E, typename A> |
1188 | void swap(F14NodeSet<K, H, E, A>& lhs, F14NodeSet<K, H, E, A>& rhs) noexcept( |
1189 | noexcept(lhs.swap(rhs))) { |
1190 | lhs.swap(rhs); |
1191 | } |
1192 | |
1193 | template <typename K, typename H, typename E, typename A> |
1194 | void swap( |
1195 | F14VectorSet<K, H, E, A>& lhs, |
1196 | F14VectorSet<K, H, E, A>& rhs) noexcept(noexcept(lhs.swap(rhs))) { |
1197 | lhs.swap(rhs); |
1198 | } |
1199 | |
1200 | template <typename K, typename H, typename E, typename A> |
1201 | void swap(F14FastSet<K, H, E, A>& lhs, F14FastSet<K, H, E, A>& rhs) noexcept( |
1202 | noexcept(lhs.swap(rhs))) { |
1203 | lhs.swap(rhs); |
1204 | } |
1205 | } // namespace folly |
1206 | |