hash_policy_traits.h (7858B)
1 // Copyright 2018 The Abseil Authors. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #ifndef ABSL_CONTAINER_INTERNAL_HASH_POLICY_TRAITS_H_ 16 #define ABSL_CONTAINER_INTERNAL_HASH_POLICY_TRAITS_H_ 17 18 #include <cstddef> 19 #include <memory> 20 #include <new> 21 #include <type_traits> 22 #include <utility> 23 24 #include "absl/container/internal/common_policy_traits.h" 25 #include "absl/meta/type_traits.h" 26 27 namespace absl { 28 ABSL_NAMESPACE_BEGIN 29 namespace container_internal { 30 31 // Defines how slots are initialized/destroyed/moved. 32 template <class Policy, class = void> 33 struct hash_policy_traits : common_policy_traits<Policy> { 34 // The type of the keys stored in the hashtable. 35 using key_type = typename Policy::key_type; 36 37 private: 38 struct ReturnKey { 39 template <class Key, 40 absl::enable_if_t<std::is_lvalue_reference<Key>::value, int> = 0> 41 static key_type& Impl(Key&& k, int) { 42 return *std::launder( 43 const_cast<key_type*>(std::addressof(std::forward<Key>(k)))); 44 } 45 46 template <class Key> 47 static Key Impl(Key&& k, char) { 48 return std::forward<Key>(k); 49 } 50 51 // When Key=T&, we forward the lvalue reference. 52 // When Key=T, we return by value to avoid a dangling reference. 53 // eg, for string_hash_map. 54 template <class Key, class... Args> 55 auto operator()(Key&& k, const Args&...) const 56 -> decltype(Impl(std::forward<Key>(k), 0)) { 57 return Impl(std::forward<Key>(k), 0); 58 } 59 }; 60 61 template <class P = Policy, class = void> 62 struct ConstantIteratorsImpl : std::false_type {}; 63 64 template <class P> 65 struct ConstantIteratorsImpl<P, absl::void_t<typename P::constant_iterators>> 66 : P::constant_iterators {}; 67 68 public: 69 // The actual object stored in the hash table. 70 using slot_type = typename Policy::slot_type; 71 72 // The argument type for insertions into the hashtable. This is different 73 // from value_type for increased performance. See initializer_list constructor 74 // and insert() member functions for more details. 75 using init_type = typename Policy::init_type; 76 77 using reference = decltype(Policy::element(std::declval<slot_type*>())); 78 using pointer = typename std::remove_reference<reference>::type*; 79 using value_type = typename std::remove_reference<reference>::type; 80 81 // Policies can set this variable to tell raw_hash_set that all iterators 82 // should be constant, even `iterator`. This is useful for set-like 83 // containers. 84 // Defaults to false if not provided by the policy. 85 using constant_iterators = ConstantIteratorsImpl<>; 86 87 // Returns the amount of memory owned by `slot`, exclusive of `sizeof(*slot)`. 88 // 89 // If `slot` is nullptr, returns the constant amount of memory owned by any 90 // full slot or -1 if slots own variable amounts of memory. 91 // 92 // PRECONDITION: `slot` is INITIALIZED or nullptr 93 template <class P = Policy> 94 static size_t space_used(const slot_type* slot) { 95 return P::space_used(slot); 96 } 97 98 // Provides generalized access to the key for elements, both for elements in 99 // the table and for elements that have not yet been inserted (or even 100 // constructed). We would like an API that allows us to say: `key(args...)` 101 // but we cannot do that for all cases, so we use this more general API that 102 // can be used for many things, including the following: 103 // 104 // - Given an element in a table, get its key. 105 // - Given an element initializer, get its key. 106 // - Given `emplace()` arguments, get the element key. 107 // 108 // Implementations of this must adhere to a very strict technical 109 // specification around aliasing and consuming arguments: 110 // 111 // Let `value_type` be the result type of `element()` without ref- and 112 // cv-qualifiers. The first argument is a functor, the rest are constructor 113 // arguments for `value_type`. Returns `std::forward<F>(f)(k, xs...)`, where 114 // `k` is the element key, and `xs...` are the new constructor arguments for 115 // `value_type`. It's allowed for `k` to alias `xs...`, and for both to alias 116 // `ts...`. The key won't be touched once `xs...` are used to construct an 117 // element; `ts...` won't be touched at all, which allows `apply()` to consume 118 // any rvalues among them. 119 // 120 // If `value_type` is constructible from `Ts&&...`, `Policy::apply()` must not 121 // trigger a hard compile error unless it originates from `f`. In other words, 122 // `Policy::apply()` must be SFINAE-friendly. If `value_type` is not 123 // constructible from `Ts&&...`, either SFINAE or a hard compile error is OK. 124 // 125 // If `Ts...` is `[cv] value_type[&]` or `[cv] init_type[&]`, 126 // `Policy::apply()` must work. A compile error is not allowed, SFINAE or not. 127 template <class F, class... Ts, class P = Policy> 128 static auto apply(F&& f, Ts&&... ts) 129 -> decltype(P::apply(std::forward<F>(f), std::forward<Ts>(ts)...)) { 130 return P::apply(std::forward<F>(f), std::forward<Ts>(ts)...); 131 } 132 133 // Returns the "key" portion of the slot. 134 // Used for node handle manipulation. 135 template <class P = Policy> 136 static auto mutable_key(slot_type* slot) 137 -> decltype(P::apply(ReturnKey(), hash_policy_traits::element(slot))) { 138 return P::apply(ReturnKey(), hash_policy_traits::element(slot)); 139 } 140 141 // Returns the "value" (as opposed to the "key") portion of the element. Used 142 // by maps to implement `operator[]`, `at()` and `insert_or_assign()`. 143 template <class T, class P = Policy> 144 static auto value(T* elem) -> decltype(P::value(elem)) { 145 return P::value(elem); 146 } 147 148 using HashSlotFn = size_t (*)(const void* hash_fn, void* slot); 149 150 template <class Hash> 151 static constexpr HashSlotFn get_hash_slot_fn() { 152 // get_hash_slot_fn may return nullptr to signal that non type erased function 153 // should be used. GCC warns against comparing function address with nullptr. 154 #if defined(__GNUC__) && !defined(__clang__) 155 #pragma GCC diagnostic push 156 // silent error: the address of * will never be NULL [-Werror=address] 157 #pragma GCC diagnostic ignored "-Waddress" 158 #endif 159 return Policy::template get_hash_slot_fn<Hash>() == nullptr 160 ? &hash_slot_fn_non_type_erased<Hash> 161 : Policy::template get_hash_slot_fn<Hash>(); 162 #if defined(__GNUC__) && !defined(__clang__) 163 #pragma GCC diagnostic pop 164 #endif 165 } 166 167 // Whether small object optimization is enabled. True by default. 168 static constexpr bool soo_enabled() { return soo_enabled_impl(Rank1{}); } 169 170 private: 171 template <class Hash> 172 struct HashElement { 173 template <class K, class... Args> 174 size_t operator()(const K& key, Args&&...) const { 175 return h(key); 176 } 177 const Hash& h; 178 }; 179 180 template <class Hash> 181 static size_t hash_slot_fn_non_type_erased(const void* hash_fn, void* slot) { 182 return Policy::apply(HashElement<Hash>{*static_cast<const Hash*>(hash_fn)}, 183 Policy::element(static_cast<slot_type*>(slot))); 184 } 185 186 // Use go/ranked-overloads for dispatching. Rank1 is preferred. 187 struct Rank0 {}; 188 struct Rank1 : Rank0 {}; 189 190 // Use auto -> decltype as an enabler. 191 template <class P = Policy> 192 static constexpr auto soo_enabled_impl(Rank1) -> decltype(P::soo_enabled()) { 193 return P::soo_enabled(); 194 } 195 196 static constexpr bool soo_enabled_impl(Rank0) { return true; } 197 }; 198 199 } // namespace container_internal 200 ABSL_NAMESPACE_END 201 } // namespace absl 202 203 #endif // ABSL_CONTAINER_INTERNAL_HASH_POLICY_TRAITS_H_