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