Coverage Report

Created: 2024-09-23 06:29

/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_