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