text: // Copyright 2018 The Abseil Authors.
  //
  // Licensed under the Apache License, Version 2.0 (the "License");
  // you may not use this file except in compliance with the License.
  // You may obtain a copy of the License at
  //
  //      http://www.apache.org/licenses/LICENSE-2.0
  //
  // Unless required by applicable law or agreed to in writing, software
  // distributed under the License is distributed on an "AS IS" BASIS,
  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  // See the License for the specific language governing permissions and
  // limitations under the License.
  
  #ifndef ABSL_CONTAINER_INTERNAL_CONTAINER_MEMORY_H_
  #define ABSL_CONTAINER_INTERNAL_CONTAINER_MEMORY_H_
  
  #ifdef ADDRESS_SANITIZER
  #include <sanitizer/asan_interface.h>
  #endif
  
  #ifdef MEMORY_SANITIZER
  #include <sanitizer/msan_interface.h>
  #endif
  
  #include <cassert>
  #include <cstddef>
  #include <memory>
  #include <tuple>
  #include <type_traits>
  #include <utility>
  
  #include "absl/memory/memory.h"
  #include "absl/utility/utility.h"
  
  namespace absl {
  namespace container_internal {
  
  // Allocates at least n bytes aligned to the specified alignment.
  // Alignment must be a power of 2. It must be positive.
  //
  // Note that many allocators don't honor alignment requirements above certain
  // threshold (usually either alignof(std::max_align_t) or alignof(void*)).
  // Allocate() doesn't apply alignment corrections. If the underlying allocator
  // returns insufficiently alignment pointer, that's what you are going to get.
  template <size_t Alignment, class Alloc>
  void* Allocate(Alloc* alloc, size_t n) {
    static_assert(Alignment > 0, "");
    assert(n && "n must be positive");
    struct alignas(Alignment) M {};
    using A = typename absl::allocator_traits<Alloc>::template rebind_alloc<M>;
    using AT = typename absl::allocator_traits<Alloc>::template rebind_traits<M>;
    A mem_alloc(*alloc);
    void* p = AT::allocate(mem_alloc, (n + sizeof(M) - 1) / sizeof(M));
    assert(reinterpret_cast<uintptr_t>(p) % Alignment == 0 &&
           "allocator does not respect alignment");
    return p;
  }
  
  // The pointer must have been previously obtained by calling
  // Allocate<Alignment>(alloc, n).
  template <size_t Alignment, class Alloc>
  void Deallocate(Alloc* alloc, void* p, size_t n) {
    static_assert(Alignment > 0, "");
    assert(n && "n must be positive");
    struct alignas(Alignment) M {};
    using A = typename absl::allocator_traits<Alloc>::template rebind_alloc<M>;
    using AT = typename absl::allocator_traits<Alloc>::template rebind_traits<M>;
    A mem_alloc(*alloc);
    AT::deallocate(mem_alloc, static_cast<M*>(p),
                   (n + sizeof(M) - 1) / sizeof(M));
  }
  
  namespace memory_internal {
  
  // Constructs T into uninitialized storage pointed by `ptr` using the args
  // specified in the tuple.
  template <class Alloc, class T, class Tuple, size_t... I>
  void ConstructFromTupleImpl(Alloc* alloc, T* ptr, Tuple&& t,
                              absl::index_sequence<I...>) {
    absl::allocator_traits<Alloc>::construct(
        *alloc, ptr, std::get<I>(std::forward<Tuple>(t))...);
  }
  
  template <class T, class F>
  struct WithConstructedImplF {
    template <class... Args>
    decltype(std::declval<F>()(std::declval<T>())) operator()(
        Args&&... args) const {
      return std::forward<F>(f)(T(std::forward<Args>(args)...));
    }
    F&& f;
  };
  
  template <class T, class Tuple, size_t... Is, class F>
  decltype(std::declval<F>()(std::declval<T>())) WithConstructedImpl(
      Tuple&& t, absl::index_sequence<Is...>, F&& f) {
    return WithConstructedImplF<T, F>{std::forward<F>(f)}(
        std::get<Is>(std::forward<Tuple>(t))...);
  }
  
  template <class T, size_t... Is>
  auto TupleRefImpl(T&& t, absl::index_sequence<Is...>)
      -> decltype(std::forward_as_tuple(std::get<Is>(std::forward<T>(t))...)) {
    return std::forward_as_tuple(std::get<Is>(std::forward<T>(t))...);
  }
  
  // Returns a tuple of references to the elements of the input tuple. T must be a
  // tuple.
  template <class T>
  auto TupleRef(T&& t) -> decltype(
      TupleRefImpl(std::forward<T>(t),
                   absl::make_index_sequence<
                       std::tuple_size<typename std::decay<T>::type>::value>())) {
    return TupleRefImpl(
        std::forward<T>(t),
        absl::make_index_sequence<
            std::tuple_size<typename std::decay<T>::type>::value>());
  }
  
  template <class F, class K, class V>
  decltype(std::declval<F>()(std::declval<const K&>(), std::piecewise_construct,
                             std::declval<std::tuple<K>>(), std::declval<V>()))
  DecomposePairImpl(F&& f, std::pair<std::tuple<K>, V> p) {
    const auto& key = std::get<0>(p.first);
    return std::forward<F>(f)(key, std::piecewise_construct, std::move(p.first),
                              std::move(p.second));
  }
  
  }  // namespace memory_internal
  
  // Constructs T into uninitialized storage pointed by `ptr` using the args
  // specified in the tuple.
  template <class Alloc, class T, class Tuple>
  void ConstructFromTuple(Alloc* alloc, T* ptr, Tuple&& t) {
    memory_internal::ConstructFromTupleImpl(
        alloc, ptr, std::forward<Tuple>(t),
        absl::make_index_sequence<
            std::tuple_size<typename std::decay<Tuple>::type>::value>());
  }
  
  // Constructs T using the args specified in the tuple and calls F with the
  // constructed value.
  template <class T, class Tuple, class F>
  decltype(std::declval<F>()(std::declval<T>())) WithConstructed(
      Tuple&& t, F&& f) {
    return memory_internal::WithConstructedImpl<T>(
        std::forward<Tuple>(t),
        absl::make_index_sequence<
            std::tuple_size<typename std::decay<Tuple>::type>::value>(),
        std::forward<F>(f));
  }
  
  // Given arguments of an std::pair's consructor, PairArgs() returns a pair of
  // tuples with references to the passed arguments. The tuples contain
  // constructor arguments for the first and the second elements of the pair.
  //
  // The following two snippets are equivalent.
  //
  // 1. std::pair<F, S> p(args...);
  //
  // 2. auto a = PairArgs(args...);
  //    std::pair<F, S> p(std::piecewise_construct,
  //                      std::move(p.first), std::move(p.second));
  inline std::pair<std::tuple<>, std::tuple<>> PairArgs() { return {}; }
  template <class F, class S>
  std::pair<std::tuple<F&&>, std::tuple<S&&>> PairArgs(F&& f, S&& s) {
    return {std::piecewise_construct, std::forward_as_tuple(std::forward<F>(f)),
            std::forward_as_tuple(std::forward<S>(s))};
  }
  template <class F, class S>
  std::pair<std::tuple<const F&>, std::tuple<const S&>> PairArgs(
      const std::pair<F, S>& p) {
    return PairArgs(p.first, p.second);
  }
  template <class F, class S>
  std::pair<std::tuple<F&&>, std::tuple<S&&>> PairArgs(std::pair<F, S>&& p) {
    return PairArgs(std::forward<F>(p.first), std::forward<S>(p.second));
  }
  template <class F, class S>
  auto PairArgs(std::piecewise_construct_t, F&& f, S&& s)
      -> decltype(std::make_pair(memory_internal::TupleRef(std::forward<F>(f)),
                                 memory_internal::TupleRef(std::forward<S>(s)))) {
    return std::make_pair(memory_internal::TupleRef(std::forward<F>(f)),
                          memory_internal::TupleRef(std::forward<S>(s)));
  }
  
  // A helper function for implementing apply() in map policies.
  template <class F, class... Args>
  auto DecomposePair(F&& f, Args&&... args)
      -> decltype(memory_internal::DecomposePairImpl(
          std::forward<F>(f), PairArgs(std::forward<Args>(args)...))) {
    return memory_internal::DecomposePairImpl(
        std::forward<F>(f), PairArgs(std::forward<Args>(args)...));
  }
  
  // A helper function for implementing apply() in set policies.
  template <class F, class Arg>
  decltype(std::declval<F>()(std::declval<const Arg&>(), std::declval<Arg>()))
  DecomposeValue(F&& f, Arg&& arg) {
    const auto& key = arg;
    return std::forward<F>(f)(key, std::forward<Arg>(arg));
  }
  
  // Helper functions for asan and msan.
  inline void SanitizerPoisonMemoryRegion(const void* m, size_t s) {
  #ifdef ADDRESS_SANITIZER
    ASAN_POISON_MEMORY_REGION(m, s);
  #endif
  #ifdef MEMORY_SANITIZER
    __msan_poison(m, s);
  #endif
    (void)m;
    (void)s;
  }
  
  inline void SanitizerUnpoisonMemoryRegion(const void* m, size_t s) {
  #ifdef ADDRESS_SANITIZER
    ASAN_UNPOISON_MEMORY_REGION(m, s);
  #endif
  #ifdef MEMORY_SANITIZER
    __msan_unpoison(m, s);
  #endif
    (void)m;
    (void)s;
  }
  
  template <typename T>
  inline void SanitizerPoisonObject(const T* object) {
    SanitizerPoisonMemoryRegion(object, sizeof(T));
  }
  
  template <typename T>
  inline void SanitizerUnpoisonObject(const T* object) {
    SanitizerUnpoisonMemoryRegion(object, sizeof(T));
  }
  
  namespace memory_internal {
  
  // If Pair is a standard-layout type, OffsetOf<Pair>::kFirst and
  // OffsetOf<Pair>::kSecond are equivalent to offsetof(Pair, first) and
  // offsetof(Pair, second) respectively. Otherwise they are -1.
  //
  // The purpose of OffsetOf is to avoid calling offsetof() on non-standard-layout
  // type, which is non-portable.
  template <class Pair, class = std::true_type>
  struct OffsetOf {
    static constexpr size_t kFirst = -1;
    static constexpr size_t kSecond = -1;
  };
  
  template <class Pair>
  struct OffsetOf<Pair, typename std::is_standard_layout<Pair>::type> {
    static constexpr size_t kFirst = offsetof(Pair, first);
    static constexpr size_t kSecond = offsetof(Pair, second);
  };
  
  template <class K, class V>
  struct IsLayoutCompatible {
   private:
    struct Pair {
      K first;
      V second;
    };
  
    // Is P layout-compatible with Pair?
    template <class P>
    static constexpr bool LayoutCompatible() {
      return std::is_standard_layout<P>() && sizeof(P) == sizeof(Pair) &&
             alignof(P) == alignof(Pair) &&
             memory_internal::OffsetOf<P>::kFirst ==
                 memory_internal::OffsetOf<Pair>::kFirst &&
             memory_internal::OffsetOf<P>::kSecond ==
                 memory_internal::OffsetOf<Pair>::kSecond;
    }
  
   public:
    // Whether pair<const K, V> and pair<K, V> are layout-compatible. If they are,
    // then it is safe to store them in a union and read from either.
    static constexpr bool value = std::is_standard_layout<K>() &&
                                  std::is_standard_layout<Pair>() &&
                                  memory_internal::OffsetOf<Pair>::kFirst == 0 &&
                                  LayoutCompatible<std::pair<K, V>>() &&
                                  LayoutCompatible<std::pair<const K, V>>();
  };
  
  }  // namespace memory_internal
  
  // The internal storage type for key-value containers like flat_hash_map.
  //
  // It is convenient for the value_type of a flat_hash_map<K, V> to be
  // pair<const K, V>; the "const K" prevents accidental modification of the key
  // when dealing with the reference returned from find() and similar methods.
  // However, this creates other problems; we want to be able to emplace(K, V)
  // efficiently with move operations, and similarly be able to move a
  // pair<K, V> in insert().
  //
  // The solution is this union, which aliases the const and non-const versions
  // of the pair. This also allows flat_hash_map<const K, V> to work, even though
  // that has the same efficiency issues with move in emplace() and insert() -
  // but people do it anyway.
  //
  // If kMutableKeys is false, only the value member can be accessed.
  //
  // If kMutableKeys is true, key can be accessed through all slots while value
  // and mutable_value must be accessed only via INITIALIZED slots. Slots are
  // created and destroyed via mutable_value so that the key can be moved later.
  //
  // Accessing one of the union fields while the other is active is safe as
  // long as they are layout-compatible, which is guaranteed by the definition of
  // kMutableKeys. For C++11, the relevant section of the standard is
  // https://timsong-cpp.github.io/cppwp/n3337/class.mem#19 (9.2.19)
  template <class K, class V>
  union slot_type {
   private:
    static void emplace(slot_type* slot) {
      // The construction of union doesn't do anything at runtime but it allows us
      // to access its members without violating aliasing rules.
      new (slot) slot_type;
    }
    // If pair<const K, V> and pair<K, V> are layout-compatible, we can accept one
    // or the other via slot_type. We are also free to access the key via
    // slot_type::key in this case.
    using kMutableKeys =
        std::integral_constant<bool,
                               memory_internal::IsLayoutCompatible<K, V>::value>;
  
   public:
    slot_type() {}
    ~slot_type() = delete;
    using value_type = std::pair<const K, V>;
    using mutable_value_type = std::pair<K, V>;
  
    value_type value;
    mutable_value_type mutable_value;
    K key;
  
    template <class Allocator, class... Args>
    static void construct(Allocator* alloc, slot_type* slot, Args&&... args) {
      emplace(slot);
      if (kMutableKeys::value) {
        absl::allocator_traits<Allocator>::construct(*alloc, &slot->mutable_value,
                                                     std::forward<Args>(args)...);
      } else {
        absl::allocator_traits<Allocator>::construct(*alloc, &slot->value,
                                                     std::forward<Args>(args)...);
      }
    }
  
    // Construct this slot by moving from another slot.
    template <class Allocator>
    static void construct(Allocator* alloc, slot_type* slot, slot_type* other) {
      emplace(slot);
      if (kMutableKeys::value) {
        absl::allocator_traits<Allocator>::construct(
            *alloc, &slot->mutable_value, std::move(other->mutable_value));
      } else {
        absl::allocator_traits<Allocator>::construct(*alloc, &slot->value,
                                                     std::move(other->value));
      }
    }
  
    template <class Allocator>
    static void destroy(Allocator* alloc, slot_type* slot) {
      if (kMutableKeys::value) {
        absl::allocator_traits<Allocator>::destroy(*alloc, &slot->mutable_value);
      } else {
        absl::allocator_traits<Allocator>::destroy(*alloc, &slot->value);
      }
    }
  
    template <class Allocator>
    static void transfer(Allocator* alloc, slot_type* new_slot,
                         slot_type* old_slot) {
      emplace(new_slot);
      if (kMutableKeys::value) {
        absl::allocator_traits<Allocator>::construct(
            *alloc, &new_slot->mutable_value, std::move(old_slot->mutable_value));
      } else {
        absl::allocator_traits<Allocator>::construct(*alloc, &new_slot->value,
                                                     std::move(old_slot->value));
      }
      destroy(alloc, old_slot);
    }
  
    template <class Allocator>
    static void swap(Allocator* alloc, slot_type* a, slot_type* b) {
      if (kMutableKeys::value) {
        using std::swap;
        swap(a->mutable_value, b->mutable_value);
      } else {
        value_type tmp = std::move(a->value);
        absl::allocator_traits<Allocator>::destroy(*alloc, &a->value);
        absl::allocator_traits<Allocator>::construct(*alloc, &a->value,
                                                     std::move(b->value));
        absl::allocator_traits<Allocator>::destroy(*alloc, &b->value);
        absl::allocator_traits<Allocator>::construct(*alloc, &b->value,
                                                     std::move(tmp));
      }
    }
  
    template <class Allocator>
    static void move(Allocator* alloc, slot_type* src, slot_type* dest) {
      if (kMutableKeys::value) {
        dest->mutable_value = std::move(src->mutable_value);
      } else {
        absl::allocator_traits<Allocator>::destroy(*alloc, &dest->value);
        absl::allocator_traits<Allocator>::construct(*alloc, &dest->value,
                                                     std::move(src->value));
      }
    }
  
    template <class Allocator>
    static void move(Allocator* alloc, slot_type* first, slot_type* last,
                     slot_type* result) {
      for (slot_type *src = first, *dest = result; src != last; ++src, ++dest)
        move(alloc, src, dest);
    }
  };
  
  }  // namespace container_internal
  }  // namespace absl
  
  #endif  // ABSL_CONTAINER_INTERNAL_CONTAINER_MEMORY_H_
  