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#include <memory>
20#include <type_traits>
21#include <utility>
22
23#include <folly/Memory.h>
24#include <folly/Portability.h>
25#include <folly/Unit.h>
26#include <folly/container/HeterogeneousAccess.h>
27#include <folly/container/detail/F14Table.h>
28#include <folly/hash/Hash.h>
29#include <folly/lang/Align.h>
30#include <folly/lang/SafeAssert.h>
31#include <folly/memory/Malloc.h>
32
33#if FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE
34
35namespace folly {
36namespace f14 {
37namespace detail {
38
39template <typename Ptr>
40using NonConstPtr = typename std::pointer_traits<Ptr>::template rebind<
41 std::remove_const_t<typename std::pointer_traits<Ptr>::element_type>>;
42
43template <typename KeyType, typename MappedType>
44using MapValueType = std::pair<KeyType const, MappedType>;
45
46template <typename KeyType, typename MappedTypeOrVoid>
47using SetOrMapValueType = std::conditional_t<
48 std::is_same<MappedTypeOrVoid, void>::value,
49 KeyType,
50 MapValueType<KeyType, MappedTypeOrVoid>>;
51
52// Used to enable EBO for Hasher, KeyEqual, and Alloc. std::tuple of
53// all empty objects is empty in libstdc++ but not libc++.
54template <
55 char Tag,
56 typename T,
57 bool Inherit = std::is_empty<T>::value && !std::is_final<T>::value>
58struct ObjectHolder {
59 T value_;
60
61 template <typename... Args>
62 ObjectHolder(Args&&... args) : value_{std::forward<Args>(args)...} {}
63
64 T& operator*() {
65 return value_;
66 }
67 T const& operator*() const {
68 return value_;
69 }
70};
71
72template <char Tag, typename T>
73struct ObjectHolder<Tag, T, true> : private T {
74 template <typename... Args>
75 ObjectHolder(Args&&... args) : T{std::forward<Args>(args)...} {}
76
77 T& operator*() {
78 return *this;
79 }
80 T const& operator*() const {
81 return *this;
82 }
83};
84
85// Policy provides the functionality of hasher, key_equal, and
86// allocator_type. In addition, it can add indirection to the values
87// contained in the base table by defining a non-trivial value() method.
88//
89// To facilitate stateful implementations it is guaranteed that there
90// will be a 1:1 relationship between BaseTable and Policy instance:
91// policies will only be copied when their owning table is copied, and
92// they will only be moved when their owning table is moved.
93//
94// Key equality will have the user-supplied search key as its first
95// argument and the table contents as its second. Heterogeneous lookup
96// should be handled on the first argument.
97//
98// Item is the data stored inline in the hash table's chunks. The policy
99// controls how this is mapped to the corresponding Value.
100//
101// The policies defined in this file work for either set or map types.
102// Most of the functionality is identical. A few methods detect the
103// collection type by checking to see if MappedType is void, and then use
104// SFINAE to select the appropriate implementation.
105template <
106 typename KeyType,
107 typename MappedTypeOrVoid,
108 typename HasherOrVoid,
109 typename KeyEqualOrVoid,
110 typename AllocOrVoid,
111 typename ItemType>
112struct BasePolicy
113 : private ObjectHolder<
114 'H',
115 Defaulted<HasherOrVoid, DefaultHasher<KeyType>>>,
116 private ObjectHolder<
117 'E',
118 Defaulted<KeyEqualOrVoid, DefaultKeyEqual<KeyType>>>,
119 private ObjectHolder<
120 'A',
121 Defaulted<
122 AllocOrVoid,
123 DefaultAlloc<SetOrMapValueType<KeyType, MappedTypeOrVoid>>>> {
124 //////// user-supplied types
125
126 using Key = KeyType;
127 using Mapped = MappedTypeOrVoid;
128 using Value = SetOrMapValueType<Key, Mapped>;
129 using Item = ItemType;
130 using Hasher = Defaulted<HasherOrVoid, DefaultHasher<Key>>;
131 using KeyEqual = Defaulted<KeyEqualOrVoid, DefaultKeyEqual<Key>>;
132 using Alloc = Defaulted<AllocOrVoid, DefaultAlloc<Value>>;
133 using AllocTraits = std::allocator_traits<Alloc>;
134
135 using ByteAlloc = typename AllocTraits::template rebind_alloc<uint8_t>;
136 using ByteAllocTraits = typename std::allocator_traits<ByteAlloc>;
137 using BytePtr = typename ByteAllocTraits::pointer;
138
139 //////// info about user-supplied types
140
141 static_assert(
142 std::is_same<typename AllocTraits::value_type, Value>::value,
143 "wrong allocator value_type");
144
145 private:
146 using HasherHolder = ObjectHolder<'H', Hasher>;
147 using KeyEqualHolder = ObjectHolder<'E', KeyEqual>;
148 using AllocHolder = ObjectHolder<'A', Alloc>;
149
150 // emulate c++17's std::allocator_traits<A>::is_always_equal
151
152 template <typename A, typename = void>
153 struct AllocIsAlwaysEqual : std::is_empty<A> {};
154
155 template <typename A>
156 struct AllocIsAlwaysEqual<A, typename A::is_always_equal>
157 : A::is_always_equal {};
158
159 // emulate c++17 has std::is_nothrow_swappable
160 template <typename T>
161 static constexpr bool isNothrowSwap() {
162 using std::swap;
163 return noexcept(swap(std::declval<T&>(), std::declval<T&>()));
164 }
165
166 public:
167 static constexpr bool kAllocIsAlwaysEqual = AllocIsAlwaysEqual<Alloc>::value;
168
169 static constexpr bool kDefaultConstructIsNoexcept =
170 std::is_nothrow_default_constructible<Hasher>::value &&
171 std::is_nothrow_default_constructible<KeyEqual>::value &&
172 std::is_nothrow_default_constructible<Alloc>::value;
173
174 static constexpr bool kSwapIsNoexcept = kAllocIsAlwaysEqual &&
175 isNothrowSwap<Hasher>() && isNothrowSwap<KeyEqual>();
176
177 static constexpr bool isAvalanchingHasher() {
178 return IsAvalanchingHasher<Hasher, Key>::value;
179 }
180
181 //////// internal types and constants
182
183 using InternalSizeType = std::size_t;
184
185 // if false, F14Table will be smaller but F14Table::begin() won't work
186 static constexpr bool kEnableItemIteration = true;
187
188 using Chunk = F14Chunk<Item>;
189 using ChunkPtr = typename std::pointer_traits<
190 typename AllocTraits::pointer>::template rebind<Chunk>;
191 using ItemIter = F14ItemIter<ChunkPtr>;
192
193 static constexpr bool kIsMap = !std::is_same<Key, Value>::value;
194 static_assert(
195 kIsMap == !std::is_void<MappedTypeOrVoid>::value,
196 "Assumption for the kIsMap check violated.");
197
198 using MappedOrBool = std::conditional_t<kIsMap, Mapped, bool>;
199
200 // if true, bucket_count() after reserve(n) will be as close as possible
201 // to n for multi-chunk tables
202 static constexpr bool kContinuousCapacity = false;
203
204 //////// methods
205
206 BasePolicy(Hasher const& hasher, KeyEqual const& keyEqual, Alloc const& alloc)
207 : HasherHolder{hasher}, KeyEqualHolder{keyEqual}, AllocHolder{alloc} {}
208
209 BasePolicy(BasePolicy const& rhs)
210 : HasherHolder{rhs.hasher()},
211 KeyEqualHolder{rhs.keyEqual()},
212 AllocHolder{
213 AllocTraits::select_on_container_copy_construction(rhs.alloc())} {}
214
215 BasePolicy(BasePolicy const& rhs, Alloc const& alloc)
216 : HasherHolder{rhs.hasher()},
217 KeyEqualHolder{rhs.keyEqual()},
218 AllocHolder{alloc} {}
219
220 BasePolicy(BasePolicy&& rhs) noexcept
221 : HasherHolder{std::move(rhs.hasher())},
222 KeyEqualHolder{std::move(rhs.keyEqual())},
223 AllocHolder{std::move(rhs.alloc())} {}
224
225 BasePolicy(BasePolicy&& rhs, Alloc const& alloc) noexcept
226 : HasherHolder{std::move(rhs.hasher())},
227 KeyEqualHolder{std::move(rhs.keyEqual())},
228 AllocHolder{alloc} {}
229
230 BasePolicy& operator=(BasePolicy const& rhs) {
231 hasher() = rhs.hasher();
232 keyEqual() = rhs.keyEqual();
233 if (AllocTraits::propagate_on_container_copy_assignment::value) {
234 alloc() = rhs.alloc();
235 }
236 return *this;
237 }
238
239 BasePolicy& operator=(BasePolicy&& rhs) noexcept {
240 hasher() = std::move(rhs.hasher());
241 keyEqual() = std::move(rhs.keyEqual());
242 if (AllocTraits::propagate_on_container_move_assignment::value) {
243 alloc() = std::move(rhs.alloc());
244 }
245 return *this;
246 }
247
248 void swapBasePolicy(BasePolicy& rhs) {
249 using std::swap;
250 swap(hasher(), rhs.hasher());
251 swap(keyEqual(), rhs.keyEqual());
252 if (AllocTraits::propagate_on_container_swap::value) {
253 swap(alloc(), rhs.alloc());
254 }
255 }
256
257 Hasher& hasher() {
258 return *static_cast<HasherHolder&>(*this);
259 }
260 Hasher const& hasher() const {
261 return *static_cast<HasherHolder const&>(*this);
262 }
263 KeyEqual& keyEqual() {
264 return *static_cast<KeyEqualHolder&>(*this);
265 }
266 KeyEqual const& keyEqual() const {
267 return *static_cast<KeyEqualHolder const&>(*this);
268 }
269 Alloc& alloc() {
270 return *static_cast<AllocHolder&>(*this);
271 }
272 Alloc const& alloc() const {
273 return *static_cast<AllocHolder const&>(*this);
274 }
275
276 template <typename K>
277 std::size_t computeKeyHash(K const& key) const {
278 static_assert(
279 isAvalanchingHasher() == IsAvalanchingHasher<Hasher, K>::value, "");
280 static_assert(
281 !isAvalanchingHasher() ||
282 sizeof(decltype(hasher()(key))) >= sizeof(std::size_t),
283 "hasher is not avalanching if it doesn't return enough bits");
284 return hasher()(key);
285 }
286
287 Key const& keyForValue(Key const& v) const {
288 return v;
289 }
290 Key const& keyForValue(std::pair<Key const, MappedOrBool> const& p) const {
291 return p.first;
292 }
293 Key const& keyForValue(std::pair<Key&&, MappedOrBool&&> const& p) const {
294 return p.first;
295 }
296
297 // map's choice of pair<K const, T> as value_type is unfortunate,
298 // because it means we either need a proxy iterator, a pointless key
299 // copy when moving items during rehash, or some sort of UB hack.
300 //
301 // This code implements the hack. Use moveValue(v) instead of
302 // std::move(v) as the source of a move construction. enable_if_t is
303 // used so that this works for maps while being a no-op for sets.
304 template <typename Dummy = int>
305 static std::pair<Key&&, MappedOrBool&&> moveValue(
306 std::pair<Key const, MappedOrBool>& value,
307 std::enable_if_t<kIsMap, Dummy> = 0) {
308 return {std::move(const_cast<Key&>(value.first)), std::move(value.second)};
309 }
310
311 template <typename Dummy = int>
312 static Value&& moveValue(Value& value, std::enable_if_t<!kIsMap, Dummy> = 0) {
313 return std::move(value);
314 }
315
316 template <typename P>
317 bool
318 beforeBuild(std::size_t /*size*/, std::size_t /*capacity*/, P&& /*rhs*/) {
319 return false;
320 }
321
322 template <typename P>
323 void afterBuild(
324 bool /*undoState*/,
325 bool /*success*/,
326 std::size_t /*size*/,
327 std::size_t /*capacity*/,
328 P&& /*rhs*/) {}
329
330 std::size_t alignedAllocSize(std::size_t n) const {
331 if (kRequiredVectorAlignment <= alignof(max_align_t) ||
332 std::is_same<ByteAlloc, std::allocator<uint8_t>>::value) {
333 return n;
334 } else {
335 return n + kRequiredVectorAlignment;
336 }
337 }
338
339 bool beforeRehash(
340 std::size_t /*size*/,
341 std::size_t /*oldCapacity*/,
342 std::size_t /*newCapacity*/,
343 std::size_t chunkAllocSize,
344 BytePtr& outChunkAllocation) {
345 outChunkAllocation =
346 allocateOverAligned<ByteAlloc, kRequiredVectorAlignment>(
347 ByteAlloc{alloc()}, chunkAllocSize);
348 return false;
349 }
350
351 void afterRehash(
352 bool /*undoState*/,
353 bool /*success*/,
354 std::size_t /*size*/,
355 std::size_t /*oldCapacity*/,
356 std::size_t /*newCapacity*/,
357 BytePtr chunkAllocation,
358 std::size_t chunkAllocSize) {
359 // on success, this will be the old allocation, on failure the new one
360 if (chunkAllocation != nullptr) {
361 deallocateOverAligned<ByteAlloc, kRequiredVectorAlignment>(
362 ByteAlloc{alloc()}, chunkAllocation, chunkAllocSize);
363 }
364 }
365
366 void beforeClear(std::size_t /*size*/, std::size_t /*capacity*/) {}
367
368 void afterClear(std::size_t /*size*/, std::size_t /*capacity*/) {}
369
370 void beforeReset(std::size_t /*size*/, std::size_t /*capacity*/) {}
371
372 void afterReset(
373 std::size_t /*size*/,
374 std::size_t /*capacity*/,
375 BytePtr chunkAllocation,
376 std::size_t chunkAllocSize) {
377 deallocateOverAligned<ByteAlloc, kRequiredVectorAlignment>(
378 ByteAlloc{alloc()}, chunkAllocation, chunkAllocSize);
379 }
380
381 void prefetchValue(Item const&) const {
382 // Subclass should disable with prefetchBeforeRehash(),
383 // prefetchBeforeCopy(), and prefetchBeforeDestroy(). if they don't
384 // override this method, because neither gcc nor clang can figure
385 // out that DenseMaskIter with an empty body can be elided.
386 FOLLY_SAFE_DCHECK(false, "should be disabled");
387 }
388
389 void afterDestroyWithoutDeallocate(Value* addr, std::size_t n) {
390 if (kIsSanitizeAddress) {
391 memset(static_cast<void*>(addr), 0x66, sizeof(Value) * n);
392 }
393 }
394};
395
396// BaseIter is a convenience for concrete set and map implementations
397template <typename ValuePtr, typename Item>
398class BaseIter : public std::iterator<
399 std::forward_iterator_tag,
400 std::remove_const_t<
401 typename std::pointer_traits<ValuePtr>::element_type>,
402 std::ptrdiff_t,
403 ValuePtr,
404 decltype(*std::declval<ValuePtr>())> {
405 protected:
406 using Chunk = F14Chunk<Item>;
407 using ChunkPtr =
408 typename std::pointer_traits<ValuePtr>::template rebind<Chunk>;
409 using ItemIter = F14ItemIter<ChunkPtr>;
410
411 using ValueConstPtr = typename std::pointer_traits<ValuePtr>::template rebind<
412 std::add_const_t<typename std::pointer_traits<ValuePtr>::element_type>>;
413};
414
415//////// ValueContainer
416
417template <
418 typename Key,
419 typename Mapped,
420 typename HasherOrVoid,
421 typename KeyEqualOrVoid,
422 typename AllocOrVoid>
423class ValueContainerPolicy;
424
425template <typename ValuePtr>
426using ValueContainerIteratorBase = BaseIter<
427 ValuePtr,
428 std::remove_const_t<typename std::pointer_traits<ValuePtr>::element_type>>;
429
430template <typename ValuePtr>
431class ValueContainerIterator : public ValueContainerIteratorBase<ValuePtr> {
432 using Super = ValueContainerIteratorBase<ValuePtr>;
433 using ItemIter = typename Super::ItemIter;
434 using ValueConstPtr = typename Super::ValueConstPtr;
435
436 public:
437 using pointer = typename Super::pointer;
438 using reference = typename Super::reference;
439 using value_type = typename Super::value_type;
440
441 ValueContainerIterator() = default;
442 ValueContainerIterator(ValueContainerIterator const&) = default;
443 ValueContainerIterator(ValueContainerIterator&&) = default;
444 ValueContainerIterator& operator=(ValueContainerIterator const&) = default;
445 ValueContainerIterator& operator=(ValueContainerIterator&&) = default;
446 ~ValueContainerIterator() = default;
447
448 /*implicit*/ operator ValueContainerIterator<ValueConstPtr>() const {
449 return ValueContainerIterator<ValueConstPtr>{underlying_};
450 }
451
452 reference operator*() const {
453 return underlying_.item();
454 }
455
456 pointer operator->() const {
457 return std::pointer_traits<pointer>::pointer_to(**this);
458 }
459
460 ValueContainerIterator& operator++() {
461 underlying_.advance();
462 return *this;
463 }
464
465 ValueContainerIterator operator++(int) {
466 auto cur = *this;
467 ++*this;
468 return cur;
469 }
470
471 bool operator==(ValueContainerIterator<ValueConstPtr> const& rhs) const {
472 return underlying_ == rhs.underlying_;
473 }
474 bool operator!=(ValueContainerIterator<ValueConstPtr> const& rhs) const {
475 return !(*this == rhs);
476 }
477
478 private:
479 ItemIter underlying_;
480
481 explicit ValueContainerIterator(ItemIter const& underlying)
482 : underlying_{underlying} {}
483
484 template <typename K, typename M, typename H, typename E, typename A>
485 friend class ValueContainerPolicy;
486
487 template <typename P>
488 friend class ValueContainerIterator;
489};
490
491template <
492 typename Key,
493 typename MappedTypeOrVoid,
494 typename HasherOrVoid,
495 typename KeyEqualOrVoid,
496 typename AllocOrVoid>
497class ValueContainerPolicy : public BasePolicy<
498 Key,
499 MappedTypeOrVoid,
500 HasherOrVoid,
501 KeyEqualOrVoid,
502 AllocOrVoid,
503 SetOrMapValueType<Key, MappedTypeOrVoid>> {
504 public:
505 using Super = BasePolicy<
506 Key,
507 MappedTypeOrVoid,
508 HasherOrVoid,
509 KeyEqualOrVoid,
510 AllocOrVoid,
511 SetOrMapValueType<Key, MappedTypeOrVoid>>;
512 using Alloc = typename Super::Alloc;
513 using AllocTraits = typename Super::AllocTraits;
514 using Item = typename Super::Item;
515 using ItemIter = typename Super::ItemIter;
516 using Value = typename Super::Value;
517
518 private:
519 using ByteAlloc = typename Super::ByteAlloc;
520
521 using Super::kIsMap;
522
523 public:
524 using ConstIter = ValueContainerIterator<typename AllocTraits::const_pointer>;
525 using Iter = std::conditional_t<
526 kIsMap,
527 ValueContainerIterator<typename AllocTraits::pointer>,
528 ConstIter>;
529
530 //////// F14Table policy
531
532 static constexpr bool prefetchBeforeRehash() {
533 return false;
534 }
535
536 static constexpr bool prefetchBeforeCopy() {
537 return false;
538 }
539
540 static constexpr bool prefetchBeforeDestroy() {
541 return false;
542 }
543
544 static constexpr bool destroyItemOnClear() {
545 return !std::is_trivially_destructible<Item>::value ||
546 !AllocatorHasDefaultObjectDestroy<Alloc, Item>::value;
547 }
548
549 // inherit constructors
550 using Super::Super;
551
552 void swapPolicy(ValueContainerPolicy& rhs) {
553 this->swapBasePolicy(rhs);
554 }
555
556 using Super::keyForValue;
557 static_assert(
558 std::is_same<Item, Value>::value,
559 "Item and Value should be the same type for ValueContainerPolicy.");
560
561 std::size_t computeItemHash(Item const& item) const {
562 return this->computeKeyHash(keyForValue(item));
563 }
564
565 template <typename K>
566 bool keyMatchesItem(K const& key, Item const& item) const {
567 return this->keyEqual()(key, keyForValue(item));
568 }
569
570 Value const& buildArgForItem(Item const& item) const& {
571 return item;
572 }
573
574 // buildArgForItem(Item&)&& is used when moving between unequal allocators
575 decltype(auto) buildArgForItem(Item& item) && {
576 return Super::moveValue(item);
577 }
578
579 Value&& valueAtItemForExtract(Item& item) {
580 return std::move(item);
581 }
582
583 template <typename Table, typename... Args>
584 void constructValueAtItem(Table&&, Item* itemAddr, Args&&... args) {
585 Alloc& a = this->alloc();
586 // GCC < 6 doesn't use the fact that itemAddr came from a reference
587 // to avoid a null-check in the placement new. folly::assume-ing it
588 // here gets rid of that branch. The branch is very predictable,
589 // but spoils some further optimizations. All clang versions that
590 // compile folly seem to be okay.
591 //
592 // TODO(T31574848): clean up assume-s used to optimize placement new
593 assume(itemAddr != nullptr);
594 AllocTraits::construct(a, itemAddr, std::forward<Args>(args)...);
595 }
596
597 template <typename T>
598 std::enable_if_t<std::is_nothrow_move_constructible<T>::value>
599 complainUnlessNothrowMove() {}
600
601 template <typename T>
602 [[deprecated(
603 "use F14NodeMap/Set or mark key and mapped type move constructor nothrow")]] std::
604 enable_if_t<!std::is_nothrow_move_constructible<T>::value>
605 complainUnlessNothrowMove() {}
606
607 void moveItemDuringRehash(Item* itemAddr, Item& src) {
608 complainUnlessNothrowMove<Key>();
609 complainUnlessNothrowMove<lift_unit_t<MappedTypeOrVoid>>();
610
611 constructValueAtItem(0, itemAddr, Super::moveValue(src));
612 if (destroyItemOnClear()) {
613 if (kIsMap) {
614 // Laundering in the standard is only described as a solution
615 // for changes to const fields due to the creation of a new
616 // object lifetime (destroy and then placement new in the same
617 // location), but it seems highly likely that it will also cause
618 // the compiler to drop such assumptions that are violated due
619 // to our UB const_cast in moveValue.
620 destroyItem(*launder(std::addressof(src)));
621 } else {
622 destroyItem(src);
623 }
624 }
625 }
626
627 void destroyItem(Item& item) {
628 Alloc& a = this->alloc();
629 auto ptr = std::addressof(item);
630 AllocTraits::destroy(a, ptr);
631 this->afterDestroyWithoutDeallocate(ptr, 1);
632 }
633
634 template <typename V>
635 void visitPolicyAllocationClasses(
636 std::size_t chunkAllocSize,
637 std::size_t /*size*/,
638 std::size_t /*capacity*/,
639 V&& visitor) const {
640 if (chunkAllocSize > 0) {
641 visitor(
642 allocationBytesForOverAligned<ByteAlloc, kRequiredVectorAlignment>(
643 chunkAllocSize),
644 1);
645 }
646 }
647
648 //////// F14BasicMap/Set policy
649
650 Iter makeIter(ItemIter const& underlying) const {
651 return Iter{underlying};
652 }
653 ConstIter makeConstIter(ItemIter const& underlying) const {
654 return ConstIter{underlying};
655 }
656 ItemIter const& unwrapIter(ConstIter const& iter) const {
657 return iter.underlying_;
658 }
659};
660
661//////// NodeContainer
662
663template <
664 typename Key,
665 typename Mapped,
666 typename HasherOrVoid,
667 typename KeyEqualOrVoid,
668 typename AllocOrVoid>
669class NodeContainerPolicy;
670
671template <typename ValuePtr>
672class NodeContainerIterator : public BaseIter<ValuePtr, NonConstPtr<ValuePtr>> {
673 using Super = BaseIter<ValuePtr, NonConstPtr<ValuePtr>>;
674 using ItemIter = typename Super::ItemIter;
675 using ValueConstPtr = typename Super::ValueConstPtr;
676
677 public:
678 using pointer = typename Super::pointer;
679 using reference = typename Super::reference;
680 using value_type = typename Super::value_type;
681
682 NodeContainerIterator() = default;
683 NodeContainerIterator(NodeContainerIterator const&) = default;
684 NodeContainerIterator(NodeContainerIterator&&) = default;
685 NodeContainerIterator& operator=(NodeContainerIterator const&) = default;
686 NodeContainerIterator& operator=(NodeContainerIterator&&) = default;
687 ~NodeContainerIterator() = default;
688
689 /*implicit*/ operator NodeContainerIterator<ValueConstPtr>() const {
690 return NodeContainerIterator<ValueConstPtr>{underlying_};
691 }
692
693 reference operator*() const {
694 return *underlying_.item();
695 }
696
697 pointer operator->() const {
698 return std::pointer_traits<pointer>::pointer_to(**this);
699 }
700
701 NodeContainerIterator& operator++() {
702 underlying_.advance();
703 return *this;
704 }
705
706 NodeContainerIterator operator++(int) {
707 auto cur = *this;
708 ++*this;
709 return cur;
710 }
711
712 bool operator==(NodeContainerIterator<ValueConstPtr> const& rhs) const {
713 return underlying_ == rhs.underlying_;
714 }
715 bool operator!=(NodeContainerIterator<ValueConstPtr> const& rhs) const {
716 return !(*this == rhs);
717 }
718
719 private:
720 ItemIter underlying_;
721
722 explicit NodeContainerIterator(ItemIter const& underlying)
723 : underlying_{underlying} {}
724
725 template <typename K, typename M, typename H, typename E, typename A>
726 friend class NodeContainerPolicy;
727
728 template <typename P>
729 friend class NodeContainerIterator;
730};
731
732template <
733 typename Key,
734 typename MappedTypeOrVoid,
735 typename HasherOrVoid,
736 typename KeyEqualOrVoid,
737 typename AllocOrVoid>
738class NodeContainerPolicy
739 : public BasePolicy<
740 Key,
741 MappedTypeOrVoid,
742 HasherOrVoid,
743 KeyEqualOrVoid,
744 AllocOrVoid,
745 typename std::allocator_traits<Defaulted<
746 AllocOrVoid,
747 DefaultAlloc<std::conditional_t<
748 std::is_void<MappedTypeOrVoid>::value,
749 Key,
750 MapValueType<Key, MappedTypeOrVoid>>>>>::pointer> {
751 public:
752 using Super = BasePolicy<
753 Key,
754 MappedTypeOrVoid,
755 HasherOrVoid,
756 KeyEqualOrVoid,
757 AllocOrVoid,
758 typename std::allocator_traits<Defaulted<
759 AllocOrVoid,
760 DefaultAlloc<std::conditional_t<
761 std::is_void<MappedTypeOrVoid>::value,
762 Key,
763 MapValueType<Key, MappedTypeOrVoid>>>>>::pointer>;
764 using Alloc = typename Super::Alloc;
765 using AllocTraits = typename Super::AllocTraits;
766 using Item = typename Super::Item;
767 using ItemIter = typename Super::ItemIter;
768 using Value = typename Super::Value;
769
770 private:
771 using ByteAlloc = typename Super::ByteAlloc;
772
773 using Super::kIsMap;
774
775 public:
776 using ConstIter = NodeContainerIterator<typename AllocTraits::const_pointer>;
777 using Iter = std::conditional_t<
778 kIsMap,
779 NodeContainerIterator<typename AllocTraits::pointer>,
780 ConstIter>;
781
782 //////// F14Table policy
783
784 static constexpr bool prefetchBeforeRehash() {
785 return true;
786 }
787
788 static constexpr bool prefetchBeforeCopy() {
789 return true;
790 }
791
792 static constexpr bool prefetchBeforeDestroy() {
793 return !std::is_trivially_destructible<Value>::value;
794 }
795
796 static constexpr bool destroyItemOnClear() {
797 return true;
798 }
799
800 // inherit constructors
801 using Super::Super;
802
803 void swapPolicy(NodeContainerPolicy& rhs) {
804 this->swapBasePolicy(rhs);
805 }
806
807 using Super::keyForValue;
808
809 std::size_t computeItemHash(Item const& item) const {
810 return this->computeKeyHash(keyForValue(*item));
811 }
812
813 template <typename K>
814 bool keyMatchesItem(K const& key, Item const& item) const {
815 return this->keyEqual()(key, keyForValue(*item));
816 }
817
818 Value const& buildArgForItem(Item const& item) const& {
819 return *item;
820 }
821
822 // buildArgForItem(Item&)&& is used when moving between unequal allocators
823 decltype(auto) buildArgForItem(Item& item) && {
824 return Super::moveValue(*item);
825 }
826
827 Value&& valueAtItemForExtract(Item& item) {
828 return std::move(*item);
829 }
830
831 template <typename Table, typename... Args>
832 void constructValueAtItem(Table&&, Item* itemAddr, Args&&... args) {
833 Alloc& a = this->alloc();
834 // TODO(T31574848): clean up assume-s used to optimize placement new
835 assume(itemAddr != nullptr);
836 new (itemAddr) Item{AllocTraits::allocate(a, 1)};
837 auto p = std::addressof(**itemAddr);
838 // TODO(T31574848): clean up assume-s used to optimize placement new
839 assume(p != nullptr);
840 AllocTraits::construct(a, p, std::forward<Args>(args)...);
841 }
842
843 void moveItemDuringRehash(Item* itemAddr, Item& src) {
844 // This is basically *itemAddr = src; src = nullptr, but allowing
845 // for fancy pointers.
846 // TODO(T31574848): clean up assume-s used to optimize placement new
847 assume(itemAddr != nullptr);
848 new (itemAddr) Item{std::move(src)};
849 src = nullptr;
850 src.~Item();
851 }
852
853 void prefetchValue(Item const& item) const {
854 prefetchAddr(std::addressof(*item));
855 }
856
857 void destroyItem(Item& item) {
858 if (item != nullptr) {
859 Alloc& a = this->alloc();
860 AllocTraits::destroy(a, std::addressof(*item));
861 AllocTraits::deallocate(a, item, 1);
862 }
863 item.~Item();
864 }
865
866 template <typename V>
867 void visitPolicyAllocationClasses(
868 std::size_t chunkAllocSize,
869 std::size_t size,
870 std::size_t /*capacity*/,
871 V&& visitor) const {
872 if (chunkAllocSize > 0) {
873 visitor(
874 allocationBytesForOverAligned<ByteAlloc, kRequiredVectorAlignment>(
875 chunkAllocSize),
876 1);
877 }
878 if (size > 0) {
879 visitor(sizeof(Value), size);
880 }
881 }
882
883 //////// F14BasicMap/Set policy
884
885 Iter makeIter(ItemIter const& underlying) const {
886 return Iter{underlying};
887 }
888 ConstIter makeConstIter(ItemIter const& underlying) const {
889 return Iter{underlying};
890 }
891 ItemIter const& unwrapIter(ConstIter const& iter) const {
892 return iter.underlying_;
893 }
894};
895
896//////// VectorContainer
897
898template <
899 typename Key,
900 typename MappedTypeOrVoid,
901 typename HasherOrVoid,
902 typename KeyEqualOrVoid,
903 typename AllocOrVoid,
904 typename EligibleForPerturbedInsertionOrder>
905class VectorContainerPolicy;
906
907template <typename ValuePtr>
908class VectorContainerIterator : public BaseIter<ValuePtr, uint32_t> {
909 using Super = BaseIter<ValuePtr, uint32_t>;
910 using ValueConstPtr = typename Super::ValueConstPtr;
911
912 public:
913 using pointer = typename Super::pointer;
914 using reference = typename Super::reference;
915 using value_type = typename Super::value_type;
916
917 VectorContainerIterator() = default;
918 VectorContainerIterator(VectorContainerIterator const&) = default;
919 VectorContainerIterator(VectorContainerIterator&&) = default;
920 VectorContainerIterator& operator=(VectorContainerIterator const&) = default;
921 VectorContainerIterator& operator=(VectorContainerIterator&&) = default;
922 ~VectorContainerIterator() = default;
923
924 /*implicit*/ operator VectorContainerIterator<ValueConstPtr>() const {
925 return VectorContainerIterator<ValueConstPtr>{current_, lowest_};
926 }
927
928 reference operator*() const {
929 return *current_;
930 }
931
932 pointer operator->() const {
933 return current_;
934 }
935
936 VectorContainerIterator& operator++() {
937 if (UNLIKELY(current_ == lowest_)) {
938 current_ = nullptr;
939 } else {
940 --current_;
941 }
942 return *this;
943 }
944
945 VectorContainerIterator operator++(int) {
946 auto cur = *this;
947 ++*this;
948 return cur;
949 }
950
951 bool operator==(VectorContainerIterator<ValueConstPtr> const& rhs) const {
952 return current_ == rhs.current_;
953 }
954 bool operator!=(VectorContainerIterator<ValueConstPtr> const& rhs) const {
955 return !(*this == rhs);
956 }
957
958 private:
959 ValuePtr current_;
960 ValuePtr lowest_;
961
962 explicit VectorContainerIterator(ValuePtr current, ValuePtr lowest)
963 : current_(current), lowest_(lowest) {}
964
965 std::size_t index() const {
966 return current_ - lowest_;
967 }
968
969 template <
970 typename K,
971 typename M,
972 typename H,
973 typename E,
974 typename A,
975 typename P>
976 friend class VectorContainerPolicy;
977
978 template <typename P>
979 friend class VectorContainerIterator;
980};
981
982struct VectorContainerIndexSearch {
983 uint32_t index_;
984};
985
986template <
987 typename Key,
988 typename MappedTypeOrVoid,
989 typename HasherOrVoid,
990 typename KeyEqualOrVoid,
991 typename AllocOrVoid,
992 typename EligibleForPerturbedInsertionOrder>
993class VectorContainerPolicy : public BasePolicy<
994 Key,
995 MappedTypeOrVoid,
996 HasherOrVoid,
997 KeyEqualOrVoid,
998 AllocOrVoid,
999 uint32_t> {
1000 public:
1001 using Super = BasePolicy<
1002 Key,
1003 MappedTypeOrVoid,
1004 HasherOrVoid,
1005 KeyEqualOrVoid,
1006 AllocOrVoid,
1007 uint32_t>;
1008 using Alloc = typename Super::Alloc;
1009 using AllocTraits = typename Super::AllocTraits;
1010 using ByteAlloc = typename Super::ByteAlloc;
1011 using ByteAllocTraits = typename Super::ByteAllocTraits;
1012 using BytePtr = typename Super::BytePtr;
1013 using Hasher = typename Super::Hasher;
1014 using Item = typename Super::Item;
1015 using ItemIter = typename Super::ItemIter;
1016 using KeyEqual = typename Super::KeyEqual;
1017 using Value = typename Super::Value;
1018
1019 using Super::kAllocIsAlwaysEqual;
1020
1021 private:
1022 using Super::kIsMap;
1023
1024 public:
1025 static constexpr bool kEnableItemIteration = false;
1026
1027 static constexpr bool kContinuousCapacity = true;
1028
1029 using InternalSizeType = Item;
1030
1031 using ConstIter =
1032 VectorContainerIterator<typename AllocTraits::const_pointer>;
1033 using Iter = std::conditional_t<
1034 kIsMap,
1035 VectorContainerIterator<typename AllocTraits::pointer>,
1036 ConstIter>;
1037 using ConstReverseIter = typename AllocTraits::const_pointer;
1038 using ReverseIter = std::
1039 conditional_t<kIsMap, typename AllocTraits::pointer, ConstReverseIter>;
1040
1041 using ValuePtr = typename AllocTraits::pointer;
1042
1043 //////// F14Table policy
1044
1045 static constexpr bool prefetchBeforeRehash() {
1046 return true;
1047 }
1048
1049 static constexpr bool prefetchBeforeCopy() {
1050 return false;
1051 }
1052
1053 static constexpr bool prefetchBeforeDestroy() {
1054 return false;
1055 }
1056
1057 static constexpr bool destroyItemOnClear() {
1058 return false;
1059 }
1060
1061 private:
1062 static constexpr bool valueIsTriviallyCopyable() {
1063 return AllocatorHasDefaultObjectConstruct<Alloc, Value, Value>::value &&
1064 AllocatorHasDefaultObjectDestroy<Alloc, Value>::value &&
1065 is_trivially_copyable<Value>::value;
1066 }
1067
1068 public:
1069 VectorContainerPolicy(
1070 Hasher const& hasher,
1071 KeyEqual const& keyEqual,
1072 Alloc const& alloc)
1073 : Super{hasher, keyEqual, alloc} {}
1074
1075 VectorContainerPolicy(VectorContainerPolicy const& rhs) : Super{rhs} {
1076 // values_ will get allocated later to do the copy
1077 }
1078
1079 VectorContainerPolicy(VectorContainerPolicy const& rhs, Alloc const& alloc)
1080 : Super{rhs, alloc} {
1081 // values_ will get allocated later to do the copy
1082 }
1083
1084 VectorContainerPolicy(VectorContainerPolicy&& rhs) noexcept
1085 : Super{std::move(rhs)}, values_{rhs.values_} {
1086 rhs.values_ = nullptr;
1087 }
1088
1089 VectorContainerPolicy(
1090 VectorContainerPolicy&& rhs,
1091 Alloc const& alloc) noexcept
1092 : Super{std::move(rhs), alloc} {
1093 if (kAllocIsAlwaysEqual || this->alloc() == rhs.alloc()) {
1094 // common case
1095 values_ = rhs.values_;
1096 rhs.values_ = nullptr;
1097 } else {
1098 // table must be constructed in new memory
1099 values_ = nullptr;
1100 }
1101 }
1102
1103 VectorContainerPolicy& operator=(VectorContainerPolicy const& rhs) {
1104 if (this != &rhs) {
1105 FOLLY_SAFE_DCHECK(values_ == nullptr, "");
1106 Super::operator=(rhs);
1107 }
1108 return *this;
1109 }
1110
1111 VectorContainerPolicy& operator=(VectorContainerPolicy&& rhs) noexcept {
1112 if (this != &rhs) {
1113 FOLLY_SAFE_DCHECK(values_ == nullptr, "");
1114 bool transfer =
1115 AllocTraits::propagate_on_container_move_assignment::value ||
1116 kAllocIsAlwaysEqual || this->alloc() == rhs.alloc();
1117 Super::operator=(std::move(rhs));
1118 if (transfer) {
1119 values_ = rhs.values_;
1120 rhs.values_ = nullptr;
1121 }
1122 }
1123 return *this;
1124 }
1125
1126 void swapPolicy(VectorContainerPolicy& rhs) {
1127 using std::swap;
1128 this->swapBasePolicy(rhs);
1129 swap(values_, rhs.values_);
1130 }
1131
1132 template <typename K>
1133 std::size_t computeKeyHash(K const& key) const {
1134 static_assert(
1135 Super::isAvalanchingHasher() == IsAvalanchingHasher<Hasher, K>::value,
1136 "");
1137 return this->hasher()(key);
1138 }
1139
1140 std::size_t computeKeyHash(VectorContainerIndexSearch const& key) const {
1141 return computeItemHash(key.index_);
1142 }
1143
1144 using Super::keyForValue;
1145
1146 std::size_t computeItemHash(Item const& item) const {
1147 return this->computeKeyHash(keyForValue(values_[item]));
1148 }
1149
1150 bool keyMatchesItem(VectorContainerIndexSearch const& key, Item const& item)
1151 const {
1152 return key.index_ == item;
1153 }
1154
1155 template <typename K>
1156 bool keyMatchesItem(K const& key, Item const& item) const {
1157 return this->keyEqual()(key, keyForValue(values_[item]));
1158 }
1159
1160 Key const& keyForValue(VectorContainerIndexSearch const& arg) const {
1161 return keyForValue(values_[arg.index_]);
1162 }
1163
1164 VectorContainerIndexSearch buildArgForItem(Item const& item) const {
1165 return {item};
1166 }
1167
1168 Value&& valueAtItemForExtract(Item& item) {
1169 return std::move(values_[item]);
1170 }
1171
1172 template <typename Table>
1173 void constructValueAtItem(
1174 Table&&,
1175 Item* itemAddr,
1176 VectorContainerIndexSearch arg) {
1177 *itemAddr = arg.index_;
1178 }
1179
1180 template <typename Table, typename... Args>
1181 void constructValueAtItem(Table&& table, Item* itemAddr, Args&&... args) {
1182 Alloc& a = this->alloc();
1183 std::size_t size = table.size();
1184 FOLLY_SAFE_DCHECK(size < std::numeric_limits<InternalSizeType>::max(), "");
1185 *itemAddr = static_cast<InternalSizeType>(size);
1186 auto dst = std::addressof(values_[size]);
1187 // TODO(T31574848): clean up assume-s used to optimize placement new
1188 assume(dst != nullptr);
1189 AllocTraits::construct(a, dst, std::forward<Args>(args)...);
1190
1191 constexpr bool perturb = FOLLY_F14_PERTURB_INSERTION_ORDER;
1192 if (EligibleForPerturbedInsertionOrder::value && perturb &&
1193 !tlsPendingSafeInserts()) {
1194 // Pick a random victim. We have to do this post-construction
1195 // because the item and tag are already set in the table before
1196 // calling constructValueAtItem, so if there is a tag collision
1197 // find may evaluate values_[size] during the search.
1198 auto i = tlsMinstdRand(size + 1);
1199 if (i != size) {
1200 auto& lhsItem = *itemAddr;
1201 auto rhsIter = table.find(
1202 VectorContainerIndexSearch{static_cast<InternalSizeType>(i)});
1203 FOLLY_SAFE_DCHECK(!rhsIter.atEnd(), "");
1204 auto& rhsItem = rhsIter.item();
1205 FOLLY_SAFE_DCHECK(lhsItem == size, "");
1206 FOLLY_SAFE_DCHECK(rhsItem == i, "");
1207
1208 aligned_storage_for_t<Value> tmp;
1209 Value* tmpValue = static_cast<Value*>(static_cast<void*>(&tmp));
1210 transfer(a, std::addressof(values_[i]), tmpValue, 1);
1211 transfer(
1212 a, std::addressof(values_[size]), std::addressof(values_[i]), 1);
1213 transfer(a, tmpValue, std::addressof(values_[size]), 1);
1214 lhsItem = i;
1215 rhsItem = size;
1216 }
1217 }
1218 }
1219
1220 void moveItemDuringRehash(Item* itemAddr, Item& src) {
1221 *itemAddr = src;
1222 }
1223
1224 void prefetchValue(Item const& item) const {
1225 prefetchAddr(std::addressof(values_[item]));
1226 }
1227
1228 void destroyItem(Item&) {}
1229
1230 template <typename T>
1231 std::enable_if_t<std::is_nothrow_move_constructible<T>::value>
1232 complainUnlessNothrowMove() {}
1233
1234 template <typename T>
1235 [[deprecated(
1236 "use F14NodeMap/Set or mark key and mapped type move constructor nothrow")]] std::
1237 enable_if_t<!std::is_nothrow_move_constructible<T>::value>
1238 complainUnlessNothrowMove() {}
1239
1240 void transfer(Alloc& a, Value* src, Value* dst, std::size_t n) {
1241 complainUnlessNothrowMove<Key>();
1242 complainUnlessNothrowMove<lift_unit_t<MappedTypeOrVoid>>();
1243
1244 auto origSrc = src;
1245 if (valueIsTriviallyCopyable()) {
1246 std::memcpy(
1247 static_cast<void*>(dst),
1248 static_cast<void const*>(src),
1249 n * sizeof(Value));
1250 } else {
1251 for (std::size_t i = 0; i < n; ++i, ++src, ++dst) {
1252 // TODO(T31574848): clean up assume-s used to optimize placement new
1253 assume(dst != nullptr);
1254 AllocTraits::construct(a, dst, Super::moveValue(*src));
1255 if (kIsMap) {
1256 AllocTraits::destroy(a, launder(src));
1257 } else {
1258 AllocTraits::destroy(a, src);
1259 }
1260 }
1261 }
1262 this->afterDestroyWithoutDeallocate(origSrc, n);
1263 }
1264
1265 template <typename P, typename V>
1266 bool beforeBuildImpl(std::size_t size, P&& rhs, V const& constructorArgFor) {
1267 Alloc& a = this->alloc();
1268
1269 FOLLY_SAFE_DCHECK(values_ != nullptr, "");
1270
1271 auto src = std::addressof(rhs.values_[0]);
1272 Value* dst = std::addressof(values_[0]);
1273
1274 if (valueIsTriviallyCopyable()) {
1275 std::memcpy(
1276 static_cast<void*>(dst),
1277 static_cast<void const*>(src),
1278 size * sizeof(Value));
1279 } else {
1280 for (std::size_t i = 0; i < size; ++i, ++src, ++dst) {
1281 try {
1282 // TODO(T31574848): clean up assume-s used to optimize placement new
1283 assume(dst != nullptr);
1284 AllocTraits::construct(a, dst, constructorArgFor(*src));
1285 } catch (...) {
1286 for (Value* cleanup = std::addressof(values_[0]); cleanup != dst;
1287 ++cleanup) {
1288 AllocTraits::destroy(a, cleanup);
1289 }
1290 throw;
1291 }
1292 }
1293 }
1294 return true;
1295 }
1296
1297 bool beforeBuild(
1298 std::size_t size,
1299 std::size_t /*capacity*/,
1300 VectorContainerPolicy const& rhs) {
1301 return beforeBuildImpl(size, rhs, [](Value const& v) { return v; });
1302 }
1303
1304 bool beforeBuild(
1305 std::size_t size,
1306 std::size_t /*capacity*/,
1307 VectorContainerPolicy&& rhs) {
1308 return beforeBuildImpl(
1309 size, rhs, [](Value& v) { return Super::moveValue(v); });
1310 }
1311
1312 template <typename P>
1313 void afterBuild(
1314 bool /*undoState*/,
1315 bool success,
1316 std::size_t /*size*/,
1317 std::size_t /*capacity*/,
1318 P&& /*rhs*/) {
1319 // buildArgForItem can be used to construct a new item trivially,
1320 // so no failure between beforeBuild and afterBuild should be possible
1321 FOLLY_SAFE_DCHECK(success, "");
1322 }
1323
1324 private:
1325 // Returns the byte offset of the first Value in a unified allocation
1326 // that first holds prefixBytes of data, where prefixBytes comes from
1327 // Chunk storage and may be only 4-byte aligned due to sub-chunk
1328 // allocation.
1329 static std::size_t valuesOffset(std::size_t prefixBytes) {
1330 FOLLY_SAFE_DCHECK((prefixBytes % alignof(Item)) == 0, "");
1331 if (alignof(Value) > alignof(Item)) {
1332 prefixBytes = -(-prefixBytes & ~(alignof(Value) - 1));
1333 }
1334 FOLLY_SAFE_DCHECK((prefixBytes % alignof(Value)) == 0, "");
1335 return prefixBytes;
1336 }
1337
1338 // Returns the total number of bytes that should be allocated to store
1339 // prefixBytes of Chunks and valueCapacity values.
1340 static std::size_t allocSize(
1341 std::size_t prefixBytes,
1342 std::size_t valueCapacity) {
1343 return valuesOffset(prefixBytes) + sizeof(Value) * valueCapacity;
1344 }
1345
1346 public:
1347 ValuePtr beforeRehash(
1348 std::size_t size,
1349 std::size_t oldCapacity,
1350 std::size_t newCapacity,
1351 std::size_t chunkAllocSize,
1352 BytePtr& outChunkAllocation) {
1353 FOLLY_SAFE_DCHECK(
1354 size <= oldCapacity && ((values_ == nullptr) == (oldCapacity == 0)) &&
1355 newCapacity > 0 &&
1356 newCapacity <= (std::numeric_limits<Item>::max)(),
1357 "");
1358
1359 outChunkAllocation =
1360 allocateOverAligned<ByteAlloc, kRequiredVectorAlignment>(
1361 ByteAlloc{Super::alloc()}, allocSize(chunkAllocSize, newCapacity));
1362
1363 ValuePtr before = values_;
1364 ValuePtr after = std::pointer_traits<ValuePtr>::pointer_to(
1365 *static_cast<Value*>(static_cast<void*>(
1366 &*outChunkAllocation + valuesOffset(chunkAllocSize))));
1367
1368 if (size > 0) {
1369 Alloc& a{this->alloc()};
1370 transfer(a, std::addressof(before[0]), std::addressof(after[0]), size);
1371 }
1372
1373 values_ = after;
1374 return before;
1375 }
1376
1377 FOLLY_NOINLINE void afterFailedRehash(ValuePtr state, std::size_t size) {
1378 // state holds the old storage
1379 Alloc& a = this->alloc();
1380 if (size > 0) {
1381 transfer(a, std::addressof(values_[0]), std::addressof(state[0]), size);
1382 }
1383 values_ = state;
1384 }
1385
1386 void afterRehash(
1387 ValuePtr state,
1388 bool success,
1389 std::size_t size,
1390 std::size_t oldCapacity,
1391 std::size_t newCapacity,
1392 BytePtr chunkAllocation,
1393 std::size_t chunkAllocSize) {
1394 if (!success) {
1395 afterFailedRehash(state, size);
1396 }
1397
1398 // on success, chunkAllocation is the old allocation, on failure it is the
1399 // new one
1400 if (chunkAllocation != nullptr) {
1401 deallocateOverAligned<ByteAlloc, kRequiredVectorAlignment>(
1402 ByteAlloc{Super::alloc()},
1403 chunkAllocation,
1404 allocSize(chunkAllocSize, (success ? oldCapacity : newCapacity)));
1405 }
1406 }
1407
1408 void beforeClear(std::size_t size, std::size_t capacity) {
1409 FOLLY_SAFE_DCHECK(
1410 size <= capacity && ((values_ == nullptr) == (capacity == 0)), "");
1411 Alloc& a = this->alloc();
1412 for (std::size_t i = 0; i < size; ++i) {
1413 AllocTraits::destroy(a, std::addressof(values_[i]));
1414 }
1415 }
1416
1417 void beforeReset(std::size_t size, std::size_t capacity) {
1418 beforeClear(size, capacity);
1419 }
1420
1421 void afterReset(
1422 std::size_t /*size*/,
1423 std::size_t capacity,
1424 BytePtr chunkAllocation,
1425 std::size_t chunkAllocSize) {
1426 if (chunkAllocation != nullptr) {
1427 deallocateOverAligned<ByteAlloc, kRequiredVectorAlignment>(
1428 ByteAlloc{Super::alloc()},
1429 chunkAllocation,
1430 allocSize(chunkAllocSize, capacity));
1431 values_ = nullptr;
1432 }
1433 }
1434
1435 template <typename V>
1436 void visitPolicyAllocationClasses(
1437 std::size_t chunkAllocSize,
1438 std::size_t /*size*/,
1439 std::size_t capacity,
1440 V&& visitor) const {
1441 FOLLY_SAFE_DCHECK((chunkAllocSize == 0) == (capacity == 0), "");
1442 if (chunkAllocSize > 0) {
1443 visitor(
1444 allocationBytesForOverAligned<ByteAlloc, kRequiredVectorAlignment>(
1445 allocSize(chunkAllocSize, capacity)),
1446 1);
1447 }
1448 }
1449
1450 // Iterator stuff
1451
1452 Iter linearBegin(std::size_t size) const {
1453 return Iter{(size > 0 ? values_ + size - 1 : nullptr), values_};
1454 }
1455
1456 Iter linearEnd() const {
1457 return Iter{nullptr, nullptr};
1458 }
1459
1460 //////// F14BasicMap/Set policy
1461
1462 Iter makeIter(ItemIter const& underlying) const {
1463 if (underlying.atEnd()) {
1464 return linearEnd();
1465 } else {
1466 assume(values_ + underlying.item() != nullptr);
1467 assume(values_ != nullptr);
1468 return Iter{values_ + underlying.item(), values_};
1469 }
1470 }
1471
1472 ConstIter makeConstIter(ItemIter const& underlying) const {
1473 return makeIter(underlying);
1474 }
1475
1476 Item iterToIndex(ConstIter const& iter) const {
1477 auto n = iter.index();
1478 assume(n <= std::numeric_limits<Item>::max());
1479 return static_cast<Item>(n);
1480 }
1481
1482 Iter indexToIter(Item index) const {
1483 return Iter{values_ + index, values_};
1484 }
1485
1486 Iter iter(ReverseIter it) {
1487 return Iter{it, values_};
1488 }
1489
1490 ConstIter iter(ConstReverseIter it) const {
1491 return ConstIter{it, values_};
1492 }
1493
1494 ReverseIter riter(Iter it) {
1495 return it.current_;
1496 }
1497
1498 ConstReverseIter riter(ConstIter it) const {
1499 return it.current_;
1500 }
1501
1502 ValuePtr values_{nullptr};
1503};
1504
1505template <
1506 template <typename, typename, typename, typename, typename, typename...>
1507 class Policy,
1508 typename Key,
1509 typename Mapped,
1510 typename Hasher,
1511 typename KeyEqual,
1512 typename Alloc,
1513 typename... Args>
1514using MapPolicyWithDefaults = Policy<
1515 Key,
1516 Mapped,
1517 VoidDefault<Hasher, DefaultHasher<Key>>,
1518 VoidDefault<KeyEqual, DefaultKeyEqual<Key>>,
1519 VoidDefault<Alloc, DefaultAlloc<std::pair<Key const, Mapped>>>,
1520 Args...>;
1521
1522template <
1523 template <typename, typename, typename, typename, typename, typename...>
1524 class Policy,
1525 typename Key,
1526 typename Hasher,
1527 typename KeyEqual,
1528 typename Alloc,
1529 typename... Args>
1530using SetPolicyWithDefaults = Policy<
1531 Key,
1532 void,
1533 VoidDefault<Hasher, DefaultHasher<Key>>,
1534 VoidDefault<KeyEqual, DefaultKeyEqual<Key>>,
1535 VoidDefault<Alloc, DefaultAlloc<Key>>,
1536 Args...>;
1537
1538} // namespace detail
1539} // namespace f14
1540} // namespace folly
1541
1542#endif // FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE
1543