legacy-libs/grpc-cloned/deps/grpc/third_party/abseil-cpp/absl/container/internal/container_memory.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_CONTAINER_MEMORY_H_
  16 #define ABSL_CONTAINER_INTERNAL_CONTAINER_MEMORY_H_
  17
  18 #ifdef ADDRESS_SANITIZER
  19 #include <sanitizer/asan_interface.h>
  20 #endif
  21
  22 #ifdef MEMORY_SANITIZER
  23 #include <sanitizer/msan_interface.h>
  24 #endif
  25
  26 #include <cassert>
  27 #include <cstddef>
  28 #include <memory>
  29 #include <tuple>
  30 #include <type_traits>
  31 #include <utility>
  32
  33 #include "absl/memory/memory.h"
  34 #include "absl/utility/utility.h"
  35
  36 namespace absl {
  37 namespace container_internal {
  38
  39 // Allocates at least n bytes aligned to the specified alignment.
  40 // Alignment must be a power of 2. It must be positive.
  41 //
  42 // Note that many allocators don't honor alignment requirements above certain
  43 // threshold (usually either alignof(std::max_align_t) or alignof(void*)).
  44 // Allocate() doesn't apply alignment corrections. If the underlying allocator
  45 // returns insufficiently alignment pointer, that's what you are going to get.
  46 template <size_t Alignment, class Alloc>
  47 void* Allocate(Alloc* alloc, size_t n) {
  48   static_assert(Alignment > 0, "");
  49   assert(n && "n must be positive");
  50   struct alignas(Alignment) M {};
  51   using A = typename absl::allocator_traits<Alloc>::template rebind_alloc<M>;
  52   using AT = typename absl::allocator_traits<Alloc>::template rebind_traits<M>;
  53   A mem_alloc(*alloc);
  54   void* p = AT::allocate(mem_alloc, (n + sizeof(M) - 1) / sizeof(M));
  55   assert(reinterpret_cast<uintptr_t>(p) % Alignment == 0 &&
  56          "allocator does not respect alignment");
  57   return p;
  58 }
  59
  60 // The pointer must have been previously obtained by calling
  61 // Allocate<Alignment>(alloc, n).
  62 template <size_t Alignment, class Alloc>
  63 void Deallocate(Alloc* alloc, void* p, size_t n) {
  64   static_assert(Alignment > 0, "");
  65   assert(n && "n must be positive");
  66   struct alignas(Alignment) M {};
  67   using A = typename absl::allocator_traits<Alloc>::template rebind_alloc<M>;
  68   using AT = typename absl::allocator_traits<Alloc>::template rebind_traits<M>;
  69   A mem_alloc(*alloc);
  70   AT::deallocate(mem_alloc, static_cast<M*>(p),
  71                  (n + sizeof(M) - 1) / sizeof(M));
  72 }
  73
  74 namespace memory_internal {
  75
  76 // Constructs T into uninitialized storage pointed by `ptr` using the args
  77 // specified in the tuple.
  78 template <class Alloc, class T, class Tuple, size_t... I>
  79 void ConstructFromTupleImpl(Alloc* alloc, T* ptr, Tuple&& t,
  80                             absl::index_sequence<I...>) {
  81   absl::allocator_traits<Alloc>::construct(
  82       *alloc, ptr, std::get<I>(std::forward<Tuple>(t))...);
  83 }
  84
  85 template <class T, class F>
  86 struct WithConstructedImplF {
  87   template <class... Args>
  88   decltype(std::declval<F>()(std::declval<T>())) operator()(
  89       Args&&... args) const {
  90     return std::forward<F>(f)(T(std::forward<Args>(args)...));
  91   }
  92   F&& f;
  93 };
  94
  95 template <class T, class Tuple, size_t... Is, class F>
  96 decltype(std::declval<F>()(std::declval<T>())) WithConstructedImpl(
  97     Tuple&& t, absl::index_sequence<Is...>, F&& f) {
  98   return WithConstructedImplF<T, F>{std::forward<F>(f)}(
  99       std::get<Is>(std::forward<Tuple>(t))...);
 100 }
 101
 102 template <class T, size_t... Is>
 103 auto TupleRefImpl(T&& t, absl::index_sequence<Is...>)
 104     -> decltype(std::forward_as_tuple(std::get<Is>(std::forward<T>(t))...)) {
 105   return std::forward_as_tuple(std::get<Is>(std::forward<T>(t))...);
 106 }
 107
 108 // Returns a tuple of references to the elements of the input tuple. T must be a
 109 // tuple.
 110 template <class T>
 111 auto TupleRef(T&& t) -> decltype(
 112     TupleRefImpl(std::forward<T>(t),
 113                  absl::make_index_sequence<
 114                      std::tuple_size<typename std::decay<T>::type>::value>())) {
 115   return TupleRefImpl(
 116       std::forward<T>(t),
 117       absl::make_index_sequence<
 118           std::tuple_size<typename std::decay<T>::type>::value>());
 119 }
 120
 121 template <class F, class K, class V>
 122 decltype(std::declval<F>()(std::declval<const K&>(), std::piecewise_construct,
 123                            std::declval<std::tuple<K>>(), std::declval<V>()))
 124 DecomposePairImpl(F&& f, std::pair<std::tuple<K>, V> p) {
 125   const auto& key = std::get<0>(p.first);
 126   return std::forward<F>(f)(key, std::piecewise_construct, std::move(p.first),
 127                             std::move(p.second));
 128 }
 129
 130 }  // namespace memory_internal
 131
 132 // Constructs T into uninitialized storage pointed by `ptr` using the args
 133 // specified in the tuple.
 134 template <class Alloc, class T, class Tuple>
 135 void ConstructFromTuple(Alloc* alloc, T* ptr, Tuple&& t) {
 136   memory_internal::ConstructFromTupleImpl(
 137       alloc, ptr, std::forward<Tuple>(t),
 138       absl::make_index_sequence<
 139           std::tuple_size<typename std::decay<Tuple>::type>::value>());
 140 }
 141
 142 // Constructs T using the args specified in the tuple and calls F with the
 143 // constructed value.
 144 template <class T, class Tuple, class F>
 145 decltype(std::declval<F>()(std::declval<T>())) WithConstructed(
 146     Tuple&& t, F&& f) {
 147   return memory_internal::WithConstructedImpl<T>(
 148       std::forward<Tuple>(t),
 149       absl::make_index_sequence<
 150           std::tuple_size<typename std::decay<Tuple>::type>::value>(),
 151       std::forward<F>(f));
 152 }
 153
 154 // Given arguments of an std::pair's consructor, PairArgs() returns a pair of
 155 // tuples with references to the passed arguments. The tuples contain
 156 // constructor arguments for the first and the second elements of the pair.
 157 //
 158 // The following two snippets are equivalent.
 159 //
 160 // 1. std::pair<F, S> p(args...);
 161 //
 162 // 2. auto a = PairArgs(args...);
 163 //    std::pair<F, S> p(std::piecewise_construct,
 164 //                      std::move(p.first), std::move(p.second));
 165 inline std::pair<std::tuple<>, std::tuple<>> PairArgs() { return {}; }
 166 template <class F, class S>
 167 std::pair<std::tuple<F&&>, std::tuple<S&&>> PairArgs(F&& f, S&& s) {
 168   return {std::piecewise_construct, std::forward_as_tuple(std::forward<F>(f)),
 169           std::forward_as_tuple(std::forward<S>(s))};
 170 }
 171 template <class F, class S>
 172 std::pair<std::tuple<const F&>, std::tuple<const S&>> PairArgs(
 173     const std::pair<F, S>& p) {
 174   return PairArgs(p.first, p.second);
 175 }
 176 template <class F, class S>
 177 std::pair<std::tuple<F&&>, std::tuple<S&&>> PairArgs(std::pair<F, S>&& p) {
 178   return PairArgs(std::forward<F>(p.first), std::forward<S>(p.second));
 179 }
 180 template <class F, class S>
 181 auto PairArgs(std::piecewise_construct_t, F&& f, S&& s)
 182     -> decltype(std::make_pair(memory_internal::TupleRef(std::forward<F>(f)),
 183                                memory_internal::TupleRef(std::forward<S>(s)))) {
 184   return std::make_pair(memory_internal::TupleRef(std::forward<F>(f)),
 185                         memory_internal::TupleRef(std::forward<S>(s)));
 186 }
 187
 188 // A helper function for implementing apply() in map policies.
 189 template <class F, class... Args>
 190 auto DecomposePair(F&& f, Args&&... args)
 191     -> decltype(memory_internal::DecomposePairImpl(
 192         std::forward<F>(f), PairArgs(std::forward<Args>(args)...))) {
 193   return memory_internal::DecomposePairImpl(
 194       std::forward<F>(f), PairArgs(std::forward<Args>(args)...));
 195 }
 196
 197 // A helper function for implementing apply() in set policies.
 198 template <class F, class Arg>
 199 decltype(std::declval<F>()(std::declval<const Arg&>(), std::declval<Arg>()))
 200 DecomposeValue(F&& f, Arg&& arg) {
 201   const auto& key = arg;
 202   return std::forward<F>(f)(key, std::forward<Arg>(arg));
 203 }
 204
 205 // Helper functions for asan and msan.
 206 inline void SanitizerPoisonMemoryRegion(const void* m, size_t s) {
 207 #ifdef ADDRESS_SANITIZER
 208   ASAN_POISON_MEMORY_REGION(m, s);
 209 #endif
 210 #ifdef MEMORY_SANITIZER
 211   __msan_poison(m, s);
 212 #endif
 213   (void)m;
 214   (void)s;
 215 }
 216
 217 inline void SanitizerUnpoisonMemoryRegion(const void* m, size_t s) {
 218 #ifdef ADDRESS_SANITIZER
 219   ASAN_UNPOISON_MEMORY_REGION(m, s);
 220 #endif
 221 #ifdef MEMORY_SANITIZER
 222   __msan_unpoison(m, s);
 223 #endif
 224   (void)m;
 225   (void)s;
 226 }
 227
 228 template <typename T>
 229 inline void SanitizerPoisonObject(const T* object) {
 230   SanitizerPoisonMemoryRegion(object, sizeof(T));
 231 }
 232
 233 template <typename T>
 234 inline void SanitizerUnpoisonObject(const T* object) {
 235   SanitizerUnpoisonMemoryRegion(object, sizeof(T));
 236 }
 237
 238 namespace memory_internal {
 239
 240 // If Pair is a standard-layout type, OffsetOf<Pair>::kFirst and
 241 // OffsetOf<Pair>::kSecond are equivalent to offsetof(Pair, first) and
 242 // offsetof(Pair, second) respectively. Otherwise they are -1.
 243 //
 244 // The purpose of OffsetOf is to avoid calling offsetof() on non-standard-layout
 245 // type, which is non-portable.
 246 template <class Pair, class = std::true_type>
 247 struct OffsetOf {
 248   static constexpr size_t kFirst = -1;
 249   static constexpr size_t kSecond = -1;
 250 };
 251
 252 template <class Pair>
 253 struct OffsetOf<Pair, typename std::is_standard_layout<Pair>::type> {
 254   static constexpr size_t kFirst = offsetof(Pair, first);
 255   static constexpr size_t kSecond = offsetof(Pair, second);
 256 };
 257
 258 template <class K, class V>
 259 struct IsLayoutCompatible {
 260  private:
 261   struct Pair {
 262     K first;
 263     V second;
 264   };
 265
 266   // Is P layout-compatible with Pair?
 267   template <class P>
 268   static constexpr bool LayoutCompatible() {
 269     return std::is_standard_layout<P>() && sizeof(P) == sizeof(Pair) &&
 270            alignof(P) == alignof(Pair) &&
 271            memory_internal::OffsetOf<P>::kFirst ==
 272                memory_internal::OffsetOf<Pair>::kFirst &&
 273            memory_internal::OffsetOf<P>::kSecond ==
 274                memory_internal::OffsetOf<Pair>::kSecond;
 275   }
 276
 277  public:
 278   // Whether pair<const K, V> and pair<K, V> are layout-compatible. If they are,
 279   // then it is safe to store them in a union and read from either.
 280   static constexpr bool value = std::is_standard_layout<K>() &&
 281                                 std::is_standard_layout<Pair>() &&
 282                                 memory_internal::OffsetOf<Pair>::kFirst == 0 &&
 283                                 LayoutCompatible<std::pair<K, V>>() &&
 284                                 LayoutCompatible<std::pair<const K, V>>();
 285 };
 286
 287 }  // namespace memory_internal
 288
 289 // The internal storage type for key-value containers like flat_hash_map.
 290 //
 291 // It is convenient for the value_type of a flat_hash_map<K, V> to be
 292 // pair<const K, V>; the "const K" prevents accidental modification of the key
 293 // when dealing with the reference returned from find() and similar methods.
 294 // However, this creates other problems; we want to be able to emplace(K, V)
 295 // efficiently with move operations, and similarly be able to move a
 296 // pair<K, V> in insert().
 297 //
 298 // The solution is this union, which aliases the const and non-const versions
 299 // of the pair. This also allows flat_hash_map<const K, V> to work, even though
 300 // that has the same efficiency issues with move in emplace() and insert() -
 301 // but people do it anyway.
 302 //
 303 // If kMutableKeys is false, only the value member can be accessed.
 304 //
 305 // If kMutableKeys is true, key can be accessed through all slots while value
 306 // and mutable_value must be accessed only via INITIALIZED slots. Slots are
 307 // created and destroyed via mutable_value so that the key can be moved later.
 308 //
 309 // Accessing one of the union fields while the other is active is safe as
 310 // long as they are layout-compatible, which is guaranteed by the definition of
 311 // kMutableKeys. For C++11, the relevant section of the standard is
 312 // https://timsong-cpp.github.io/cppwp/n3337/class.mem#19 (9.2.19)
 313 template <class K, class V>
 314 union map_slot_type {
 315   map_slot_type() {}
 316   ~map_slot_type() = delete;
 317   using value_type = std::pair<const K, V>;
 318   using mutable_value_type = std::pair<K, V>;
 319
 320   value_type value;
 321   mutable_value_type mutable_value;
 322   K key;
 323 };
 324
 325 template <class K, class V>
 326 struct map_slot_policy {
 327   using slot_type = map_slot_type<K, V>;
 328   using value_type = std::pair<const K, V>;
 329   using mutable_value_type = std::pair<K, V>;
 330
 331  private:
 332   static void emplace(slot_type* slot) {
 333     // The construction of union doesn't do anything at runtime but it allows us
 334     // to access its members without violating aliasing rules.
 335     new (slot) slot_type;
 336   }
 337   // If pair<const K, V> and pair<K, V> are layout-compatible, we can accept one
 338   // or the other via slot_type. We are also free to access the key via
 339   // slot_type::key in this case.
 340   using kMutableKeys = memory_internal::IsLayoutCompatible<K, V>;
 341
 342  public:
 343   static value_type& element(slot_type* slot) { return slot->value; }
 344   static const value_type& element(const slot_type* slot) {
 345     return slot->value;
 346   }
 347
 348   static const K& key(const slot_type* slot) {
 349     return kMutableKeys::value ? slot->key : slot->value.first;
 350   }
 351
 352   template <class Allocator, class... Args>
 353   static void construct(Allocator* alloc, slot_type* slot, Args&&... args) {
 354     emplace(slot);
 355     if (kMutableKeys::value) {
 356       absl::allocator_traits<Allocator>::construct(*alloc, &slot->mutable_value,
 357                                                    std::forward<Args>(args)...);
 358     } else {
 359       absl::allocator_traits<Allocator>::construct(*alloc, &slot->value,
 360                                                    std::forward<Args>(args)...);
 361     }
 362   }
 363
 364   // Construct this slot by moving from another slot.
 365   template <class Allocator>
 366   static void construct(Allocator* alloc, slot_type* slot, slot_type* other) {
 367     emplace(slot);
 368     if (kMutableKeys::value) {
 369       absl::allocator_traits<Allocator>::construct(
 370           *alloc, &slot->mutable_value, std::move(other->mutable_value));
 371     } else {
 372       absl::allocator_traits<Allocator>::construct(*alloc, &slot->value,
 373                                                    std::move(other->value));
 374     }
 375   }
 376
 377   template <class Allocator>
 378   static void destroy(Allocator* alloc, slot_type* slot) {
 379     if (kMutableKeys::value) {
 380       absl::allocator_traits<Allocator>::destroy(*alloc, &slot->mutable_value);
 381     } else {
 382       absl::allocator_traits<Allocator>::destroy(*alloc, &slot->value);
 383     }
 384   }
 385
 386   template <class Allocator>
 387   static void transfer(Allocator* alloc, slot_type* new_slot,
 388                        slot_type* old_slot) {
 389     emplace(new_slot);
 390     if (kMutableKeys::value) {
 391       absl::allocator_traits<Allocator>::construct(
 392           *alloc, &new_slot->mutable_value, std::move(old_slot->mutable_value));
 393     } else {
 394       absl::allocator_traits<Allocator>::construct(*alloc, &new_slot->value,
 395                                                    std::move(old_slot->value));
 396     }
 397     destroy(alloc, old_slot);
 398   }
 399
 400   template <class Allocator>
 401   static void swap(Allocator* alloc, slot_type* a, slot_type* b) {
 402     if (kMutableKeys::value) {
 403       using std::swap;
 404       swap(a->mutable_value, b->mutable_value);
 405     } else {
 406       value_type tmp = std::move(a->value);
 407       absl::allocator_traits<Allocator>::destroy(*alloc, &a->value);
 408       absl::allocator_traits<Allocator>::construct(*alloc, &a->value,
 409                                                    std::move(b->value));
 410       absl::allocator_traits<Allocator>::destroy(*alloc, &b->value);
 411       absl::allocator_traits<Allocator>::construct(*alloc, &b->value,
 412                                                    std::move(tmp));
 413     }
 414   }
 415
 416   template <class Allocator>
 417   static void move(Allocator* alloc, slot_type* src, slot_type* dest) {
 418     if (kMutableKeys::value) {
 419       dest->mutable_value = std::move(src->mutable_value);
 420     } else {
 421       absl::allocator_traits<Allocator>::destroy(*alloc, &dest->value);
 422       absl::allocator_traits<Allocator>::construct(*alloc, &dest->value,
 423                                                    std::move(src->value));
 424     }
 425   }
 426
 427   template <class Allocator>
 428   static void move(Allocator* alloc, slot_type* first, slot_type* last,
 429                    slot_type* result) {
 430     for (slot_type *src = first, *dest = result; src != last; ++src, ++dest)
 431       move(alloc, src, dest);
 432   }
 433 };
 434
 435 }  // namespace container_internal
 436 }  // namespace absl
 437
 438 #endif  // ABSL_CONTAINER_INTERNAL_CONTAINER_MEMORY_H_