legacy-libs/grpc/deps/grpc/third_party/abseil-cpp/absl/container/internal/hash_policy_traits.h

   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>
  30 struct 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_