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
44namespace folly {
45
46namespace f14 {
47namespace detail {
48template <typename K, typename H, typename E, typename A>
49class 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
93template <typename Key, typename Hasher, typename KeyEqual, typename Alloc>
94class 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
111template <typename Key, typename Hasher, typename KeyEqual, typename Alloc>
112class 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
129template <typename Key, typename Hasher, typename KeyEqual, typename Alloc>
130class 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
147template <typename Key, typename Hasher, typename KeyEqual, typename Alloc>
148class 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
170namespace folly {
171namespace f14 {
172namespace detail {
173
174template <typename Policy>
175class 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
721template <typename S>
722bool 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
745template <typename Key, typename Hasher, typename KeyEqual, typename Alloc>
746class 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
786template <typename K, typename H, typename E, typename A>
787bool operator==(
788 F14ValueSet<K, H, E, A> const& lhs,
789 F14ValueSet<K, H, E, A> const& rhs) {
790 return setsEqual(lhs, rhs);
791}
792
793template <typename K, typename H, typename E, typename A>
794bool operator!=(
795 F14ValueSet<K, H, E, A> const& lhs,
796 F14ValueSet<K, H, E, A> const& rhs) {
797 return !(lhs == rhs);
798}
799
800template <typename Key, typename Hasher, typename KeyEqual, typename Alloc>
801class 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
844template <typename K, typename H, typename E, typename A>
845bool operator==(
846 F14NodeSet<K, H, E, A> const& lhs,
847 F14NodeSet<K, H, E, A> const& rhs) {
848 return setsEqual(lhs, rhs);
849}
850
851template <typename K, typename H, typename E, typename A>
852bool operator!=(
853 F14NodeSet<K, H, E, A> const& lhs,
854 F14NodeSet<K, H, E, A> const& rhs) {
855 return !(lhs == rhs);
856}
857
858namespace f14 {
859namespace detail {
860template <
861 typename Key,
862 typename Hasher,
863 typename KeyEqual,
864 typename Alloc,
865 typename EligibleForPerturbedInsertionOrder>
866class 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
1029template <typename Key, typename Hasher, typename KeyEqual, typename Alloc>
1030class 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
1118template <typename K, typename H, typename E, typename A>
1119bool operator==(
1120 F14VectorSet<K, H, E, A> const& lhs,
1121 F14VectorSet<K, H, E, A> const& rhs) {
1122 return setsEqual(lhs, rhs);
1123}
1124
1125template <typename K, typename H, typename E, typename A>
1126bool operator!=(
1127 F14VectorSet<K, H, E, A> const& lhs,
1128 F14VectorSet<K, H, E, A> const& rhs) {
1129 return !(lhs == rhs);
1130}
1131
1132template <typename Key, typename Hasher, typename KeyEqual, typename Alloc>
1133class 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
1162template <typename K, typename H, typename E, typename A>
1163bool operator==(
1164 F14FastSet<K, H, E, A> const& lhs,
1165 F14FastSet<K, H, E, A> const& rhs) {
1166 return setsEqual(lhs, rhs);
1167}
1168
1169template <typename K, typename H, typename E, typename A>
1170bool 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
1179namespace folly {
1180
1181template <typename K, typename H, typename E, typename A>
1182void 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
1187template <typename K, typename H, typename E, typename A>
1188void 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
1193template <typename K, typename H, typename E, typename A>
1194void 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
1200template <typename K, typename H, typename E, typename A>
1201void 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