/src/abseil-cpp/absl/container/internal/hash_policy_traits.h
Line | Count | Source (jump to first uncovered line) |
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 | | // When C++17 is available, we can use std::launder to provide mutable |
40 | | // access to the key for use in node handle. |
41 | | #if defined(__cpp_lib_launder) && __cpp_lib_launder >= 201606 |
42 | | template <class Key, |
43 | | absl::enable_if_t<std::is_lvalue_reference<Key>::value, int> = 0> |
44 | | static key_type& Impl(Key&& k, int) { |
45 | | return *std::launder( |
46 | | const_cast<key_type*>(std::addressof(std::forward<Key>(k)))); |
47 | | } |
48 | | #endif |
49 | | |
50 | | template <class Key> |
51 | | static Key Impl(Key&& k, char) { |
52 | | return std::forward<Key>(k); |
53 | | } |
54 | | |
55 | | // When Key=T&, we forward the lvalue reference. |
56 | | // When Key=T, we return by value to avoid a dangling reference. |
57 | | // eg, for string_hash_map. |
58 | | template <class Key, class... Args> |
59 | | auto operator()(Key&& k, const Args&...) const |
60 | | -> decltype(Impl(std::forward<Key>(k), 0)) { |
61 | | return Impl(std::forward<Key>(k), 0); |
62 | | } |
63 | | }; |
64 | | |
65 | | template <class P = Policy, class = void> |
66 | | struct ConstantIteratorsImpl : std::false_type {}; |
67 | | |
68 | | template <class P> |
69 | | struct ConstantIteratorsImpl<P, absl::void_t<typename P::constant_iterators>> |
70 | | : P::constant_iterators {}; |
71 | | |
72 | | public: |
73 | | // The actual object stored in the hash table. |
74 | | using slot_type = typename Policy::slot_type; |
75 | | |
76 | | // The argument type for insertions into the hashtable. This is different |
77 | | // from value_type for increased performance. See initializer_list constructor |
78 | | // and insert() member functions for more details. |
79 | | using init_type = typename Policy::init_type; |
80 | | |
81 | | using reference = decltype(Policy::element(std::declval<slot_type*>())); |
82 | | using pointer = typename std::remove_reference<reference>::type*; |
83 | | using value_type = typename std::remove_reference<reference>::type; |
84 | | |
85 | | // Policies can set this variable to tell raw_hash_set that all iterators |
86 | | // should be constant, even `iterator`. This is useful for set-like |
87 | | // containers. |
88 | | // Defaults to false if not provided by the policy. |
89 | | using constant_iterators = ConstantIteratorsImpl<>; |
90 | | |
91 | | // Returns the amount of memory owned by `slot`, exclusive of `sizeof(*slot)`. |
92 | | // |
93 | | // If `slot` is nullptr, returns the constant amount of memory owned by any |
94 | | // full slot or -1 if slots own variable amounts of memory. |
95 | | // |
96 | | // PRECONDITION: `slot` is INITIALIZED or nullptr |
97 | | template <class P = Policy> |
98 | | static size_t space_used(const slot_type* slot) { |
99 | | return P::space_used(slot); |
100 | | } |
101 | | |
102 | | // Provides generalized access to the key for elements, both for elements in |
103 | | // the table and for elements that have not yet been inserted (or even |
104 | | // constructed). We would like an API that allows us to say: `key(args...)` |
105 | | // but we cannot do that for all cases, so we use this more general API that |
106 | | // can be used for many things, including the following: |
107 | | // |
108 | | // - Given an element in a table, get its key. |
109 | | // - Given an element initializer, get its key. |
110 | | // - Given `emplace()` arguments, get the element key. |
111 | | // |
112 | | // Implementations of this must adhere to a very strict technical |
113 | | // specification around aliasing and consuming arguments: |
114 | | // |
115 | | // Let `value_type` be the result type of `element()` without ref- and |
116 | | // cv-qualifiers. The first argument is a functor, the rest are constructor |
117 | | // arguments for `value_type`. Returns `std::forward<F>(f)(k, xs...)`, where |
118 | | // `k` is the element key, and `xs...` are the new constructor arguments for |
119 | | // `value_type`. It's allowed for `k` to alias `xs...`, and for both to alias |
120 | | // `ts...`. The key won't be touched once `xs...` are used to construct an |
121 | | // element; `ts...` won't be touched at all, which allows `apply()` to consume |
122 | | // any rvalues among them. |
123 | | // |
124 | | // If `value_type` is constructible from `Ts&&...`, `Policy::apply()` must not |
125 | | // trigger a hard compile error unless it originates from `f`. In other words, |
126 | | // `Policy::apply()` must be SFINAE-friendly. If `value_type` is not |
127 | | // constructible from `Ts&&...`, either SFINAE or a hard compile error is OK. |
128 | | // |
129 | | // If `Ts...` is `[cv] value_type[&]` or `[cv] init_type[&]`, |
130 | | // `Policy::apply()` must work. A compile error is not allowed, SFINAE or not. |
131 | | template <class F, class... Ts, class P = Policy> |
132 | | static auto apply(F&& f, Ts&&... ts) |
133 | 51 | -> decltype(P::apply(std::forward<F>(f), std::forward<Ts>(ts)...)) { |
134 | 51 | return P::apply(std::forward<F>(f), std::forward<Ts>(ts)...); |
135 | 51 | } _ZN4absl18container_internal18hash_policy_traitsINS0_17FlatHashMapPolicyINSt3__117basic_string_viewIcNS3_11char_traitsIcEEEEPNS_15CommandLineFlagEEEvE5applyINS0_12raw_hash_setISA_NS0_10StringHashENS0_8StringEqENS3_9allocatorINS3_4pairIKS7_S9_EEEEE12EqualElementIS7_EEJRSJ_ESA_EEDTclsrT1_5applyclsr3stdE7forwardIT_Efp_Espclsr3stdE7forwardIT0_Efp0_EEEOSQ_DpOSR_ Line | Count | Source | 133 | 19 | -> decltype(P::apply(std::forward<F>(f), std::forward<Ts>(ts)...)) { | 134 | 19 | return P::apply(std::forward<F>(f), std::forward<Ts>(ts)...); | 135 | 19 | } |
_ZN4absl18container_internal18hash_policy_traitsINS0_17FlatHashMapPolicyINSt3__117basic_string_viewIcNS3_11char_traitsIcEEEEPNS_15CommandLineFlagEEEvE5applyINS0_12raw_hash_setISA_NS0_10StringHashENS0_8StringEqENS3_9allocatorINS3_4pairIKS7_S9_EEEEE19EmplaceDecomposableEJSJ_ESA_EEDTclsrT1_5applyclsr3stdE7forwardIT_Efp_Espclsr3stdE7forwardIT0_Efp0_EEEOSO_DpOSP_ Line | Count | Source | 133 | 16 | -> decltype(P::apply(std::forward<F>(f), std::forward<Ts>(ts)...)) { | 134 | 16 | return P::apply(std::forward<F>(f), std::forward<Ts>(ts)...); | 135 | 16 | } |
Unexecuted instantiation: _ZN4absl18container_internal18hash_policy_traitsINS0_17FlatHashMapPolicyINSt3__117basic_string_viewIcNS3_11char_traitsIcEEEEPNS_15CommandLineFlagEEEvE5applyINS0_12raw_hash_setISA_NS0_10StringHashENS0_8StringEqENS3_9allocatorINS3_4pairIKS7_S9_EEEEE11HashElementEJRSJ_ESA_EEDTclsrT1_5applyclsr3stdE7forwardIT_Efp_Espclsr3stdE7forwardIT0_Efp0_EEEOSP_DpOSQ_ _ZN4absl18container_internal18hash_policy_traitsINS0_17FlatHashMapPolicyINSt3__117basic_string_viewIcNS3_11char_traitsIcEEEEPNS_15CommandLineFlagEEEvE5applyINS0_12raw_hash_setISA_NS0_10StringHashENS0_8StringEqENS3_9allocatorINS3_4pairIKS7_S9_EEEEE11FindElementEJRSJ_ESA_EEDTclsrT1_5applyclsr3stdE7forwardIT_Efp_Espclsr3stdE7forwardIT0_Efp0_EEEOSP_DpOSQ_ Line | Count | Source | 133 | 16 | -> decltype(P::apply(std::forward<F>(f), std::forward<Ts>(ts)...)) { | 134 | 16 | return P::apply(std::forward<F>(f), std::forward<Ts>(ts)...); | 135 | 16 | } |
Unexecuted instantiation: _ZN4absl18container_internal18hash_policy_traitsINS0_17FlatHashMapPolicyINSt3__117basic_string_viewIcNS3_11char_traitsIcEEEEPNS_15CommandLineFlagEEEvE5applyINS0_12raw_hash_setISA_NS0_10StringHashENS0_8StringEqENS3_9allocatorINS3_4pairIKS7_S9_EEEEE19EmplaceDecomposableEJNSH_IS7_S9_EEESA_EEDTclsrT1_5applyclsr3stdE7forwardIT_Efp_Espclsr3stdE7forwardIT0_Efp0_EEEOSP_DpOSQ_ Unexecuted instantiation: _ZN4absl18container_internal18hash_policy_traitsINS0_17FlatHashMapPolicyINSt3__117basic_string_viewIcNS3_11char_traitsIcEEEEPNS_15CommandLineFlagEEEvE5applyINS0_12raw_hash_setISA_NS0_10StringHashENS0_8StringEqENS3_9allocatorINS3_4pairIKS7_S9_EEEEE12EqualElementIS7_EEJRKSJ_ESA_EEDTclsrT1_5applyclsr3stdE7forwardIT_Efp_Espclsr3stdE7forwardIT0_Efp0_EEEOSR_DpOSS_ Unexecuted instantiation: _ZN4absl18container_internal18hash_policy_traitsINS0_17FlatHashMapPolicyINSt3__117basic_string_viewIcNS3_11char_traitsIcEEEEPNS_15CommandLineFlagEEEvE5applyINS0_12raw_hash_setISA_NS0_10StringHashENS0_8StringEqENS3_9allocatorINS3_4pairIKS7_S9_EEEEE11HashElementEJRKSJ_ESA_EEDTclsrT1_5applyclsr3stdE7forwardIT_Efp_Espclsr3stdE7forwardIT0_Efp0_EEEOSQ_DpOSR_ |
136 | | |
137 | | // Returns the "key" portion of the slot. |
138 | | // Used for node handle manipulation. |
139 | | template <class P = Policy> |
140 | | static auto mutable_key(slot_type* slot) |
141 | | -> decltype(P::apply(ReturnKey(), hash_policy_traits::element(slot))) { |
142 | | return P::apply(ReturnKey(), hash_policy_traits::element(slot)); |
143 | | } |
144 | | |
145 | | // Returns the "value" (as opposed to the "key") portion of the element. Used |
146 | | // by maps to implement `operator[]`, `at()` and `insert_or_assign()`. |
147 | | template <class T, class P = Policy> |
148 | | static auto value(T* elem) -> decltype(P::value(elem)) { |
149 | | return P::value(elem); |
150 | | } |
151 | | |
152 | | using HashSlotFn = size_t (*)(const void* hash_fn, void* slot); |
153 | | |
154 | | template <class Hash> |
155 | 0 | static constexpr HashSlotFn get_hash_slot_fn() { |
156 | 0 | // get_hash_slot_fn may return nullptr to signal that non type erased function |
157 | 0 | // should be used. GCC warns against comparing function address with nullptr. |
158 | 0 | #if defined(__GNUC__) && !defined(__clang__) |
159 | 0 | #pragma GCC diagnostic push |
160 | 0 | // silent error: the address of * will never be NULL [-Werror=address] |
161 | 0 | #pragma GCC diagnostic ignored "-Waddress" |
162 | 0 | #endif |
163 | 0 | return Policy::template get_hash_slot_fn<Hash>() == nullptr |
164 | 0 | ? &hash_slot_fn_non_type_erased<Hash> |
165 | 0 | : Policy::template get_hash_slot_fn<Hash>(); |
166 | 0 | #if defined(__GNUC__) && !defined(__clang__) |
167 | 0 | #pragma GCC diagnostic pop |
168 | 0 | #endif |
169 | 0 | } |
170 | | |
171 | | // Whether small object optimization is enabled. True by default. |
172 | 0 | static constexpr bool soo_enabled() { return soo_enabled_impl(Rank1{}); } |
173 | | |
174 | | private: |
175 | | template <class Hash> |
176 | | struct HashElement { |
177 | | template <class K, class... Args> |
178 | 0 | size_t operator()(const K& key, Args&&...) const { |
179 | 0 | return h(key); |
180 | 0 | } |
181 | | const Hash& h; |
182 | | }; |
183 | | |
184 | | template <class Hash> |
185 | 0 | static size_t hash_slot_fn_non_type_erased(const void* hash_fn, void* slot) { |
186 | 0 | return Policy::apply(HashElement<Hash>{*static_cast<const Hash*>(hash_fn)}, |
187 | 0 | Policy::element(static_cast<slot_type*>(slot))); |
188 | 0 | } |
189 | | |
190 | | // Use go/ranked-overloads for dispatching. Rank1 is preferred. |
191 | | struct Rank0 {}; |
192 | | struct Rank1 : Rank0 {}; |
193 | | |
194 | | // Use auto -> decltype as an enabler. |
195 | | template <class P = Policy> |
196 | | static constexpr auto soo_enabled_impl(Rank1) -> decltype(P::soo_enabled()) { |
197 | | return P::soo_enabled(); |
198 | | } |
199 | | |
200 | 0 | static constexpr bool soo_enabled_impl(Rank0) { return true; } |
201 | | }; |
202 | | |
203 | | } // namespace container_internal |
204 | | ABSL_NAMESPACE_END |
205 | | } // namespace absl |
206 | | |
207 | | #endif // ABSL_CONTAINER_INTERNAL_HASH_POLICY_TRAITS_H_ |