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 <type_traits> 21 #include <utility> 22 23 #include "absl/meta/type_traits.h" 24 25 namespace absl { 26 ABSL_NAMESPACE_BEGIN 27 namespace container_internal { 28 29 // Defines how slots are initialized/destroyed/moved. 30 template <class Policy, class = void> 31 struct hash_policy_traits { 32 private: 33 struct ReturnKey { 34 // We return `Key` here. 35 // When Key=T&, we forward the lvalue reference. 36 // When Key=T, we return by value to avoid a dangling reference. 37 // eg, for string_hash_map. 38 template <class Key, class... Args> operatorhash_policy_traits::ReturnKey39 Key operator()(Key&& k, const Args&...) const { 40 return std::forward<Key>(k); 41 } 42 }; 43 44 template <class P = Policy, class = void> 45 struct ConstantIteratorsImpl : std::false_type {}; 46 47 template <class P> 48 struct ConstantIteratorsImpl<P, absl::void_t<typename P::constant_iterators>> 49 : P::constant_iterators {}; 50 51 public: 52 // The actual object stored in the hash table. 53 using slot_type = typename Policy::slot_type; 54 55 // The type of the keys stored in the hashtable. 56 using key_type = typename Policy::key_type; 57 58 // The argument type for insertions into the hashtable. This is different 59 // from value_type for increased performance. See initializer_list constructor 60 // and insert() member functions for more details. 61 using init_type = typename Policy::init_type; 62 63 using reference = decltype(Policy::element(std::declval<slot_type*>())); 64 using pointer = typename std::remove_reference<reference>::type*; 65 using value_type = typename std::remove_reference<reference>::type; 66 67 // Policies can set this variable to tell raw_hash_set that all iterators 68 // should be constant, even `iterator`. This is useful for set-like 69 // containers. 70 // Defaults to false if not provided by the policy. 71 using constant_iterators = ConstantIteratorsImpl<>; 72 73 // PRECONDITION: `slot` is UNINITIALIZED 74 // POSTCONDITION: `slot` is INITIALIZED 75 template <class Alloc, class... Args> 76 static void construct(Alloc* alloc, slot_type* slot, Args&&... args) { 77 Policy::construct(alloc, slot, std::forward<Args>(args)...); 78 } 79 80 // PRECONDITION: `slot` is INITIALIZED 81 // POSTCONDITION: `slot` is UNINITIALIZED 82 template <class Alloc> 83 static void destroy(Alloc* alloc, slot_type* slot) { 84 Policy::destroy(alloc, slot); 85 } 86 87 // Transfers the `old_slot` to `new_slot`. Any memory allocated by the 88 // allocator inside `old_slot` to `new_slot` can be transferred. 89 // 90 // OPTIONAL: defaults to: 91 // 92 // clone(new_slot, std::move(*old_slot)); 93 // destroy(old_slot); 94 // 95 // PRECONDITION: `new_slot` is UNINITIALIZED and `old_slot` is INITIALIZED 96 // POSTCONDITION: `new_slot` is INITIALIZED and `old_slot` is 97 // UNINITIALIZED 98 template <class Alloc> 99 static void transfer(Alloc* alloc, slot_type* new_slot, slot_type* old_slot) { 100 transfer_impl(alloc, new_slot, old_slot, 0); 101 } 102 103 // PRECONDITION: `slot` is INITIALIZED 104 // POSTCONDITION: `slot` is INITIALIZED 105 template <class P = Policy> 106 static auto element(slot_type* slot) -> decltype(P::element(slot)) { 107 return P::element(slot); 108 } 109 110 // Returns the amount of memory owned by `slot`, exclusive of `sizeof(*slot)`. 111 // 112 // If `slot` is nullptr, returns the constant amount of memory owned by any 113 // full slot or -1 if slots own variable amounts of memory. 114 // 115 // PRECONDITION: `slot` is INITIALIZED or nullptr 116 template <class P = Policy> 117 static size_t space_used(const slot_type* slot) { 118 return P::space_used(slot); 119 } 120 121 // Provides generalized access to the key for elements, both for elements in 122 // the table and for elements that have not yet been inserted (or even 123 // constructed). We would like an API that allows us to say: `key(args...)` 124 // but we cannot do that for all cases, so we use this more general API that 125 // can be used for many things, including the following: 126 // 127 // - Given an element in a table, get its key. 128 // - Given an element initializer, get its key. 129 // - Given `emplace()` arguments, get the element key. 130 // 131 // Implementations of this must adhere to a very strict technical 132 // specification around aliasing and consuming arguments: 133 // 134 // Let `value_type` be the result type of `element()` without ref- and 135 // cv-qualifiers. The first argument is a functor, the rest are constructor 136 // arguments for `value_type`. Returns `std::forward<F>(f)(k, xs...)`, where 137 // `k` is the element key, and `xs...` are the new constructor arguments for 138 // `value_type`. It's allowed for `k` to alias `xs...`, and for both to alias 139 // `ts...`. The key won't be touched once `xs...` are used to construct an 140 // element; `ts...` won't be touched at all, which allows `apply()` to consume 141 // any rvalues among them. 142 // 143 // If `value_type` is constructible from `Ts&&...`, `Policy::apply()` must not 144 // trigger a hard compile error unless it originates from `f`. In other words, 145 // `Policy::apply()` must be SFINAE-friendly. If `value_type` is not 146 // constructible from `Ts&&...`, either SFINAE or a hard compile error is OK. 147 // 148 // If `Ts...` is `[cv] value_type[&]` or `[cv] init_type[&]`, 149 // `Policy::apply()` must work. A compile error is not allowed, SFINAE or not. 150 template <class F, class... Ts, class P = Policy> 151 static auto apply(F&& f, Ts&&... ts) 152 -> decltype(P::apply(std::forward<F>(f), std::forward<Ts>(ts)...)) { 153 return P::apply(std::forward<F>(f), std::forward<Ts>(ts)...); 154 } 155 156 // Returns the "key" portion of the slot. 157 // Used for node handle manipulation. 158 template <class P = Policy> 159 static auto key(slot_type* slot) 160 -> decltype(P::apply(ReturnKey(), element(slot))) { 161 return P::apply(ReturnKey(), element(slot)); 162 } 163 164 // Returns the "value" (as opposed to the "key") portion of the element. Used 165 // by maps to implement `operator[]`, `at()` and `insert_or_assign()`. 166 template <class T, class P = Policy> 167 static auto value(T* elem) -> decltype(P::value(elem)) { 168 return P::value(elem); 169 } 170 171 private: 172 // Use auto -> decltype as an enabler. 173 template <class Alloc, class P = Policy> 174 static auto transfer_impl(Alloc* alloc, slot_type* new_slot, 175 slot_type* old_slot, int) 176 -> decltype((void)P::transfer(alloc, new_slot, old_slot)) { 177 P::transfer(alloc, new_slot, old_slot); 178 } 179 template <class Alloc> 180 static void transfer_impl(Alloc* alloc, slot_type* new_slot, 181 slot_type* old_slot, char) { 182 construct(alloc, new_slot, std::move(element(old_slot))); 183 destroy(alloc, old_slot); 184 } 185 }; 186 187 } // namespace container_internal 188 ABSL_NAMESPACE_END 189 } // namespace absl 190 191 #endif // ABSL_CONTAINER_INTERNAL_HASH_POLICY_TRAITS_H_ 192