hash_policy_traits.h
Go to the documentation of this file.
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 namespace container_internal {
27 
28 // Defines how slots are initialized/destroyed/moved.
29 template <class Policy, class = void>
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.
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_
static std::function< Slot &(Slot *)> element
static size_t space_used(const slot_type *slot)
decltype(Policy::element(std::declval< slot_type * >())) reference
static auto key(slot_type *slot) -> decltype(P::apply(ReturnKey(), element(slot)))
static void transfer(Alloc *alloc, slot_type *new_slot, slot_type *old_slot)
Definition: algorithm.h:29
static auto transfer_impl(Alloc *alloc, slot_type *new_slot, slot_type *old_slot, int) -> decltype((void) P::transfer(alloc, new_slot, old_slot))
static std::function< void(void *, Slot *)> destroy
static void transfer_impl(Alloc *alloc, slot_type *new_slot, slot_type *old_slot, char)
size_t value
static auto value(T *elem) -> decltype(P::value(elem))
static std::function< void(void *, Slot *, Slot *)> transfer
static std::function< void(void *, Slot *, Slot)> construct
typename type_traits_internal::VoidTImpl< Ts... >::type void_t
Definition: type_traits.h:171
static auto apply(F &&f, Ts &&...ts) -> decltype(P::apply(std::forward< F >(f), std::forward< Ts >(ts)...))
static void construct(Alloc *alloc, slot_type *slot, Args &&...args)
typename std::remove_reference< reference >::type value_type
std::allocator< int > alloc
constexpr absl::remove_reference_t< T > && move(T &&t) noexcept
Definition: utility.h:219
MockFunction< int(int)> apply
static void destroy(Alloc *alloc, slot_type *slot)
typename std::remove_reference< reference >::type * pointer
static auto element(slot_type *slot) -> decltype(P::element(slot))


abseil_cpp
Author(s):
autogenerated on Wed Jun 19 2019 19:19:56