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 | |
35 | namespace folly { |
36 | namespace f14 { |
37 | namespace detail { |
38 | |
39 | template <typename Ptr> |
40 | using NonConstPtr = typename std::pointer_traits<Ptr>::template rebind< |
41 | std::remove_const_t<typename std::pointer_traits<Ptr>::element_type>>; |
42 | |
43 | template <typename KeyType, typename MappedType> |
44 | using MapValueType = std::pair<KeyType const, MappedType>; |
45 | |
46 | template <typename KeyType, typename MappedTypeOrVoid> |
47 | using 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++. |
54 | template < |
55 | char Tag, |
56 | typename T, |
57 | bool Inherit = std::is_empty<T>::value && !std::is_final<T>::value> |
58 | struct 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 | |
72 | template <char Tag, typename T> |
73 | struct 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. |
105 | template < |
106 | typename KeyType, |
107 | typename MappedTypeOrVoid, |
108 | typename HasherOrVoid, |
109 | typename KeyEqualOrVoid, |
110 | typename AllocOrVoid, |
111 | typename ItemType> |
112 | struct 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 |
397 | template <typename ValuePtr, typename Item> |
398 | class 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 | |
417 | template < |
418 | typename Key, |
419 | typename Mapped, |
420 | typename HasherOrVoid, |
421 | typename KeyEqualOrVoid, |
422 | typename AllocOrVoid> |
423 | class ValueContainerPolicy; |
424 | |
425 | template <typename ValuePtr> |
426 | using ValueContainerIteratorBase = BaseIter< |
427 | ValuePtr, |
428 | std::remove_const_t<typename std::pointer_traits<ValuePtr>::element_type>>; |
429 | |
430 | template <typename ValuePtr> |
431 | class 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 | |
491 | template < |
492 | typename Key, |
493 | typename MappedTypeOrVoid, |
494 | typename HasherOrVoid, |
495 | typename KeyEqualOrVoid, |
496 | typename AllocOrVoid> |
497 | class 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&& (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 | |
663 | template < |
664 | typename Key, |
665 | typename Mapped, |
666 | typename HasherOrVoid, |
667 | typename KeyEqualOrVoid, |
668 | typename AllocOrVoid> |
669 | class NodeContainerPolicy; |
670 | |
671 | template <typename ValuePtr> |
672 | class 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 | |
732 | template < |
733 | typename Key, |
734 | typename MappedTypeOrVoid, |
735 | typename HasherOrVoid, |
736 | typename KeyEqualOrVoid, |
737 | typename AllocOrVoid> |
738 | class 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&& (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 | |
898 | template < |
899 | typename Key, |
900 | typename MappedTypeOrVoid, |
901 | typename HasherOrVoid, |
902 | typename KeyEqualOrVoid, |
903 | typename AllocOrVoid, |
904 | typename EligibleForPerturbedInsertionOrder> |
905 | class VectorContainerPolicy; |
906 | |
907 | template <typename ValuePtr> |
908 | class 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 | |
982 | struct VectorContainerIndexSearch { |
983 | uint32_t index_; |
984 | }; |
985 | |
986 | template < |
987 | typename Key, |
988 | typename MappedTypeOrVoid, |
989 | typename HasherOrVoid, |
990 | typename KeyEqualOrVoid, |
991 | typename AllocOrVoid, |
992 | typename EligibleForPerturbedInsertionOrder> |
993 | class 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&& (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 | |
1505 | template < |
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> |
1514 | using 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 | |
1522 | template < |
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> |
1530 | using 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 | |