// 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 // // https://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_ #include <cassert> #include <cstddef> #include <cstdint> #include <cstring> #include <memory> #include <new> #include <tuple> #include <type_traits> #include <utility> #include "absl/base/config.h" #include "absl/memory/memory.h" #include "absl/meta/type_traits.h" #include "absl/utility/utility.h" #ifdef ABSL_HAVE_ADDRESS_SANITIZER #include <sanitizer/asan_interface.h> #endif #ifdef ABSL_HAVE_MEMORY_SANITIZER #include <sanitizer/msan_interface.h> #endif namespace absl { ABSL_NAMESPACE_BEGIN namespace container_internal { template <size_t Alignment> struct alignas(Alignment) AlignedType { … }; // 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) { … } // Returns true if the destruction of the value with given Allocator will be // trivial. template <class Allocator, class ValueType> constexpr auto IsDestructionTrivial() { … } // 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) { … } 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...>) { … } template <class T, class F> struct WithConstructedImplF { … }; 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) { … } 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))...)) { … } // 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>())) { … } 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) { … } } // 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) { … } // 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) { … } // Given arguments of an std::pair's constructor, 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(a.first), std::move(a.second)); inline std::pair<std::tuple<>, std::tuple<>> PairArgs() { … } template <class F, class S> std::pair<std::tuple<F&&>, std::tuple<S&&>> PairArgs(F&& f, S&& s) { … } template <class F, class S> std::pair<std::tuple<const F&>, std::tuple<const S&>> PairArgs( const std::pair<F, S>& p) { … } template <class F, class S> std::pair<std::tuple<F&&>, std::tuple<S&&>> PairArgs(std::pair<F, S>&& p) { … } 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)))) { … } // 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)...))) { … } // 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) { … } // Helper functions for asan and msan. inline void SanitizerPoisonMemoryRegion(const void* m, size_t s) { … } inline void SanitizerUnpoisonMemoryRegion(const void* m, size_t s) { … } template <typename T> inline void SanitizerPoisonObject(const T* object) { … } template <typename T> inline void SanitizerUnpoisonObject(const T* object) { … } 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 { … }; OffsetOf<Pair, typename std::is_standard_layout<Pair>::type>; template <class K, class V> struct IsLayoutCompatible { … }; } // 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 map_slot_type { … }; template <class K, class V> struct map_slot_policy { … }; // Type erased function for computing hash of the slot. HashSlotFn; // Type erased function to apply `Fn` to data inside of the `slot`. // The data is expected to have type `T`. template <class Fn, class T> size_t TypeErasedApplyToSlotFn(const void* fn, void* slot) { … } // Type erased function to apply `Fn` to data inside of the `*slot_ptr`. // The data is expected to have type `T`. template <class Fn, class T> size_t TypeErasedDerefAndApplyToSlotFn(const void* fn, void* slot_ptr) { … } } // namespace container_internal ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_CONTAINER_INTERNAL_CONTAINER_MEMORY_H_
Codebase Browser
chromium