/* * Copyright (c) Meta Platforms, Inc. and affiliates. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ #pragma once #include <memory> #include <new> #include <type_traits> #include <utility> #include <folly/Memory.h> #include <folly/Portability.h> #include <folly/Traits.h> #include <folly/Unit.h> #include <folly/container/HeterogeneousAccess.h> #include <folly/container/detail/F14Table.h> #include <folly/hash/Hash.h> #include <folly/lang/Align.h> #include <folly/lang/SafeAssert.h> #include <folly/memory/Malloc.h> #if FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE namespace folly { namespace f14 { namespace detail { NonConstPtr; MapValueType; SetOrMapValueType; IsNothrowMoveAndDestroy; // Used to enable EBO for Hasher, KeyEqual, and Alloc. std::tuple of // all empty objects is empty in libstdc++ but not libc++. template < char Tag, typename T, bool Inherit = std::is_empty<T>::value && !std::is_final<T>::value> struct ObjectHolder { … }; ObjectHolder<Tag, T, true>; // Policy provides the functionality of hasher, key_equal, and // allocator_type. In addition, it can add indirection to the values // contained in the base table by defining a non-trivial value() method. // // To facilitate stateful implementations it is guaranteed that there // will be a 1:1 relationship between BaseTable and Policy instance: // policies will only be copied when their owning table is copied, and // they will only be moved when their owning table is moved. // // Key equality will have the user-supplied search key as its first // argument and the table contents as its second. Heterogeneous lookup // should be handled on the first argument. // // Item is the data stored inline in the hash table's chunks. The policy // controls how this is mapped to the corresponding Value. // // The policies defined in this file work for either set or map types. // Most of the functionality is identical. A few methods detect the // collection type by checking to see if MappedType is void, and then use // SFINAE to select the appropriate implementation. template < typename KeyType, typename MappedTypeOrVoid, typename HasherOrVoid, typename KeyEqualOrVoid, typename AllocOrVoid, typename ItemType> struct FOLLY_MSVC_DECLSPEC(empty_bases) BasePolicy : private ObjectHolder< 'H', Defaulted<HasherOrVoid, DefaultHasher<KeyType>>>, private ObjectHolder< 'E', Defaulted<KeyEqualOrVoid, DefaultKeyEqual<KeyType>>>, private ObjectHolder< 'A', Defaulted< AllocOrVoid, DefaultAlloc<SetOrMapValueType<KeyType, MappedTypeOrVoid>>>> { … }; // BaseIter is a convenience for concrete set and map implementations template <typename ValuePtr, typename Item> class BaseIter { … }; //////// ValueContainer template < typename Key, typename Mapped, typename HasherOrVoid, typename KeyEqualOrVoid, typename AllocOrVoid> class ValueContainerPolicy; ValueContainerIteratorBase; template <typename ValuePtr> class ValueContainerIterator : public ValueContainerIteratorBase<ValuePtr> { … }; template < typename Key, typename MappedTypeOrVoid, typename HasherOrVoid, typename KeyEqualOrVoid, typename AllocOrVoid> class ValueContainerPolicy : public BasePolicy< Key, MappedTypeOrVoid, HasherOrVoid, KeyEqualOrVoid, AllocOrVoid, SetOrMapValueType<Key, MappedTypeOrVoid>> { … }; //////// NodeContainer template < typename Key, typename Mapped, typename HasherOrVoid, typename KeyEqualOrVoid, typename AllocOrVoid> class NodeContainerPolicy; template <typename ValuePtr> class NodeContainerIterator : public BaseIter<ValuePtr, NonConstPtr<ValuePtr>> { … }; template < typename Key, typename MappedTypeOrVoid, typename HasherOrVoid, typename KeyEqualOrVoid, typename AllocOrVoid> class NodeContainerPolicy : public BasePolicy< Key, MappedTypeOrVoid, HasherOrVoid, KeyEqualOrVoid, AllocOrVoid, typename std::allocator_traits<Defaulted< AllocOrVoid, DefaultAlloc<std::conditional_t< std::is_void<MappedTypeOrVoid>::value, Key, MapValueType<Key, MappedTypeOrVoid>>>>>::pointer> { … }; //////// VectorContainer template < typename Key, typename MappedTypeOrVoid, typename HasherOrVoid, typename KeyEqualOrVoid, typename AllocOrVoid, typename EligibleForPerturbedInsertionOrder> class VectorContainerPolicy; template <typename ValuePtr> class VectorContainerIterator : public BaseIter<ValuePtr, uint32_t> { … }; struct VectorContainerIndexSearch { … }; template < typename Key, typename MappedTypeOrVoid, typename HasherOrVoid, typename KeyEqualOrVoid, typename AllocOrVoid, typename EligibleForPerturbedInsertionOrder> class VectorContainerPolicy : public BasePolicy< Key, MappedTypeOrVoid, HasherOrVoid, KeyEqualOrVoid, AllocOrVoid, uint32_t> { … }; MapPolicyWithDefaults; SetPolicyWithDefaults; } // namespace detail } // namespace f14 } // namespace folly #endif // FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE
Codebase Browser
folly