diff options
| author | Tyge Løvset <[email protected]> | 2022-07-07 10:47:14 +0200 |
|---|---|---|
| committer | Tyge Løvset <[email protected]> | 2022-07-07 10:47:14 +0200 |
| commit | 9aafd5ce068da6f87c2f3ac8c9cf0721976f2bbc (patch) | |
| tree | b0a3a29177ac1d891c606aaee51fe438a917401b /benchmarks/external/parallel_hashmap/phmap_base.h | |
| parent | d108c705ae0b51874f1d18b8916466bdc5830415 (diff) | |
| download | STC-modified-9aafd5ce068da6f87c2f3ac8c9cf0721976f2bbc.tar.gz STC-modified-9aafd5ce068da6f87c2f3ac8c9cf0721976f2bbc.zip | |
Added emhash by ktprime to external benchmarks. Very fast iteration and lookups.
Diffstat (limited to 'benchmarks/external/parallel_hashmap/phmap_base.h')
| -rw-r--r-- | benchmarks/external/parallel_hashmap/phmap_base.h | 5171 |
1 files changed, 0 insertions, 5171 deletions
diff --git a/benchmarks/external/parallel_hashmap/phmap_base.h b/benchmarks/external/parallel_hashmap/phmap_base.h deleted file mode 100644 index d0c6f3ce..00000000 --- a/benchmarks/external/parallel_hashmap/phmap_base.h +++ /dev/null @@ -1,5171 +0,0 @@ -#if !defined(phmap_base_h_guard_) -#define phmap_base_h_guard_ - -// --------------------------------------------------------------------------- -// Copyright (c) 2019, Gregory Popovitch - [email protected] -// -// 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. -// -// Includes work from abseil-cpp (https://github.com/abseil/abseil-cpp) -// with modifications. -// -// 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. -// --------------------------------------------------------------------------- - -#include <algorithm> -#include <cassert> -#include <cstddef> -#include <initializer_list> -#include <iterator> -#include <string> -#include <type_traits> -#include <utility> -#include <functional> -#include <tuple> -#include <utility> -#include <memory> -#include <mutex> // for std::lock - -#include "phmap_config.h" - -#ifdef PHMAP_HAVE_SHARED_MUTEX - #include <shared_mutex> // after "phmap_config.h" -#endif - -#ifdef _MSC_VER - #pragma warning(push) - #pragma warning(disable : 4514) // unreferenced inline function has been removed - #pragma warning(disable : 4582) // constructor is not implicitly called - #pragma warning(disable : 4625) // copy constructor was implicitly defined as deleted - #pragma warning(disable : 4626) // assignment operator was implicitly defined as deleted - #pragma warning(disable : 4710) // function not inlined - #pragma warning(disable : 4711) // selected for automatic inline expansion - #pragma warning(disable : 4820) // '6' bytes padding added after data member -#endif // _MSC_VER - -namespace phmap { - -template <class T> using Allocator = typename std::allocator<T>; - -template<class T1, class T2> using Pair = typename std::pair<T1, T2>; - -template <class T> -struct EqualTo -{ - inline bool operator()(const T& a, const T& b) const - { - return std::equal_to<T>()(a, b); - } -}; - -template <class T> -struct Less -{ - inline bool operator()(const T& a, const T& b) const - { - return std::less<T>()(a, b); - } -}; - -namespace type_traits_internal { - -template <typename... Ts> -struct VoidTImpl { - using type = void; -}; - -// This trick to retrieve a default alignment is necessary for our -// implementation of aligned_storage_t to be consistent with any implementation -// of std::aligned_storage. -// --------------------------------------------------------------------------- -template <size_t Len, typename T = std::aligned_storage<Len>> -struct default_alignment_of_aligned_storage; - -template <size_t Len, size_t Align> -struct default_alignment_of_aligned_storage<Len, - std::aligned_storage<Len, Align>> { - static constexpr size_t value = Align; -}; - -// NOTE: The `is_detected` family of templates here differ from the library -// fundamentals specification in that for library fundamentals, `Op<Args...>` is -// evaluated as soon as the type `is_detected<Op, Args...>` undergoes -// substitution, regardless of whether or not the `::value` is accessed. That -// is inconsistent with all other standard traits and prevents lazy evaluation -// in larger contexts (such as if the `is_detected` check is a trailing argument -// of a `conjunction`. This implementation opts to instead be lazy in the same -// way that the standard traits are (this "defect" of the detection idiom -// specifications has been reported). -// --------------------------------------------------------------------------- - -template <class Enabler, template <class...> class Op, class... Args> -struct is_detected_impl { - using type = std::false_type; -}; - -template <template <class...> class Op, class... Args> -struct is_detected_impl<typename VoidTImpl<Op<Args...>>::type, Op, Args...> { - using type = std::true_type; -}; - -template <template <class...> class Op, class... Args> -struct is_detected : is_detected_impl<void, Op, Args...>::type {}; - -template <class Enabler, class To, template <class...> class Op, class... Args> -struct is_detected_convertible_impl { - using type = std::false_type; -}; - -template <class To, template <class...> class Op, class... Args> -struct is_detected_convertible_impl< - typename std::enable_if<std::is_convertible<Op<Args...>, To>::value>::type, - To, Op, Args...> { - using type = std::true_type; -}; - -template <class To, template <class...> class Op, class... Args> -struct is_detected_convertible - : is_detected_convertible_impl<void, To, Op, Args...>::type {}; - -template <typename T> -using IsCopyAssignableImpl = - decltype(std::declval<T&>() = std::declval<const T&>()); - -template <typename T> -using IsMoveAssignableImpl = decltype(std::declval<T&>() = std::declval<T&&>()); - -} // namespace type_traits_internal - -template <typename T> -struct is_copy_assignable : type_traits_internal::is_detected< - type_traits_internal::IsCopyAssignableImpl, T> { -}; - -template <typename T> -struct is_move_assignable : type_traits_internal::is_detected< - type_traits_internal::IsMoveAssignableImpl, T> { -}; - -// --------------------------------------------------------------------------- -// void_t() -// -// Ignores the type of any its arguments and returns `void`. In general, this -// metafunction allows you to create a general case that maps to `void` while -// allowing specializations that map to specific types. -// -// This metafunction is designed to be a drop-in replacement for the C++17 -// `std::void_t` metafunction. -// -// NOTE: `phmap::void_t` does not use the standard-specified implementation so -// that it can remain compatible with gcc < 5.1. This can introduce slightly -// different behavior, such as when ordering partial specializations. -// --------------------------------------------------------------------------- -template <typename... Ts> -using void_t = typename type_traits_internal::VoidTImpl<Ts...>::type; - -// --------------------------------------------------------------------------- -// conjunction -// -// Performs a compile-time logical AND operation on the passed types (which -// must have `::value` members convertible to `bool`. Short-circuits if it -// encounters any `false` members (and does not compare the `::value` members -// of any remaining arguments). -// -// This metafunction is designed to be a drop-in replacement for the C++17 -// `std::conjunction` metafunction. -// --------------------------------------------------------------------------- -template <typename... Ts> -struct conjunction; - -template <typename T, typename... Ts> -struct conjunction<T, Ts...> - : std::conditional<T::value, conjunction<Ts...>, T>::type {}; - -template <typename T> -struct conjunction<T> : T {}; - -template <> -struct conjunction<> : std::true_type {}; - -// --------------------------------------------------------------------------- -// disjunction -// -// Performs a compile-time logical OR operation on the passed types (which -// must have `::value` members convertible to `bool`. Short-circuits if it -// encounters any `true` members (and does not compare the `::value` members -// of any remaining arguments). -// -// This metafunction is designed to be a drop-in replacement for the C++17 -// `std::disjunction` metafunction. -// --------------------------------------------------------------------------- -template <typename... Ts> -struct disjunction; - -template <typename T, typename... Ts> -struct disjunction<T, Ts...> : - std::conditional<T::value, T, disjunction<Ts...>>::type {}; - -template <typename T> -struct disjunction<T> : T {}; - -template <> -struct disjunction<> : std::false_type {}; - -template <typename T> -struct negation : std::integral_constant<bool, !T::value> {}; - -template <typename T> -struct is_trivially_destructible - : std::integral_constant<bool, __has_trivial_destructor(T) && - std::is_destructible<T>::value> {}; - -template <typename T> -struct is_trivially_default_constructible - : std::integral_constant<bool, __has_trivial_constructor(T) && - std::is_default_constructible<T>::value && - is_trivially_destructible<T>::value> {}; - -template <typename T> -struct is_trivially_copy_constructible - : std::integral_constant<bool, __has_trivial_copy(T) && - std::is_copy_constructible<T>::value && - is_trivially_destructible<T>::value> {}; - -template <typename T> -struct is_trivially_copy_assignable - : std::integral_constant< - bool, __has_trivial_assign(typename std::remove_reference<T>::type) && - phmap::is_copy_assignable<T>::value> {}; - -// ----------------------------------------------------------------------------- -// C++14 "_t" trait aliases -// ----------------------------------------------------------------------------- - -template <typename T> -using remove_cv_t = typename std::remove_cv<T>::type; - -template <typename T> -using remove_const_t = typename std::remove_const<T>::type; - -template <typename T> -using remove_volatile_t = typename std::remove_volatile<T>::type; - -template <typename T> -using add_cv_t = typename std::add_cv<T>::type; - -template <typename T> -using add_const_t = typename std::add_const<T>::type; - -template <typename T> -using add_volatile_t = typename std::add_volatile<T>::type; - -template <typename T> -using remove_reference_t = typename std::remove_reference<T>::type; - -template <typename T> -using add_lvalue_reference_t = typename std::add_lvalue_reference<T>::type; - -template <typename T> -using add_rvalue_reference_t = typename std::add_rvalue_reference<T>::type; - -template <typename T> -using remove_pointer_t = typename std::remove_pointer<T>::type; - -template <typename T> -using add_pointer_t = typename std::add_pointer<T>::type; - -template <typename T> -using make_signed_t = typename std::make_signed<T>::type; - -template <typename T> -using make_unsigned_t = typename std::make_unsigned<T>::type; - -template <typename T> -using remove_extent_t = typename std::remove_extent<T>::type; - -template <typename T> -using remove_all_extents_t = typename std::remove_all_extents<T>::type; - -template <size_t Len, size_t Align = type_traits_internal:: - default_alignment_of_aligned_storage<Len>::value> -using aligned_storage_t = typename std::aligned_storage<Len, Align>::type; - -template <typename T> -using decay_t = typename std::decay<T>::type; - -template <bool B, typename T = void> -using enable_if_t = typename std::enable_if<B, T>::type; - -template <bool B, typename T, typename F> -using conditional_t = typename std::conditional<B, T, F>::type; - - -template <typename... T> -using common_type_t = typename std::common_type<T...>::type; - -template <typename T> -using underlying_type_t = typename std::underlying_type<T>::type; - -template< class F, class... ArgTypes> -#if PHMAP_HAVE_CC17 - using invoke_result = typename std::invoke_result<F, ArgTypes...>; -#else - using invoke_result = typename std::result_of<F(ArgTypes...)>::type; -#endif - -namespace type_traits_internal { - -// ---------------------------------------------------------------------- -// In MSVC we can't probe std::hash or stdext::hash because it triggers a -// static_assert instead of failing substitution. Libc++ prior to 4.0 -// also used a static_assert. -// ---------------------------------------------------------------------- -#if defined(_MSC_VER) || (defined(_LIBCPP_VERSION) && \ - _LIBCPP_VERSION < 4000 && _LIBCPP_STD_VER > 11) - #define PHMAP_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_ 0 -#else - #define PHMAP_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_ 1 -#endif - -#if !PHMAP_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_ - template <typename Key, typename = size_t> - struct IsHashable : std::true_type {}; -#else // PHMAP_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_ - template <typename Key, typename = void> - struct IsHashable : std::false_type {}; - - template <typename Key> - struct IsHashable<Key, - phmap::enable_if_t<std::is_convertible< - decltype(std::declval<std::hash<Key>&>()(std::declval<Key const&>())), - std::size_t>::value>> : std::true_type {}; -#endif - -struct AssertHashEnabledHelper -{ -private: - static void Sink(...) {} - struct NAT {}; - - template <class Key> - static auto GetReturnType(int) - -> decltype(std::declval<std::hash<Key>>()(std::declval<Key const&>())); - template <class Key> - static NAT GetReturnType(...); - - template <class Key> - static std::nullptr_t DoIt() { - static_assert(IsHashable<Key>::value, - "std::hash<Key> does not provide a call operator"); - static_assert( - std::is_default_constructible<std::hash<Key>>::value, - "std::hash<Key> must be default constructible when it is enabled"); - static_assert( - std::is_copy_constructible<std::hash<Key>>::value, - "std::hash<Key> must be copy constructible when it is enabled"); - static_assert(phmap::is_copy_assignable<std::hash<Key>>::value, - "std::hash<Key> must be copy assignable when it is enabled"); - // is_destructible is unchecked as it's implied by each of the - // is_constructible checks. - using ReturnType = decltype(GetReturnType<Key>(0)); - static_assert(std::is_same<ReturnType, NAT>::value || - std::is_same<ReturnType, size_t>::value, - "std::hash<Key> must return size_t"); - return nullptr; - } - - template <class... Ts> - friend void AssertHashEnabled(); -}; - -template <class... Ts> -inline void AssertHashEnabled -() -{ - using Helper = AssertHashEnabledHelper; - Helper::Sink(Helper::DoIt<Ts>()...); -} - -} // namespace type_traits_internal - -} // namespace phmap - - -// ----------------------------------------------------------------------------- -// hash_policy_traits -// ----------------------------------------------------------------------------- -namespace phmap { -namespace priv { - -// Defines how slots are initialized/destroyed/moved. -template <class Policy, class = void> -struct hash_policy_traits -{ -private: - struct ReturnKey - { - // We return `Key` here. - // When Key=T&, we forward the lvalue reference. - // When Key=T, we return by value to avoid a dangling reference. - // eg, for string_hash_map. - template <class Key, class... Args> - Key operator()(Key&& k, const Args&...) const { - return std::forward<Key>(k); - } - }; - - template <class P = Policy, class = void> - struct ConstantIteratorsImpl : std::false_type {}; - - template <class P> - struct ConstantIteratorsImpl<P, phmap::void_t<typename P::constant_iterators>> - : P::constant_iterators {}; - -public: - // The actual object stored in the hash table. - using slot_type = typename Policy::slot_type; - - // The type of the keys stored in the hashtable. - using key_type = typename Policy::key_type; - - // The argument type for insertions into the hashtable. This is different - // from value_type for increased performance. See initializer_list constructor - // and insert() member functions for more details. - using init_type = typename Policy::init_type; - - using reference = decltype(Policy::element(std::declval<slot_type*>())); - using pointer = typename std::remove_reference<reference>::type*; - using value_type = typename std::remove_reference<reference>::type; - - // Policies can set this variable to tell raw_hash_set that all iterators - // should be constant, even `iterator`. This is useful for set-like - // containers. - // Defaults to false if not provided by the policy. - using constant_iterators = ConstantIteratorsImpl<>; - - // PRECONDITION: `slot` is UNINITIALIZED - // POSTCONDITION: `slot` is INITIALIZED - template <class Alloc, class... Args> - static void construct(Alloc* alloc, slot_type* slot, Args&&... args) { - Policy::construct(alloc, slot, std::forward<Args>(args)...); - } - - // PRECONDITION: `slot` is INITIALIZED - // POSTCONDITION: `slot` is UNINITIALIZED - template <class Alloc> - static void destroy(Alloc* alloc, slot_type* slot) { - Policy::destroy(alloc, slot); - } - - // Transfers the `old_slot` to `new_slot`. Any memory allocated by the - // allocator inside `old_slot` to `new_slot` can be transferred. - // - // OPTIONAL: defaults to: - // - // clone(new_slot, std::move(*old_slot)); - // destroy(old_slot); - // - // PRECONDITION: `new_slot` is UNINITIALIZED and `old_slot` is INITIALIZED - // POSTCONDITION: `new_slot` is INITIALIZED and `old_slot` is - // UNINITIALIZED - template <class Alloc> - static void transfer(Alloc* alloc, slot_type* new_slot, slot_type* old_slot) { - transfer_impl(alloc, new_slot, old_slot, 0); - } - - // PRECONDITION: `slot` is INITIALIZED - // POSTCONDITION: `slot` is INITIALIZED - template <class P = Policy> - static auto element(slot_type* slot) -> decltype(P::element(slot)) { - return P::element(slot); - } - - // Returns the amount of memory owned by `slot`, exclusive of `sizeof(*slot)`. - // - // If `slot` is nullptr, returns the constant amount of memory owned by any - // full slot or -1 if slots own variable amounts of memory. - // - // PRECONDITION: `slot` is INITIALIZED or nullptr - template <class P = Policy> - static size_t space_used(const slot_type* slot) { - return P::space_used(slot); - } - - // Provides generalized access to the key for elements, both for elements in - // the table and for elements that have not yet been inserted (or even - // constructed). We would like an API that allows us to say: `key(args...)` - // but we cannot do that for all cases, so we use this more general API that - // can be used for many things, including the following: - // - // - Given an element in a table, get its key. - // - Given an element initializer, get its key. - // - Given `emplace()` arguments, get the element key. - // - // Implementations of this must adhere to a very strict technical - // specification around aliasing and consuming arguments: - // - // Let `value_type` be the result type of `element()` without ref- and - // cv-qualifiers. The first argument is a functor, the rest are constructor - // arguments for `value_type`. Returns `std::forward<F>(f)(k, xs...)`, where - // `k` is the element key, and `xs...` are the new constructor arguments for - // `value_type`. It's allowed for `k` to alias `xs...`, and for both to alias - // `ts...`. The key won't be touched once `xs...` are used to construct an - // element; `ts...` won't be touched at all, which allows `apply()` to consume - // any rvalues among them. - // - // If `value_type` is constructible from `Ts&&...`, `Policy::apply()` must not - // trigger a hard compile error unless it originates from `f`. In other words, - // `Policy::apply()` must be SFINAE-friendly. If `value_type` is not - // constructible from `Ts&&...`, either SFINAE or a hard compile error is OK. - // - // If `Ts...` is `[cv] value_type[&]` or `[cv] init_type[&]`, - // `Policy::apply()` must work. A compile error is not allowed, SFINAE or not. - template <class F, class... Ts, class P = Policy> - static auto apply(F&& f, Ts&&... ts) - -> decltype(P::apply(std::forward<F>(f), std::forward<Ts>(ts)...)) { - return P::apply(std::forward<F>(f), std::forward<Ts>(ts)...); - } - - // Returns the "key" portion of the slot. - // Used for node handle manipulation. - template <class P = Policy> - static auto key(slot_type* slot) - -> decltype(P::apply(ReturnKey(), element(slot))) { - return P::apply(ReturnKey(), element(slot)); - } - - // Returns the "value" (as opposed to the "key") portion of the element. Used - // by maps to implement `operator[]`, `at()` and `insert_or_assign()`. - template <class T, class P = Policy> - static auto value(T* elem) -> decltype(P::value(elem)) { - return P::value(elem); - } - -private: - - // Use auto -> decltype as an enabler. - template <class Alloc, class P = Policy> - static auto transfer_impl(Alloc* alloc, slot_type* new_slot, - slot_type* old_slot, int) - -> decltype((void)P::transfer(alloc, new_slot, old_slot)) { - P::transfer(alloc, new_slot, old_slot); - } - - template <class Alloc> - static void transfer_impl(Alloc* alloc, slot_type* new_slot, - slot_type* old_slot, char) { - construct(alloc, new_slot, std::move(element(old_slot))); - destroy(alloc, old_slot); - } -}; - -} // namespace priv -} // namespace phmap - -// ----------------------------------------------------------------------------- -// file utility.h -// ----------------------------------------------------------------------------- - -// --------- identity.h -namespace phmap { -namespace internal { - -template <typename T> -struct identity { - typedef T type; -}; - -template <typename T> -using identity_t = typename identity<T>::type; - -} // namespace internal -} // namespace phmap - - -// --------- inline_variable.h - -#ifdef __cpp_inline_variables - -#if defined(__clang__) - #define PHMAP_INTERNAL_EXTERN_DECL(type, name) \ - extern const ::phmap::internal::identity_t<type> name; -#else // Otherwise, just define the macro to do nothing. - #define PHMAP_INTERNAL_EXTERN_DECL(type, name) -#endif // defined(__clang__) - -// See above comment at top of file for details. -#define PHMAP_INTERNAL_INLINE_CONSTEXPR(type, name, init) \ - PHMAP_INTERNAL_EXTERN_DECL(type, name) \ - inline constexpr ::phmap::internal::identity_t<type> name = init - -#else - -// See above comment at top of file for details. -// -// Note: -// identity_t is used here so that the const and name are in the -// appropriate place for pointer types, reference types, function pointer -// types, etc.. -#define PHMAP_INTERNAL_INLINE_CONSTEXPR(var_type, name, init) \ - template <class /*PhmapInternalDummy*/ = void> \ - struct PhmapInternalInlineVariableHolder##name { \ - static constexpr ::phmap::internal::identity_t<var_type> kInstance = init; \ - }; \ - \ - template <class PhmapInternalDummy> \ - constexpr ::phmap::internal::identity_t<var_type> \ - PhmapInternalInlineVariableHolder##name<PhmapInternalDummy>::kInstance; \ - \ - static constexpr const ::phmap::internal::identity_t<var_type>& \ - name = /* NOLINT */ \ - PhmapInternalInlineVariableHolder##name<>::kInstance; \ - static_assert(sizeof(void (*)(decltype(name))) != 0, \ - "Silence unused variable warnings.") - -#endif // __cpp_inline_variables - -// ----------- throw_delegate - -namespace phmap { -namespace base_internal { - -namespace { -template <typename T> -#ifdef PHMAP_HAVE_EXCEPTIONS -[[noreturn]] void Throw(const T& error) { - throw error; -} -#else -[[noreturn]] void Throw(const T&) { - std::abort(); -} -#endif -} // namespace - -static inline void ThrowStdLogicError(const std::string& what_arg) { - Throw(std::logic_error(what_arg)); -} -static inline void ThrowStdLogicError(const char* what_arg) { - Throw(std::logic_error(what_arg)); -} -static inline void ThrowStdInvalidArgument(const std::string& what_arg) { - Throw(std::invalid_argument(what_arg)); -} -static inline void ThrowStdInvalidArgument(const char* what_arg) { - Throw(std::invalid_argument(what_arg)); -} - -static inline void ThrowStdDomainError(const std::string& what_arg) { - Throw(std::domain_error(what_arg)); -} -static inline void ThrowStdDomainError(const char* what_arg) { - Throw(std::domain_error(what_arg)); -} - -static inline void ThrowStdLengthError(const std::string& what_arg) { - Throw(std::length_error(what_arg)); -} -static inline void ThrowStdLengthError(const char* what_arg) { - Throw(std::length_error(what_arg)); -} - -static inline void ThrowStdOutOfRange(const std::string& what_arg) { - Throw(std::out_of_range(what_arg)); -} -static inline void ThrowStdOutOfRange(const char* what_arg) { - Throw(std::out_of_range(what_arg)); -} - -static inline void ThrowStdRuntimeError(const std::string& what_arg) { - Throw(std::runtime_error(what_arg)); -} -static inline void ThrowStdRuntimeError(const char* what_arg) { - Throw(std::runtime_error(what_arg)); -} - -static inline void ThrowStdRangeError(const std::string& what_arg) { - Throw(std::range_error(what_arg)); -} -static inline void ThrowStdRangeError(const char* what_arg) { - Throw(std::range_error(what_arg)); -} - -static inline void ThrowStdOverflowError(const std::string& what_arg) { - Throw(std::overflow_error(what_arg)); -} -static inline void ThrowStdOverflowError(const char* what_arg) { - Throw(std::overflow_error(what_arg)); -} - -static inline void ThrowStdUnderflowError(const std::string& what_arg) { - Throw(std::underflow_error(what_arg)); -} -static inline void ThrowStdUnderflowError(const char* what_arg) { - Throw(std::underflow_error(what_arg)); -} - -static inline void ThrowStdBadFunctionCall() { Throw(std::bad_function_call()); } - -static inline void ThrowStdBadAlloc() { Throw(std::bad_alloc()); } - -} // namespace base_internal -} // namespace phmap - -// ----------- invoke.h - -namespace phmap { -namespace base_internal { - -template <typename Derived> -struct StrippedAccept -{ - template <typename... Args> - struct Accept : Derived::template AcceptImpl<typename std::remove_cv< - typename std::remove_reference<Args>::type>::type...> {}; -}; - -// (t1.*f)(t2, ..., tN) when f is a pointer to a member function of a class T -// and t1 is an object of type T or a reference to an object of type T or a -// reference to an object of a type derived from T. -struct MemFunAndRef : StrippedAccept<MemFunAndRef> -{ - template <typename... Args> - struct AcceptImpl : std::false_type {}; - - template <typename R, typename C, typename... Params, typename Obj, - typename... Args> - struct AcceptImpl<R (C::*)(Params...), Obj, Args...> - : std::is_base_of<C, Obj> {}; - - template <typename R, typename C, typename... Params, typename Obj, - typename... Args> - struct AcceptImpl<R (C::*)(Params...) const, Obj, Args...> - : std::is_base_of<C, Obj> {}; - - template <typename MemFun, typename Obj, typename... Args> - static decltype((std::declval<Obj>().* - std::declval<MemFun>())(std::declval<Args>()...)) - Invoke(MemFun&& mem_fun, Obj&& obj, Args&&... args) { - return (std::forward<Obj>(obj).* - std::forward<MemFun>(mem_fun))(std::forward<Args>(args)...); - } -}; - -// ((*t1).*f)(t2, ..., tN) when f is a pointer to a member function of a -// class T and t1 is not one of the types described in the previous item. -struct MemFunAndPtr : StrippedAccept<MemFunAndPtr> -{ - template <typename... Args> - struct AcceptImpl : std::false_type {}; - - template <typename R, typename C, typename... Params, typename Ptr, - typename... Args> - struct AcceptImpl<R (C::*)(Params...), Ptr, Args...> - : std::integral_constant<bool, !std::is_base_of<C, Ptr>::value> {}; - - template <typename R, typename C, typename... Params, typename Ptr, - typename... Args> - struct AcceptImpl<R (C::*)(Params...) const, Ptr, Args...> - : std::integral_constant<bool, !std::is_base_of<C, Ptr>::value> {}; - - template <typename MemFun, typename Ptr, typename... Args> - static decltype(((*std::declval<Ptr>()).* - std::declval<MemFun>())(std::declval<Args>()...)) - Invoke(MemFun&& mem_fun, Ptr&& ptr, Args&&... args) { - return ((*std::forward<Ptr>(ptr)).* - std::forward<MemFun>(mem_fun))(std::forward<Args>(args)...); - } -}; - -// t1.*f when N == 1 and f is a pointer to member data of a class T and t1 is -// an object of type T or a reference to an object of type T or a reference -// to an object of a type derived from T. -struct DataMemAndRef : StrippedAccept<DataMemAndRef> -{ - template <typename... Args> - struct AcceptImpl : std::false_type {}; - - template <typename R, typename C, typename Obj> - struct AcceptImpl<R C::*, Obj> : std::is_base_of<C, Obj> {}; - - template <typename DataMem, typename Ref> - static decltype(std::declval<Ref>().*std::declval<DataMem>()) Invoke( - DataMem&& data_mem, Ref&& ref) { - return std::forward<Ref>(ref).*std::forward<DataMem>(data_mem); - } -}; - -// (*t1).*f when N == 1 and f is a pointer to member data of a class T and t1 -// is not one of the types described in the previous item. -struct DataMemAndPtr : StrippedAccept<DataMemAndPtr> -{ - template <typename... Args> - struct AcceptImpl : std::false_type {}; - - template <typename R, typename C, typename Ptr> - struct AcceptImpl<R C::*, Ptr> - : std::integral_constant<bool, !std::is_base_of<C, Ptr>::value> {}; - - template <typename DataMem, typename Ptr> - static decltype((*std::declval<Ptr>()).*std::declval<DataMem>()) Invoke( - DataMem&& data_mem, Ptr&& ptr) { - return (*std::forward<Ptr>(ptr)).*std::forward<DataMem>(data_mem); - } -}; - -// f(t1, t2, ..., tN) in all other cases. -struct Callable -{ - // Callable doesn't have Accept because it's the last clause that gets picked - // when none of the previous clauses are applicable. - template <typename F, typename... Args> - static decltype(std::declval<F>()(std::declval<Args>()...)) Invoke( - F&& f, Args&&... args) { - return std::forward<F>(f)(std::forward<Args>(args)...); - } -}; - -// Resolves to the first matching clause. -template <typename... Args> -struct Invoker -{ - typedef typename std::conditional< - MemFunAndRef::Accept<Args...>::value, MemFunAndRef, - typename std::conditional< - MemFunAndPtr::Accept<Args...>::value, MemFunAndPtr, - typename std::conditional< - DataMemAndRef::Accept<Args...>::value, DataMemAndRef, - typename std::conditional<DataMemAndPtr::Accept<Args...>::value, - DataMemAndPtr, Callable>::type>::type>:: - type>::type type; -}; - -// The result type of Invoke<F, Args...>. -template <typename F, typename... Args> -using InvokeT = decltype(Invoker<F, Args...>::type::Invoke( - std::declval<F>(), std::declval<Args>()...)); - -// Invoke(f, args...) is an implementation of INVOKE(f, args...) from section -// [func.require] of the C++ standard. -template <typename F, typename... Args> -InvokeT<F, Args...> Invoke(F&& f, Args&&... args) { - return Invoker<F, Args...>::type::Invoke(std::forward<F>(f), - std::forward<Args>(args)...); -} -} // namespace base_internal -} // namespace phmap - - -// ----------- utility.h - -namespace phmap { - -// integer_sequence -// -// Class template representing a compile-time integer sequence. An instantiation -// of `integer_sequence<T, Ints...>` has a sequence of integers encoded in its -// type through its template arguments (which is a common need when -// working with C++11 variadic templates). `phmap::integer_sequence` is designed -// to be a drop-in replacement for C++14's `std::integer_sequence`. -// -// Example: -// -// template< class T, T... Ints > -// void user_function(integer_sequence<T, Ints...>); -// -// int main() -// { -// // user_function's `T` will be deduced to `int` and `Ints...` -// // will be deduced to `0, 1, 2, 3, 4`. -// user_function(make_integer_sequence<int, 5>()); -// } -template <typename T, T... Ints> -struct integer_sequence -{ - using value_type = T; - static constexpr size_t size() noexcept { return sizeof...(Ints); } -}; - -// index_sequence -// -// A helper template for an `integer_sequence` of `size_t`, -// `phmap::index_sequence` is designed to be a drop-in replacement for C++14's -// `std::index_sequence`. -template <size_t... Ints> -using index_sequence = integer_sequence<size_t, Ints...>; - -namespace utility_internal { - -template <typename Seq, size_t SeqSize, size_t Rem> -struct Extend; - -// Note that SeqSize == sizeof...(Ints). It's passed explicitly for efficiency. -template <typename T, T... Ints, size_t SeqSize> -struct Extend<integer_sequence<T, Ints...>, SeqSize, 0> { - using type = integer_sequence<T, Ints..., (Ints + SeqSize)...>; -}; - -template <typename T, T... Ints, size_t SeqSize> -struct Extend<integer_sequence<T, Ints...>, SeqSize, 1> { - using type = integer_sequence<T, Ints..., (Ints + SeqSize)..., 2 * SeqSize>; -}; - -// Recursion helper for 'make_integer_sequence<T, N>'. -// 'Gen<T, N>::type' is an alias for 'integer_sequence<T, 0, 1, ... N-1>'. -template <typename T, size_t N> -struct Gen { - using type = - typename Extend<typename Gen<T, N / 2>::type, N / 2, N % 2>::type; -}; - -template <typename T> -struct Gen<T, 0> { - using type = integer_sequence<T>; -}; - -} // namespace utility_internal - -// Compile-time sequences of integers - -// make_integer_sequence -// -// This template alias is equivalent to -// `integer_sequence<int, 0, 1, ..., N-1>`, and is designed to be a drop-in -// replacement for C++14's `std::make_integer_sequence`. -template <typename T, T N> -using make_integer_sequence = typename utility_internal::Gen<T, N>::type; - -// make_index_sequence -// -// This template alias is equivalent to `index_sequence<0, 1, ..., N-1>`, -// and is designed to be a drop-in replacement for C++14's -// `std::make_index_sequence`. -template <size_t N> -using make_index_sequence = make_integer_sequence<size_t, N>; - -// index_sequence_for -// -// Converts a typename pack into an index sequence of the same length, and -// is designed to be a drop-in replacement for C++14's -// `std::index_sequence_for()` -template <typename... Ts> -using index_sequence_for = make_index_sequence<sizeof...(Ts)>; - -// Tag types - -#ifdef PHMAP_HAVE_STD_OPTIONAL - -using std::in_place_t; -using std::in_place; - -#else // PHMAP_HAVE_STD_OPTIONAL - -// in_place_t -// -// Tag type used to specify in-place construction, such as with -// `phmap::optional`, designed to be a drop-in replacement for C++17's -// `std::in_place_t`. -struct in_place_t {}; - -PHMAP_INTERNAL_INLINE_CONSTEXPR(in_place_t, in_place, {}); - -#endif // PHMAP_HAVE_STD_OPTIONAL - -#if defined(PHMAP_HAVE_STD_ANY) || defined(PHMAP_HAVE_STD_VARIANT) -using std::in_place_type_t; -#else - -// in_place_type_t -// -// Tag type used for in-place construction when the type to construct needs to -// be specified, such as with `phmap::any`, designed to be a drop-in replacement -// for C++17's `std::in_place_type_t`. -template <typename T> -struct in_place_type_t {}; -#endif // PHMAP_HAVE_STD_ANY || PHMAP_HAVE_STD_VARIANT - -#ifdef PHMAP_HAVE_STD_VARIANT -using std::in_place_index_t; -#else - -// in_place_index_t -// -// Tag type used for in-place construction when the type to construct needs to -// be specified, such as with `phmap::any`, designed to be a drop-in replacement -// for C++17's `std::in_place_index_t`. -template <size_t I> -struct in_place_index_t {}; -#endif // PHMAP_HAVE_STD_VARIANT - -// Constexpr move and forward - -// move() -// -// A constexpr version of `std::move()`, designed to be a drop-in replacement -// for C++14's `std::move()`. -template <typename T> -constexpr phmap::remove_reference_t<T>&& move(T&& t) noexcept { - return static_cast<phmap::remove_reference_t<T>&&>(t); -} - -// forward() -// -// A constexpr version of `std::forward()`, designed to be a drop-in replacement -// for C++14's `std::forward()`. -template <typename T> -constexpr T&& forward( - phmap::remove_reference_t<T>& t) noexcept { // NOLINT(runtime/references) - return static_cast<T&&>(t); -} - -namespace utility_internal { -// Helper method for expanding tuple into a called method. -template <typename Functor, typename Tuple, std::size_t... Indexes> -auto apply_helper(Functor&& functor, Tuple&& t, index_sequence<Indexes...>) - -> decltype(phmap::base_internal::Invoke( - phmap::forward<Functor>(functor), - std::get<Indexes>(phmap::forward<Tuple>(t))...)) { - return phmap::base_internal::Invoke( - phmap::forward<Functor>(functor), - std::get<Indexes>(phmap::forward<Tuple>(t))...); -} - -} // namespace utility_internal - -// apply -// -// Invokes a Callable using elements of a tuple as its arguments. -// Each element of the tuple corresponds to an argument of the call (in order). -// Both the Callable argument and the tuple argument are perfect-forwarded. -// For member-function Callables, the first tuple element acts as the `this` -// pointer. `phmap::apply` is designed to be a drop-in replacement for C++17's -// `std::apply`. Unlike C++17's `std::apply`, this is not currently `constexpr`. -// -// Example: -// -// class Foo { -// public: -// void Bar(int); -// }; -// void user_function1(int, std::string); -// void user_function2(std::unique_ptr<Foo>); -// auto user_lambda = [](int, int) {}; -// -// int main() -// { -// std::tuple<int, std::string> tuple1(42, "bar"); -// // Invokes the first user function on int, std::string. -// phmap::apply(&user_function1, tuple1); -// -// std::tuple<std::unique_ptr<Foo>> tuple2(phmap::make_unique<Foo>()); -// // Invokes the user function that takes ownership of the unique -// // pointer. -// phmap::apply(&user_function2, std::move(tuple2)); -// -// auto foo = phmap::make_unique<Foo>(); -// std::tuple<Foo*, int> tuple3(foo.get(), 42); -// // Invokes the method Bar on foo with one argument, 42. -// phmap::apply(&Foo::Bar, tuple3); -// -// std::tuple<int, int> tuple4(8, 9); -// // Invokes a lambda. -// phmap::apply(user_lambda, tuple4); -// } -template <typename Functor, typename Tuple> -auto apply(Functor&& functor, Tuple&& t) - -> decltype(utility_internal::apply_helper( - phmap::forward<Functor>(functor), phmap::forward<Tuple>(t), - phmap::make_index_sequence<std::tuple_size< - typename std::remove_reference<Tuple>::type>::value>{})) { - return utility_internal::apply_helper( - phmap::forward<Functor>(functor), phmap::forward<Tuple>(t), - phmap::make_index_sequence<std::tuple_size< - typename std::remove_reference<Tuple>::type>::value>{}); -} - -#ifdef _MSC_VER - #pragma warning(push) - #pragma warning(disable : 4365) // '=': conversion from 'T' to 'T', signed/unsigned mismatch -#endif // _MSC_VER - -// exchange -// -// Replaces the value of `obj` with `new_value` and returns the old value of -// `obj`. `phmap::exchange` is designed to be a drop-in replacement for C++14's -// `std::exchange`. -// -// Example: -// -// Foo& operator=(Foo&& other) { -// ptr1_ = phmap::exchange(other.ptr1_, nullptr); -// int1_ = phmap::exchange(other.int1_, -1); -// return *this; -// } -template <typename T, typename U = T> -T exchange(T& obj, U&& new_value) -{ - T old_value = phmap::move(obj); - obj = phmap::forward<U>(new_value); - return old_value; -} - -#ifdef _MSC_VER - #pragma warning(pop) -#endif // _MSC_VER - - -} // namespace phmap - -// ----------------------------------------------------------------------------- -// memory.h -// ----------------------------------------------------------------------------- - -namespace phmap { - -template <typename T> -std::unique_ptr<T> WrapUnique(T* ptr) -{ - static_assert(!std::is_array<T>::value, "array types are unsupported"); - static_assert(std::is_object<T>::value, "non-object types are unsupported"); - return std::unique_ptr<T>(ptr); -} - -namespace memory_internal { - -// Traits to select proper overload and return type for `phmap::make_unique<>`. -template <typename T> -struct MakeUniqueResult { - using scalar = std::unique_ptr<T>; -}; -template <typename T> -struct MakeUniqueResult<T[]> { - using array = std::unique_ptr<T[]>; -}; -template <typename T, size_t N> -struct MakeUniqueResult<T[N]> { - using invalid = void; -}; - -} // namespace memory_internal - -#if (__cplusplus > 201103L || defined(_MSC_VER)) && \ - !(defined(__GNUC__) && __GNUC__ == 4 && __GNUC_MINOR__ == 8) - using std::make_unique; -#else - - template <typename T, typename... Args> - typename memory_internal::MakeUniqueResult<T>::scalar make_unique( - Args&&... args) { - return std::unique_ptr<T>(new T(std::forward<Args>(args)...)); - } - - template <typename T> - typename memory_internal::MakeUniqueResult<T>::array make_unique(size_t n) { - return std::unique_ptr<T>(new typename phmap::remove_extent_t<T>[n]()); - } - - template <typename T, typename... Args> - typename memory_internal::MakeUniqueResult<T>::invalid make_unique( - Args&&... /* args */) = delete; -#endif - -template <typename T> -auto RawPtr(T&& ptr) -> decltype(std::addressof(*ptr)) -{ - // ptr is a forwarding reference to support Ts with non-const operators. - return (ptr != nullptr) ? std::addressof(*ptr) : nullptr; -} - -inline std::nullptr_t RawPtr(std::nullptr_t) { return nullptr; } - -template <typename T, typename D> -std::shared_ptr<T> ShareUniquePtr(std::unique_ptr<T, D>&& ptr) { - return ptr ? std::shared_ptr<T>(std::move(ptr)) : std::shared_ptr<T>(); -} - -template <typename T> -std::weak_ptr<T> WeakenPtr(const std::shared_ptr<T>& ptr) { - return std::weak_ptr<T>(ptr); -} - -namespace memory_internal { - -// ExtractOr<E, O, D>::type evaluates to E<O> if possible. Otherwise, D. -template <template <typename> class Extract, typename Obj, typename Default, - typename> -struct ExtractOr { - using type = Default; -}; - -template <template <typename> class Extract, typename Obj, typename Default> -struct ExtractOr<Extract, Obj, Default, void_t<Extract<Obj>>> { - using type = Extract<Obj>; -}; - -template <template <typename> class Extract, typename Obj, typename Default> -using ExtractOrT = typename ExtractOr<Extract, Obj, Default, void>::type; - -// Extractors for the features of allocators. -template <typename T> -using GetPointer = typename T::pointer; - -template <typename T> -using GetConstPointer = typename T::const_pointer; - -template <typename T> -using GetVoidPointer = typename T::void_pointer; - -template <typename T> -using GetConstVoidPointer = typename T::const_void_pointer; - -template <typename T> -using GetDifferenceType = typename T::difference_type; - -template <typename T> -using GetSizeType = typename T::size_type; - -template <typename T> -using GetPropagateOnContainerCopyAssignment = - typename T::propagate_on_container_copy_assignment; - -template <typename T> -using GetPropagateOnContainerMoveAssignment = - typename T::propagate_on_container_move_assignment; - -template <typename T> -using GetPropagateOnContainerSwap = typename T::propagate_on_container_swap; - -template <typename T> -using GetIsAlwaysEqual = typename T::is_always_equal; - -template <typename T> -struct GetFirstArg; - -template <template <typename...> class Class, typename T, typename... Args> -struct GetFirstArg<Class<T, Args...>> { - using type = T; -}; - -template <typename Ptr, typename = void> -struct ElementType { - using type = typename GetFirstArg<Ptr>::type; -}; - -template <typename T> -struct ElementType<T, void_t<typename T::element_type>> { - using type = typename T::element_type; -}; - -template <typename T, typename U> -struct RebindFirstArg; - -template <template <typename...> class Class, typename T, typename... Args, - typename U> -struct RebindFirstArg<Class<T, Args...>, U> { - using type = Class<U, Args...>; -}; - -template <typename T, typename U, typename = void> -struct RebindPtr { - using type = typename RebindFirstArg<T, U>::type; -}; - -template <typename T, typename U> -struct RebindPtr<T, U, void_t<typename T::template rebind<U>>> { - using type = typename T::template rebind<U>; -}; - -template <typename T, typename U> -constexpr bool HasRebindAlloc(...) { - return false; -} - -template <typename T, typename U> -constexpr bool HasRebindAlloc(typename std::allocator_traits<T>::template rebind_alloc<U>*) { - return true; -} - -template <typename T, typename U, bool = HasRebindAlloc<T, U>(nullptr)> -struct RebindAlloc { - using type = typename RebindFirstArg<T, U>::type; -}; - -template <typename A, typename U> -struct RebindAlloc<A, U, true> { - using type = typename std::allocator_traits<A>::template rebind_alloc<U>; -}; - - -} // namespace memory_internal - -template <typename Ptr> -struct pointer_traits -{ - using pointer = Ptr; - - // element_type: - // Ptr::element_type if present. Otherwise T if Ptr is a template - // instantiation Template<T, Args...> - using element_type = typename memory_internal::ElementType<Ptr>::type; - - // difference_type: - // Ptr::difference_type if present, otherwise std::ptrdiff_t - using difference_type = - memory_internal::ExtractOrT<memory_internal::GetDifferenceType, Ptr, - std::ptrdiff_t>; - - // rebind: - // Ptr::rebind<U> if exists, otherwise Template<U, Args...> if Ptr is a - // template instantiation Template<T, Args...> - template <typename U> - using rebind = typename memory_internal::RebindPtr<Ptr, U>::type; - - // pointer_to: - // Calls Ptr::pointer_to(r) - static pointer pointer_to(element_type& r) { // NOLINT(runtime/references) - return Ptr::pointer_to(r); - } -}; - -// Specialization for T*. -template <typename T> -struct pointer_traits<T*> -{ - using pointer = T*; - using element_type = T; - using difference_type = std::ptrdiff_t; - - template <typename U> - using rebind = U*; - - // pointer_to: - // Calls std::addressof(r) - static pointer pointer_to( - element_type& r) noexcept { // NOLINT(runtime/references) - return std::addressof(r); - } -}; - -// ----------------------------------------------------------------------------- -// Class Template: allocator_traits -// ----------------------------------------------------------------------------- -// -// A C++11 compatible implementation of C++17's std::allocator_traits. -// -template <typename Alloc> -struct allocator_traits -{ - using allocator_type = Alloc; - - // value_type: - // Alloc::value_type - using value_type = typename Alloc::value_type; - - // pointer: - // Alloc::pointer if present, otherwise value_type* - using pointer = memory_internal::ExtractOrT<memory_internal::GetPointer, - Alloc, value_type*>; - - // const_pointer: - // Alloc::const_pointer if present, otherwise - // phmap::pointer_traits<pointer>::rebind<const value_type> - using const_pointer = - memory_internal::ExtractOrT<memory_internal::GetConstPointer, Alloc, - typename phmap::pointer_traits<pointer>:: - template rebind<const value_type>>; - - // void_pointer: - // Alloc::void_pointer if present, otherwise - // phmap::pointer_traits<pointer>::rebind<void> - using void_pointer = memory_internal::ExtractOrT< - memory_internal::GetVoidPointer, Alloc, - typename phmap::pointer_traits<pointer>::template rebind<void>>; - - // const_void_pointer: - // Alloc::const_void_pointer if present, otherwise - // phmap::pointer_traits<pointer>::rebind<const void> - using const_void_pointer = memory_internal::ExtractOrT< - memory_internal::GetConstVoidPointer, Alloc, - typename phmap::pointer_traits<pointer>::template rebind<const void>>; - - // difference_type: - // Alloc::difference_type if present, otherwise - // phmap::pointer_traits<pointer>::difference_type - using difference_type = memory_internal::ExtractOrT< - memory_internal::GetDifferenceType, Alloc, - typename phmap::pointer_traits<pointer>::difference_type>; - - // size_type: - // Alloc::size_type if present, otherwise - // std::make_unsigned<difference_type>::type - using size_type = memory_internal::ExtractOrT< - memory_internal::GetSizeType, Alloc, - typename std::make_unsigned<difference_type>::type>; - - // propagate_on_container_copy_assignment: - // Alloc::propagate_on_container_copy_assignment if present, otherwise - // std::false_type - using propagate_on_container_copy_assignment = memory_internal::ExtractOrT< - memory_internal::GetPropagateOnContainerCopyAssignment, Alloc, - std::false_type>; - - // propagate_on_container_move_assignment: - // Alloc::propagate_on_container_move_assignment if present, otherwise - // std::false_type - using propagate_on_container_move_assignment = memory_internal::ExtractOrT< - memory_internal::GetPropagateOnContainerMoveAssignment, Alloc, - std::false_type>; - - // propagate_on_container_swap: - // Alloc::propagate_on_container_swap if present, otherwise std::false_type - using propagate_on_container_swap = - memory_internal::ExtractOrT<memory_internal::GetPropagateOnContainerSwap, - Alloc, std::false_type>; - - // is_always_equal: - // Alloc::is_always_equal if present, otherwise std::is_empty<Alloc>::type - using is_always_equal = - memory_internal::ExtractOrT<memory_internal::GetIsAlwaysEqual, Alloc, - typename std::is_empty<Alloc>::type>; - - // rebind_alloc: - // Alloc::rebind<T>::other if present, otherwise Alloc<T, Args> if this Alloc - // is Alloc<U, Args> - template <typename T> - using rebind_alloc = typename memory_internal::RebindAlloc<Alloc, T>::type; - - // rebind_traits: - // phmap::allocator_traits<rebind_alloc<T>> - template <typename T> - using rebind_traits = phmap::allocator_traits<rebind_alloc<T>>; - - // allocate(Alloc& a, size_type n): - // Calls a.allocate(n) - static pointer allocate(Alloc& a, // NOLINT(runtime/references) - size_type n) { - return a.allocate(n); - } - - // allocate(Alloc& a, size_type n, const_void_pointer hint): - // Calls a.allocate(n, hint) if possible. - // If not possible, calls a.allocate(n) - static pointer allocate(Alloc& a, size_type n, // NOLINT(runtime/references) - const_void_pointer hint) { - return allocate_impl(0, a, n, hint); - } - - // deallocate(Alloc& a, pointer p, size_type n): - // Calls a.deallocate(p, n) - static void deallocate(Alloc& a, pointer p, // NOLINT(runtime/references) - size_type n) { - a.deallocate(p, n); - } - - // construct(Alloc& a, T* p, Args&&... args): - // Calls a.construct(p, std::forward<Args>(args)...) if possible. - // If not possible, calls - // ::new (static_cast<void*>(p)) T(std::forward<Args>(args)...) - template <typename T, typename... Args> - static void construct(Alloc& a, T* p, // NOLINT(runtime/references) - Args&&... args) { - construct_impl(0, a, p, std::forward<Args>(args)...); - } - - // destroy(Alloc& a, T* p): - // Calls a.destroy(p) if possible. If not possible, calls p->~T(). - template <typename T> - static void destroy(Alloc& a, T* p) { // NOLINT(runtime/references) - destroy_impl(0, a, p); - } - - // max_size(const Alloc& a): - // Returns a.max_size() if possible. If not possible, returns - // std::numeric_limits<size_type>::max() / sizeof(value_type) - static size_type max_size(const Alloc& a) { return max_size_impl(0, a); } - - // select_on_container_copy_construction(const Alloc& a): - // Returns a.select_on_container_copy_construction() if possible. - // If not possible, returns a. - static Alloc select_on_container_copy_construction(const Alloc& a) { - return select_on_container_copy_construction_impl(0, a); - } - -private: - template <typename A> - static auto allocate_impl(int, A& a, // NOLINT(runtime/references) - size_type n, const_void_pointer hint) - -> decltype(a.allocate(n, hint)) { - return a.allocate(n, hint); - } - static pointer allocate_impl(char, Alloc& a, // NOLINT(runtime/references) - size_type n, const_void_pointer) { - return a.allocate(n); - } - - template <typename A, typename... Args> - static auto construct_impl(int, A& a, // NOLINT(runtime/references) - Args&&... args) - -> decltype(std::allocator_traits<A>::construct(a, std::forward<Args>(args)...)) { - std::allocator_traits<A>::construct(a, std::forward<Args>(args)...); - } - - template <typename T, typename... Args> - static void construct_impl(char, Alloc&, T* p, Args&&... args) { - ::new (static_cast<void*>(p)) T(std::forward<Args>(args)...); - } - - template <typename A, typename T> - static auto destroy_impl(int, A& a, // NOLINT(runtime/references) - T* p) -> decltype(std::allocator_traits<A>::destroy(a, p)) { - std::allocator_traits<A>::destroy(a, p); - } - template <typename T> - static void destroy_impl(char, Alloc&, T* p) { - p->~T(); - } - - template <typename A> - static auto max_size_impl(int, const A& a) -> decltype(a.max_size()) { - return a.max_size(); - } - static size_type max_size_impl(char, const Alloc&) { - return (std::numeric_limits<size_type>::max)() / sizeof(value_type); - } - - template <typename A> - static auto select_on_container_copy_construction_impl(int, const A& a) - -> decltype(a.select_on_container_copy_construction()) { - return a.select_on_container_copy_construction(); - } - static Alloc select_on_container_copy_construction_impl(char, - const Alloc& a) { - return a; - } -}; - -namespace memory_internal { - -// This template alias transforms Alloc::is_nothrow into a metafunction with -// Alloc as a parameter so it can be used with ExtractOrT<>. -template <typename Alloc> -using GetIsNothrow = typename Alloc::is_nothrow; - -} // namespace memory_internal - -// PHMAP_ALLOCATOR_NOTHROW is a build time configuration macro for user to -// specify whether the default allocation function can throw or never throws. -// If the allocation function never throws, user should define it to a non-zero -// value (e.g. via `-DPHMAP_ALLOCATOR_NOTHROW`). -// If the allocation function can throw, user should leave it undefined or -// define it to zero. -// -// allocator_is_nothrow<Alloc> is a traits class that derives from -// Alloc::is_nothrow if present, otherwise std::false_type. It's specialized -// for Alloc = std::allocator<T> for any type T according to the state of -// PHMAP_ALLOCATOR_NOTHROW. -// -// default_allocator_is_nothrow is a class that derives from std::true_type -// when the default allocator (global operator new) never throws, and -// std::false_type when it can throw. It is a convenience shorthand for writing -// allocator_is_nothrow<std::allocator<T>> (T can be any type). -// NOTE: allocator_is_nothrow<std::allocator<T>> is guaranteed to derive from -// the same type for all T, because users should specialize neither -// allocator_is_nothrow nor std::allocator. -template <typename Alloc> -struct allocator_is_nothrow - : memory_internal::ExtractOrT<memory_internal::GetIsNothrow, Alloc, - std::false_type> {}; - -#if defined(PHMAP_ALLOCATOR_NOTHROW) && PHMAP_ALLOCATOR_NOTHROW - template <typename T> - struct allocator_is_nothrow<std::allocator<T>> : std::true_type {}; - struct default_allocator_is_nothrow : std::true_type {}; -#else - struct default_allocator_is_nothrow : std::false_type {}; -#endif - -namespace memory_internal { -template <typename Allocator, typename Iterator, typename... Args> -void ConstructRange(Allocator& alloc, Iterator first, Iterator last, - const Args&... args) -{ - for (Iterator cur = first; cur != last; ++cur) { - PHMAP_INTERNAL_TRY { - std::allocator_traits<Allocator>::construct(alloc, std::addressof(*cur), - args...); - } - PHMAP_INTERNAL_CATCH_ANY { - while (cur != first) { - --cur; - std::allocator_traits<Allocator>::destroy(alloc, std::addressof(*cur)); - } - PHMAP_INTERNAL_RETHROW; - } - } -} - -template <typename Allocator, typename Iterator, typename InputIterator> -void CopyRange(Allocator& alloc, Iterator destination, InputIterator first, - InputIterator last) -{ - for (Iterator cur = destination; first != last; - static_cast<void>(++cur), static_cast<void>(++first)) { - PHMAP_INTERNAL_TRY { - std::allocator_traits<Allocator>::construct(alloc, std::addressof(*cur), - *first); - } - PHMAP_INTERNAL_CATCH_ANY { - while (cur != destination) { - --cur; - std::allocator_traits<Allocator>::destroy(alloc, std::addressof(*cur)); - } - PHMAP_INTERNAL_RETHROW; - } - } -} -} // namespace memory_internal -} // namespace phmap - - -// ----------------------------------------------------------------------------- -// optional.h -// ----------------------------------------------------------------------------- -#ifdef PHMAP_HAVE_STD_OPTIONAL - -#include <optional> // IWYU pragma: export - -namespace phmap { -using std::bad_optional_access; -using std::optional; -using std::make_optional; -using std::nullopt_t; -using std::nullopt; -} // namespace phmap - -#else - -#if defined(__clang__) - #if __has_feature(cxx_inheriting_constructors) - #define PHMAP_OPTIONAL_USE_INHERITING_CONSTRUCTORS 1 - #endif -#elif (defined(__GNUC__) && \ - (__GNUC__ > 4 || __GNUC__ == 4 && __GNUC_MINOR__ >= 8)) || \ - (__cpp_inheriting_constructors >= 200802) || \ - (defined(_MSC_VER) && _MSC_VER >= 1910) - - #define PHMAP_OPTIONAL_USE_INHERITING_CONSTRUCTORS 1 -#endif - -namespace phmap { - -class bad_optional_access : public std::exception -{ -public: - bad_optional_access() = default; - ~bad_optional_access() override; - const char* what() const noexcept override; -}; - -template <typename T> -class optional; - -// -------------------------------- -struct nullopt_t -{ - struct init_t {}; - static init_t init; - - explicit constexpr nullopt_t(init_t& /*unused*/) {} -}; - -constexpr nullopt_t nullopt(nullopt_t::init); - -namespace optional_internal { - -// throw delegator -[[noreturn]] void throw_bad_optional_access(); - - -struct empty_struct {}; - -// This class stores the data in optional<T>. -// It is specialized based on whether T is trivially destructible. -// This is the specialization for non trivially destructible type. -template <typename T, bool unused = std::is_trivially_destructible<T>::value> -class optional_data_dtor_base -{ - struct dummy_type { - static_assert(sizeof(T) % sizeof(empty_struct) == 0, ""); - // Use an array to avoid GCC 6 placement-new warning. - empty_struct data[sizeof(T) / sizeof(empty_struct)]; - }; - -protected: - // Whether there is data or not. - bool engaged_; - // Data storage - union { - dummy_type dummy_; - T data_; - }; - - void destruct() noexcept { - if (engaged_) { - data_.~T(); - engaged_ = false; - } - } - - // dummy_ must be initialized for constexpr constructor. - constexpr optional_data_dtor_base() noexcept : engaged_(false), dummy_{{}} {} - - template <typename... Args> - constexpr explicit optional_data_dtor_base(in_place_t, Args&&... args) - : engaged_(true), data_(phmap::forward<Args>(args)...) {} - - ~optional_data_dtor_base() { destruct(); } -}; - -// Specialization for trivially destructible type. -template <typename T> -class optional_data_dtor_base<T, true> -{ - struct dummy_type { - static_assert(sizeof(T) % sizeof(empty_struct) == 0, ""); - // Use array to avoid GCC 6 placement-new warning. - empty_struct data[sizeof(T) / sizeof(empty_struct)]; - }; - -protected: - // Whether there is data or not. - bool engaged_; - // Data storage - union { - dummy_type dummy_; - T data_; - }; - void destruct() noexcept { engaged_ = false; } - - // dummy_ must be initialized for constexpr constructor. - constexpr optional_data_dtor_base() noexcept : engaged_(false), dummy_{{}} {} - - template <typename... Args> - constexpr explicit optional_data_dtor_base(in_place_t, Args&&... args) - : engaged_(true), data_(phmap::forward<Args>(args)...) {} -}; - -template <typename T> -class optional_data_base : public optional_data_dtor_base<T> -{ -protected: - using base = optional_data_dtor_base<T>; -#if PHMAP_OPTIONAL_USE_INHERITING_CONSTRUCTORS - using base::base; -#else - optional_data_base() = default; - - template <typename... Args> - constexpr explicit optional_data_base(in_place_t t, Args&&... args) - : base(t, phmap::forward<Args>(args)...) {} -#endif - - template <typename... Args> - void construct(Args&&... args) { - // Use dummy_'s address to work around casting cv-qualified T* to void*. - ::new (static_cast<void*>(&this->dummy_)) T(std::forward<Args>(args)...); - this->engaged_ = true; - } - - template <typename U> - void assign(U&& u) { - if (this->engaged_) { - this->data_ = std::forward<U>(u); - } else { - construct(std::forward<U>(u)); - } - } -}; - -// TODO: Add another class using -// std::is_trivially_move_constructible trait when available to match -// http://cplusplus.github.io/LWG/lwg-defects.html#2900, for types that -// have trivial move but nontrivial copy. -// Also, we should be checking is_trivially_copyable here, which is not -// supported now, so we use is_trivially_* traits instead. -template <typename T, - bool unused = phmap::is_trivially_copy_constructible<T>::value&& - phmap::is_trivially_copy_assignable<typename std::remove_cv< - T>::type>::value&& std::is_trivially_destructible<T>::value> -class optional_data; - -// Trivially copyable types -template <typename T> -class optional_data<T, true> : public optional_data_base<T> -{ -protected: -#if PHMAP_OPTIONAL_USE_INHERITING_CONSTRUCTORS - using optional_data_base<T>::optional_data_base; -#else - optional_data() = default; - - template <typename... Args> - constexpr explicit optional_data(in_place_t t, Args&&... args) - : optional_data_base<T>(t, phmap::forward<Args>(args)...) {} -#endif -}; - -template <typename T> -class optional_data<T, false> : public optional_data_base<T> -{ -protected: -#if PHMAP_OPTIONAL_USE_INHERITING_CONSTRUCTORS - using optional_data_base<T>::optional_data_base; -#else - template <typename... Args> - constexpr explicit optional_data(in_place_t t, Args&&... args) - : optional_data_base<T>(t, phmap::forward<Args>(args)...) {} -#endif - - optional_data() = default; - - optional_data(const optional_data& rhs) : optional_data_base<T>() { - if (rhs.engaged_) { - this->construct(rhs.data_); - } - } - - optional_data(optional_data&& rhs) noexcept( - phmap::default_allocator_is_nothrow::value || - std::is_nothrow_move_constructible<T>::value) - : optional_data_base<T>() { - if (rhs.engaged_) { - this->construct(std::move(rhs.data_)); - } - } - - optional_data& operator=(const optional_data& rhs) { - if (rhs.engaged_) { - this->assign(rhs.data_); - } else { - this->destruct(); - } - return *this; - } - - optional_data& operator=(optional_data&& rhs) noexcept( - std::is_nothrow_move_assignable<T>::value&& - std::is_nothrow_move_constructible<T>::value) { - if (rhs.engaged_) { - this->assign(std::move(rhs.data_)); - } else { - this->destruct(); - } - return *this; - } -}; - -// Ordered by level of restriction, from low to high. -// Copyable implies movable. -enum class copy_traits { copyable = 0, movable = 1, non_movable = 2 }; - -// Base class for enabling/disabling copy/move constructor. -template <copy_traits> -class optional_ctor_base; - -template <> -class optional_ctor_base<copy_traits::copyable> -{ -public: - constexpr optional_ctor_base() = default; - optional_ctor_base(const optional_ctor_base&) = default; - optional_ctor_base(optional_ctor_base&&) = default; - optional_ctor_base& operator=(const optional_ctor_base&) = default; - optional_ctor_base& operator=(optional_ctor_base&&) = default; -}; - -template <> -class optional_ctor_base<copy_traits::movable> -{ -public: - constexpr optional_ctor_base() = default; - optional_ctor_base(const optional_ctor_base&) = delete; - optional_ctor_base(optional_ctor_base&&) = default; - optional_ctor_base& operator=(const optional_ctor_base&) = default; - optional_ctor_base& operator=(optional_ctor_base&&) = default; -}; - -template <> -class optional_ctor_base<copy_traits::non_movable> -{ -public: - constexpr optional_ctor_base() = default; - optional_ctor_base(const optional_ctor_base&) = delete; - optional_ctor_base(optional_ctor_base&&) = delete; - optional_ctor_base& operator=(const optional_ctor_base&) = default; - optional_ctor_base& operator=(optional_ctor_base&&) = default; -}; - -// Base class for enabling/disabling copy/move assignment. -template <copy_traits> -class optional_assign_base; - -template <> -class optional_assign_base<copy_traits::copyable> -{ -public: - constexpr optional_assign_base() = default; - optional_assign_base(const optional_assign_base&) = default; - optional_assign_base(optional_assign_base&&) = default; - optional_assign_base& operator=(const optional_assign_base&) = default; - optional_assign_base& operator=(optional_assign_base&&) = default; -}; - -template <> -class optional_assign_base<copy_traits::movable> -{ -public: - constexpr optional_assign_base() = default; - optional_assign_base(const optional_assign_base&) = default; - optional_assign_base(optional_assign_base&&) = default; - optional_assign_base& operator=(const optional_assign_base&) = delete; - optional_assign_base& operator=(optional_assign_base&&) = default; -}; - -template <> -class optional_assign_base<copy_traits::non_movable> -{ -public: - constexpr optional_assign_base() = default; - optional_assign_base(const optional_assign_base&) = default; - optional_assign_base(optional_assign_base&&) = default; - optional_assign_base& operator=(const optional_assign_base&) = delete; - optional_assign_base& operator=(optional_assign_base&&) = delete; -}; - -template <typename T> -constexpr copy_traits get_ctor_copy_traits() -{ - return std::is_copy_constructible<T>::value - ? copy_traits::copyable - : std::is_move_constructible<T>::value ? copy_traits::movable - : copy_traits::non_movable; -} - -template <typename T> -constexpr copy_traits get_assign_copy_traits() -{ - return phmap::is_copy_assignable<T>::value && - std::is_copy_constructible<T>::value - ? copy_traits::copyable - : phmap::is_move_assignable<T>::value && - std::is_move_constructible<T>::value - ? copy_traits::movable - : copy_traits::non_movable; -} - -// Whether T is constructible or convertible from optional<U>. -template <typename T, typename U> -struct is_constructible_convertible_from_optional - : std::integral_constant< - bool, std::is_constructible<T, optional<U>&>::value || - std::is_constructible<T, optional<U>&&>::value || - std::is_constructible<T, const optional<U>&>::value || - std::is_constructible<T, const optional<U>&&>::value || - std::is_convertible<optional<U>&, T>::value || - std::is_convertible<optional<U>&&, T>::value || - std::is_convertible<const optional<U>&, T>::value || - std::is_convertible<const optional<U>&&, T>::value> {}; - -// Whether T is constructible or convertible or assignable from optional<U>. -template <typename T, typename U> -struct is_constructible_convertible_assignable_from_optional - : std::integral_constant< - bool, is_constructible_convertible_from_optional<T, U>::value || - std::is_assignable<T&, optional<U>&>::value || - std::is_assignable<T&, optional<U>&&>::value || - std::is_assignable<T&, const optional<U>&>::value || - std::is_assignable<T&, const optional<U>&&>::value> {}; - -// Helper function used by [optional.relops], [optional.comp_with_t], -// for checking whether an expression is convertible to bool. -bool convertible_to_bool(bool); - -// Base class for std::hash<phmap::optional<T>>: -// If std::hash<std::remove_const_t<T>> is enabled, it provides operator() to -// compute the hash; Otherwise, it is disabled. -// Reference N4659 23.14.15 [unord.hash]. -template <typename T, typename = size_t> -struct optional_hash_base -{ - optional_hash_base() = delete; - optional_hash_base(const optional_hash_base&) = delete; - optional_hash_base(optional_hash_base&&) = delete; - optional_hash_base& operator=(const optional_hash_base&) = delete; - optional_hash_base& operator=(optional_hash_base&&) = delete; -}; - -template <typename T> -struct optional_hash_base<T, decltype(std::hash<phmap::remove_const_t<T> >()( - std::declval<phmap::remove_const_t<T> >()))> -{ - using argument_type = phmap::optional<T>; - using result_type = size_t; - size_t operator()(const phmap::optional<T>& opt) const { - phmap::type_traits_internal::AssertHashEnabled<phmap::remove_const_t<T>>(); - if (opt) { - return std::hash<phmap::remove_const_t<T> >()(*opt); - } else { - return static_cast<size_t>(0x297814aaad196e6dULL); - } - } -}; - -} // namespace optional_internal - - -// ----------------------------------------------------------------------------- -// phmap::optional class definition -// ----------------------------------------------------------------------------- - -template <typename T> -class optional : private optional_internal::optional_data<T>, - private optional_internal::optional_ctor_base< - optional_internal::get_ctor_copy_traits<T>()>, - private optional_internal::optional_assign_base< - optional_internal::get_assign_copy_traits<T>()> -{ - using data_base = optional_internal::optional_data<T>; - -public: - typedef T value_type; - - // Constructors - - // Constructs an `optional` holding an empty value, NOT a default constructed - // `T`. - constexpr optional() noexcept {} - - // Constructs an `optional` initialized with `nullopt` to hold an empty value. - constexpr optional(nullopt_t) noexcept {} // NOLINT(runtime/explicit) - - // Copy constructor, standard semantics - optional(const optional& src) = default; - - // Move constructor, standard semantics - optional(optional&& src) = default; - - // Constructs a non-empty `optional` direct-initialized value of type `T` from - // the arguments `std::forward<Args>(args)...` within the `optional`. - // (The `in_place_t` is a tag used to indicate that the contained object - // should be constructed in-place.) - template <typename InPlaceT, typename... Args, - phmap::enable_if_t<phmap::conjunction< - std::is_same<InPlaceT, in_place_t>, - std::is_constructible<T, Args&&...> >::value>* = nullptr> - constexpr explicit optional(InPlaceT, Args&&... args) - : data_base(in_place_t(), phmap::forward<Args>(args)...) {} - - // Constructs a non-empty `optional` direct-initialized value of type `T` from - // the arguments of an initializer_list and `std::forward<Args>(args)...`. - // (The `in_place_t` is a tag used to indicate that the contained object - // should be constructed in-place.) - template <typename U, typename... Args, - typename = typename std::enable_if<std::is_constructible< - T, std::initializer_list<U>&, Args&&...>::value>::type> - constexpr explicit optional(in_place_t, std::initializer_list<U> il, - Args&&... args) - : data_base(in_place_t(), il, phmap::forward<Args>(args)...) { - } - - // Value constructor (implicit) - template < - typename U = T, - typename std::enable_if< - phmap::conjunction<phmap::negation<std::is_same< - in_place_t, typename std::decay<U>::type> >, - phmap::negation<std::is_same< - optional<T>, typename std::decay<U>::type> >, - std::is_convertible<U&&, T>, - std::is_constructible<T, U&&> >::value, - bool>::type = false> - constexpr optional(U&& v) : data_base(in_place_t(), phmap::forward<U>(v)) {} - - // Value constructor (explicit) - template < - typename U = T, - typename std::enable_if< - phmap::conjunction<phmap::negation<std::is_same< - in_place_t, typename std::decay<U>::type>>, - phmap::negation<std::is_same< - optional<T>, typename std::decay<U>::type>>, - phmap::negation<std::is_convertible<U&&, T>>, - std::is_constructible<T, U&&>>::value, - bool>::type = false> - explicit constexpr optional(U&& v) - : data_base(in_place_t(), phmap::forward<U>(v)) {} - - // Converting copy constructor (implicit) - template <typename U, - typename std::enable_if< - phmap::conjunction< - phmap::negation<std::is_same<T, U> >, - std::is_constructible<T, const U&>, - phmap::negation< - optional_internal:: - is_constructible_convertible_from_optional<T, U> >, - std::is_convertible<const U&, T> >::value, - bool>::type = false> - optional(const optional<U>& rhs) { - if (rhs) { - this->construct(*rhs); - } - } - - // Converting copy constructor (explicit) - template <typename U, - typename std::enable_if< - phmap::conjunction< - phmap::negation<std::is_same<T, U>>, - std::is_constructible<T, const U&>, - phmap::negation< - optional_internal:: - is_constructible_convertible_from_optional<T, U>>, - phmap::negation<std::is_convertible<const U&, T>>>::value, - bool>::type = false> - explicit optional(const optional<U>& rhs) { - if (rhs) { - this->construct(*rhs); - } - } - - // Converting move constructor (implicit) - template <typename U, - typename std::enable_if< - phmap::conjunction< - phmap::negation<std::is_same<T, U> >, - std::is_constructible<T, U&&>, - phmap::negation< - optional_internal:: - is_constructible_convertible_from_optional<T, U> >, - std::is_convertible<U&&, T> >::value, - bool>::type = false> - optional(optional<U>&& rhs) { - if (rhs) { - this->construct(std::move(*rhs)); - } - } - - // Converting move constructor (explicit) - template < - typename U, - typename std::enable_if< - phmap::conjunction< - phmap::negation<std::is_same<T, U>>, std::is_constructible<T, U&&>, - phmap::negation< - optional_internal::is_constructible_convertible_from_optional< - T, U>>, - phmap::negation<std::is_convertible<U&&, T>>>::value, - bool>::type = false> - explicit optional(optional<U>&& rhs) { - if (rhs) { - this->construct(std::move(*rhs)); - } - } - - // Destructor. Trivial if `T` is trivially destructible. - ~optional() = default; - - // Assignment Operators - - // Assignment from `nullopt` - // - // Example: - // - // struct S { int value; }; - // optional<S> opt = phmap::nullopt; // Could also use opt = { }; - optional& operator=(nullopt_t) noexcept { - this->destruct(); - return *this; - } - - // Copy assignment operator, standard semantics - optional& operator=(const optional& src) = default; - - // Move assignment operator, standard semantics - optional& operator=(optional&& src) = default; - - // Value assignment operators - template < - typename U = T, - typename = typename std::enable_if<phmap::conjunction< - phmap::negation< - std::is_same<optional<T>, typename std::decay<U>::type>>, - phmap::negation< - phmap::conjunction<std::is_scalar<T>, - std::is_same<T, typename std::decay<U>::type>>>, - std::is_constructible<T, U>, std::is_assignable<T&, U>>::value>::type> - optional& operator=(U&& v) { - this->assign(std::forward<U>(v)); - return *this; - } - - template < - typename U, - typename = typename std::enable_if<phmap::conjunction< - phmap::negation<std::is_same<T, U>>, - std::is_constructible<T, const U&>, std::is_assignable<T&, const U&>, - phmap::negation< - optional_internal:: - is_constructible_convertible_assignable_from_optional< - T, U>>>::value>::type> - optional& operator=(const optional<U>& rhs) { - if (rhs) { - this->assign(*rhs); - } else { - this->destruct(); - } - return *this; - } - - template <typename U, - typename = typename std::enable_if<phmap::conjunction< - phmap::negation<std::is_same<T, U>>, std::is_constructible<T, U>, - std::is_assignable<T&, U>, - phmap::negation< - optional_internal:: - is_constructible_convertible_assignable_from_optional< - T, U>>>::value>::type> - optional& operator=(optional<U>&& rhs) { - if (rhs) { - this->assign(std::move(*rhs)); - } else { - this->destruct(); - } - return *this; - } - - // Modifiers - - // optional::reset() - // - // Destroys the inner `T` value of an `phmap::optional` if one is present. - PHMAP_ATTRIBUTE_REINITIALIZES void reset() noexcept { this->destruct(); } - - // optional::emplace() - // - // (Re)constructs the underlying `T` in-place with the given forwarded - // arguments. - // - // Example: - // - // optional<Foo> opt; - // opt.emplace(arg1,arg2,arg3); // Constructs Foo(arg1,arg2,arg3) - // - // If the optional is non-empty, and the `args` refer to subobjects of the - // current object, then behaviour is undefined, because the current object - // will be destructed before the new object is constructed with `args`. - template <typename... Args, - typename = typename std::enable_if< - std::is_constructible<T, Args&&...>::value>::type> - T& emplace(Args&&... args) { - this->destruct(); - this->construct(std::forward<Args>(args)...); - return reference(); - } - - // Emplace reconstruction overload for an initializer list and the given - // forwarded arguments. - // - // Example: - // - // struct Foo { - // Foo(std::initializer_list<int>); - // }; - // - // optional<Foo> opt; - // opt.emplace({1,2,3}); // Constructs Foo({1,2,3}) - template <typename U, typename... Args, - typename = typename std::enable_if<std::is_constructible< - T, std::initializer_list<U>&, Args&&...>::value>::type> - T& emplace(std::initializer_list<U> il, Args&&... args) { - this->destruct(); - this->construct(il, std::forward<Args>(args)...); - return reference(); - } - - // Swaps - - // Swap, standard semantics - void swap(optional& rhs) noexcept( - std::is_nothrow_move_constructible<T>::value&& - std::is_trivial<T>::value) { - if (*this) { - if (rhs) { - using std::swap; - swap(**this, *rhs); - } else { - rhs.construct(std::move(**this)); - this->destruct(); - } - } else { - if (rhs) { - this->construct(std::move(*rhs)); - rhs.destruct(); - } else { - // No effect (swap(disengaged, disengaged)). - } - } - } - - // Observers - - // optional::operator->() - // - // Accesses the underlying `T` value's member `m` of an `optional`. If the - // `optional` is empty, behavior is undefined. - // - // If you need myOpt->foo in constexpr, use (*myOpt).foo instead. - const T* operator->() const { - assert(this->engaged_); - return std::addressof(this->data_); - } - T* operator->() { - assert(this->engaged_); - return std::addressof(this->data_); - } - - // optional::operator*() - // - // Accesses the underlying `T` value of an `optional`. If the `optional` is - // empty, behavior is undefined. - constexpr const T& operator*() const & { return reference(); } - T& operator*() & { - assert(this->engaged_); - return reference(); - } - constexpr const T&& operator*() const && { - return phmap::move(reference()); - } - T&& operator*() && { - assert(this->engaged_); - return std::move(reference()); - } - - // optional::operator bool() - // - // Returns false if and only if the `optional` is empty. - // - // if (opt) { - // // do something with opt.value(); - // } else { - // // opt is empty. - // } - // - constexpr explicit operator bool() const noexcept { return this->engaged_; } - - // optional::has_value() - // - // Determines whether the `optional` contains a value. Returns `false` if and - // only if `*this` is empty. - constexpr bool has_value() const noexcept { return this->engaged_; } - -// Suppress bogus warning on MSVC: MSVC complains call to reference() after -// throw_bad_optional_access() is unreachable. -#ifdef _MSC_VER - #pragma warning(push) - #pragma warning(disable : 4702) -#endif // _MSC_VER - // optional::value() - // - // Returns a reference to an `optional`s underlying value. The constness - // and lvalue/rvalue-ness of the `optional` is preserved to the view of - // the `T` sub-object. Throws `phmap::bad_optional_access` when the `optional` - // is empty. - constexpr const T& value() const & { - return static_cast<bool>(*this) - ? reference() - : (optional_internal::throw_bad_optional_access(), reference()); - } - T& value() & { - return static_cast<bool>(*this) - ? reference() - : (optional_internal::throw_bad_optional_access(), reference()); - } - T&& value() && { // NOLINT(build/c++11) - return std::move( - static_cast<bool>(*this) - ? reference() - : (optional_internal::throw_bad_optional_access(), reference())); - } - constexpr const T&& value() const && { // NOLINT(build/c++11) - return phmap::move( - static_cast<bool>(*this) - ? reference() - : (optional_internal::throw_bad_optional_access(), reference())); - } -#ifdef _MSC_VER - #pragma warning(pop) -#endif // _MSC_VER - - // optional::value_or() - // - // Returns either the value of `T` or a passed default `v` if the `optional` - // is empty. - template <typename U> - constexpr T value_or(U&& v) const& { - static_assert(std::is_copy_constructible<value_type>::value, - "optional<T>::value_or: T must by copy constructible"); - static_assert(std::is_convertible<U&&, value_type>::value, - "optional<T>::value_or: U must be convertible to T"); - return static_cast<bool>(*this) - ? **this - : static_cast<T>(phmap::forward<U>(v)); - } - template <typename U> - T value_or(U&& v) && { // NOLINT(build/c++11) - static_assert(std::is_move_constructible<value_type>::value, - "optional<T>::value_or: T must by move constructible"); - static_assert(std::is_convertible<U&&, value_type>::value, - "optional<T>::value_or: U must be convertible to T"); - return static_cast<bool>(*this) ? std::move(**this) - : static_cast<T>(std::forward<U>(v)); - } - -private: - // Private accessors for internal storage viewed as reference to T. - constexpr const T& reference() const { return this->data_; } - T& reference() { return this->data_; } - - // T constraint checks. You can't have an optional of nullopt_t, in_place_t - // or a reference. - static_assert( - !std::is_same<nullopt_t, typename std::remove_cv<T>::type>::value, - "optional<nullopt_t> is not allowed."); - static_assert( - !std::is_same<in_place_t, typename std::remove_cv<T>::type>::value, - "optional<in_place_t> is not allowed."); - static_assert(!std::is_reference<T>::value, - "optional<reference> is not allowed."); -}; - -// Non-member functions - -// swap() -// -// Performs a swap between two `phmap::optional` objects, using standard -// semantics. -// -// NOTE: we assume `is_swappable()` is always `true`. A compile error will -// result if this is not the case. -template <typename T, - typename std::enable_if<std::is_move_constructible<T>::value, - bool>::type = false> -void swap(optional<T>& a, optional<T>& b) noexcept(noexcept(a.swap(b))) { - a.swap(b); -} - -// make_optional() -// -// Creates a non-empty `optional<T>` where the type of `T` is deduced. An -// `phmap::optional` can also be explicitly instantiated with -// `make_optional<T>(v)`. -// -// Note: `make_optional()` constructions may be declared `constexpr` for -// trivially copyable types `T`. Non-trivial types require copy elision -// support in C++17 for `make_optional` to support `constexpr` on such -// non-trivial types. -// -// Example: -// -// constexpr phmap::optional<int> opt = phmap::make_optional(1); -// static_assert(opt.value() == 1, ""); -template <typename T> -constexpr optional<typename std::decay<T>::type> make_optional(T&& v) { - return optional<typename std::decay<T>::type>(phmap::forward<T>(v)); -} - -template <typename T, typename... Args> -constexpr optional<T> make_optional(Args&&... args) { - return optional<T>(in_place_t(), phmap::forward<Args>(args)...); -} - -template <typename T, typename U, typename... Args> -constexpr optional<T> make_optional(std::initializer_list<U> il, - Args&&... args) { - return optional<T>(in_place_t(), il, - phmap::forward<Args>(args)...); -} - -// Relational operators [optional.relops] - -// Empty optionals are considered equal to each other and less than non-empty -// optionals. Supports relations between optional<T> and optional<U>, between -// optional<T> and U, and between optional<T> and nullopt. -// -// Note: We're careful to support T having non-bool relationals. - -// Requires: The expression, e.g. "*x == *y" shall be well-formed and its result -// shall be convertible to bool. -// The C++17 (N4606) "Returns:" statements are translated into -// code in an obvious way here, and the original text retained as function docs. -// Returns: If bool(x) != bool(y), false; otherwise if bool(x) == false, true; -// otherwise *x == *y. -template <typename T, typename U> -constexpr auto operator==(const optional<T>& x, const optional<U>& y) - -> decltype(optional_internal::convertible_to_bool(*x == *y)) { - return static_cast<bool>(x) != static_cast<bool>(y) - ? false - : static_cast<bool>(x) == false ? true - : static_cast<bool>(*x == *y); -} - -// Returns: If bool(x) != bool(y), true; otherwise, if bool(x) == false, false; -// otherwise *x != *y. -template <typename T, typename U> -constexpr auto operator!=(const optional<T>& x, const optional<U>& y) - -> decltype(optional_internal::convertible_to_bool(*x != *y)) { - return static_cast<bool>(x) != static_cast<bool>(y) - ? true - : static_cast<bool>(x) == false ? false - : static_cast<bool>(*x != *y); -} -// Returns: If !y, false; otherwise, if !x, true; otherwise *x < *y. -template <typename T, typename U> -constexpr auto operator<(const optional<T>& x, const optional<U>& y) - -> decltype(optional_internal::convertible_to_bool(*x < *y)) { - return !y ? false : !x ? true : static_cast<bool>(*x < *y); -} -// Returns: If !x, false; otherwise, if !y, true; otherwise *x > *y. -template <typename T, typename U> -constexpr auto operator>(const optional<T>& x, const optional<U>& y) - -> decltype(optional_internal::convertible_to_bool(*x > *y)) { - return !x ? false : !y ? true : static_cast<bool>(*x > *y); -} -// Returns: If !x, true; otherwise, if !y, false; otherwise *x <= *y. -template <typename T, typename U> -constexpr auto operator<=(const optional<T>& x, const optional<U>& y) - -> decltype(optional_internal::convertible_to_bool(*x <= *y)) { - return !x ? true : !y ? false : static_cast<bool>(*x <= *y); -} -// Returns: If !y, true; otherwise, if !x, false; otherwise *x >= *y. -template <typename T, typename U> -constexpr auto operator>=(const optional<T>& x, const optional<U>& y) - -> decltype(optional_internal::convertible_to_bool(*x >= *y)) { - return !y ? true : !x ? false : static_cast<bool>(*x >= *y); -} - -// Comparison with nullopt [optional.nullops] -// The C++17 (N4606) "Returns:" statements are used directly here. -template <typename T> -constexpr bool operator==(const optional<T>& x, nullopt_t) noexcept { - return !x; -} -template <typename T> -constexpr bool operator==(nullopt_t, const optional<T>& x) noexcept { - return !x; -} -template <typename T> -constexpr bool operator!=(const optional<T>& x, nullopt_t) noexcept { - return static_cast<bool>(x); -} -template <typename T> -constexpr bool operator!=(nullopt_t, const optional<T>& x) noexcept { - return static_cast<bool>(x); -} -template <typename T> -constexpr bool operator<(const optional<T>&, nullopt_t) noexcept { - return false; -} -template <typename T> -constexpr bool operator<(nullopt_t, const optional<T>& x) noexcept { - return static_cast<bool>(x); -} -template <typename T> -constexpr bool operator<=(const optional<T>& x, nullopt_t) noexcept { - return !x; -} -template <typename T> -constexpr bool operator<=(nullopt_t, const optional<T>&) noexcept { - return true; -} -template <typename T> -constexpr bool operator>(const optional<T>& x, nullopt_t) noexcept { - return static_cast<bool>(x); -} -template <typename T> -constexpr bool operator>(nullopt_t, const optional<T>&) noexcept { - return false; -} -template <typename T> -constexpr bool operator>=(const optional<T>&, nullopt_t) noexcept { - return true; -} -template <typename T> -constexpr bool operator>=(nullopt_t, const optional<T>& x) noexcept { - return !x; -} - -// Comparison with T [optional.comp_with_t] - -// Requires: The expression, e.g. "*x == v" shall be well-formed and its result -// shall be convertible to bool. -// The C++17 (N4606) "Equivalent to:" statements are used directly here. -template <typename T, typename U> -constexpr auto operator==(const optional<T>& x, const U& v) - -> decltype(optional_internal::convertible_to_bool(*x == v)) { - return static_cast<bool>(x) ? static_cast<bool>(*x == v) : false; -} -template <typename T, typename U> -constexpr auto operator==(const U& v, const optional<T>& x) - -> decltype(optional_internal::convertible_to_bool(v == *x)) { - return static_cast<bool>(x) ? static_cast<bool>(v == *x) : false; -} -template <typename T, typename U> -constexpr auto operator!=(const optional<T>& x, const U& v) - -> decltype(optional_internal::convertible_to_bool(*x != v)) { - return static_cast<bool>(x) ? static_cast<bool>(*x != v) : true; -} -template <typename T, typename U> -constexpr auto operator!=(const U& v, const optional<T>& x) - -> decltype(optional_internal::convertible_to_bool(v != *x)) { - return static_cast<bool>(x) ? static_cast<bool>(v != *x) : true; -} -template <typename T, typename U> -constexpr auto operator<(const optional<T>& x, const U& v) - -> decltype(optional_internal::convertible_to_bool(*x < v)) { - return static_cast<bool>(x) ? static_cast<bool>(*x < v) : true; -} -template <typename T, typename U> -constexpr auto operator<(const U& v, const optional<T>& x) - -> decltype(optional_internal::convertible_to_bool(v < *x)) { - return static_cast<bool>(x) ? static_cast<bool>(v < *x) : false; -} -template <typename T, typename U> -constexpr auto operator<=(const optional<T>& x, const U& v) - -> decltype(optional_internal::convertible_to_bool(*x <= v)) { - return static_cast<bool>(x) ? static_cast<bool>(*x <= v) : true; -} -template <typename T, typename U> -constexpr auto operator<=(const U& v, const optional<T>& x) - -> decltype(optional_internal::convertible_to_bool(v <= *x)) { - return static_cast<bool>(x) ? static_cast<bool>(v <= *x) : false; -} -template <typename T, typename U> -constexpr auto operator>(const optional<T>& x, const U& v) - -> decltype(optional_internal::convertible_to_bool(*x > v)) { - return static_cast<bool>(x) ? static_cast<bool>(*x > v) : false; -} -template <typename T, typename U> -constexpr auto operator>(const U& v, const optional<T>& x) - -> decltype(optional_internal::convertible_to_bool(v > *x)) { - return static_cast<bool>(x) ? static_cast<bool>(v > *x) : true; -} -template <typename T, typename U> -constexpr auto operator>=(const optional<T>& x, const U& v) - -> decltype(optional_internal::convertible_to_bool(*x >= v)) { - return static_cast<bool>(x) ? static_cast<bool>(*x >= v) : false; -} -template <typename T, typename U> -constexpr auto operator>=(const U& v, const optional<T>& x) - -> decltype(optional_internal::convertible_to_bool(v >= *x)) { - return static_cast<bool>(x) ? static_cast<bool>(v >= *x) : true; -} - -} // namespace phmap - -namespace std { - -// std::hash specialization for phmap::optional. -template <typename T> -struct hash<phmap::optional<T> > - : phmap::optional_internal::optional_hash_base<T> {}; - -} // namespace std - -#endif - -// ----------------------------------------------------------------------------- -// common.h -// ----------------------------------------------------------------------------- -namespace phmap { -namespace priv { - -template <class, class = void> -struct IsTransparent : std::false_type {}; -template <class T> -struct IsTransparent<T, phmap::void_t<typename T::is_transparent>> - : std::true_type {}; - -template <bool is_transparent> -struct KeyArg -{ - // Transparent. Forward `K`. - template <typename K, typename key_type> - using type = K; -}; - -template <> -struct KeyArg<false> -{ - // Not transparent. Always use `key_type`. - template <typename K, typename key_type> - using type = key_type; -}; - -#ifdef _MSC_VER - #pragma warning(push) - // warning C4820: '6' bytes padding added after data member - #pragma warning(disable : 4820) -#endif - -// The node_handle concept from C++17. -// We specialize node_handle for sets and maps. node_handle_base holds the -// common API of both. -// ----------------------------------------------------------------------- -template <typename PolicyTraits, typename Alloc> -class node_handle_base -{ -protected: - using slot_type = typename PolicyTraits::slot_type; - -public: - using allocator_type = Alloc; - - constexpr node_handle_base() {} - - node_handle_base(node_handle_base&& other) noexcept { - *this = std::move(other); - } - - ~node_handle_base() { destroy(); } - - node_handle_base& operator=(node_handle_base&& other) noexcept { - destroy(); - if (!other.empty()) { - alloc_ = other.alloc_; - PolicyTraits::transfer(alloc(), slot(), other.slot()); - other.reset(); - } - return *this; - } - - bool empty() const noexcept { return !alloc_; } - explicit operator bool() const noexcept { return !empty(); } - allocator_type get_allocator() const { return *alloc_; } - -protected: - friend struct CommonAccess; - - struct transfer_tag_t {}; - node_handle_base(transfer_tag_t, const allocator_type& a, slot_type* s) - : alloc_(a) { - PolicyTraits::transfer(alloc(), slot(), s); - } - - struct move_tag_t {}; - node_handle_base(move_tag_t, const allocator_type& a, slot_type* s) - : alloc_(a) { - PolicyTraits::construct(alloc(), slot(), s); - } - - node_handle_base(const allocator_type& a, slot_type* s) : alloc_(a) { - PolicyTraits::transfer(alloc(), slot(), s); - } - - //node_handle_base(const node_handle_base&) = delete; - //node_handle_base& operator=(const node_handle_base&) = delete; - - void destroy() { - if (!empty()) { - PolicyTraits::destroy(alloc(), slot()); - reset(); - } - } - - void reset() { - assert(alloc_.has_value()); - alloc_ = phmap::nullopt; - } - - slot_type* slot() const { - assert(!empty()); - return reinterpret_cast<slot_type*>(std::addressof(slot_space_)); - } - - allocator_type* alloc() { return std::addressof(*alloc_); } - -private: - phmap::optional<allocator_type> alloc_; - mutable phmap::aligned_storage_t<sizeof(slot_type), alignof(slot_type)> slot_space_; -}; - -#ifdef _MSC_VER - #pragma warning(pop) -#endif - -// For sets. -// --------- -template <typename Policy, typename PolicyTraits, typename Alloc, - typename = void> -class node_handle : public node_handle_base<PolicyTraits, Alloc> -{ - using Base = node_handle_base<PolicyTraits, Alloc>; - -public: - using value_type = typename PolicyTraits::value_type; - - constexpr node_handle() {} - - value_type& value() const { return PolicyTraits::element(this->slot()); } - - value_type& key() const { return PolicyTraits::element(this->slot()); } - -private: - friend struct CommonAccess; - - using Base::Base; -}; - -// For maps. -// --------- -template <typename Policy, typename PolicyTraits, typename Alloc> -class node_handle<Policy, PolicyTraits, Alloc, - phmap::void_t<typename Policy::mapped_type>> - : public node_handle_base<PolicyTraits, Alloc> -{ - using Base = node_handle_base<PolicyTraits, Alloc>; - -public: - using key_type = typename Policy::key_type; - using mapped_type = typename Policy::mapped_type; - - constexpr node_handle() {} - - auto key() const -> decltype(PolicyTraits::key(this->slot())) { - return PolicyTraits::key(this->slot()); - } - - mapped_type& mapped() const { - return PolicyTraits::value(&PolicyTraits::element(this->slot())); - } - -private: - friend struct CommonAccess; - - using Base::Base; -}; - -// Provide access to non-public node-handle functions. -struct CommonAccess -{ - template <typename Node> - static auto GetSlot(const Node& node) -> decltype(node.slot()) { - return node.slot(); - } - - template <typename Node> - static void Destroy(Node* node) { - node->destroy(); - } - - template <typename Node> - static void Reset(Node* node) { - node->reset(); - } - - template <typename T, typename... Args> - static T Make(Args&&... args) { - return T(std::forward<Args>(args)...); - } - - template <typename T, typename... Args> - static T Transfer(Args&&... args) { - return T(typename T::transfer_tag_t{}, std::forward<Args>(args)...); - } - - template <typename T, typename... Args> - static T Move(Args&&... args) { - return T(typename T::move_tag_t{}, std::forward<Args>(args)...); - } -}; - -// Implement the insert_return_type<> concept of C++17. -template <class Iterator, class NodeType> -struct InsertReturnType -{ - Iterator position; - bool inserted; - NodeType node; -}; - -} // namespace priv -} // namespace phmap - - -#ifdef ADDRESS_SANITIZER - #include <sanitizer/asan_interface.h> -#endif - -// --------------------------------------------------------------------------- -// span.h -// --------------------------------------------------------------------------- - -namespace phmap { - -template <typename T> -class Span; - -namespace span_internal { -// A constexpr min function -constexpr size_t Min(size_t a, size_t b) noexcept { return a < b ? a : b; } - -// Wrappers for access to container data pointers. -template <typename C> -constexpr auto GetDataImpl(C& c, char) noexcept // NOLINT(runtime/references) - -> decltype(c.data()) { - return c.data(); -} - -// Before C++17, std::string::data returns a const char* in all cases. -inline char* GetDataImpl(std::string& s, // NOLINT(runtime/references) - int) noexcept { - return &s[0]; -} - -template <typename C> -constexpr auto GetData(C& c) noexcept // NOLINT(runtime/references) - -> decltype(GetDataImpl(c, 0)) { - return GetDataImpl(c, 0); -} - -// Detection idioms for size() and data(). -template <typename C> -using HasSize = - std::is_integral<phmap::decay_t<decltype(std::declval<C&>().size())>>; - -// We want to enable conversion from vector<T*> to Span<const T* const> but -// disable conversion from vector<Derived> to Span<Base>. Here we use -// the fact that U** is convertible to Q* const* if and only if Q is the same -// type or a more cv-qualified version of U. We also decay the result type of -// data() to avoid problems with classes which have a member function data() -// which returns a reference. -template <typename T, typename C> -using HasData = - std::is_convertible<phmap::decay_t<decltype(GetData(std::declval<C&>()))>*, - T* const*>; - -// Extracts value type from a Container -template <typename C> -struct ElementType { - using type = typename phmap::remove_reference_t<C>::value_type; -}; - -template <typename T, size_t N> -struct ElementType<T (&)[N]> { - using type = T; -}; - -template <typename C> -using ElementT = typename ElementType<C>::type; - -template <typename T> -using EnableIfMutable = - typename std::enable_if<!std::is_const<T>::value, int>::type; - -template <typename T> -bool EqualImpl(Span<T> a, Span<T> b) { - static_assert(std::is_const<T>::value, ""); - return std::equal(a.begin(), a.end(), b.begin(), b.end()); -} - -template <typename T> -bool LessThanImpl(Span<T> a, Span<T> b) { - static_assert(std::is_const<T>::value, ""); - return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end()); -} - -// The `IsConvertible` classes here are needed because of the -// `std::is_convertible` bug in libcxx when compiled with GCC. This build -// configuration is used by Android NDK toolchain. Reference link: -// https://bugs.llvm.org/show_bug.cgi?id=27538. -template <typename From, typename To> -struct IsConvertibleHelper { - static std::true_type testval(To); - static std::false_type testval(...); - - using type = decltype(testval(std::declval<From>())); -}; - -template <typename From, typename To> -struct IsConvertible : IsConvertibleHelper<From, To>::type {}; - -// TODO(zhangxy): replace `IsConvertible` with `std::is_convertible` once the -// older version of libcxx is not supported. -template <typename From, typename To> -using EnableIfConvertibleToSpanConst = - typename std::enable_if<IsConvertible<From, Span<const To>>::value>::type; -} // namespace span_internal - -//------------------------------------------------------------------------------ -// Span -//------------------------------------------------------------------------------ -// -// A `Span` is an "array view" type for holding a view of a contiguous data -// array; the `Span` object does not and cannot own such data itself. A span -// provides an easy way to provide overloads for anything operating on -// contiguous sequences without needing to manage pointers and array lengths -// manually. - -// A span is conceptually a pointer (ptr) and a length (size) into an already -// existing array of contiguous memory; the array it represents references the -// elements "ptr[0] .. ptr[size-1]". Passing a properly-constructed `Span` -// instead of raw pointers avoids many issues related to index out of bounds -// errors. -// -// Spans may also be constructed from containers holding contiguous sequences. -// Such containers must supply `data()` and `size() const` methods (e.g -// `std::vector<T>`, `phmap::InlinedVector<T, N>`). All implicit conversions to -// `phmap::Span` from such containers will create spans of type `const T`; -// spans which can mutate their values (of type `T`) must use explicit -// constructors. -// -// A `Span<T>` is somewhat analogous to an `phmap::string_view`, but for an array -// of elements of type `T`. A user of `Span` must ensure that the data being -// pointed to outlives the `Span` itself. -// -// You can construct a `Span<T>` in several ways: -// -// * Explicitly from a reference to a container type -// * Explicitly from a pointer and size -// * Implicitly from a container type (but only for spans of type `const T`) -// * Using the `MakeSpan()` or `MakeConstSpan()` factory functions. -// -// Examples: -// -// // Construct a Span explicitly from a container: -// std::vector<int> v = {1, 2, 3, 4, 5}; -// auto span = phmap::Span<const int>(v); -// -// // Construct a Span explicitly from a C-style array: -// int a[5] = {1, 2, 3, 4, 5}; -// auto span = phmap::Span<const int>(a); -// -// // Construct a Span implicitly from a container -// void MyRoutine(phmap::Span<const int> a) { -// ... -// } -// std::vector v = {1,2,3,4,5}; -// MyRoutine(v) // convert to Span<const T> -// -// Note that `Span` objects, in addition to requiring that the memory they -// point to remains alive, must also ensure that such memory does not get -// reallocated. Therefore, to avoid undefined behavior, containers with -// associated span views should not invoke operations that may reallocate memory -// (such as resizing) or invalidate iterators into the container. -// -// One common use for a `Span` is when passing arguments to a routine that can -// accept a variety of array types (e.g. a `std::vector`, `phmap::InlinedVector`, -// a C-style array, etc.). Instead of creating overloads for each case, you -// can simply specify a `Span` as the argument to such a routine. -// -// Example: -// -// void MyRoutine(phmap::Span<const int> a) { -// ... -// } -// -// std::vector v = {1,2,3,4,5}; -// MyRoutine(v); -// -// phmap::InlinedVector<int, 4> my_inline_vector; -// MyRoutine(my_inline_vector); -// -// // Explicit constructor from pointer,size -// int* my_array = new int[10]; -// MyRoutine(phmap::Span<const int>(my_array, 10)); -template <typename T> -class Span -{ -private: - // Used to determine whether a Span can be constructed from a container of - // type C. - template <typename C> - using EnableIfConvertibleFrom = - typename std::enable_if<span_internal::HasData<T, C>::value && - span_internal::HasSize<C>::value>::type; - - // Used to SFINAE-enable a function when the slice elements are const. - template <typename U> - using EnableIfConstView = - typename std::enable_if<std::is_const<T>::value, U>::type; - - // Used to SFINAE-enable a function when the slice elements are mutable. - template <typename U> - using EnableIfMutableView = - typename std::enable_if<!std::is_const<T>::value, U>::type; - -public: - using value_type = phmap::remove_cv_t<T>; - using pointer = T*; - using const_pointer = const T*; - using reference = T&; - using const_reference = const T&; - using iterator = pointer; - using const_iterator = const_pointer; - using reverse_iterator = std::reverse_iterator<iterator>; - using const_reverse_iterator = std::reverse_iterator<const_iterator>; - using size_type = size_t; - using difference_type = ptrdiff_t; - - static const size_type npos = ~(size_type(0)); - - constexpr Span() noexcept : Span(nullptr, 0) {} - constexpr Span(pointer array, size_type lgth) noexcept - : ptr_(array), len_(lgth) {} - - // Implicit conversion constructors - template <size_t N> - constexpr Span(T (&a)[N]) noexcept // NOLINT(runtime/explicit) - : Span(a, N) {} - - // Explicit reference constructor for a mutable `Span<T>` type. Can be - // replaced with MakeSpan() to infer the type parameter. - template <typename V, typename = EnableIfConvertibleFrom<V>, - typename = EnableIfMutableView<V>> - explicit Span(V& v) noexcept // NOLINT(runtime/references) - : Span(span_internal::GetData(v), v.size()) {} - - // Implicit reference constructor for a read-only `Span<const T>` type - template <typename V, typename = EnableIfConvertibleFrom<V>, - typename = EnableIfConstView<V>> - constexpr Span(const V& v) noexcept // NOLINT(runtime/explicit) - : Span(span_internal::GetData(v), v.size()) {} - - // Implicit constructor from an initializer list, making it possible to pass a - // brace-enclosed initializer list to a function expecting a `Span`. Such - // spans constructed from an initializer list must be of type `Span<const T>`. - // - // void Process(phmap::Span<const int> x); - // Process({1, 2, 3}); - // - // Note that as always the array referenced by the span must outlive the span. - // Since an initializer list constructor acts as if it is fed a temporary - // array (cf. C++ standard [dcl.init.list]/5), it's safe to use this - // constructor only when the `std::initializer_list` itself outlives the span. - // In order to meet this requirement it's sufficient to ensure that neither - // the span nor a copy of it is used outside of the expression in which it's - // created: - // - // // Assume that this function uses the array directly, not retaining any - // // copy of the span or pointer to any of its elements. - // void Process(phmap::Span<const int> ints); - // - // // Okay: the std::initializer_list<int> will reference a temporary array - // // that isn't destroyed until after the call to Process returns. - // Process({ 17, 19 }); - // - // // Not okay: the storage used by the std::initializer_list<int> is not - // // allowed to be referenced after the first line. - // phmap::Span<const int> ints = { 17, 19 }; - // Process(ints); - // - // // Not okay for the same reason as above: even when the elements of the - // // initializer list expression are not temporaries the underlying array - // // is, so the initializer list must still outlive the span. - // const int foo = 17; - // phmap::Span<const int> ints = { foo }; - // Process(ints); - // - template <typename LazyT = T, - typename = EnableIfConstView<LazyT>> - Span( - std::initializer_list<value_type> v) noexcept // NOLINT(runtime/explicit) - : Span(v.begin(), v.size()) {} - - // Accessors - - // Span::data() - // - // Returns a pointer to the span's underlying array of data (which is held - // outside the span). - constexpr pointer data() const noexcept { return ptr_; } - - // Span::size() - // - // Returns the size of this span. - constexpr size_type size() const noexcept { return len_; } - - // Span::length() - // - // Returns the length (size) of this span. - constexpr size_type length() const noexcept { return size(); } - - // Span::empty() - // - // Returns a boolean indicating whether or not this span is considered empty. - constexpr bool empty() const noexcept { return size() == 0; } - - // Span::operator[] - // - // Returns a reference to the i'th element of this span. - constexpr reference operator[](size_type i) const noexcept { - // MSVC 2015 accepts this as constexpr, but not ptr_[i] - return *(data() + i); - } - - // Span::at() - // - // Returns a reference to the i'th element of this span. - constexpr reference at(size_type i) const { - return PHMAP_PREDICT_TRUE(i < size()) // - ? *(data() + i) - : (base_internal::ThrowStdOutOfRange( - "Span::at failed bounds check"), - *(data() + i)); - } - - // Span::front() - // - // Returns a reference to the first element of this span. - constexpr reference front() const noexcept { - return PHMAP_ASSERT(size() > 0), *data(); - } - - // Span::back() - // - // Returns a reference to the last element of this span. - constexpr reference back() const noexcept { - return PHMAP_ASSERT(size() > 0), *(data() + size() - 1); - } - - // Span::begin() - // - // Returns an iterator to the first element of this span. - constexpr iterator begin() const noexcept { return data(); } - - // Span::cbegin() - // - // Returns a const iterator to the first element of this span. - constexpr const_iterator cbegin() const noexcept { return begin(); } - - // Span::end() - // - // Returns an iterator to the last element of this span. - constexpr iterator end() const noexcept { return data() + size(); } - - // Span::cend() - // - // Returns a const iterator to the last element of this span. - constexpr const_iterator cend() const noexcept { return end(); } - - // Span::rbegin() - // - // Returns a reverse iterator starting at the last element of this span. - constexpr reverse_iterator rbegin() const noexcept { - return reverse_iterator(end()); - } - - // Span::crbegin() - // - // Returns a reverse const iterator starting at the last element of this span. - constexpr const_reverse_iterator crbegin() const noexcept { return rbegin(); } - - // Span::rend() - // - // Returns a reverse iterator starting at the first element of this span. - constexpr reverse_iterator rend() const noexcept { - return reverse_iterator(begin()); - } - - // Span::crend() - // - // Returns a reverse iterator starting at the first element of this span. - constexpr const_reverse_iterator crend() const noexcept { return rend(); } - - // Span mutations - - // Span::remove_prefix() - // - // Removes the first `n` elements from the span. - void remove_prefix(size_type n) noexcept { - assert(size() >= n); - ptr_ += n; - len_ -= n; - } - - // Span::remove_suffix() - // - // Removes the last `n` elements from the span. - void remove_suffix(size_type n) noexcept { - assert(size() >= n); - len_ -= n; - } - - // Span::subspan() - // - // Returns a `Span` starting at element `pos` and of length `len`. Both `pos` - // and `len` are of type `size_type` and thus non-negative. Parameter `pos` - // must be <= size(). Any `len` value that points past the end of the span - // will be trimmed to at most size() - `pos`. A default `len` value of `npos` - // ensures the returned subspan continues until the end of the span. - // - // Examples: - // - // std::vector<int> vec = {10, 11, 12, 13}; - // phmap::MakeSpan(vec).subspan(1, 2); // {11, 12} - // phmap::MakeSpan(vec).subspan(2, 8); // {12, 13} - // phmap::MakeSpan(vec).subspan(1); // {11, 12, 13} - // phmap::MakeSpan(vec).subspan(4); // {} - // phmap::MakeSpan(vec).subspan(5); // throws std::out_of_range - constexpr Span subspan(size_type pos = 0, size_type len = npos) const { - return (pos <= size()) - ? Span(data() + pos, span_internal::Min(size() - pos, len)) - : (base_internal::ThrowStdOutOfRange("pos > size()"), Span()); - } - - // Span::first() - // - // Returns a `Span` containing first `len` elements. Parameter `len` is of - // type `size_type` and thus non-negative. `len` value must be <= size(). - // - // Examples: - // - // std::vector<int> vec = {10, 11, 12, 13}; - // phmap::MakeSpan(vec).first(1); // {10} - // phmap::MakeSpan(vec).first(3); // {10, 11, 12} - // phmap::MakeSpan(vec).first(5); // throws std::out_of_range - constexpr Span first(size_type len) const { - return (len <= size()) - ? Span(data(), len) - : (base_internal::ThrowStdOutOfRange("len > size()"), Span()); - } - - // Span::last() - // - // Returns a `Span` containing last `len` elements. Parameter `len` is of - // type `size_type` and thus non-negative. `len` value must be <= size(). - // - // Examples: - // - // std::vector<int> vec = {10, 11, 12, 13}; - // phmap::MakeSpan(vec).last(1); // {13} - // phmap::MakeSpan(vec).last(3); // {11, 12, 13} - // phmap::MakeSpan(vec).last(5); // throws std::out_of_range - constexpr Span last(size_type len) const { - return (len <= size()) - ? Span(size() - len + data(), len) - : (base_internal::ThrowStdOutOfRange("len > size()"), Span()); - } - - // Support for phmap::Hash. - template <typename H> - friend H AbslHashValue(H h, Span v) { - return H::combine(H::combine_contiguous(std::move(h), v.data(), v.size()), - v.size()); - } - -private: - pointer ptr_; - size_type len_; -}; - -template <typename T> -const typename Span<T>::size_type Span<T>::npos; - -// Span relationals - -// Equality is compared element-by-element, while ordering is lexicographical. -// We provide three overloads for each operator to cover any combination on the -// left or right hand side of mutable Span<T>, read-only Span<const T>, and -// convertible-to-read-only Span<T>. -// TODO(zhangxy): Due to MSVC overload resolution bug with partial ordering -// template functions, 5 overloads per operator is needed as a workaround. We -// should update them to 3 overloads per operator using non-deduced context like -// string_view, i.e. -// - (Span<T>, Span<T>) -// - (Span<T>, non_deduced<Span<const T>>) -// - (non_deduced<Span<const T>>, Span<T>) - -// operator== -template <typename T> -bool operator==(Span<T> a, Span<T> b) { - return span_internal::EqualImpl<const T>(a, b); -} - -template <typename T> -bool operator==(Span<const T> a, Span<T> b) { - return span_internal::EqualImpl<const T>(a, b); -} - -template <typename T> -bool operator==(Span<T> a, Span<const T> b) { - return span_internal::EqualImpl<const T>(a, b); -} - -template <typename T, typename U, - typename = span_internal::EnableIfConvertibleToSpanConst<U, T>> -bool operator==(const U& a, Span<T> b) { - return span_internal::EqualImpl<const T>(a, b); -} - -template <typename T, typename U, - typename = span_internal::EnableIfConvertibleToSpanConst<U, T>> -bool operator==(Span<T> a, const U& b) { - return span_internal::EqualImpl<const T>(a, b); -} - -// operator!= -template <typename T> -bool operator!=(Span<T> a, Span<T> b) { - return !(a == b); -} - -template <typename T> -bool operator!=(Span<const T> a, Span<T> b) { - return !(a == b); -} - -template <typename T> -bool operator!=(Span<T> a, Span<const T> b) { - return !(a == b); -} - -template <typename T, typename U, - typename = span_internal::EnableIfConvertibleToSpanConst<U, T>> -bool operator!=(const U& a, Span<T> b) { - return !(a == b); -} - -template <typename T, typename U, - typename = span_internal::EnableIfConvertibleToSpanConst<U, T>> -bool operator!=(Span<T> a, const U& b) { - return !(a == b); -} - -// operator< -template <typename T> -bool operator<(Span<T> a, Span<T> b) { - return span_internal::LessThanImpl<const T>(a, b); -} - -template <typename T> -bool operator<(Span<const T> a, Span<T> b) { - return span_internal::LessThanImpl<const T>(a, b); -} - -template <typename T> -bool operator<(Span<T> a, Span<const T> b) { - return span_internal::LessThanImpl<const T>(a, b); -} - -template <typename T, typename U, - typename = span_internal::EnableIfConvertibleToSpanConst<U, T>> -bool operator<(const U& a, Span<T> b) { - return span_internal::LessThanImpl<const T>(a, b); -} - -template <typename T, typename U, - typename = span_internal::EnableIfConvertibleToSpanConst<U, T>> -bool operator<(Span<T> a, const U& b) { - return span_internal::LessThanImpl<const T>(a, b); -} - -// operator> -template <typename T> -bool operator>(Span<T> a, Span<T> b) { - return b < a; -} - -template <typename T> -bool operator>(Span<const T> a, Span<T> b) { - return b < a; -} - -template <typename T> -bool operator>(Span<T> a, Span<const T> b) { - return b < a; -} - -template <typename T, typename U, - typename = span_internal::EnableIfConvertibleToSpanConst<U, T>> -bool operator>(const U& a, Span<T> b) { - return b < a; -} - -template <typename T, typename U, - typename = span_internal::EnableIfConvertibleToSpanConst<U, T>> -bool operator>(Span<T> a, const U& b) { - return b < a; -} - -// operator<= -template <typename T> -bool operator<=(Span<T> a, Span<T> b) { - return !(b < a); -} - -template <typename T> -bool operator<=(Span<const T> a, Span<T> b) { - return !(b < a); -} - -template <typename T> -bool operator<=(Span<T> a, Span<const T> b) { - return !(b < a); -} - -template <typename T, typename U, - typename = span_internal::EnableIfConvertibleToSpanConst<U, T>> -bool operator<=(const U& a, Span<T> b) { - return !(b < a); -} - -template <typename T, typename U, - typename = span_internal::EnableIfConvertibleToSpanConst<U, T>> -bool operator<=(Span<T> a, const U& b) { - return !(b < a); -} - -// operator>= -template <typename T> -bool operator>=(Span<T> a, Span<T> b) { - return !(a < b); -} - -template <typename T> -bool operator>=(Span<const T> a, Span<T> b) { - return !(a < b); -} - -template <typename T> -bool operator>=(Span<T> a, Span<const T> b) { - return !(a < b); -} - -template <typename T, typename U, - typename = span_internal::EnableIfConvertibleToSpanConst<U, T>> -bool operator>=(const U& a, Span<T> b) { - return !(a < b); -} - -template <typename T, typename U, - typename = span_internal::EnableIfConvertibleToSpanConst<U, T>> -bool operator>=(Span<T> a, const U& b) { - return !(a < b); -} - -// MakeSpan() -// -// Constructs a mutable `Span<T>`, deducing `T` automatically from either a -// container or pointer+size. -// -// Because a read-only `Span<const T>` is implicitly constructed from container -// types regardless of whether the container itself is a const container, -// constructing mutable spans of type `Span<T>` from containers requires -// explicit constructors. The container-accepting version of `MakeSpan()` -// deduces the type of `T` by the constness of the pointer received from the -// container's `data()` member. Similarly, the pointer-accepting version returns -// a `Span<const T>` if `T` is `const`, and a `Span<T>` otherwise. -// -// Examples: -// -// void MyRoutine(phmap::Span<MyComplicatedType> a) { -// ... -// }; -// // my_vector is a container of non-const types -// std::vector<MyComplicatedType> my_vector; -// -// // Constructing a Span implicitly attempts to create a Span of type -// // `Span<const T>` -// MyRoutine(my_vector); // error, type mismatch -// -// // Explicitly constructing the Span is verbose -// MyRoutine(phmap::Span<MyComplicatedType>(my_vector)); -// -// // Use MakeSpan() to make an phmap::Span<T> -// MyRoutine(phmap::MakeSpan(my_vector)); -// -// // Construct a span from an array ptr+size -// phmap::Span<T> my_span() { -// return phmap::MakeSpan(&array[0], num_elements_); -// } -// -template <int&... ExplicitArgumentBarrier, typename T> -constexpr Span<T> MakeSpan(T* ptr, size_t size) noexcept { - return Span<T>(ptr, size); -} - -template <int&... ExplicitArgumentBarrier, typename T> -Span<T> MakeSpan(T* begin, T* end) noexcept { - return PHMAP_ASSERT(begin <= end), Span<T>(begin, end - begin); -} - -template <int&... ExplicitArgumentBarrier, typename C> -constexpr auto MakeSpan(C& c) noexcept // NOLINT(runtime/references) - -> decltype(phmap::MakeSpan(span_internal::GetData(c), c.size())) { - return MakeSpan(span_internal::GetData(c), c.size()); -} - -template <int&... ExplicitArgumentBarrier, typename T, size_t N> -constexpr Span<T> MakeSpan(T (&array)[N]) noexcept { - return Span<T>(array, N); -} - -// MakeConstSpan() -// -// Constructs a `Span<const T>` as with `MakeSpan`, deducing `T` automatically, -// but always returning a `Span<const T>`. -// -// Examples: -// -// void ProcessInts(phmap::Span<const int> some_ints); -// -// // Call with a pointer and size. -// int array[3] = { 0, 0, 0 }; -// ProcessInts(phmap::MakeConstSpan(&array[0], 3)); -// -// // Call with a [begin, end) pair. -// ProcessInts(phmap::MakeConstSpan(&array[0], &array[3])); -// -// // Call directly with an array. -// ProcessInts(phmap::MakeConstSpan(array)); -// -// // Call with a contiguous container. -// std::vector<int> some_ints = ...; -// ProcessInts(phmap::MakeConstSpan(some_ints)); -// ProcessInts(phmap::MakeConstSpan(std::vector<int>{ 0, 0, 0 })); -// -template <int&... ExplicitArgumentBarrier, typename T> -constexpr Span<const T> MakeConstSpan(T* ptr, size_t size) noexcept { - return Span<const T>(ptr, size); -} - -template <int&... ExplicitArgumentBarrier, typename T> -Span<const T> MakeConstSpan(T* begin, T* end) noexcept { - return PHMAP_ASSERT(begin <= end), Span<const T>(begin, end - begin); -} - -template <int&... ExplicitArgumentBarrier, typename C> -constexpr auto MakeConstSpan(const C& c) noexcept -> decltype(MakeSpan(c)) { - return MakeSpan(c); -} - -template <int&... ExplicitArgumentBarrier, typename T, size_t N> -constexpr Span<const T> MakeConstSpan(const T (&array)[N]) noexcept { - return Span<const T>(array, N); -} -} // namespace phmap - -// --------------------------------------------------------------------------- -// layout.h -// --------------------------------------------------------------------------- -#if defined(__GXX_RTTI) - #define PHMAP_INTERNAL_HAS_CXA_DEMANGLE -#endif - -#ifdef PHMAP_INTERNAL_HAS_CXA_DEMANGLE - #include <cxxabi.h> -#endif - -namespace phmap { -namespace priv { - -// A type wrapper that instructs `Layout` to use the specific alignment for the -// array. `Layout<..., Aligned<T, N>, ...>` has exactly the same API -// and behavior as `Layout<..., T, ...>` except that the first element of the -// array of `T` is aligned to `N` (the rest of the elements follow without -// padding). -// -// Requires: `N >= alignof(T)` and `N` is a power of 2. -template <class T, size_t N> -struct Aligned; - -namespace internal_layout { - -template <class T> -struct NotAligned {}; - -template <class T, size_t N> -struct NotAligned<const Aligned<T, N>> { - static_assert(sizeof(T) == 0, "Aligned<T, N> cannot be const-qualified"); -}; - -template <size_t> -using IntToSize = size_t; - -template <class> -using TypeToSize = size_t; - -template <class T> -struct Type : NotAligned<T> { - using type = T; -}; - -template <class T, size_t N> -struct Type<Aligned<T, N>> { - using type = T; -}; - -template <class T> -struct SizeOf : NotAligned<T>, std::integral_constant<size_t, sizeof(T)> {}; - -template <class T, size_t N> -struct SizeOf<Aligned<T, N>> : std::integral_constant<size_t, sizeof(T)> {}; - -// Note: workaround for https://gcc.gnu.org/PR88115 -template <class T> -struct AlignOf : NotAligned<T> { - static constexpr size_t value = alignof(T); -}; - -template <class T, size_t N> -struct AlignOf<Aligned<T, N>> { - static_assert(N % alignof(T) == 0, - "Custom alignment can't be lower than the type's alignment"); - static constexpr size_t value = N; -}; - -// Does `Ts...` contain `T`? -template <class T, class... Ts> -using Contains = phmap::disjunction<std::is_same<T, Ts>...>; - -template <class From, class To> -using CopyConst = - typename std::conditional<std::is_const<From>::value, const To, To>::type; - -// Note: We're not qualifying this with phmap:: because it doesn't compile under -// MSVC. -template <class T> -using SliceType = Span<T>; - -// This namespace contains no types. It prevents functions defined in it from -// being found by ADL. -namespace adl_barrier { - -template <class Needle, class... Ts> -constexpr size_t Find(Needle, Needle, Ts...) { - static_assert(!Contains<Needle, Ts...>(), "Duplicate element type"); - return 0; -} - -template <class Needle, class T, class... Ts> -constexpr size_t Find(Needle, T, Ts...) { - return adl_barrier::Find(Needle(), Ts()...) + 1; -} - -constexpr bool IsPow2(size_t n) { return !(n & (n - 1)); } - -// Returns `q * m` for the smallest `q` such that `q * m >= n`. -// Requires: `m` is a power of two. It's enforced by IsLegalElementType below. -constexpr size_t Align(size_t n, size_t m) { return (n + m - 1) & ~(m - 1); } - -constexpr size_t Min(size_t a, size_t b) { return b < a ? b : a; } - -constexpr size_t Max(size_t a) { return a; } - -template <class... Ts> -constexpr size_t Max(size_t a, size_t b, Ts... rest) { - return adl_barrier::Max(b < a ? a : b, rest...); -} - -} // namespace adl_barrier - -template <bool C> -using EnableIf = typename std::enable_if<C, int>::type; - -// Can `T` be a template argument of `Layout`? -// --------------------------------------------------------------------------- -template <class T> -using IsLegalElementType = std::integral_constant< - bool, !std::is_reference<T>::value && !std::is_volatile<T>::value && - !std::is_reference<typename Type<T>::type>::value && - !std::is_volatile<typename Type<T>::type>::value && - adl_barrier::IsPow2(AlignOf<T>::value)>; - -template <class Elements, class SizeSeq, class OffsetSeq> -class LayoutImpl; - -// --------------------------------------------------------------------------- -// Public base class of `Layout` and the result type of `Layout::Partial()`. -// -// `Elements...` contains all template arguments of `Layout` that created this -// instance. -// -// `SizeSeq...` is `[0, NumSizes)` where `NumSizes` is the number of arguments -// passed to `Layout::Partial()` or `Layout::Layout()`. -// -// `OffsetSeq...` is `[0, NumOffsets)` where `NumOffsets` is -// `Min(sizeof...(Elements), NumSizes + 1)` (the number of arrays for which we -// can compute offsets). -// --------------------------------------------------------------------------- -template <class... Elements, size_t... SizeSeq, size_t... OffsetSeq> -class LayoutImpl<std::tuple<Elements...>, phmap::index_sequence<SizeSeq...>, - phmap::index_sequence<OffsetSeq...>> -{ -private: - static_assert(sizeof...(Elements) > 0, "At least one field is required"); - static_assert(phmap::conjunction<IsLegalElementType<Elements>...>::value, - "Invalid element type (see IsLegalElementType)"); - - enum { - NumTypes = sizeof...(Elements), - NumSizes = sizeof...(SizeSeq), - NumOffsets = sizeof...(OffsetSeq), - }; - - // These are guaranteed by `Layout`. - static_assert(NumOffsets == adl_barrier::Min(NumTypes, NumSizes + 1), - "Internal error"); - static_assert(NumTypes > 0, "Internal error"); - - // Returns the index of `T` in `Elements...`. Results in a compilation error - // if `Elements...` doesn't contain exactly one instance of `T`. - template <class T> - static constexpr size_t ElementIndex() { - static_assert(Contains<Type<T>, Type<typename Type<Elements>::type>...>(), - "Type not found"); - return adl_barrier::Find(Type<T>(), - Type<typename Type<Elements>::type>()...); - } - - template <size_t N> - using ElementAlignment = - AlignOf<typename std::tuple_element<N, std::tuple<Elements...>>::type>; - -public: - // Element types of all arrays packed in a tuple. - using ElementTypes = std::tuple<typename Type<Elements>::type...>; - - // Element type of the Nth array. - template <size_t N> - using ElementType = typename std::tuple_element<N, ElementTypes>::type; - - constexpr explicit LayoutImpl(IntToSize<SizeSeq>... sizes) - : size_{sizes...} {} - - // Alignment of the layout, equal to the strictest alignment of all elements. - // All pointers passed to the methods of layout must be aligned to this value. - static constexpr size_t Alignment() { - return adl_barrier::Max(AlignOf<Elements>::value...); - } - - // Offset in bytes of the Nth array. - // - // // int[3], 4 bytes of padding, double[4]. - // Layout<int, double> x(3, 4); - // assert(x.Offset<0>() == 0); // The ints starts from 0. - // assert(x.Offset<1>() == 16); // The doubles starts from 16. - // - // Requires: `N <= NumSizes && N < sizeof...(Ts)`. - template <size_t N, EnableIf<N == 0> = 0> - constexpr size_t Offset() const { - return 0; - } - - template <size_t N, EnableIf<N != 0> = 0> - constexpr size_t Offset() const { - static_assert(N < NumOffsets, "Index out of bounds"); - return adl_barrier::Align( - Offset<N - 1>() + SizeOf<ElementType<N - 1>>() * size_[N - 1], - ElementAlignment<N>::value); - } - - // Offset in bytes of the array with the specified element type. There must - // be exactly one such array and its zero-based index must be at most - // `NumSizes`. - // - // // int[3], 4 bytes of padding, double[4]. - // Layout<int, double> x(3, 4); - // assert(x.Offset<int>() == 0); // The ints starts from 0. - // assert(x.Offset<double>() == 16); // The doubles starts from 16. - template <class T> - constexpr size_t Offset() const { - return Offset<ElementIndex<T>()>(); - } - - // Offsets in bytes of all arrays for which the offsets are known. - constexpr std::array<size_t, NumOffsets> Offsets() const { - return {{Offset<OffsetSeq>()...}}; - } - - // The number of elements in the Nth array. This is the Nth argument of - // `Layout::Partial()` or `Layout::Layout()` (zero-based). - // - // // int[3], 4 bytes of padding, double[4]. - // Layout<int, double> x(3, 4); - // assert(x.Size<0>() == 3); - // assert(x.Size<1>() == 4); - // - // Requires: `N < NumSizes`. - template <size_t N> - constexpr size_t Size() const { - static_assert(N < NumSizes, "Index out of bounds"); - return size_[N]; - } - - // The number of elements in the array with the specified element type. - // There must be exactly one such array and its zero-based index must be - // at most `NumSizes`. - // - // // int[3], 4 bytes of padding, double[4]. - // Layout<int, double> x(3, 4); - // assert(x.Size<int>() == 3); - // assert(x.Size<double>() == 4); - template <class T> - constexpr size_t Size() const { - return Size<ElementIndex<T>()>(); - } - - // The number of elements of all arrays for which they are known. - constexpr std::array<size_t, NumSizes> Sizes() const { - return {{Size<SizeSeq>()...}}; - } - - // Pointer to the beginning of the Nth array. - // - // `Char` must be `[const] [signed|unsigned] char`. - // - // // int[3], 4 bytes of padding, double[4]. - // Layout<int, double> x(3, 4); - // unsigned char* p = new unsigned char[x.AllocSize()]; - // int* ints = x.Pointer<0>(p); - // double* doubles = x.Pointer<1>(p); - // - // Requires: `N <= NumSizes && N < sizeof...(Ts)`. - // Requires: `p` is aligned to `Alignment()`. - template <size_t N, class Char> - CopyConst<Char, ElementType<N>>* Pointer(Char* p) const { - using C = typename std::remove_const<Char>::type; - static_assert( - std::is_same<C, char>() || std::is_same<C, unsigned char>() || - std::is_same<C, signed char>(), - "The argument must be a pointer to [const] [signed|unsigned] char"); - constexpr size_t alignment = Alignment(); - (void)alignment; - assert(reinterpret_cast<uintptr_t>(p) % alignment == 0); - return reinterpret_cast<CopyConst<Char, ElementType<N>>*>(p + Offset<N>()); - } - - // Pointer to the beginning of the array with the specified element type. - // There must be exactly one such array and its zero-based index must be at - // most `NumSizes`. - // - // `Char` must be `[const] [signed|unsigned] char`. - // - // // int[3], 4 bytes of padding, double[4]. - // Layout<int, double> x(3, 4); - // unsigned char* p = new unsigned char[x.AllocSize()]; - // int* ints = x.Pointer<int>(p); - // double* doubles = x.Pointer<double>(p); - // - // Requires: `p` is aligned to `Alignment()`. - template <class T, class Char> - CopyConst<Char, T>* Pointer(Char* p) const { - return Pointer<ElementIndex<T>()>(p); - } - - // Pointers to all arrays for which pointers are known. - // - // `Char` must be `[const] [signed|unsigned] char`. - // - // // int[3], 4 bytes of padding, double[4]. - // Layout<int, double> x(3, 4); - // unsigned char* p = new unsigned char[x.AllocSize()]; - // - // int* ints; - // double* doubles; - // std::tie(ints, doubles) = x.Pointers(p); - // - // Requires: `p` is aligned to `Alignment()`. - // - // Note: We're not using ElementType alias here because it does not compile - // under MSVC. - template <class Char> - std::tuple<CopyConst< - Char, typename std::tuple_element<OffsetSeq, ElementTypes>::type>*...> - Pointers(Char* p) const { - return std::tuple<CopyConst<Char, ElementType<OffsetSeq>>*...>( - Pointer<OffsetSeq>(p)...); - } - - // The Nth array. - // - // `Char` must be `[const] [signed|unsigned] char`. - // - // // int[3], 4 bytes of padding, double[4]. - // Layout<int, double> x(3, 4); - // unsigned char* p = new unsigned char[x.AllocSize()]; - // Span<int> ints = x.Slice<0>(p); - // Span<double> doubles = x.Slice<1>(p); - // - // Requires: `N < NumSizes`. - // Requires: `p` is aligned to `Alignment()`. - template <size_t N, class Char> - SliceType<CopyConst<Char, ElementType<N>>> Slice(Char* p) const { - return SliceType<CopyConst<Char, ElementType<N>>>(Pointer<N>(p), Size<N>()); - } - - // The array with the specified element type. There must be exactly one - // such array and its zero-based index must be less than `NumSizes`. - // - // `Char` must be `[const] [signed|unsigned] char`. - // - // // int[3], 4 bytes of padding, double[4]. - // Layout<int, double> x(3, 4); - // unsigned char* p = new unsigned char[x.AllocSize()]; - // Span<int> ints = x.Slice<int>(p); - // Span<double> doubles = x.Slice<double>(p); - // - // Requires: `p` is aligned to `Alignment()`. - template <class T, class Char> - SliceType<CopyConst<Char, T>> Slice(Char* p) const { - return Slice<ElementIndex<T>()>(p); - } - - // All arrays with known sizes. - // - // `Char` must be `[const] [signed|unsigned] char`. - // - // // int[3], 4 bytes of padding, double[4]. - // Layout<int, double> x(3, 4); - // unsigned char* p = new unsigned char[x.AllocSize()]; - // - // Span<int> ints; - // Span<double> doubles; - // std::tie(ints, doubles) = x.Slices(p); - // - // Requires: `p` is aligned to `Alignment()`. - // - // Note: We're not using ElementType alias here because it does not compile - // under MSVC. - template <class Char> - std::tuple<SliceType<CopyConst< - Char, typename std::tuple_element<SizeSeq, ElementTypes>::type>>...> - Slices(Char* p) const { - // Workaround for https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63875 (fixed - // in 6.1). - (void)p; - return std::tuple<SliceType<CopyConst<Char, ElementType<SizeSeq>>>...>( - Slice<SizeSeq>(p)...); - } - - // The size of the allocation that fits all arrays. - // - // // int[3], 4 bytes of padding, double[4]. - // Layout<int, double> x(3, 4); - // unsigned char* p = new unsigned char[x.AllocSize()]; // 48 bytes - // - // Requires: `NumSizes == sizeof...(Ts)`. - constexpr size_t AllocSize() const { - static_assert(NumTypes == NumSizes, "You must specify sizes of all fields"); - return Offset<NumTypes - 1>() + - SizeOf<ElementType<NumTypes - 1>>() * size_[NumTypes - 1]; - } - - // If built with --config=asan, poisons padding bytes (if any) in the - // allocation. The pointer must point to a memory block at least - // `AllocSize()` bytes in length. - // - // `Char` must be `[const] [signed|unsigned] char`. - // - // Requires: `p` is aligned to `Alignment()`. - template <class Char, size_t N = NumOffsets - 1, EnableIf<N == 0> = 0> - void PoisonPadding(const Char* p) const { - Pointer<0>(p); // verify the requirements on `Char` and `p` - } - - template <class Char, size_t N = NumOffsets - 1, EnableIf<N != 0> = 0> - void PoisonPadding(const Char* p) const { - static_assert(N < NumOffsets, "Index out of bounds"); - (void)p; -#ifdef ADDRESS_SANITIZER - PoisonPadding<Char, N - 1>(p); - // The `if` is an optimization. It doesn't affect the observable behaviour. - if (ElementAlignment<N - 1>::value % ElementAlignment<N>::value) { - size_t start = - Offset<N - 1>() + SizeOf<ElementType<N - 1>>() * size_[N - 1]; - ASAN_POISON_MEMORY_REGION(p + start, Offset<N>() - start); - } -#endif - } - -private: - // Arguments of `Layout::Partial()` or `Layout::Layout()`. - size_t size_[NumSizes > 0 ? NumSizes : 1]; -}; - -template <size_t NumSizes, class... Ts> -using LayoutType = LayoutImpl< - std::tuple<Ts...>, phmap::make_index_sequence<NumSizes>, - phmap::make_index_sequence<adl_barrier::Min(sizeof...(Ts), NumSizes + 1)>>; - -} // namespace internal_layout - -// --------------------------------------------------------------------------- -// Descriptor of arrays of various types and sizes laid out in memory one after -// another. See the top of the file for documentation. -// -// Check out the public API of internal_layout::LayoutImpl above. The type is -// internal to the library but its methods are public, and they are inherited -// by `Layout`. -// --------------------------------------------------------------------------- -template <class... Ts> -class Layout : public internal_layout::LayoutType<sizeof...(Ts), Ts...> -{ -public: - static_assert(sizeof...(Ts) > 0, "At least one field is required"); - static_assert( - phmap::conjunction<internal_layout::IsLegalElementType<Ts>...>::value, - "Invalid element type (see IsLegalElementType)"); - - template <size_t NumSizes> - using PartialType = internal_layout::LayoutType<NumSizes, Ts...>; - - template <class... Sizes> - static constexpr PartialType<sizeof...(Sizes)> Partial(Sizes&&... sizes) { - static_assert(sizeof...(Sizes) <= sizeof...(Ts), ""); - return PartialType<sizeof...(Sizes)>(phmap::forward<Sizes>(sizes)...); - } - - // Creates a layout with the sizes of all arrays specified. If you know - // only the sizes of the first N arrays (where N can be zero), you can use - // `Partial()` defined above. The constructor is essentially equivalent to - // calling `Partial()` and passing in all array sizes; the constructor is - // provided as a convenient abbreviation. - // - // Note: The sizes of the arrays must be specified in number of elements, - // not in bytes. - constexpr explicit Layout(internal_layout::TypeToSize<Ts>... sizes) - : internal_layout::LayoutType<sizeof...(Ts), Ts...>(sizes...) {} -}; - -} // namespace priv -} // namespace phmap - -// --------------------------------------------------------------------------- -// compressed_tuple.h -// --------------------------------------------------------------------------- - -#ifdef _MSC_VER - // We need to mark these classes with this declspec to ensure that - // CompressedTuple happens. - #define PHMAP_INTERNAL_COMPRESSED_TUPLE_DECLSPEC __declspec(empty_bases) -#else // _MSC_VER - #define PHMAP_INTERNAL_COMPRESSED_TUPLE_DECLSPEC -#endif // _MSC_VER - -namespace phmap { -namespace priv { - -template <typename... Ts> -class CompressedTuple; - -namespace internal_compressed_tuple { - -template <typename D, size_t I> -struct Elem; -template <typename... B, size_t I> -struct Elem<CompressedTuple<B...>, I> - : std::tuple_element<I, std::tuple<B...>> {}; -template <typename D, size_t I> -using ElemT = typename Elem<D, I>::type; - -// --------------------------------------------------------------------------- -// Use the __is_final intrinsic if available. Where it's not available, classes -// declared with the 'final' specifier cannot be used as CompressedTuple -// elements. -// TODO(sbenza): Replace this with std::is_final in C++14. -// --------------------------------------------------------------------------- -template <typename T> -constexpr bool IsFinal() { -#if defined(__clang__) || defined(__GNUC__) - return __is_final(T); -#else - return false; -#endif -} - -template <typename T> -constexpr bool ShouldUseBase() { -#ifdef __INTEL_COMPILER - // avoid crash in Intel compiler - // assertion failed at: "shared/cfe/edgcpfe/lower_init.c", line 7013 - return false; -#else - return std::is_class<T>::value && std::is_empty<T>::value && !IsFinal<T>(); -#endif -} - -// The storage class provides two specializations: -// - For empty classes, it stores T as a base class. -// - For everything else, it stores T as a member. -// ------------------------------------------------ -template <typename D, size_t I, bool = ShouldUseBase<ElemT<D, I>>()> -struct Storage -{ - using T = ElemT<D, I>; - T value; - constexpr Storage() = default; - explicit constexpr Storage(T&& v) : value(phmap::forward<T>(v)) {} - constexpr const T& get() const& { return value; } - T& get() & { return value; } - constexpr const T&& get() const&& { return phmap::move(*this).value; } - T&& get() && { return std::move(*this).value; } -}; - -template <typename D, size_t I> -struct PHMAP_INTERNAL_COMPRESSED_TUPLE_DECLSPEC Storage<D, I, true> - : ElemT<D, I> -{ - using T = internal_compressed_tuple::ElemT<D, I>; - constexpr Storage() = default; - explicit constexpr Storage(T&& v) : T(phmap::forward<T>(v)) {} - constexpr const T& get() const& { return *this; } - T& get() & { return *this; } - constexpr const T&& get() const&& { return phmap::move(*this); } - T&& get() && { return std::move(*this); } -}; - -template <typename D, typename I> -struct PHMAP_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTupleImpl; - -template <typename... Ts, size_t... I> -struct PHMAP_INTERNAL_COMPRESSED_TUPLE_DECLSPEC - CompressedTupleImpl<CompressedTuple<Ts...>, phmap::index_sequence<I...>> - // We use the dummy identity function through std::integral_constant to - // convince MSVC of accepting and expanding I in that context. Without it - // you would get: - // error C3548: 'I': parameter pack cannot be used in this context - : Storage<CompressedTuple<Ts...>, - std::integral_constant<size_t, I>::value>... -{ - constexpr CompressedTupleImpl() = default; - explicit constexpr CompressedTupleImpl(Ts&&... args) - : Storage<CompressedTuple<Ts...>, I>(phmap::forward<Ts>(args))... {} -}; - -} // namespace internal_compressed_tuple - -// --------------------------------------------------------------------------- -// Helper class to perform the Empty Base Class Optimization. -// Ts can contain classes and non-classes, empty or not. For the ones that -// are empty classes, we perform the CompressedTuple. If all types in Ts are -// empty classes, then CompressedTuple<Ts...> is itself an empty class. -// -// To access the members, use member .get<N>() function. -// -// Eg: -// phmap::priv::CompressedTuple<int, T1, T2, T3> value(7, t1, t2, -// t3); -// assert(value.get<0>() == 7); -// T1& t1 = value.get<1>(); -// const T2& t2 = value.get<2>(); -// ... -// -// https://en.cppreference.com/w/cpp/language/ebo -// --------------------------------------------------------------------------- -template <typename... Ts> -class PHMAP_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTuple - : private internal_compressed_tuple::CompressedTupleImpl< - CompressedTuple<Ts...>, phmap::index_sequence_for<Ts...>> -{ -private: - template <int I> - using ElemT = internal_compressed_tuple::ElemT<CompressedTuple, I>; - -public: - constexpr CompressedTuple() = default; - explicit constexpr CompressedTuple(Ts... base) - : CompressedTuple::CompressedTupleImpl(phmap::forward<Ts>(base)...) {} - - template <int I> - ElemT<I>& get() & { - return internal_compressed_tuple::Storage<CompressedTuple, I>::get(); - } - - template <int I> - constexpr const ElemT<I>& get() const& { - return internal_compressed_tuple::Storage<CompressedTuple, I>::get(); - } - - template <int I> - ElemT<I>&& get() && { - return std::move(*this) - .internal_compressed_tuple::template Storage<CompressedTuple, I>::get(); - } - - template <int I> - constexpr const ElemT<I>&& get() const&& { - return phmap::move(*this) - .internal_compressed_tuple::template Storage<CompressedTuple, I>::get(); - } -}; - -// Explicit specialization for a zero-element tuple -// (needed to avoid ambiguous overloads for the default constructor). -// --------------------------------------------------------------------------- -template <> -class PHMAP_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTuple<> {}; - -} // namespace priv -} // namespace phmap - - -namespace phmap { -namespace priv { - -#ifdef _MSC_VER - #pragma warning(push) - // warning warning C4324: structure was padded due to alignment specifier - #pragma warning(disable : 4324) -#endif - - -// ---------------------------------------------------------------------------- -// 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 phmap::allocator_traits<Alloc>::template rebind_alloc<M>; - using AT = typename phmap::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 phmap::allocator_traits<Alloc>::template rebind_alloc<M>; - using AT = typename phmap::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)); -} - -#ifdef _MSC_VER - #pragma warning(pop) -#endif - -// 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 priv -} // namespace phmap - - -// --------------------------------------------------------------------------- -// thread_annotations.h -// --------------------------------------------------------------------------- - -#if defined(__clang__) - #define PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(x) __attribute__((x)) -#else - #define PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(x) // no-op -#endif - -#define PHMAP_GUARDED_BY(x) PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(guarded_by(x)) -#define PHMAP_PT_GUARDED_BY(x) PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(pt_guarded_by(x)) - -#define PHMAP_ACQUIRED_AFTER(...) \ - PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(acquired_after(__VA_ARGS__)) - -#define PHMAP_ACQUIRED_BEFORE(...) \ - PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(acquired_before(__VA_ARGS__)) - -#define PHMAP_EXCLUSIVE_LOCKS_REQUIRED(...) \ - PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(exclusive_locks_required(__VA_ARGS__)) - -#define PHMAP_SHARED_LOCKS_REQUIRED(...) \ - PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(shared_locks_required(__VA_ARGS__)) - -#define PHMAP_LOCKS_EXCLUDED(...) \ - PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(locks_excluded(__VA_ARGS__)) - -#define PHMAP_LOCK_RETURNED(x) \ - PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(lock_returned(x)) - -#define PHMAP_LOCKABLE \ - PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(lockable) - -#define PHMAP_SCOPED_LOCKABLE \ - PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(scoped_lockable) - -#define PHMAP_EXCLUSIVE_LOCK_FUNCTION(...) \ - PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(exclusive_lock_function(__VA_ARGS__)) - -#define PHMAP_SHARED_LOCK_FUNCTION(...) \ - PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(shared_lock_function(__VA_ARGS__)) - -#define PHMAP_UNLOCK_FUNCTION(...) \ - PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(unlock_function(__VA_ARGS__)) - -#define PHMAP_EXCLUSIVE_TRYLOCK_FUNCTION(...) \ - PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(exclusive_trylock_function(__VA_ARGS__)) - -#define PHMAP_SHARED_TRYLOCK_FUNCTION(...) \ - PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(shared_trylock_function(__VA_ARGS__)) - -#define PHMAP_ASSERT_EXCLUSIVE_LOCK(...) \ - PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(assert_exclusive_lock(__VA_ARGS__)) - -#define PHMAP_ASSERT_SHARED_LOCK(...) \ - PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(assert_shared_lock(__VA_ARGS__)) - -#define PHMAP_NO_THREAD_SAFETY_ANALYSIS \ - PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(no_thread_safety_analysis) - -//------------------------------------------------------------------------------ -// Tool-Supplied Annotations -//------------------------------------------------------------------------------ - -// TS_UNCHECKED should be placed around lock expressions that are not valid -// C++ syntax, but which are present for documentation purposes. These -// annotations will be ignored by the analysis. -#define PHMAP_TS_UNCHECKED(x) "" - -// TS_FIXME is used to mark lock expressions that are not valid C++ syntax. -// It is used by automated tools to mark and disable invalid expressions. -// The annotation should either be fixed, or changed to TS_UNCHECKED. -#define PHMAP_TS_FIXME(x) "" - -// Like NO_THREAD_SAFETY_ANALYSIS, this turns off checking within the body of -// a particular function. However, this attribute is used to mark functions -// that are incorrect and need to be fixed. It is used by automated tools to -// avoid breaking the build when the analysis is updated. -// Code owners are expected to eventually fix the routine. -#define PHMAP_NO_THREAD_SAFETY_ANALYSIS_FIXME PHMAP_NO_THREAD_SAFETY_ANALYSIS - -// Similar to NO_THREAD_SAFETY_ANALYSIS_FIXME, this macro marks a GUARDED_BY -// annotation that needs to be fixed, because it is producing thread safety -// warning. It disables the GUARDED_BY. -#define PHMAP_GUARDED_BY_FIXME(x) - -// Disables warnings for a single read operation. This can be used to avoid -// warnings when it is known that the read is not actually involved in a race, -// but the compiler cannot confirm that. -#define PHMAP_TS_UNCHECKED_READ(x) thread_safety_analysis::ts_unchecked_read(x) - - -namespace phmap { -namespace thread_safety_analysis { - -// Takes a reference to a guarded data member, and returns an unguarded -// reference. -template <typename T> -inline const T& ts_unchecked_read(const T& v) PHMAP_NO_THREAD_SAFETY_ANALYSIS { - return v; -} - -template <typename T> -inline T& ts_unchecked_read(T& v) PHMAP_NO_THREAD_SAFETY_ANALYSIS { - return v; -} - -} // namespace thread_safety_analysis - -namespace priv { - -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 = (size_t)-1; - static constexpr size_t kSecond = (size_t)-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 map_slot_type -{ - map_slot_type() {} - ~map_slot_type() = delete; - map_slot_type(const map_slot_type&) = delete; - map_slot_type& operator=(const map_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 K, class V> -struct map_slot_policy -{ - using slot_type = map_slot_type<K, V>; - using value_type = std::pair<const K, V>; - using mutable_value_type = std::pair<K, V>; - -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 = memory_internal::IsLayoutCompatible<K, V>; - -public: - static value_type& element(slot_type* slot) { return slot->value; } - static const value_type& element(const slot_type* slot) { - return slot->value; - } - - static const K& key(const slot_type* slot) { - return kMutableKeys::value ? slot->key : slot->value.first; - } - - template <class Allocator, class... Args> - static void construct(Allocator* alloc, slot_type* slot, Args&&... args) { - emplace(slot); - if (kMutableKeys::value) { - phmap::allocator_traits<Allocator>::construct(*alloc, &slot->mutable_value, - std::forward<Args>(args)...); - } else { - phmap::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) { - phmap::allocator_traits<Allocator>::construct( - *alloc, &slot->mutable_value, std::move(other->mutable_value)); - } else { - phmap::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) { - phmap::allocator_traits<Allocator>::destroy(*alloc, &slot->mutable_value); - } else { - phmap::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) { - phmap::allocator_traits<Allocator>::construct( - *alloc, &new_slot->mutable_value, std::move(old_slot->mutable_value)); - } else { - phmap::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); - phmap::allocator_traits<Allocator>::destroy(*alloc, &a->value); - phmap::allocator_traits<Allocator>::construct(*alloc, &a->value, - std::move(b->value)); - phmap::allocator_traits<Allocator>::destroy(*alloc, &b->value); - phmap::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 { - phmap::allocator_traits<Allocator>::destroy(*alloc, &dest->value); - phmap::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 priv -} // phmap - - -namespace phmap { - -#ifdef BOOST_THREAD_LOCK_OPTIONS_HPP - using defer_lock_t = boost::defer_lock_t; - using try_to_lock_t = boost::try_to_lock_t; - using adopt_lock_t = boost::adopt_lock_t; -#else - struct adopt_lock_t { explicit adopt_lock_t() = default; }; - struct defer_lock_t { explicit defer_lock_t() = default; }; - struct try_to_lock_t { explicit try_to_lock_t() = default; }; -#endif - -// ----------------------------------------------------------------------------- -// NullMutex -// ----------------------------------------------------------------------------- -// A class that implements the Mutex interface, but does nothing. This is to be -// used as a default template parameters for classes who provide optional -// internal locking (like phmap::parallel_flat_hash_map). -// ----------------------------------------------------------------------------- -class NullMutex { -public: - NullMutex() {} - ~NullMutex() {} - void lock() {} - void unlock() {} - bool try_lock() { return true; } - void lock_shared() {} - void unlock_shared() {} - bool try_lock_shared() { return true; } -}; - -// ------------------------ lockable object used internally ------------------------- -template <class MutexType> -class LockableBaseImpl -{ -public: - // ---------------------------------------------------- - struct DoNothing - { - using mutex_type = MutexType; - DoNothing() noexcept {} - explicit DoNothing(mutex_type& ) noexcept {} - explicit DoNothing(mutex_type& , mutex_type&) noexcept {} - DoNothing(mutex_type&, phmap::adopt_lock_t) noexcept {} - DoNothing(mutex_type&, phmap::defer_lock_t) noexcept {} - DoNothing(mutex_type&, phmap::try_to_lock_t) {} - template<class T> explicit DoNothing(T&&) {} - DoNothing& operator=(const DoNothing&) { return *this; } - DoNothing& operator=(DoNothing&&) { return *this; } - void swap(DoNothing &) {} - bool owns_lock() const noexcept { return true; } - }; - - // ---------------------------------------------------- - class WriteLock - { - public: - using mutex_type = MutexType; - - WriteLock() : m_(nullptr), locked_(false) {} - - explicit WriteLock(mutex_type &m) : m_(&m) { - m_->lock(); - locked_ = true; - } - - WriteLock(mutex_type& m, adopt_lock_t) noexcept : - m_(&m), locked_(true) - {} - - WriteLock(mutex_type& m, defer_lock_t) noexcept : - m_(&m), locked_(false) - {} - - WriteLock(mutex_type& m, try_to_lock_t) : - m_(&m), locked_(false) { - m_->try_lock(); - } - - WriteLock(WriteLock &&o) : - m_(std::move(o.m_)), locked_(std::move(o.locked_)) { - o.locked_ = false; - o.m_ = nullptr; - } - - WriteLock& operator=(WriteLock&& other) { - WriteLock temp(std::move(other)); - swap(temp); - return *this; - } - - ~WriteLock() { - if (locked_) - m_->unlock(); - } - - void lock() { - if (!locked_) { - m_->lock(); - locked_ = true; - } - } - - void unlock() { - if (locked_) { - m_->unlock(); - locked_ = false; - } - } - - bool try_lock() { - if (locked_) - return true; - locked_ = m_->try_lock(); - return locked_; - } - - bool owns_lock() const noexcept { return locked_; } - - void swap(WriteLock &o) noexcept { - std::swap(m_, o.m_); - std::swap(locked_, o.locked_); - } - - mutex_type *mutex() const noexcept { return m_; } - - private: - mutex_type *m_; - bool locked_; - }; - - // ---------------------------------------------------- - class ReadLock - { - public: - using mutex_type = MutexType; - - ReadLock() : m_(nullptr), locked_(false) {} - - explicit ReadLock(mutex_type &m) : m_(&m) { - m_->lock_shared(); - locked_ = true; - } - - ReadLock(mutex_type& m, adopt_lock_t) noexcept : - m_(&m), locked_(true) - {} - - ReadLock(mutex_type& m, defer_lock_t) noexcept : - m_(&m), locked_(false) - {} - - ReadLock(mutex_type& m, try_to_lock_t) : - m_(&m), locked_(false) { - m_->try_lock_shared(); - } - - ReadLock(ReadLock &&o) : - m_(std::move(o.m_)), locked_(std::move(o.locked_)) { - o.locked_ = false; - o.m_ = nullptr; - } - - ReadLock& operator=(ReadLock&& other) { - ReadLock temp(std::move(other)); - swap(temp); - return *this; - } - - ~ReadLock() { - if (locked_) - m_->unlock_shared(); - } - - void lock() { - if (!locked_) { - m_->lock_shared(); - locked_ = true; - } - } - - void unlock() { - if (locked_) { - m_->unlock_shared(); - locked_ = false; - } - } - - bool try_lock() { - if (locked_) - return true; - locked_ = m_->try_lock_shared(); - return locked_; - } - - bool owns_lock() const noexcept { return locked_; } - - void swap(ReadLock &o) noexcept { - std::swap(m_, o.m_); - std::swap(locked_, o.locked_); - } - - mutex_type *mutex() const noexcept { return m_; } - - private: - mutex_type *m_; - bool locked_; - }; - - // ---------------------------------------------------- - class WriteLocks - { - public: - using mutex_type = MutexType; - - explicit WriteLocks(mutex_type& m1, mutex_type& m2) : - _m1(m1), _m2(m2) - { - std::lock(m1, m2); - } - - WriteLocks(adopt_lock_t, mutex_type& m1, mutex_type& m2) : - _m1(m1), _m2(m2) - { // adopt means we already own the mutexes - } - - ~WriteLocks() - { - _m1.unlock(); - _m2.unlock(); - } - - WriteLocks(WriteLocks const&) = delete; - WriteLocks& operator=(WriteLocks const&) = delete; - private: - mutex_type& _m1; - mutex_type& _m2; - }; - - // ---------------------------------------------------- - class ReadLocks - { - public: - using mutex_type = MutexType; - - explicit ReadLocks(mutex_type& m1, mutex_type& m2) : - _m1(m1), _m2(m2) - { - _m1.lock_shared(); - _m2.lock_shared(); - } - - ReadLocks(adopt_lock_t, mutex_type& m1, mutex_type& m2) : - _m1(m1), _m2(m2) - { // adopt means we already own the mutexes - } - - ~ReadLocks() - { - _m1.unlock_shared(); - _m2.unlock_shared(); - } - - ReadLocks(ReadLocks const&) = delete; - ReadLocks& operator=(ReadLocks const&) = delete; - private: - mutex_type& _m1; - mutex_type& _m2; - }; -}; - -// ------------------------ holds a mutex ------------------------------------ -// Default implementation for Lockable, should work fine for std::mutex -// ----------------------------------- -// use as: -// using Lockable = phmap::LockableImpl<mutex_type>; -// Lockable m; -// -// Lockable::UpgradeLock read_lock(m); // take a upgradable lock -// -// { -// Lockable::UpgradeToUnique unique_lock(read_lock); -// // now locked for write -// } -// -// --------------------------------------------------------------------------- -// Generic mutex support (always write locks) -// -------------------------------------------------------------------------- -template <class Mtx_> -class LockableImpl : public Mtx_ -{ -public: - using mutex_type = Mtx_; - using Base = LockableBaseImpl<Mtx_>; - using SharedLock = typename Base::WriteLock; - using UpgradeLock = typename Base::WriteLock; - using UniqueLock = typename Base::WriteLock; - using SharedLocks = typename Base::WriteLocks; - using UniqueLocks = typename Base::WriteLocks; - using UpgradeToUnique = typename Base::DoNothing; // we already have unique ownership -}; - -// --------------------------------------------------------------------------- -// Null mutex (no-op) - when we don't want internal synchronization -// --------------------------------------------------------------------------- -template <> -class LockableImpl<phmap::NullMutex>: public phmap::NullMutex -{ -public: - using mutex_type = phmap::NullMutex; - using Base = LockableBaseImpl<phmap::NullMutex>; - using SharedLock = typename Base::DoNothing; - using UpgradeLock = typename Base::DoNothing; - using UniqueLock = typename Base::DoNothing; - using UpgradeToUnique = typename Base::DoNothing; - using SharedLocks = typename Base::DoNothing; - using UniqueLocks = typename Base::DoNothing; -}; - -// -------------------------------------------------------------------------- -// Abseil Mutex support (read and write lock support) -// -------------------------------------------------------------------------- -#ifdef ABSL_SYNCHRONIZATION_MUTEX_H_ - - struct AbslMutex : protected absl::Mutex - { - void lock() { this->Lock(); } - void unlock() { this->Unlock(); } - void try_lock() { this->TryLock(); } - void lock_shared() { this->ReaderLock(); } - void unlock_shared() { this->ReaderUnlock(); } - void try_lock_shared() { this->ReaderTryLock(); } - }; - - template <> - class LockableImpl<absl::Mutex> : public AbslMutex - { - public: - using mutex_type = phmap::AbslMutex; - using Base = LockableBaseImpl<phmap::AbslMutex>; - using SharedLock = typename Base::ReadLock; - using UpgradeLock = typename Base::WriteLock; - using UniqueLock = typename Base::WriteLock; - using SharedLocks = typename Base::ReadLocks; - using UniqueLocks = typename Base::WriteLocks; - using UpgradeToUnique = typename Base::DoNothing; // we already have unique ownership - }; - -#endif - -// -------------------------------------------------------------------------- -// Boost shared_mutex support (read and write lock support) -// -------------------------------------------------------------------------- -#ifdef BOOST_THREAD_SHARED_MUTEX_HPP - -#if 1 - // --------------------------------------------------------------------------- - template <> - class LockableImpl<boost::shared_mutex> : public boost::shared_mutex - { - public: - using mutex_type = boost::shared_mutex; - using Base = LockableBaseImpl<boost::shared_mutex>; - using SharedLock = boost::shared_lock<mutex_type>; - using UpgradeLock = boost::unique_lock<mutex_type>; // assume can't upgrade - using UniqueLock = boost::unique_lock<mutex_type>; - using SharedLocks = typename Base::ReadLocks; - using UniqueLocks = typename Base::WriteLocks; - using UpgradeToUnique = typename Base::DoNothing; // we already have unique ownership - }; -#else - // --------------------------------------------------------------------------- - template <> - class LockableImpl<boost::upgrade_mutex> : public boost::upgrade_mutex - { - public: - using mutex_type = boost::upgrade_mutex; - using SharedLock = boost::shared_lock<mutex_type>; - using UpgradeLock = boost::upgrade_lock<mutex_type>; - using UniqueLock = boost::unique_lock<mutex_type>; - using SharedLocks = typename Base::ReadLocks; - using UniqueLocks = typename Base::WriteLocks; - using UpgradeToUnique = boost::upgrade_to_unique_lock<mutex_type>; - }; -#endif - -#endif // BOOST_THREAD_SHARED_MUTEX_HPP - -// -------------------------------------------------------------------------- -// std::shared_mutex support (read and write lock support) -// -------------------------------------------------------------------------- -#ifdef PHMAP_HAVE_SHARED_MUTEX - - // --------------------------------------------------------------------------- - template <> - class LockableImpl<std::shared_mutex> : public std::shared_mutex - { - public: - using mutex_type = std::shared_mutex; - using Base = LockableBaseImpl<std::shared_mutex>; - using SharedLock = std::shared_lock<mutex_type>; - using UpgradeLock = std::unique_lock<mutex_type>; // assume can't upgrade - using UniqueLock = std::unique_lock<mutex_type>; - using SharedLocks = typename Base::ReadLocks; - using UniqueLocks = typename Base::WriteLocks; - using UpgradeToUnique = typename Base::DoNothing; // we already have unique ownership - }; -#endif // PHMAP_HAVE_SHARED_MUTEX - - -} // phmap - -#ifdef _MSC_VER - #pragma warning(pop) -#endif - - -#endif // phmap_base_h_guard_ |