diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -107,6 +107,9 @@ __functional_03 __functional_base __functional_base_03 + __functional/hash.h + __functional/unary_function.h + __functional/unwrap_ref.h __hash_table __iterator/advance.h __iterator/concepts.h @@ -160,9 +163,17 @@ __tuple __undef_macros __utility/__decay_copy.h + __utility/as_const.h + __utility/cmp.h __utility/declval.h + __utility/exchange.h __utility/forward.h + __utility/in_place.h + __utility/integer_sequence.h __utility/move.h + __utility/pair.h + __utility/piecewise_construct.h + __utility/rel_ops.h __utility/swap.h __utility/to_underlying.h algorithm diff --git a/libcxx/include/__functional/hash.h b/libcxx/include/__functional/hash.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__functional/hash.h @@ -0,0 +1,872 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___FUNCTIONAL_HASH_H +#define _LIBCPP___FUNCTIONAL_HASH_H + +#include <__config> +#include <__functional/unary_function.h> +#include <__tuple> +#include <__utility/forward.h> +#include <__utility/move.h> +#include <__utility/swap.h> +#include +#include +#include +#include +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +inline _LIBCPP_INLINE_VISIBILITY +_Size +__loadword(const void* __p) +{ + _Size __r; + _VSTD::memcpy(&__r, __p, sizeof(__r)); + return __r; +} + +// We use murmur2 when size_t is 32 bits, and cityhash64 when size_t +// is 64 bits. This is because cityhash64 uses 64bit x 64bit +// multiplication, which can be very slow on 32-bit systems. +template +struct __murmur2_or_cityhash; + +template +struct __murmur2_or_cityhash<_Size, 32> +{ + inline _Size operator()(const void* __key, _Size __len) + _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK; +}; + +// murmur2 +template +_Size +__murmur2_or_cityhash<_Size, 32>::operator()(const void* __key, _Size __len) +{ + const _Size __m = 0x5bd1e995; + const _Size __r = 24; + _Size __h = __len; + const unsigned char* __data = static_cast(__key); + for (; __len >= 4; __data += 4, __len -= 4) + { + _Size __k = __loadword<_Size>(__data); + __k *= __m; + __k ^= __k >> __r; + __k *= __m; + __h *= __m; + __h ^= __k; + } + switch (__len) + { + case 3: + __h ^= __data[2] << 16; + _LIBCPP_FALLTHROUGH(); + case 2: + __h ^= __data[1] << 8; + _LIBCPP_FALLTHROUGH(); + case 1: + __h ^= __data[0]; + __h *= __m; + } + __h ^= __h >> 13; + __h *= __m; + __h ^= __h >> 15; + return __h; +} + +template +struct __murmur2_or_cityhash<_Size, 64> +{ + inline _Size operator()(const void* __key, _Size __len) _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK; + + private: + // Some primes between 2^63 and 2^64. + static const _Size __k0 = 0xc3a5c85c97cb3127ULL; + static const _Size __k1 = 0xb492b66fbe98f273ULL; + static const _Size __k2 = 0x9ae16a3b2f90404fULL; + static const _Size __k3 = 0xc949d7c7509e6557ULL; + + static _Size __rotate(_Size __val, int __shift) { + return __shift == 0 ? __val : ((__val >> __shift) | (__val << (64 - __shift))); + } + + static _Size __rotate_by_at_least_1(_Size __val, int __shift) { + return (__val >> __shift) | (__val << (64 - __shift)); + } + + static _Size __shift_mix(_Size __val) { + return __val ^ (__val >> 47); + } + + static _Size __hash_len_16(_Size __u, _Size __v) + _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK + { + const _Size __mul = 0x9ddfea08eb382d69ULL; + _Size __a = (__u ^ __v) * __mul; + __a ^= (__a >> 47); + _Size __b = (__v ^ __a) * __mul; + __b ^= (__b >> 47); + __b *= __mul; + return __b; + } + + static _Size __hash_len_0_to_16(const char* __s, _Size __len) + _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK + { + if (__len > 8) { + const _Size __a = __loadword<_Size>(__s); + const _Size __b = __loadword<_Size>(__s + __len - 8); + return __hash_len_16(__a, __rotate_by_at_least_1(__b + __len, __len)) ^ __b; + } + if (__len >= 4) { + const uint32_t __a = __loadword(__s); + const uint32_t __b = __loadword(__s + __len - 4); + return __hash_len_16(__len + (__a << 3), __b); + } + if (__len > 0) { + const unsigned char __a = __s[0]; + const unsigned char __b = __s[__len >> 1]; + const unsigned char __c = __s[__len - 1]; + const uint32_t __y = static_cast(__a) + + (static_cast(__b) << 8); + const uint32_t __z = __len + (static_cast(__c) << 2); + return __shift_mix(__y * __k2 ^ __z * __k3) * __k2; + } + return __k2; + } + + static _Size __hash_len_17_to_32(const char *__s, _Size __len) + _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK + { + const _Size __a = __loadword<_Size>(__s) * __k1; + const _Size __b = __loadword<_Size>(__s + 8); + const _Size __c = __loadword<_Size>(__s + __len - 8) * __k2; + const _Size __d = __loadword<_Size>(__s + __len - 16) * __k0; + return __hash_len_16(__rotate(__a - __b, 43) + __rotate(__c, 30) + __d, + __a + __rotate(__b ^ __k3, 20) - __c + __len); + } + + // Return a 16-byte hash for 48 bytes. Quick and dirty. + // Callers do best to use "random-looking" values for a and b. + static pair<_Size, _Size> __weak_hash_len_32_with_seeds( + _Size __w, _Size __x, _Size __y, _Size __z, _Size __a, _Size __b) + _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK + { + __a += __w; + __b = __rotate(__b + __a + __z, 21); + const _Size __c = __a; + __a += __x; + __a += __y; + __b += __rotate(__a, 44); + return pair<_Size, _Size>(__a + __z, __b + __c); + } + + // Return a 16-byte hash for s[0] ... s[31], a, and b. Quick and dirty. + static pair<_Size, _Size> __weak_hash_len_32_with_seeds( + const char* __s, _Size __a, _Size __b) + _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK + { + return __weak_hash_len_32_with_seeds(__loadword<_Size>(__s), + __loadword<_Size>(__s + 8), + __loadword<_Size>(__s + 16), + __loadword<_Size>(__s + 24), + __a, + __b); + } + + // Return an 8-byte hash for 33 to 64 bytes. + static _Size __hash_len_33_to_64(const char *__s, size_t __len) + _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK + { + _Size __z = __loadword<_Size>(__s + 24); + _Size __a = __loadword<_Size>(__s) + + (__len + __loadword<_Size>(__s + __len - 16)) * __k0; + _Size __b = __rotate(__a + __z, 52); + _Size __c = __rotate(__a, 37); + __a += __loadword<_Size>(__s + 8); + __c += __rotate(__a, 7); + __a += __loadword<_Size>(__s + 16); + _Size __vf = __a + __z; + _Size __vs = __b + __rotate(__a, 31) + __c; + __a = __loadword<_Size>(__s + 16) + __loadword<_Size>(__s + __len - 32); + __z += __loadword<_Size>(__s + __len - 8); + __b = __rotate(__a + __z, 52); + __c = __rotate(__a, 37); + __a += __loadword<_Size>(__s + __len - 24); + __c += __rotate(__a, 7); + __a += __loadword<_Size>(__s + __len - 16); + _Size __wf = __a + __z; + _Size __ws = __b + __rotate(__a, 31) + __c; + _Size __r = __shift_mix((__vf + __ws) * __k2 + (__wf + __vs) * __k0); + return __shift_mix(__r * __k0 + __vs) * __k2; + } +}; + +// cityhash64 +template +_Size +__murmur2_or_cityhash<_Size, 64>::operator()(const void* __key, _Size __len) +{ + const char* __s = static_cast(__key); + if (__len <= 32) { + if (__len <= 16) { + return __hash_len_0_to_16(__s, __len); + } else { + return __hash_len_17_to_32(__s, __len); + } + } else if (__len <= 64) { + return __hash_len_33_to_64(__s, __len); + } + + // For strings over 64 bytes we hash the end first, and then as we + // loop we keep 56 bytes of state: v, w, x, y, and z. + _Size __x = __loadword<_Size>(__s + __len - 40); + _Size __y = __loadword<_Size>(__s + __len - 16) + + __loadword<_Size>(__s + __len - 56); + _Size __z = __hash_len_16(__loadword<_Size>(__s + __len - 48) + __len, + __loadword<_Size>(__s + __len - 24)); + pair<_Size, _Size> __v = __weak_hash_len_32_with_seeds(__s + __len - 64, __len, __z); + pair<_Size, _Size> __w = __weak_hash_len_32_with_seeds(__s + __len - 32, __y + __k1, __x); + __x = __x * __k1 + __loadword<_Size>(__s); + + // Decrease len to the nearest multiple of 64, and operate on 64-byte chunks. + __len = (__len - 1) & ~static_cast<_Size>(63); + do { + __x = __rotate(__x + __y + __v.first + __loadword<_Size>(__s + 8), 37) * __k1; + __y = __rotate(__y + __v.second + __loadword<_Size>(__s + 48), 42) * __k1; + __x ^= __w.second; + __y += __v.first + __loadword<_Size>(__s + 40); + __z = __rotate(__z + __w.first, 33) * __k1; + __v = __weak_hash_len_32_with_seeds(__s, __v.second * __k1, __x + __w.first); + __w = __weak_hash_len_32_with_seeds(__s + 32, __z + __w.second, + __y + __loadword<_Size>(__s + 16)); + _VSTD::swap(__z, __x); + __s += 64; + __len -= 64; + } while (__len != 0); + return __hash_len_16( + __hash_len_16(__v.first, __w.first) + __shift_mix(__y) * __k1 + __z, + __hash_len_16(__v.second, __w.second) + __x); +} + +template +struct __scalar_hash; + +_LIBCPP_SUPPRESS_DEPRECATED_PUSH +template +struct __scalar_hash<_Tp, 0> +#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) + : public unary_function<_Tp, size_t> +#endif +{ +_LIBCPP_SUPPRESS_DEPRECATED_POP +#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) + _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; + _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp argument_type; +#endif + _LIBCPP_INLINE_VISIBILITY + size_t operator()(_Tp __v) const _NOEXCEPT + { + union + { + _Tp __t; + size_t __a; + } __u; + __u.__a = 0; + __u.__t = __v; + return __u.__a; + } +}; + +_LIBCPP_SUPPRESS_DEPRECATED_PUSH +template +struct __scalar_hash<_Tp, 1> +#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) + : public unary_function<_Tp, size_t> +#endif +{ +_LIBCPP_SUPPRESS_DEPRECATED_POP +#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) + _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; + _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp argument_type; +#endif + _LIBCPP_INLINE_VISIBILITY + size_t operator()(_Tp __v) const _NOEXCEPT + { + union + { + _Tp __t; + size_t __a; + } __u; + __u.__t = __v; + return __u.__a; + } +}; + +_LIBCPP_SUPPRESS_DEPRECATED_PUSH +template +struct __scalar_hash<_Tp, 2> +#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) + : public unary_function<_Tp, size_t> +#endif +{ +_LIBCPP_SUPPRESS_DEPRECATED_POP +#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) + _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; + _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp argument_type; +#endif + _LIBCPP_INLINE_VISIBILITY + size_t operator()(_Tp __v) const _NOEXCEPT + { + union + { + _Tp __t; + struct + { + size_t __a; + size_t __b; + } __s; + } __u; + __u.__t = __v; + return __murmur2_or_cityhash()(&__u, sizeof(__u)); + } +}; + +_LIBCPP_SUPPRESS_DEPRECATED_PUSH +template +struct __scalar_hash<_Tp, 3> +#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) + : public unary_function<_Tp, size_t> +#endif +{ +_LIBCPP_SUPPRESS_DEPRECATED_POP +#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) + _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; + _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp argument_type; +#endif + _LIBCPP_INLINE_VISIBILITY + size_t operator()(_Tp __v) const _NOEXCEPT + { + union + { + _Tp __t; + struct + { + size_t __a; + size_t __b; + size_t __c; + } __s; + } __u; + __u.__t = __v; + return __murmur2_or_cityhash()(&__u, sizeof(__u)); + } +}; + +_LIBCPP_SUPPRESS_DEPRECATED_PUSH +template +struct __scalar_hash<_Tp, 4> +#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) + : public unary_function<_Tp, size_t> +#endif +{ +_LIBCPP_SUPPRESS_DEPRECATED_POP +#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) + _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; + _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp argument_type; +#endif + _LIBCPP_INLINE_VISIBILITY + size_t operator()(_Tp __v) const _NOEXCEPT + { + union + { + _Tp __t; + struct + { + size_t __a; + size_t __b; + size_t __c; + size_t __d; + } __s; + } __u; + __u.__t = __v; + return __murmur2_or_cityhash()(&__u, sizeof(__u)); + } +}; + +struct _PairT { + size_t first; + size_t second; +}; + +_LIBCPP_INLINE_VISIBILITY +inline size_t __hash_combine(size_t __lhs, size_t __rhs) _NOEXCEPT { + typedef __scalar_hash<_PairT> _HashT; + const _PairT __p = {__lhs, __rhs}; + return _HashT()(__p); +} + +_LIBCPP_SUPPRESS_DEPRECATED_PUSH +template +struct _LIBCPP_TEMPLATE_VIS hash<_Tp*> +#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) + : public unary_function<_Tp*, size_t> +#endif +{ +_LIBCPP_SUPPRESS_DEPRECATED_POP +#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) + _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; + _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp* argument_type; +#endif + _LIBCPP_INLINE_VISIBILITY + size_t operator()(_Tp* __v) const _NOEXCEPT + { + union + { + _Tp* __t; + size_t __a; + } __u; + __u.__t = __v; + return __murmur2_or_cityhash()(&__u, sizeof(__u)); + } +}; + +_LIBCPP_SUPPRESS_DEPRECATED_PUSH +template <> +struct _LIBCPP_TEMPLATE_VIS hash +#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) + : public unary_function +#endif +{ +_LIBCPP_SUPPRESS_DEPRECATED_POP +#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) + _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; + _LIBCPP_DEPRECATED_IN_CXX17 typedef bool argument_type; +#endif + _LIBCPP_INLINE_VISIBILITY + size_t operator()(bool __v) const _NOEXCEPT {return static_cast(__v);} +}; + +_LIBCPP_SUPPRESS_DEPRECATED_PUSH +template <> +struct _LIBCPP_TEMPLATE_VIS hash +#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) + : public unary_function +#endif +{ +_LIBCPP_SUPPRESS_DEPRECATED_POP +#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) + _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; + _LIBCPP_DEPRECATED_IN_CXX17 typedef char argument_type; +#endif + _LIBCPP_INLINE_VISIBILITY + size_t operator()(char __v) const _NOEXCEPT {return static_cast(__v);} +}; + +_LIBCPP_SUPPRESS_DEPRECATED_PUSH +template <> +struct _LIBCPP_TEMPLATE_VIS hash +#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) + : public unary_function +#endif +{ +_LIBCPP_SUPPRESS_DEPRECATED_POP +#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) + _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; + _LIBCPP_DEPRECATED_IN_CXX17 typedef signed char argument_type; +#endif + _LIBCPP_INLINE_VISIBILITY + size_t operator()(signed char __v) const _NOEXCEPT {return static_cast(__v);} +}; + +_LIBCPP_SUPPRESS_DEPRECATED_PUSH +template <> +struct _LIBCPP_TEMPLATE_VIS hash +#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) + : public unary_function +#endif +{ +_LIBCPP_SUPPRESS_DEPRECATED_POP +#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) + _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; + _LIBCPP_DEPRECATED_IN_CXX17 typedef unsigned char argument_type; +#endif + _LIBCPP_INLINE_VISIBILITY + size_t operator()(unsigned char __v) const _NOEXCEPT {return static_cast(__v);} +}; + +#ifndef _LIBCPP_HAS_NO_CHAR8_T +_LIBCPP_SUPPRESS_DEPRECATED_PUSH +template <> +struct _LIBCPP_TEMPLATE_VIS hash +#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) + : public unary_function +#endif +{ +_LIBCPP_SUPPRESS_DEPRECATED_POP +#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) + _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; + _LIBCPP_DEPRECATED_IN_CXX17 typedef char8_t argument_type; +#endif + _LIBCPP_INLINE_VISIBILITY + size_t operator()(char8_t __v) const _NOEXCEPT {return static_cast(__v);} +}; +#endif // !_LIBCPP_HAS_NO_CHAR8_T + +#ifndef _LIBCPP_HAS_NO_UNICODE_CHARS + +_LIBCPP_SUPPRESS_DEPRECATED_PUSH +template <> +struct _LIBCPP_TEMPLATE_VIS hash +#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) + : public unary_function +#endif +{ +_LIBCPP_SUPPRESS_DEPRECATED_POP +#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) + _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; + _LIBCPP_DEPRECATED_IN_CXX17 typedef char16_t argument_type; +#endif + _LIBCPP_INLINE_VISIBILITY + size_t operator()(char16_t __v) const _NOEXCEPT {return static_cast(__v);} +}; + +_LIBCPP_SUPPRESS_DEPRECATED_PUSH +template <> +struct _LIBCPP_TEMPLATE_VIS hash +#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) + : public unary_function +#endif +{ +_LIBCPP_SUPPRESS_DEPRECATED_POP +#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) + _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; + _LIBCPP_DEPRECATED_IN_CXX17 typedef char32_t argument_type; +#endif + _LIBCPP_INLINE_VISIBILITY + size_t operator()(char32_t __v) const _NOEXCEPT {return static_cast(__v);} +}; + +#endif // _LIBCPP_HAS_NO_UNICODE_CHARS + +_LIBCPP_SUPPRESS_DEPRECATED_PUSH +template <> +struct _LIBCPP_TEMPLATE_VIS hash +#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) + : public unary_function +#endif +{ +_LIBCPP_SUPPRESS_DEPRECATED_POP +#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) + _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; + _LIBCPP_DEPRECATED_IN_CXX17 typedef wchar_t argument_type; +#endif + _LIBCPP_INLINE_VISIBILITY + size_t operator()(wchar_t __v) const _NOEXCEPT {return static_cast(__v);} +}; + +_LIBCPP_SUPPRESS_DEPRECATED_PUSH +template <> +struct _LIBCPP_TEMPLATE_VIS hash +#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) + : public unary_function +#endif +{ +_LIBCPP_SUPPRESS_DEPRECATED_POP +#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) + _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; + _LIBCPP_DEPRECATED_IN_CXX17 typedef short argument_type; +#endif + _LIBCPP_INLINE_VISIBILITY + size_t operator()(short __v) const _NOEXCEPT {return static_cast(__v);} +}; + +_LIBCPP_SUPPRESS_DEPRECATED_PUSH +template <> +struct _LIBCPP_TEMPLATE_VIS hash +#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) + : public unary_function +#endif +{ +_LIBCPP_SUPPRESS_DEPRECATED_POP +#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) + _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; + _LIBCPP_DEPRECATED_IN_CXX17 typedef unsigned short argument_type; +#endif + _LIBCPP_INLINE_VISIBILITY + size_t operator()(unsigned short __v) const _NOEXCEPT {return static_cast(__v);} +}; + +_LIBCPP_SUPPRESS_DEPRECATED_PUSH +template <> +struct _LIBCPP_TEMPLATE_VIS hash +#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) + : public unary_function +#endif +{ +_LIBCPP_SUPPRESS_DEPRECATED_POP +#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) + _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; + _LIBCPP_DEPRECATED_IN_CXX17 typedef int argument_type; +#endif + _LIBCPP_INLINE_VISIBILITY + size_t operator()(int __v) const _NOEXCEPT {return static_cast(__v);} +}; + +_LIBCPP_SUPPRESS_DEPRECATED_PUSH +template <> +struct _LIBCPP_TEMPLATE_VIS hash +#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) + : public unary_function +#endif +{ +_LIBCPP_SUPPRESS_DEPRECATED_POP +#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) + _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; + _LIBCPP_DEPRECATED_IN_CXX17 typedef unsigned int argument_type; +#endif + _LIBCPP_INLINE_VISIBILITY + size_t operator()(unsigned int __v) const _NOEXCEPT {return static_cast(__v);} +}; + +_LIBCPP_SUPPRESS_DEPRECATED_PUSH +template <> +struct _LIBCPP_TEMPLATE_VIS hash +#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) + : public unary_function +#endif +{ +_LIBCPP_SUPPRESS_DEPRECATED_POP +#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) + _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; + _LIBCPP_DEPRECATED_IN_CXX17 typedef long argument_type; +#endif + _LIBCPP_INLINE_VISIBILITY + size_t operator()(long __v) const _NOEXCEPT {return static_cast(__v);} +}; + +_LIBCPP_SUPPRESS_DEPRECATED_PUSH +template <> +struct _LIBCPP_TEMPLATE_VIS hash +#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) + : public unary_function +#endif +{ +_LIBCPP_SUPPRESS_DEPRECATED_POP +#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) + _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; + _LIBCPP_DEPRECATED_IN_CXX17 typedef unsigned long argument_type; +#endif + _LIBCPP_INLINE_VISIBILITY + size_t operator()(unsigned long __v) const _NOEXCEPT {return static_cast(__v);} +}; + +template <> +struct _LIBCPP_TEMPLATE_VIS hash + : public __scalar_hash +{ +}; + +template <> +struct _LIBCPP_TEMPLATE_VIS hash + : public __scalar_hash +{ +}; + +#ifndef _LIBCPP_HAS_NO_INT128 + +template <> +struct _LIBCPP_TEMPLATE_VIS hash<__int128_t> + : public __scalar_hash<__int128_t> +{ +}; + +template <> +struct _LIBCPP_TEMPLATE_VIS hash<__uint128_t> + : public __scalar_hash<__uint128_t> +{ +}; + +#endif + +template <> +struct _LIBCPP_TEMPLATE_VIS hash + : public __scalar_hash +{ + _LIBCPP_INLINE_VISIBILITY + size_t operator()(float __v) const _NOEXCEPT + { + // -0.0 and 0.0 should return same hash + if (__v == 0.0f) + return 0; + return __scalar_hash::operator()(__v); + } +}; + +template <> +struct _LIBCPP_TEMPLATE_VIS hash + : public __scalar_hash +{ + _LIBCPP_INLINE_VISIBILITY + size_t operator()(double __v) const _NOEXCEPT + { + // -0.0 and 0.0 should return same hash + if (__v == 0.0) + return 0; + return __scalar_hash::operator()(__v); + } +}; + +template <> +struct _LIBCPP_TEMPLATE_VIS hash + : public __scalar_hash +{ + _LIBCPP_INLINE_VISIBILITY + size_t operator()(long double __v) const _NOEXCEPT + { + // -0.0 and 0.0 should return same hash + if (__v == 0.0L) + return 0; +#if defined(__i386__) || (defined(__x86_64__) && defined(__ILP32__)) + // Zero out padding bits + union + { + long double __t; + struct + { + size_t __a; + size_t __b; + size_t __c; + size_t __d; + } __s; + } __u; + __u.__s.__a = 0; + __u.__s.__b = 0; + __u.__s.__c = 0; + __u.__s.__d = 0; + __u.__t = __v; + return __u.__s.__a ^ __u.__s.__b ^ __u.__s.__c ^ __u.__s.__d; +#elif defined(__x86_64__) + // Zero out padding bits + union + { + long double __t; + struct + { + size_t __a; + size_t __b; + } __s; + } __u; + __u.__s.__a = 0; + __u.__s.__b = 0; + __u.__t = __v; + return __u.__s.__a ^ __u.__s.__b; +#else + return __scalar_hash::operator()(__v); +#endif + } +}; + +#if _LIBCPP_STD_VER > 11 + +_LIBCPP_SUPPRESS_DEPRECATED_PUSH +template ::value> +struct _LIBCPP_TEMPLATE_VIS __enum_hash +#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) + : public unary_function<_Tp, size_t> +#endif +{ +_LIBCPP_SUPPRESS_DEPRECATED_POP +#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) + _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; + _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp argument_type; +#endif + _LIBCPP_INLINE_VISIBILITY + size_t operator()(_Tp __v) const _NOEXCEPT + { + typedef typename underlying_type<_Tp>::type type; + return hash{}(static_cast(__v)); + } +}; +template +struct _LIBCPP_TEMPLATE_VIS __enum_hash<_Tp, false> { + __enum_hash() = delete; + __enum_hash(__enum_hash const&) = delete; + __enum_hash& operator=(__enum_hash const&) = delete; +}; + +template +struct _LIBCPP_TEMPLATE_VIS hash : public __enum_hash<_Tp> +{ +}; +#endif + +#if _LIBCPP_STD_VER > 14 + +_LIBCPP_SUPPRESS_DEPRECATED_PUSH +template <> +struct _LIBCPP_TEMPLATE_VIS hash +#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) + : public unary_function +#endif +{ +_LIBCPP_SUPPRESS_DEPRECATED_POP +#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) + _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; + _LIBCPP_DEPRECATED_IN_CXX17 typedef nullptr_t argument_type; +#endif + _LIBCPP_INLINE_VISIBILITY + size_t operator()(nullptr_t) const _NOEXCEPT { + return 662607004ull; + } +}; +#endif + +#ifndef _LIBCPP_CXX03_LANG +template +using __check_hash_requirements _LIBCPP_NODEBUG_TYPE = integral_constant::value && + is_move_constructible<_Hash>::value && + __invokable_r::value +>; + +template > +using __has_enabled_hash _LIBCPP_NODEBUG_TYPE = integral_constant::value && + is_default_constructible<_Hash>::value +>; + +#if _LIBCPP_STD_VER > 14 +template +using __enable_hash_helper_imp _LIBCPP_NODEBUG_TYPE = _Type; + +template +using __enable_hash_helper _LIBCPP_NODEBUG_TYPE = __enable_hash_helper_imp<_Type, + typename enable_if<__all<__has_enabled_hash<_Keys>::value...>::value>::type +>; +#else +template +using __enable_hash_helper _LIBCPP_NODEBUG_TYPE = _Type; +#endif + +#endif // !_LIBCPP_CXX03_LANG + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___FUNCTIONAL_HASH_H diff --git a/libcxx/include/__functional/unary_function.h b/libcxx/include/__functional/unary_function.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__functional/unary_function.h @@ -0,0 +1,34 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___FUNCTIONAL_UNARY_FUNCTION_H +#define _LIBCPP___FUNCTIONAL_UNARY_FUNCTION_H + +#include <__config> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +struct _LIBCPP_TEMPLATE_VIS unary_function +{ + typedef _Arg argument_type; + typedef _Result result_type; +}; + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___FUNCTIONAL_UNARY_FUNCTION_H diff --git a/libcxx/include/__functional/unwrap_ref.h b/libcxx/include/__functional/unwrap_ref.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__functional/unwrap_ref.h @@ -0,0 +1,56 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___FUNCTIONAL_UNWRAP_REF_H +#define _LIBCPP___FUNCTIONAL_UNWRAP_REF_H + +#include <__config> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +struct __unwrap_reference { typedef _LIBCPP_NODEBUG_TYPE _Tp type; }; + +template +class reference_wrapper; + +template +struct __unwrap_reference > { typedef _LIBCPP_NODEBUG_TYPE _Tp& type; }; + +template +struct decay; + +#if _LIBCPP_STD_VER > 17 +template +struct unwrap_reference : __unwrap_reference<_Tp> { }; + +template +struct unwrap_ref_decay : unwrap_reference::type> { }; +#endif // > C++17 + +template +struct __unwrap_ref_decay +#if _LIBCPP_STD_VER > 17 + : unwrap_ref_decay<_Tp> +#else + : __unwrap_reference::type> +#endif +{ }; + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___FUNCTIONAL_UNWRAP_REF_H diff --git a/libcxx/include/__functional_base b/libcxx/include/__functional_base --- a/libcxx/include/__functional_base +++ b/libcxx/include/__functional_base @@ -11,6 +11,7 @@ #define _LIBCPP_FUNCTIONAL_BASE #include <__config> +#include <__functional/unary_function.h> #include #include #include diff --git a/libcxx/include/__memory/unique_ptr.h b/libcxx/include/__memory/unique_ptr.h --- a/libcxx/include/__memory/unique_ptr.h +++ b/libcxx/include/__memory/unique_ptr.h @@ -12,6 +12,7 @@ #include <__config> #include <__functional_base> // std::less +#include <__functional/hash.h> #include <__memory/allocator_traits.h> // __pointer #include <__memory/compressed_pair.h> #include <__utility/forward.h> diff --git a/libcxx/include/__tree b/libcxx/include/__tree --- a/libcxx/include/__tree +++ b/libcxx/include/__tree @@ -14,6 +14,7 @@ #include <__utility/forward.h> #include #include +#include #include #include diff --git a/libcxx/include/__utility/as_const.h b/libcxx/include/__utility/as_const.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__utility/as_const.h @@ -0,0 +1,38 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___UTILITY_AS_CONST_H +#define _LIBCPP___UTILITY_AS_CONST_H + +#include <__config> +#include <__utility/forward.h> +#include <__utility/move.h> +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER > 14 +template +_LIBCPP_NODISCARD_EXT constexpr add_const_t<_Tp>& as_const(_Tp& __t) noexcept { return __t; } + +template +void as_const(const _Tp&&) = delete; +#endif + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___UTILITY_AS_CONST_H diff --git a/libcxx/include/__utility/cmp.h b/libcxx/include/__utility/cmp.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__utility/cmp.h @@ -0,0 +1,107 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___UTILITY_CMP_H +#define _LIBCPP___UTILITY_CMP_H + +#include <__config> +#include <__utility/forward.h> +#include <__utility/move.h> +#include +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_CONCEPTS) +template +struct _IsSameAsAny : _Or<_IsSame<_Tp, _Up>...> {}; + +template +concept __is_safe_integral_cmp = is_integral_v<_Tp> && + !_IsSameAsAny<_Tp, bool, char, +#ifndef _LIBCPP_HAS_NO_CHAR8_T + char8_t, +#endif +#ifndef _LIBCPP_HAS_NO_UNICODE_CHARS + char16_t, char32_t, +#endif + wchar_t>::value; + +template<__is_safe_integral_cmp _Tp, __is_safe_integral_cmp _Up> +_LIBCPP_INLINE_VISIBILITY constexpr +bool cmp_equal(_Tp __t, _Up __u) noexcept +{ + if constexpr (is_signed_v<_Tp> == is_signed_v<_Up>) + return __t == __u; + else if constexpr (is_signed_v<_Tp>) + return __t < 0 ? false : make_unsigned_t<_Tp>(__t) == __u; + else + return __u < 0 ? false : __t == make_unsigned_t<_Up>(__u); +} + +template<__is_safe_integral_cmp _Tp, __is_safe_integral_cmp _Up> +_LIBCPP_INLINE_VISIBILITY constexpr +bool cmp_not_equal(_Tp __t, _Up __u) noexcept +{ + return !_VSTD::cmp_equal(__t, __u); +} + +template<__is_safe_integral_cmp _Tp, __is_safe_integral_cmp _Up> +_LIBCPP_INLINE_VISIBILITY constexpr +bool cmp_less(_Tp __t, _Up __u) noexcept +{ + if constexpr (is_signed_v<_Tp> == is_signed_v<_Up>) + return __t < __u; + else if constexpr (is_signed_v<_Tp>) + return __t < 0 ? true : make_unsigned_t<_Tp>(__t) < __u; + else + return __u < 0 ? false : __t < make_unsigned_t<_Up>(__u); +} + +template<__is_safe_integral_cmp _Tp, __is_safe_integral_cmp _Up> +_LIBCPP_INLINE_VISIBILITY constexpr +bool cmp_greater(_Tp __t, _Up __u) noexcept +{ + return _VSTD::cmp_less(__u, __t); +} + +template<__is_safe_integral_cmp _Tp, __is_safe_integral_cmp _Up> +_LIBCPP_INLINE_VISIBILITY constexpr +bool cmp_less_equal(_Tp __t, _Up __u) noexcept +{ + return !_VSTD::cmp_greater(__t, __u); +} + +template<__is_safe_integral_cmp _Tp, __is_safe_integral_cmp _Up> +_LIBCPP_INLINE_VISIBILITY constexpr +bool cmp_greater_equal(_Tp __t, _Up __u) noexcept +{ + return !_VSTD::cmp_less(__t, __u); +} + +template<__is_safe_integral_cmp _Tp, __is_safe_integral_cmp _Up> +_LIBCPP_INLINE_VISIBILITY constexpr +bool in_range(_Up __u) noexcept +{ + return _VSTD::cmp_less_equal(__u, numeric_limits<_Tp>::max()) && + _VSTD::cmp_greater_equal(__u, numeric_limits<_Tp>::min()); +} +#endif + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___UTILITY_CMP_H diff --git a/libcxx/include/__utility/exchange.h b/libcxx/include/__utility/exchange.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__utility/exchange.h @@ -0,0 +1,40 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___UTILITY_EXCHANGE_H +#define _LIBCPP___UTILITY_EXCHANGE_H + +#include <__config> +#include <__utility/forward.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER > 11 +template +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 +_T1 exchange(_T1& __obj, _T2 && __new_value) +{ + _T1 __old_value = _VSTD::move(__obj); + __obj = _VSTD::forward<_T2>(__new_value); + return __old_value; +} +#endif // _LIBCPP_STD_VER > 11 + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___UTILITY_EXCHANGE_H diff --git a/libcxx/include/__utility/in_place.h b/libcxx/include/__utility/in_place.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__utility/in_place.h @@ -0,0 +1,63 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___UTILITY_IN_PLACE_H +#define _LIBCPP___UTILITY_IN_PLACE_H + +#include <__config> +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER > 14 + +struct _LIBCPP_TYPE_VIS in_place_t { + explicit in_place_t() = default; +}; +_LIBCPP_INLINE_VAR constexpr in_place_t in_place{}; + +template +struct _LIBCPP_TEMPLATE_VIS in_place_type_t { + explicit in_place_type_t() = default; +}; +template +_LIBCPP_INLINE_VAR constexpr in_place_type_t<_Tp> in_place_type{}; + +template +struct _LIBCPP_TEMPLATE_VIS in_place_index_t { + explicit in_place_index_t() = default; +}; +template +_LIBCPP_INLINE_VAR constexpr in_place_index_t<_Idx> in_place_index{}; + +template struct __is_inplace_type_imp : false_type {}; +template struct __is_inplace_type_imp> : true_type {}; + +template +using __is_inplace_type = __is_inplace_type_imp<__uncvref_t<_Tp>>; + +template struct __is_inplace_index_imp : false_type {}; +template struct __is_inplace_index_imp> : true_type {}; + +template +using __is_inplace_index = __is_inplace_index_imp<__uncvref_t<_Tp>>; + +#endif // _LIBCPP_STD_VER > 14 + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___UTILITY_IN_PLACE_H diff --git a/libcxx/include/__utility/integer_sequence.h b/libcxx/include/__utility/integer_sequence.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__utility/integer_sequence.h @@ -0,0 +1,83 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___UTILITY_INTEGER_SEQUENCE_H +#define _LIBCPP___UTILITY_INTEGER_SEQUENCE_H + +#include <__config> +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER > 11 + +template +struct _LIBCPP_TEMPLATE_VIS integer_sequence +{ + typedef _Tp value_type; + static_assert( is_integral<_Tp>::value, + "std::integer_sequence can only be instantiated with an integral type" ); + static + _LIBCPP_INLINE_VISIBILITY + constexpr + size_t + size() noexcept { return sizeof...(_Ip); } +}; + +template + using index_sequence = integer_sequence; + +#if __has_builtin(__make_integer_seq) && !defined(_LIBCPP_TESTING_FALLBACK_MAKE_INTEGER_SEQUENCE) + +template +using __make_integer_sequence _LIBCPP_NODEBUG_TYPE = __make_integer_seq; + +#else + +template using __make_integer_sequence_unchecked _LIBCPP_NODEBUG_TYPE = + typename __detail::__make<_Np>::type::template __convert; + +template +struct __make_integer_sequence_checked +{ + static_assert(is_integral<_Tp>::value, + "std::make_integer_sequence can only be instantiated with an integral type" ); + static_assert(0 <= _Ep, "std::make_integer_sequence must have a non-negative sequence length"); + // Workaround GCC bug by preventing bad installations when 0 <= _Ep + // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68929 + typedef _LIBCPP_NODEBUG_TYPE __make_integer_sequence_unchecked<_Tp, 0 <= _Ep ? _Ep : 0> type; +}; + +template +using __make_integer_sequence _LIBCPP_NODEBUG_TYPE = typename __make_integer_sequence_checked<_Tp, _Ep>::type; + +#endif + +template + using make_integer_sequence = __make_integer_sequence<_Tp, _Np>; + +template + using make_index_sequence = make_integer_sequence; + +template + using index_sequence_for = make_index_sequence; + +#endif // _LIBCPP_STD_VER > 11 + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___UTILITY_INTEGER_SEQUENCE_H diff --git a/libcxx/include/__utility/pair.h b/libcxx/include/__utility/pair.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__utility/pair.h @@ -0,0 +1,585 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___UTILITY_PAIR_H +#define _LIBCPP___UTILITY_PAIR_H + +#include <__config> +#include <__functional/unwrap_ref.h> +#include <__tuple> +#include <__utility/forward.h> +#include <__utility/move.h> +#include <__utility/piecewise_construct.h> +#include +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + + +#if defined(_LIBCPP_DEPRECATED_ABI_DISABLE_PAIR_TRIVIAL_COPY_CTOR) +template +struct __non_trivially_copyable_base { + _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY + __non_trivially_copyable_base() _NOEXCEPT {} + _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY + __non_trivially_copyable_base(__non_trivially_copyable_base const&) _NOEXCEPT {} +}; +#endif + +template +struct _LIBCPP_TEMPLATE_VIS pair +#if defined(_LIBCPP_DEPRECATED_ABI_DISABLE_PAIR_TRIVIAL_COPY_CTOR) +: private __non_trivially_copyable_base<_T1, _T2> +#endif +{ + typedef _T1 first_type; + typedef _T2 second_type; + + _T1 first; + _T2 second; + +#if !defined(_LIBCPP_CXX03_LANG) + pair(pair const&) = default; + pair(pair&&) = default; +#else + // Use the implicitly declared copy constructor in C++03 +#endif + +#ifdef _LIBCPP_CXX03_LANG + _LIBCPP_INLINE_VISIBILITY + pair() : first(), second() {} + + _LIBCPP_INLINE_VISIBILITY + pair(_T1 const& __t1, _T2 const& __t2) : first(__t1), second(__t2) {} + + template + _LIBCPP_INLINE_VISIBILITY + pair(const pair<_U1, _U2>& __p) : first(__p.first), second(__p.second) {} + + _LIBCPP_INLINE_VISIBILITY + pair& operator=(pair const& __p) { + first = __p.first; + second = __p.second; + return *this; + } +#else + template + using _EnableB _LIBCPP_NODEBUG_TYPE = typename enable_if<_Val, bool>::type; + + struct _CheckArgs { + template + static constexpr bool __enable_explicit_default() { + return is_default_constructible<_T1>::value + && is_default_constructible<_T2>::value + && !__enable_implicit_default<>(); + } + + template + static constexpr bool __enable_implicit_default() { + return __is_implicitly_default_constructible<_T1>::value + && __is_implicitly_default_constructible<_T2>::value; + } + + template + static constexpr bool __enable_explicit() { + return is_constructible::value + && is_constructible::value + && (!is_convertible<_U1, first_type>::value + || !is_convertible<_U2, second_type>::value); + } + + template + static constexpr bool __enable_implicit() { + return is_constructible::value + && is_constructible::value + && is_convertible<_U1, first_type>::value + && is_convertible<_U2, second_type>::value; + } + }; + + template + using _CheckArgsDep _LIBCPP_NODEBUG_TYPE = typename conditional< + _MaybeEnable, _CheckArgs, __check_tuple_constructor_fail>::type; + + struct _CheckTupleLikeConstructor { + template + static constexpr bool __enable_implicit() { + return __tuple_convertible<_Tuple, pair>::value; + } + + template + static constexpr bool __enable_explicit() { + return __tuple_constructible<_Tuple, pair>::value + && !__tuple_convertible<_Tuple, pair>::value; + } + + template + static constexpr bool __enable_assign() { + return __tuple_assignable<_Tuple, pair>::value; + } + }; + + template + using _CheckTLC _LIBCPP_NODEBUG_TYPE = typename conditional< + __tuple_like_with_size<_Tuple, 2>::value + && !is_same::type, pair>::value, + _CheckTupleLikeConstructor, + __check_tuple_constructor_fail + >::type; + + template::__enable_explicit_default() + > = false> + explicit _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR + pair() _NOEXCEPT_(is_nothrow_default_constructible::value && + is_nothrow_default_constructible::value) + : first(), second() {} + + template::__enable_implicit_default() + > = false> + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR + pair() _NOEXCEPT_(is_nothrow_default_constructible::value && + is_nothrow_default_constructible::value) + : first(), second() {} + + template ::template __enable_explicit<_T1 const&, _T2 const&>() + > = false> + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + explicit pair(_T1 const& __t1, _T2 const& __t2) + _NOEXCEPT_(is_nothrow_copy_constructible::value && + is_nothrow_copy_constructible::value) + : first(__t1), second(__t2) {} + + template::template __enable_implicit<_T1 const&, _T2 const&>() + > = false> + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + pair(_T1 const& __t1, _T2 const& __t2) + _NOEXCEPT_(is_nothrow_copy_constructible::value && + is_nothrow_copy_constructible::value) + : first(__t1), second(__t2) {} + + template() + > = false> + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + explicit pair(_U1&& __u1, _U2&& __u2) + _NOEXCEPT_((is_nothrow_constructible::value && + is_nothrow_constructible::value)) + : first(_VSTD::forward<_U1>(__u1)), second(_VSTD::forward<_U2>(__u2)) {} + + template() + > = false> + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + pair(_U1&& __u1, _U2&& __u2) + _NOEXCEPT_((is_nothrow_constructible::value && + is_nothrow_constructible::value)) + : first(_VSTD::forward<_U1>(__u1)), second(_VSTD::forward<_U2>(__u2)) {} + + template() + > = false> + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + explicit pair(pair<_U1, _U2> const& __p) + _NOEXCEPT_((is_nothrow_constructible::value && + is_nothrow_constructible::value)) + : first(__p.first), second(__p.second) {} + + template() + > = false> + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + pair(pair<_U1, _U2> const& __p) + _NOEXCEPT_((is_nothrow_constructible::value && + is_nothrow_constructible::value)) + : first(__p.first), second(__p.second) {} + + template() + > = false> + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + explicit pair(pair<_U1, _U2>&&__p) + _NOEXCEPT_((is_nothrow_constructible::value && + is_nothrow_constructible::value)) + : first(_VSTD::forward<_U1>(__p.first)), second(_VSTD::forward<_U2>(__p.second)) {} + + template() + > = false> + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + pair(pair<_U1, _U2>&& __p) + _NOEXCEPT_((is_nothrow_constructible::value && + is_nothrow_constructible::value)) + : first(_VSTD::forward<_U1>(__p.first)), second(_VSTD::forward<_U2>(__p.second)) {} + + template::template __enable_explicit<_Tuple>() + > = false> + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + explicit pair(_Tuple&& __p) + : first(_VSTD::get<0>(_VSTD::forward<_Tuple>(__p))), + second(_VSTD::get<1>(_VSTD::forward<_Tuple>(__p))) {} + + template::template __enable_implicit<_Tuple>() + > = false> + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + pair(_Tuple&& __p) + : first(_VSTD::get<0>(_VSTD::forward<_Tuple>(__p))), + second(_VSTD::get<1>(_VSTD::forward<_Tuple>(__p))) {} + + template + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 + pair(piecewise_construct_t __pc, + tuple<_Args1...> __first_args, tuple<_Args2...> __second_args) + _NOEXCEPT_((is_nothrow_constructible::value && + is_nothrow_constructible::value)) + : pair(__pc, __first_args, __second_args, + typename __make_tuple_indices::type(), + typename __make_tuple_indices::type()) {} + + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 + pair& operator=(typename conditional< + is_copy_assignable::value && + is_copy_assignable::value, + pair, __nat>::type const& __p) + _NOEXCEPT_(is_nothrow_copy_assignable::value && + is_nothrow_copy_assignable::value) + { + first = __p.first; + second = __p.second; + return *this; + } + + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 + pair& operator=(typename conditional< + is_move_assignable::value && + is_move_assignable::value, + pair, __nat>::type&& __p) + _NOEXCEPT_(is_nothrow_move_assignable::value && + is_nothrow_move_assignable::value) + { + first = _VSTD::forward(__p.first); + second = _VSTD::forward(__p.second); + return *this; + } + + template ::template __enable_assign<_Tuple>() + > = false> + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 + pair& operator=(_Tuple&& __p) { + first = _VSTD::get<0>(_VSTD::forward<_Tuple>(__p)); + second = _VSTD::get<1>(_VSTD::forward<_Tuple>(__p)); + return *this; + } +#endif + + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 + void + swap(pair& __p) _NOEXCEPT_(__is_nothrow_swappable::value && + __is_nothrow_swappable::value) + { + using _VSTD::swap; + swap(first, __p.first); + swap(second, __p.second); + } +private: + +#ifndef _LIBCPP_CXX03_LANG + template + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 + pair(piecewise_construct_t, + tuple<_Args1...>& __first_args, tuple<_Args2...>& __second_args, + __tuple_indices<_I1...>, __tuple_indices<_I2...>); +#endif +}; + +#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES +template +pair(_T1, _T2) -> pair<_T1, _T2>; +#endif // _LIBCPP_HAS_NO_DEDUCTION_GUIDES + +template +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 +bool +operator==(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y) +{ + return __x.first == __y.first && __x.second == __y.second; +} + +template +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 +bool +operator!=(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y) +{ + return !(__x == __y); +} + +template +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 +bool +operator< (const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y) +{ + return __x.first < __y.first || (!(__y.first < __x.first) && __x.second < __y.second); +} + +template +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 +bool +operator> (const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y) +{ + return __y < __x; +} + +template +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 +bool +operator>=(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y) +{ + return !(__x < __y); +} + +template +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 +bool +operator<=(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y) +{ + return !(__y < __x); +} + +template +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 +typename enable_if +< + __is_swappable<_T1>::value && + __is_swappable<_T2>::value, + void +>::type +swap(pair<_T1, _T2>& __x, pair<_T1, _T2>& __y) + _NOEXCEPT_((__is_nothrow_swappable<_T1>::value && + __is_nothrow_swappable<_T2>::value)) +{ + __x.swap(__y); +} + +#ifndef _LIBCPP_CXX03_LANG + +template +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair::type, typename __unwrap_ref_decay<_T2>::type> +make_pair(_T1&& __t1, _T2&& __t2) +{ + return pair::type, typename __unwrap_ref_decay<_T2>::type> + (_VSTD::forward<_T1>(__t1), _VSTD::forward<_T2>(__t2)); +} + +#else // _LIBCPP_CXX03_LANG + +template +inline _LIBCPP_INLINE_VISIBILITY +pair<_T1,_T2> +make_pair(_T1 __x, _T2 __y) +{ + return pair<_T1, _T2>(__x, __y); +} + +#endif // _LIBCPP_CXX03_LANG + +template + struct _LIBCPP_TEMPLATE_VIS tuple_size > + : public integral_constant {}; + +template +struct _LIBCPP_TEMPLATE_VIS tuple_element<_Ip, pair<_T1, _T2> > +{ + static_assert(_Ip < 2, "Index out of bounds in std::tuple_element>"); +}; + +template +struct _LIBCPP_TEMPLATE_VIS tuple_element<0, pair<_T1, _T2> > +{ + typedef _LIBCPP_NODEBUG_TYPE _T1 type; +}; + +template +struct _LIBCPP_TEMPLATE_VIS tuple_element<1, pair<_T1, _T2> > +{ + typedef _LIBCPP_NODEBUG_TYPE _T2 type; +}; + +template struct __get_pair; + +template <> +struct __get_pair<0> +{ + template + static + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + _T1& + get(pair<_T1, _T2>& __p) _NOEXCEPT {return __p.first;} + + template + static + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + const _T1& + get(const pair<_T1, _T2>& __p) _NOEXCEPT {return __p.first;} + +#ifndef _LIBCPP_CXX03_LANG + template + static + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + _T1&& + get(pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<_T1>(__p.first);} + + template + static + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + const _T1&& + get(const pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward(__p.first);} +#endif // _LIBCPP_CXX03_LANG +}; + +template <> +struct __get_pair<1> +{ + template + static + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + _T2& + get(pair<_T1, _T2>& __p) _NOEXCEPT {return __p.second;} + + template + static + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + const _T2& + get(const pair<_T1, _T2>& __p) _NOEXCEPT {return __p.second;} + +#ifndef _LIBCPP_CXX03_LANG + template + static + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + _T2&& + get(pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<_T2>(__p.second);} + + template + static + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + const _T2&& + get(const pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward(__p.second);} +#endif // _LIBCPP_CXX03_LANG +}; + +template +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 +typename tuple_element<_Ip, pair<_T1, _T2> >::type& +get(pair<_T1, _T2>& __p) _NOEXCEPT +{ + return __get_pair<_Ip>::get(__p); +} + +template +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 +const typename tuple_element<_Ip, pair<_T1, _T2> >::type& +get(const pair<_T1, _T2>& __p) _NOEXCEPT +{ + return __get_pair<_Ip>::get(__p); +} + +#ifndef _LIBCPP_CXX03_LANG +template +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 +typename tuple_element<_Ip, pair<_T1, _T2> >::type&& +get(pair<_T1, _T2>&& __p) _NOEXCEPT +{ + return __get_pair<_Ip>::get(_VSTD::move(__p)); +} + +template +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 +const typename tuple_element<_Ip, pair<_T1, _T2> >::type&& +get(const pair<_T1, _T2>&& __p) _NOEXCEPT +{ + return __get_pair<_Ip>::get(_VSTD::move(__p)); +} +#endif // _LIBCPP_CXX03_LANG + +#if _LIBCPP_STD_VER > 11 +template +inline _LIBCPP_INLINE_VISIBILITY +constexpr _T1 & get(pair<_T1, _T2>& __p) _NOEXCEPT +{ + return __get_pair<0>::get(__p); +} + +template +inline _LIBCPP_INLINE_VISIBILITY +constexpr _T1 const & get(pair<_T1, _T2> const& __p) _NOEXCEPT +{ + return __get_pair<0>::get(__p); +} + +template +inline _LIBCPP_INLINE_VISIBILITY +constexpr _T1 && get(pair<_T1, _T2>&& __p) _NOEXCEPT +{ + return __get_pair<0>::get(_VSTD::move(__p)); +} + +template +inline _LIBCPP_INLINE_VISIBILITY +constexpr _T1 const && get(pair<_T1, _T2> const&& __p) _NOEXCEPT +{ + return __get_pair<0>::get(_VSTD::move(__p)); +} + +template +inline _LIBCPP_INLINE_VISIBILITY +constexpr _T1 & get(pair<_T2, _T1>& __p) _NOEXCEPT +{ + return __get_pair<1>::get(__p); +} + +template +inline _LIBCPP_INLINE_VISIBILITY +constexpr _T1 const & get(pair<_T2, _T1> const& __p) _NOEXCEPT +{ + return __get_pair<1>::get(__p); +} + +template +inline _LIBCPP_INLINE_VISIBILITY +constexpr _T1 && get(pair<_T2, _T1>&& __p) _NOEXCEPT +{ + return __get_pair<1>::get(_VSTD::move(__p)); +} + +template +inline _LIBCPP_INLINE_VISIBILITY +constexpr _T1 const && get(pair<_T2, _T1> const&& __p) _NOEXCEPT +{ + return __get_pair<1>::get(_VSTD::move(__p)); +} + +#endif + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___UTILITY_PAIR_H diff --git a/libcxx/include/__utility/piecewise_construct.h b/libcxx/include/__utility/piecewise_construct.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__utility/piecewise_construct.h @@ -0,0 +1,34 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___UTILITY_PIECEWISE_CONSTRUCT_H +#define _LIBCPP___UTILITY_PIECEWISE_CONSTRUCT_H + +#include <__config> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +struct _LIBCPP_TEMPLATE_VIS piecewise_construct_t { explicit piecewise_construct_t() = default; }; +#if defined(_LIBCPP_CXX03_LANG) || defined(_LIBCPP_BUILDING_LIBRARY) +extern _LIBCPP_EXPORTED_FROM_ABI const piecewise_construct_t piecewise_construct;// = piecewise_construct_t(); +#else +/* _LIBCPP_INLINE_VAR */ constexpr piecewise_construct_t piecewise_construct = piecewise_construct_t(); +#endif + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___UTILITY_PIECEWISE_CONSTRUCT_H diff --git a/libcxx/include/__utility/rel_ops.h b/libcxx/include/__utility/rel_ops.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__utility/rel_ops.h @@ -0,0 +1,67 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___UTILITY_REL_OPS_H +#define _LIBCPP___UTILITY_REL_OPS_H + +#include <__config> +#include <__utility/forward.h> +#include <__utility/move.h> +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace rel_ops +{ + +template +inline _LIBCPP_INLINE_VISIBILITY +bool +operator!=(const _Tp& __x, const _Tp& __y) +{ + return !(__x == __y); +} + +template +inline _LIBCPP_INLINE_VISIBILITY +bool +operator> (const _Tp& __x, const _Tp& __y) +{ + return __y < __x; +} + +template +inline _LIBCPP_INLINE_VISIBILITY +bool +operator<=(const _Tp& __x, const _Tp& __y) +{ + return !(__y < __x); +} + +template +inline _LIBCPP_INLINE_VISIBILITY +bool +operator>=(const _Tp& __x, const _Tp& __y) +{ + return !(__x < __y); +} + +} // rel_ops + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___UTILITY_REL_OPS_H diff --git a/libcxx/include/deque b/libcxx/include/deque --- a/libcxx/include/deque +++ b/libcxx/include/deque @@ -168,6 +168,7 @@ #include #include #include +#include #include #include #include diff --git a/libcxx/include/functional b/libcxx/include/functional --- a/libcxx/include/functional +++ b/libcxx/include/functional @@ -490,7 +490,10 @@ #include <__config> #include <__debug> #include <__functional_base> +#include <__functional/hash.h> #include <__functional/search.h> +#include <__functional/unary_function.h> +#include <__functional/unwrap_ref.h> #include <__utility/forward.h> #include #include diff --git a/libcxx/include/module.modulemap b/libcxx/include/module.modulemap --- a/libcxx/include/module.modulemap +++ b/libcxx/include/module.modulemap @@ -408,7 +408,10 @@ header "functional" export * module __functional { - module search { header "__functional/search.h" } + module hash { header "__functional/hash.h" } + module search { header "__functional/search.h" } + module unary_function { header "__functional/unary_function.h" } + module unwrap_ref { header "__functional/unwrap_ref.h" } } } module future { @@ -640,6 +643,7 @@ } module type_traits { header "type_traits" + export functional.__functional.unwrap_ref export * } module typeindex { @@ -666,12 +670,20 @@ export * module __utility { - module __decay_copy { header "__utility/__decay_copy.h" } - module declval { header "__utility/declval.h" } - module forward { header "__utility/forward.h" } - module move { header "__utility/move.h" } - module swap { header "__utility/swap.h" } - module to_underlying { header "__utility/to_underlying.h" } + module __decay_copy { header "__utility/__decay_copy.h" } + module as_const { header "__utility/as_const.h" } + module cmp { header "__utility/cmp.h" } + module declval { header "__utility/declval.h" } + module exchange { header "__utility/exchange.h" } + module forward { header "__utility/forward.h" } + module in_place { header "__utility/in_place.h" } + module integer_sequence { header "__utility/integer_sequence.h" } + module move { header "__utility/move.h" } + module pair { header "__utility/pair.h" } + module piecewise_construct { header "__utility/piecewise_construct.h" } + module rel_ops { header "__utility/rel_ops.h" } + module swap { header "__utility/swap.h" } + module to_underlying { header "__utility/to_underlying.h" } } } module valarray { diff --git a/libcxx/include/span b/libcxx/include/span --- a/libcxx/include/span +++ b/libcxx/include/span @@ -134,6 +134,7 @@ #include // for array #include // for byte #include // for iterators +#include #include // for remove_cv, etc #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) diff --git a/libcxx/include/tuple b/libcxx/include/tuple --- a/libcxx/include/tuple +++ b/libcxx/include/tuple @@ -151,6 +151,7 @@ #include <__config> #include <__functional_base> +#include <__functional/unwrap_ref.h> #include <__utility/forward.h> #include <__utility/move.h> #include <__tuple> diff --git a/libcxx/include/utility b/libcxx/include/utility --- a/libcxx/include/utility +++ b/libcxx/include/utility @@ -210,1675 +210,21 @@ #include <__config> #include <__debug> #include <__tuple> +#include <__utility/as_const.h> +#include <__utility/cmp.h> #include <__utility/declval.h> +#include <__utility/exchange.h> #include <__utility/forward.h> +#include <__utility/in_place.h> +#include <__utility/integer_sequence.h> #include <__utility/move.h> +#include <__utility/pair.h> +#include <__utility/piecewise_construct.h> +#include <__utility/rel_ops.h> #include <__utility/swap.h> #include <__utility/to_underlying.h> #include -#include -#include -#include #include -#include -#include #include -#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header -#endif - -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - -_LIBCPP_BEGIN_NAMESPACE_STD - -namespace rel_ops -{ - -template -inline _LIBCPP_INLINE_VISIBILITY -bool -operator!=(const _Tp& __x, const _Tp& __y) -{ - return !(__x == __y); -} - -template -inline _LIBCPP_INLINE_VISIBILITY -bool -operator> (const _Tp& __x, const _Tp& __y) -{ - return __y < __x; -} - -template -inline _LIBCPP_INLINE_VISIBILITY -bool -operator<=(const _Tp& __x, const _Tp& __y) -{ - return !(__y < __x); -} - -template -inline _LIBCPP_INLINE_VISIBILITY -bool -operator>=(const _Tp& __x, const _Tp& __y) -{ - return !(__x < __y); -} - -} // rel_ops - -#if _LIBCPP_STD_VER > 14 -template -_LIBCPP_NODISCARD_EXT constexpr add_const_t<_Tp>& as_const(_Tp& __t) noexcept { return __t; } - -template -void as_const(const _Tp&&) = delete; -#endif - -#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_CONCEPTS) -template -struct _IsSameAsAny : _Or<_IsSame<_Tp, _Up>...> {}; - -template -concept __is_safe_integral_cmp = is_integral_v<_Tp> && - !_IsSameAsAny<_Tp, bool, char, -#ifndef _LIBCPP_HAS_NO_CHAR8_T - char8_t, -#endif -#ifndef _LIBCPP_HAS_NO_UNICODE_CHARS - char16_t, char32_t, -#endif - wchar_t>::value; - -template<__is_safe_integral_cmp _Tp, __is_safe_integral_cmp _Up> -_LIBCPP_INLINE_VISIBILITY constexpr -bool cmp_equal(_Tp __t, _Up __u) noexcept -{ - if constexpr (is_signed_v<_Tp> == is_signed_v<_Up>) - return __t == __u; - else if constexpr (is_signed_v<_Tp>) - return __t < 0 ? false : make_unsigned_t<_Tp>(__t) == __u; - else - return __u < 0 ? false : __t == make_unsigned_t<_Up>(__u); -} - -template<__is_safe_integral_cmp _Tp, __is_safe_integral_cmp _Up> -_LIBCPP_INLINE_VISIBILITY constexpr -bool cmp_not_equal(_Tp __t, _Up __u) noexcept -{ - return !_VSTD::cmp_equal(__t, __u); -} - -template<__is_safe_integral_cmp _Tp, __is_safe_integral_cmp _Up> -_LIBCPP_INLINE_VISIBILITY constexpr -bool cmp_less(_Tp __t, _Up __u) noexcept -{ - if constexpr (is_signed_v<_Tp> == is_signed_v<_Up>) - return __t < __u; - else if constexpr (is_signed_v<_Tp>) - return __t < 0 ? true : make_unsigned_t<_Tp>(__t) < __u; - else - return __u < 0 ? false : __t < make_unsigned_t<_Up>(__u); -} - -template<__is_safe_integral_cmp _Tp, __is_safe_integral_cmp _Up> -_LIBCPP_INLINE_VISIBILITY constexpr -bool cmp_greater(_Tp __t, _Up __u) noexcept -{ - return _VSTD::cmp_less(__u, __t); -} - -template<__is_safe_integral_cmp _Tp, __is_safe_integral_cmp _Up> -_LIBCPP_INLINE_VISIBILITY constexpr -bool cmp_less_equal(_Tp __t, _Up __u) noexcept -{ - return !_VSTD::cmp_greater(__t, __u); -} - -template<__is_safe_integral_cmp _Tp, __is_safe_integral_cmp _Up> -_LIBCPP_INLINE_VISIBILITY constexpr -bool cmp_greater_equal(_Tp __t, _Up __u) noexcept -{ - return !_VSTD::cmp_less(__t, __u); -} - -template<__is_safe_integral_cmp _Tp, __is_safe_integral_cmp _Up> -_LIBCPP_INLINE_VISIBILITY constexpr -bool in_range(_Up __u) noexcept -{ - return _VSTD::cmp_less_equal(__u, numeric_limits<_Tp>::max()) && - _VSTD::cmp_greater_equal(__u, numeric_limits<_Tp>::min()); -} -#endif - -struct _LIBCPP_TEMPLATE_VIS piecewise_construct_t { explicit piecewise_construct_t() = default; }; -#if defined(_LIBCPP_CXX03_LANG) || defined(_LIBCPP_BUILDING_LIBRARY) -extern _LIBCPP_EXPORTED_FROM_ABI const piecewise_construct_t piecewise_construct;// = piecewise_construct_t(); -#else -/* _LIBCPP_INLINE_VAR */ constexpr piecewise_construct_t piecewise_construct = piecewise_construct_t(); -#endif - -#if defined(_LIBCPP_DEPRECATED_ABI_DISABLE_PAIR_TRIVIAL_COPY_CTOR) -template -struct __non_trivially_copyable_base { - _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY - __non_trivially_copyable_base() _NOEXCEPT {} - _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY - __non_trivially_copyable_base(__non_trivially_copyable_base const&) _NOEXCEPT {} -}; -#endif - -template -struct _LIBCPP_TEMPLATE_VIS pair -#if defined(_LIBCPP_DEPRECATED_ABI_DISABLE_PAIR_TRIVIAL_COPY_CTOR) -: private __non_trivially_copyable_base<_T1, _T2> -#endif -{ - typedef _T1 first_type; - typedef _T2 second_type; - - _T1 first; - _T2 second; - -#if !defined(_LIBCPP_CXX03_LANG) - pair(pair const&) = default; - pair(pair&&) = default; -#else - // Use the implicitly declared copy constructor in C++03 -#endif - -#ifdef _LIBCPP_CXX03_LANG - _LIBCPP_INLINE_VISIBILITY - pair() : first(), second() {} - - _LIBCPP_INLINE_VISIBILITY - pair(_T1 const& __t1, _T2 const& __t2) : first(__t1), second(__t2) {} - - template - _LIBCPP_INLINE_VISIBILITY - pair(const pair<_U1, _U2>& __p) : first(__p.first), second(__p.second) {} - - _LIBCPP_INLINE_VISIBILITY - pair& operator=(pair const& __p) { - first = __p.first; - second = __p.second; - return *this; - } -#else - template - using _EnableB _LIBCPP_NODEBUG_TYPE = typename enable_if<_Val, bool>::type; - - struct _CheckArgs { - template - static constexpr bool __enable_explicit_default() { - return is_default_constructible<_T1>::value - && is_default_constructible<_T2>::value - && !__enable_implicit_default<>(); - } - - template - static constexpr bool __enable_implicit_default() { - return __is_implicitly_default_constructible<_T1>::value - && __is_implicitly_default_constructible<_T2>::value; - } - - template - static constexpr bool __enable_explicit() { - return is_constructible::value - && is_constructible::value - && (!is_convertible<_U1, first_type>::value - || !is_convertible<_U2, second_type>::value); - } - - template - static constexpr bool __enable_implicit() { - return is_constructible::value - && is_constructible::value - && is_convertible<_U1, first_type>::value - && is_convertible<_U2, second_type>::value; - } - }; - - template - using _CheckArgsDep _LIBCPP_NODEBUG_TYPE = typename conditional< - _MaybeEnable, _CheckArgs, __check_tuple_constructor_fail>::type; - - struct _CheckTupleLikeConstructor { - template - static constexpr bool __enable_implicit() { - return __tuple_convertible<_Tuple, pair>::value; - } - - template - static constexpr bool __enable_explicit() { - return __tuple_constructible<_Tuple, pair>::value - && !__tuple_convertible<_Tuple, pair>::value; - } - - template - static constexpr bool __enable_assign() { - return __tuple_assignable<_Tuple, pair>::value; - } - }; - - template - using _CheckTLC _LIBCPP_NODEBUG_TYPE = typename conditional< - __tuple_like_with_size<_Tuple, 2>::value - && !is_same::type, pair>::value, - _CheckTupleLikeConstructor, - __check_tuple_constructor_fail - >::type; - - template::__enable_explicit_default() - > = false> - explicit _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR - pair() _NOEXCEPT_(is_nothrow_default_constructible::value && - is_nothrow_default_constructible::value) - : first(), second() {} - - template::__enable_implicit_default() - > = false> - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR - pair() _NOEXCEPT_(is_nothrow_default_constructible::value && - is_nothrow_default_constructible::value) - : first(), second() {} - - template ::template __enable_explicit<_T1 const&, _T2 const&>() - > = false> - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 - explicit pair(_T1 const& __t1, _T2 const& __t2) - _NOEXCEPT_(is_nothrow_copy_constructible::value && - is_nothrow_copy_constructible::value) - : first(__t1), second(__t2) {} - - template::template __enable_implicit<_T1 const&, _T2 const&>() - > = false> - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 - pair(_T1 const& __t1, _T2 const& __t2) - _NOEXCEPT_(is_nothrow_copy_constructible::value && - is_nothrow_copy_constructible::value) - : first(__t1), second(__t2) {} - - template() - > = false> - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 - explicit pair(_U1&& __u1, _U2&& __u2) - _NOEXCEPT_((is_nothrow_constructible::value && - is_nothrow_constructible::value)) - : first(_VSTD::forward<_U1>(__u1)), second(_VSTD::forward<_U2>(__u2)) {} - - template() - > = false> - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 - pair(_U1&& __u1, _U2&& __u2) - _NOEXCEPT_((is_nothrow_constructible::value && - is_nothrow_constructible::value)) - : first(_VSTD::forward<_U1>(__u1)), second(_VSTD::forward<_U2>(__u2)) {} - - template() - > = false> - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 - explicit pair(pair<_U1, _U2> const& __p) - _NOEXCEPT_((is_nothrow_constructible::value && - is_nothrow_constructible::value)) - : first(__p.first), second(__p.second) {} - - template() - > = false> - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 - pair(pair<_U1, _U2> const& __p) - _NOEXCEPT_((is_nothrow_constructible::value && - is_nothrow_constructible::value)) - : first(__p.first), second(__p.second) {} - - template() - > = false> - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 - explicit pair(pair<_U1, _U2>&&__p) - _NOEXCEPT_((is_nothrow_constructible::value && - is_nothrow_constructible::value)) - : first(_VSTD::forward<_U1>(__p.first)), second(_VSTD::forward<_U2>(__p.second)) {} - - template() - > = false> - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 - pair(pair<_U1, _U2>&& __p) - _NOEXCEPT_((is_nothrow_constructible::value && - is_nothrow_constructible::value)) - : first(_VSTD::forward<_U1>(__p.first)), second(_VSTD::forward<_U2>(__p.second)) {} - - template::template __enable_explicit<_Tuple>() - > = false> - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 - explicit pair(_Tuple&& __p) - : first(_VSTD::get<0>(_VSTD::forward<_Tuple>(__p))), - second(_VSTD::get<1>(_VSTD::forward<_Tuple>(__p))) {} - - template::template __enable_implicit<_Tuple>() - > = false> - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 - pair(_Tuple&& __p) - : first(_VSTD::get<0>(_VSTD::forward<_Tuple>(__p))), - second(_VSTD::get<1>(_VSTD::forward<_Tuple>(__p))) {} - - template - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 - pair(piecewise_construct_t __pc, - tuple<_Args1...> __first_args, tuple<_Args2...> __second_args) - _NOEXCEPT_((is_nothrow_constructible::value && - is_nothrow_constructible::value)) - : pair(__pc, __first_args, __second_args, - typename __make_tuple_indices::type(), - typename __make_tuple_indices::type()) {} - - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 - pair& operator=(typename conditional< - is_copy_assignable::value && - is_copy_assignable::value, - pair, __nat>::type const& __p) - _NOEXCEPT_(is_nothrow_copy_assignable::value && - is_nothrow_copy_assignable::value) - { - first = __p.first; - second = __p.second; - return *this; - } - - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 - pair& operator=(typename conditional< - is_move_assignable::value && - is_move_assignable::value, - pair, __nat>::type&& __p) - _NOEXCEPT_(is_nothrow_move_assignable::value && - is_nothrow_move_assignable::value) - { - first = _VSTD::forward(__p.first); - second = _VSTD::forward(__p.second); - return *this; - } - - template ::template __enable_assign<_Tuple>() - > = false> - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 - pair& operator=(_Tuple&& __p) { - first = _VSTD::get<0>(_VSTD::forward<_Tuple>(__p)); - second = _VSTD::get<1>(_VSTD::forward<_Tuple>(__p)); - return *this; - } -#endif - - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 - void - swap(pair& __p) _NOEXCEPT_(__is_nothrow_swappable::value && - __is_nothrow_swappable::value) - { - using _VSTD::swap; - swap(first, __p.first); - swap(second, __p.second); - } -private: - -#ifndef _LIBCPP_CXX03_LANG - template - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 - pair(piecewise_construct_t, - tuple<_Args1...>& __first_args, tuple<_Args2...>& __second_args, - __tuple_indices<_I1...>, __tuple_indices<_I2...>); -#endif -}; - -#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES -template -pair(_T1, _T2) -> pair<_T1, _T2>; -#endif // _LIBCPP_HAS_NO_DEDUCTION_GUIDES - -template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 -bool -operator==(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y) -{ - return __x.first == __y.first && __x.second == __y.second; -} - -template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 -bool -operator!=(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y) -{ - return !(__x == __y); -} - -template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 -bool -operator< (const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y) -{ - return __x.first < __y.first || (!(__y.first < __x.first) && __x.second < __y.second); -} - -template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 -bool -operator> (const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y) -{ - return __y < __x; -} - -template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 -bool -operator>=(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y) -{ - return !(__x < __y); -} - -template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 -bool -operator<=(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y) -{ - return !(__y < __x); -} - -template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -typename enable_if -< - __is_swappable<_T1>::value && - __is_swappable<_T2>::value, - void ->::type -swap(pair<_T1, _T2>& __x, pair<_T1, _T2>& __y) - _NOEXCEPT_((__is_nothrow_swappable<_T1>::value && - __is_nothrow_swappable<_T2>::value)) -{ - __x.swap(__y); -} - -template -struct __unwrap_reference { typedef _LIBCPP_NODEBUG_TYPE _Tp type; }; - -template -struct __unwrap_reference > { typedef _LIBCPP_NODEBUG_TYPE _Tp& type; }; - -#if _LIBCPP_STD_VER > 17 -template -struct unwrap_reference : __unwrap_reference<_Tp> { }; - -template -struct unwrap_ref_decay : unwrap_reference::type> { }; -#endif // > C++17 - -template -struct __unwrap_ref_decay -#if _LIBCPP_STD_VER > 17 - : unwrap_ref_decay<_Tp> -#else - : __unwrap_reference::type> -#endif -{ }; - -#ifndef _LIBCPP_CXX03_LANG - -template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 -pair::type, typename __unwrap_ref_decay<_T2>::type> -make_pair(_T1&& __t1, _T2&& __t2) -{ - return pair::type, typename __unwrap_ref_decay<_T2>::type> - (_VSTD::forward<_T1>(__t1), _VSTD::forward<_T2>(__t2)); -} - -#else // _LIBCPP_CXX03_LANG - -template -inline _LIBCPP_INLINE_VISIBILITY -pair<_T1,_T2> -make_pair(_T1 __x, _T2 __y) -{ - return pair<_T1, _T2>(__x, __y); -} - -#endif // _LIBCPP_CXX03_LANG - -template - struct _LIBCPP_TEMPLATE_VIS tuple_size > - : public integral_constant {}; - -template -struct _LIBCPP_TEMPLATE_VIS tuple_element<_Ip, pair<_T1, _T2> > -{ - static_assert(_Ip < 2, "Index out of bounds in std::tuple_element>"); -}; - -template -struct _LIBCPP_TEMPLATE_VIS tuple_element<0, pair<_T1, _T2> > -{ - typedef _LIBCPP_NODEBUG_TYPE _T1 type; -}; - -template -struct _LIBCPP_TEMPLATE_VIS tuple_element<1, pair<_T1, _T2> > -{ - typedef _LIBCPP_NODEBUG_TYPE _T2 type; -}; - -template struct __get_pair; - -template <> -struct __get_pair<0> -{ - template - static - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 - _T1& - get(pair<_T1, _T2>& __p) _NOEXCEPT {return __p.first;} - - template - static - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 - const _T1& - get(const pair<_T1, _T2>& __p) _NOEXCEPT {return __p.first;} - -#ifndef _LIBCPP_CXX03_LANG - template - static - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 - _T1&& - get(pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<_T1>(__p.first);} - - template - static - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 - const _T1&& - get(const pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward(__p.first);} -#endif // _LIBCPP_CXX03_LANG -}; - -template <> -struct __get_pair<1> -{ - template - static - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 - _T2& - get(pair<_T1, _T2>& __p) _NOEXCEPT {return __p.second;} - - template - static - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 - const _T2& - get(const pair<_T1, _T2>& __p) _NOEXCEPT {return __p.second;} - -#ifndef _LIBCPP_CXX03_LANG - template - static - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 - _T2&& - get(pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<_T2>(__p.second);} - - template - static - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 - const _T2&& - get(const pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward(__p.second);} -#endif // _LIBCPP_CXX03_LANG -}; - -template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 -typename tuple_element<_Ip, pair<_T1, _T2> >::type& -get(pair<_T1, _T2>& __p) _NOEXCEPT -{ - return __get_pair<_Ip>::get(__p); -} - -template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 -const typename tuple_element<_Ip, pair<_T1, _T2> >::type& -get(const pair<_T1, _T2>& __p) _NOEXCEPT -{ - return __get_pair<_Ip>::get(__p); -} - -#ifndef _LIBCPP_CXX03_LANG -template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 -typename tuple_element<_Ip, pair<_T1, _T2> >::type&& -get(pair<_T1, _T2>&& __p) _NOEXCEPT -{ - return __get_pair<_Ip>::get(_VSTD::move(__p)); -} - -template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 -const typename tuple_element<_Ip, pair<_T1, _T2> >::type&& -get(const pair<_T1, _T2>&& __p) _NOEXCEPT -{ - return __get_pair<_Ip>::get(_VSTD::move(__p)); -} -#endif // _LIBCPP_CXX03_LANG - -#if _LIBCPP_STD_VER > 11 -template -inline _LIBCPP_INLINE_VISIBILITY -constexpr _T1 & get(pair<_T1, _T2>& __p) _NOEXCEPT -{ - return __get_pair<0>::get(__p); -} - -template -inline _LIBCPP_INLINE_VISIBILITY -constexpr _T1 const & get(pair<_T1, _T2> const& __p) _NOEXCEPT -{ - return __get_pair<0>::get(__p); -} - -template -inline _LIBCPP_INLINE_VISIBILITY -constexpr _T1 && get(pair<_T1, _T2>&& __p) _NOEXCEPT -{ - return __get_pair<0>::get(_VSTD::move(__p)); -} - -template -inline _LIBCPP_INLINE_VISIBILITY -constexpr _T1 const && get(pair<_T1, _T2> const&& __p) _NOEXCEPT -{ - return __get_pair<0>::get(_VSTD::move(__p)); -} - -template -inline _LIBCPP_INLINE_VISIBILITY -constexpr _T1 & get(pair<_T2, _T1>& __p) _NOEXCEPT -{ - return __get_pair<1>::get(__p); -} - -template -inline _LIBCPP_INLINE_VISIBILITY -constexpr _T1 const & get(pair<_T2, _T1> const& __p) _NOEXCEPT -{ - return __get_pair<1>::get(__p); -} - -template -inline _LIBCPP_INLINE_VISIBILITY -constexpr _T1 && get(pair<_T2, _T1>&& __p) _NOEXCEPT -{ - return __get_pair<1>::get(_VSTD::move(__p)); -} - -template -inline _LIBCPP_INLINE_VISIBILITY -constexpr _T1 const && get(pair<_T2, _T1> const&& __p) _NOEXCEPT -{ - return __get_pair<1>::get(_VSTD::move(__p)); -} - -#endif - -#if _LIBCPP_STD_VER > 11 - -template -struct _LIBCPP_TEMPLATE_VIS integer_sequence -{ - typedef _Tp value_type; - static_assert( is_integral<_Tp>::value, - "std::integer_sequence can only be instantiated with an integral type" ); - static - _LIBCPP_INLINE_VISIBILITY - constexpr - size_t - size() noexcept { return sizeof...(_Ip); } -}; - -template - using index_sequence = integer_sequence; - -#if __has_builtin(__make_integer_seq) && !defined(_LIBCPP_TESTING_FALLBACK_MAKE_INTEGER_SEQUENCE) - -template -using __make_integer_sequence _LIBCPP_NODEBUG_TYPE = __make_integer_seq; - -#else - -template using __make_integer_sequence_unchecked _LIBCPP_NODEBUG_TYPE = - typename __detail::__make<_Np>::type::template __convert; - -template -struct __make_integer_sequence_checked -{ - static_assert(is_integral<_Tp>::value, - "std::make_integer_sequence can only be instantiated with an integral type" ); - static_assert(0 <= _Ep, "std::make_integer_sequence must have a non-negative sequence length"); - // Workaround GCC bug by preventing bad installations when 0 <= _Ep - // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68929 - typedef _LIBCPP_NODEBUG_TYPE __make_integer_sequence_unchecked<_Tp, 0 <= _Ep ? _Ep : 0> type; -}; - -template -using __make_integer_sequence _LIBCPP_NODEBUG_TYPE = typename __make_integer_sequence_checked<_Tp, _Ep>::type; - -#endif - -template - using make_integer_sequence = __make_integer_sequence<_Tp, _Np>; - -template - using make_index_sequence = make_integer_sequence; - -template - using index_sequence_for = make_index_sequence; - -#endif // _LIBCPP_STD_VER > 11 - -#if _LIBCPP_STD_VER > 11 -template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_T1 exchange(_T1& __obj, _T2 && __new_value) -{ - _T1 __old_value = _VSTD::move(__obj); - __obj = _VSTD::forward<_T2>(__new_value); - return __old_value; -} -#endif // _LIBCPP_STD_VER > 11 - -#if _LIBCPP_STD_VER > 14 - -struct _LIBCPP_TYPE_VIS in_place_t { - explicit in_place_t() = default; -}; -_LIBCPP_INLINE_VAR constexpr in_place_t in_place{}; - -template -struct _LIBCPP_TEMPLATE_VIS in_place_type_t { - explicit in_place_type_t() = default; -}; -template -_LIBCPP_INLINE_VAR constexpr in_place_type_t<_Tp> in_place_type{}; - -template -struct _LIBCPP_TEMPLATE_VIS in_place_index_t { - explicit in_place_index_t() = default; -}; -template -_LIBCPP_INLINE_VAR constexpr in_place_index_t<_Idx> in_place_index{}; - -template struct __is_inplace_type_imp : false_type {}; -template struct __is_inplace_type_imp> : true_type {}; - -template -using __is_inplace_type = __is_inplace_type_imp<__uncvref_t<_Tp>>; - -template struct __is_inplace_index_imp : false_type {}; -template struct __is_inplace_index_imp> : true_type {}; - -template -using __is_inplace_index = __is_inplace_index_imp<__uncvref_t<_Tp>>; - -#endif // _LIBCPP_STD_VER > 14 - -template -struct _LIBCPP_TEMPLATE_VIS unary_function -{ - typedef _Arg argument_type; - typedef _Result result_type; -}; - -template -inline _LIBCPP_INLINE_VISIBILITY -_Size -__loadword(const void* __p) -{ - _Size __r; - _VSTD::memcpy(&__r, __p, sizeof(__r)); - return __r; -} - -// We use murmur2 when size_t is 32 bits, and cityhash64 when size_t -// is 64 bits. This is because cityhash64 uses 64bit x 64bit -// multiplication, which can be very slow on 32-bit systems. -template -struct __murmur2_or_cityhash; - -template -struct __murmur2_or_cityhash<_Size, 32> -{ - inline _Size operator()(const void* __key, _Size __len) - _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK; -}; - -// murmur2 -template -_Size -__murmur2_or_cityhash<_Size, 32>::operator()(const void* __key, _Size __len) -{ - const _Size __m = 0x5bd1e995; - const _Size __r = 24; - _Size __h = __len; - const unsigned char* __data = static_cast(__key); - for (; __len >= 4; __data += 4, __len -= 4) - { - _Size __k = __loadword<_Size>(__data); - __k *= __m; - __k ^= __k >> __r; - __k *= __m; - __h *= __m; - __h ^= __k; - } - switch (__len) - { - case 3: - __h ^= __data[2] << 16; - _LIBCPP_FALLTHROUGH(); - case 2: - __h ^= __data[1] << 8; - _LIBCPP_FALLTHROUGH(); - case 1: - __h ^= __data[0]; - __h *= __m; - } - __h ^= __h >> 13; - __h *= __m; - __h ^= __h >> 15; - return __h; -} - -template -struct __murmur2_or_cityhash<_Size, 64> -{ - inline _Size operator()(const void* __key, _Size __len) _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK; - - private: - // Some primes between 2^63 and 2^64. - static const _Size __k0 = 0xc3a5c85c97cb3127ULL; - static const _Size __k1 = 0xb492b66fbe98f273ULL; - static const _Size __k2 = 0x9ae16a3b2f90404fULL; - static const _Size __k3 = 0xc949d7c7509e6557ULL; - - static _Size __rotate(_Size __val, int __shift) { - return __shift == 0 ? __val : ((__val >> __shift) | (__val << (64 - __shift))); - } - - static _Size __rotate_by_at_least_1(_Size __val, int __shift) { - return (__val >> __shift) | (__val << (64 - __shift)); - } - - static _Size __shift_mix(_Size __val) { - return __val ^ (__val >> 47); - } - - static _Size __hash_len_16(_Size __u, _Size __v) - _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK - { - const _Size __mul = 0x9ddfea08eb382d69ULL; - _Size __a = (__u ^ __v) * __mul; - __a ^= (__a >> 47); - _Size __b = (__v ^ __a) * __mul; - __b ^= (__b >> 47); - __b *= __mul; - return __b; - } - - static _Size __hash_len_0_to_16(const char* __s, _Size __len) - _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK - { - if (__len > 8) { - const _Size __a = __loadword<_Size>(__s); - const _Size __b = __loadword<_Size>(__s + __len - 8); - return __hash_len_16(__a, __rotate_by_at_least_1(__b + __len, __len)) ^ __b; - } - if (__len >= 4) { - const uint32_t __a = __loadword(__s); - const uint32_t __b = __loadword(__s + __len - 4); - return __hash_len_16(__len + (__a << 3), __b); - } - if (__len > 0) { - const unsigned char __a = __s[0]; - const unsigned char __b = __s[__len >> 1]; - const unsigned char __c = __s[__len - 1]; - const uint32_t __y = static_cast(__a) + - (static_cast(__b) << 8); - const uint32_t __z = __len + (static_cast(__c) << 2); - return __shift_mix(__y * __k2 ^ __z * __k3) * __k2; - } - return __k2; - } - - static _Size __hash_len_17_to_32(const char *__s, _Size __len) - _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK - { - const _Size __a = __loadword<_Size>(__s) * __k1; - const _Size __b = __loadword<_Size>(__s + 8); - const _Size __c = __loadword<_Size>(__s + __len - 8) * __k2; - const _Size __d = __loadword<_Size>(__s + __len - 16) * __k0; - return __hash_len_16(__rotate(__a - __b, 43) + __rotate(__c, 30) + __d, - __a + __rotate(__b ^ __k3, 20) - __c + __len); - } - - // Return a 16-byte hash for 48 bytes. Quick and dirty. - // Callers do best to use "random-looking" values for a and b. - static pair<_Size, _Size> __weak_hash_len_32_with_seeds( - _Size __w, _Size __x, _Size __y, _Size __z, _Size __a, _Size __b) - _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK - { - __a += __w; - __b = __rotate(__b + __a + __z, 21); - const _Size __c = __a; - __a += __x; - __a += __y; - __b += __rotate(__a, 44); - return pair<_Size, _Size>(__a + __z, __b + __c); - } - - // Return a 16-byte hash for s[0] ... s[31], a, and b. Quick and dirty. - static pair<_Size, _Size> __weak_hash_len_32_with_seeds( - const char* __s, _Size __a, _Size __b) - _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK - { - return __weak_hash_len_32_with_seeds(__loadword<_Size>(__s), - __loadword<_Size>(__s + 8), - __loadword<_Size>(__s + 16), - __loadword<_Size>(__s + 24), - __a, - __b); - } - - // Return an 8-byte hash for 33 to 64 bytes. - static _Size __hash_len_33_to_64(const char *__s, size_t __len) - _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK - { - _Size __z = __loadword<_Size>(__s + 24); - _Size __a = __loadword<_Size>(__s) + - (__len + __loadword<_Size>(__s + __len - 16)) * __k0; - _Size __b = __rotate(__a + __z, 52); - _Size __c = __rotate(__a, 37); - __a += __loadword<_Size>(__s + 8); - __c += __rotate(__a, 7); - __a += __loadword<_Size>(__s + 16); - _Size __vf = __a + __z; - _Size __vs = __b + __rotate(__a, 31) + __c; - __a = __loadword<_Size>(__s + 16) + __loadword<_Size>(__s + __len - 32); - __z += __loadword<_Size>(__s + __len - 8); - __b = __rotate(__a + __z, 52); - __c = __rotate(__a, 37); - __a += __loadword<_Size>(__s + __len - 24); - __c += __rotate(__a, 7); - __a += __loadword<_Size>(__s + __len - 16); - _Size __wf = __a + __z; - _Size __ws = __b + __rotate(__a, 31) + __c; - _Size __r = __shift_mix((__vf + __ws) * __k2 + (__wf + __vs) * __k0); - return __shift_mix(__r * __k0 + __vs) * __k2; - } -}; - -// cityhash64 -template -_Size -__murmur2_or_cityhash<_Size, 64>::operator()(const void* __key, _Size __len) -{ - const char* __s = static_cast(__key); - if (__len <= 32) { - if (__len <= 16) { - return __hash_len_0_to_16(__s, __len); - } else { - return __hash_len_17_to_32(__s, __len); - } - } else if (__len <= 64) { - return __hash_len_33_to_64(__s, __len); - } - - // For strings over 64 bytes we hash the end first, and then as we - // loop we keep 56 bytes of state: v, w, x, y, and z. - _Size __x = __loadword<_Size>(__s + __len - 40); - _Size __y = __loadword<_Size>(__s + __len - 16) + - __loadword<_Size>(__s + __len - 56); - _Size __z = __hash_len_16(__loadword<_Size>(__s + __len - 48) + __len, - __loadword<_Size>(__s + __len - 24)); - pair<_Size, _Size> __v = __weak_hash_len_32_with_seeds(__s + __len - 64, __len, __z); - pair<_Size, _Size> __w = __weak_hash_len_32_with_seeds(__s + __len - 32, __y + __k1, __x); - __x = __x * __k1 + __loadword<_Size>(__s); - - // Decrease len to the nearest multiple of 64, and operate on 64-byte chunks. - __len = (__len - 1) & ~static_cast<_Size>(63); - do { - __x = __rotate(__x + __y + __v.first + __loadword<_Size>(__s + 8), 37) * __k1; - __y = __rotate(__y + __v.second + __loadword<_Size>(__s + 48), 42) * __k1; - __x ^= __w.second; - __y += __v.first + __loadword<_Size>(__s + 40); - __z = __rotate(__z + __w.first, 33) * __k1; - __v = __weak_hash_len_32_with_seeds(__s, __v.second * __k1, __x + __w.first); - __w = __weak_hash_len_32_with_seeds(__s + 32, __z + __w.second, - __y + __loadword<_Size>(__s + 16)); - _VSTD::swap(__z, __x); - __s += 64; - __len -= 64; - } while (__len != 0); - return __hash_len_16( - __hash_len_16(__v.first, __w.first) + __shift_mix(__y) * __k1 + __z, - __hash_len_16(__v.second, __w.second) + __x); -} - -template -struct __scalar_hash; - -_LIBCPP_SUPPRESS_DEPRECATED_PUSH -template -struct __scalar_hash<_Tp, 0> -#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) - : public unary_function<_Tp, size_t> -#endif -{ -_LIBCPP_SUPPRESS_DEPRECATED_POP -#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) - _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; - _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp argument_type; -#endif - _LIBCPP_INLINE_VISIBILITY - size_t operator()(_Tp __v) const _NOEXCEPT - { - union - { - _Tp __t; - size_t __a; - } __u; - __u.__a = 0; - __u.__t = __v; - return __u.__a; - } -}; - -_LIBCPP_SUPPRESS_DEPRECATED_PUSH -template -struct __scalar_hash<_Tp, 1> -#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) - : public unary_function<_Tp, size_t> -#endif -{ -_LIBCPP_SUPPRESS_DEPRECATED_POP -#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) - _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; - _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp argument_type; -#endif - _LIBCPP_INLINE_VISIBILITY - size_t operator()(_Tp __v) const _NOEXCEPT - { - union - { - _Tp __t; - size_t __a; - } __u; - __u.__t = __v; - return __u.__a; - } -}; - -_LIBCPP_SUPPRESS_DEPRECATED_PUSH -template -struct __scalar_hash<_Tp, 2> -#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) - : public unary_function<_Tp, size_t> -#endif -{ -_LIBCPP_SUPPRESS_DEPRECATED_POP -#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) - _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; - _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp argument_type; -#endif - _LIBCPP_INLINE_VISIBILITY - size_t operator()(_Tp __v) const _NOEXCEPT - { - union - { - _Tp __t; - struct - { - size_t __a; - size_t __b; - } __s; - } __u; - __u.__t = __v; - return __murmur2_or_cityhash()(&__u, sizeof(__u)); - } -}; - -_LIBCPP_SUPPRESS_DEPRECATED_PUSH -template -struct __scalar_hash<_Tp, 3> -#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) - : public unary_function<_Tp, size_t> -#endif -{ -_LIBCPP_SUPPRESS_DEPRECATED_POP -#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) - _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; - _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp argument_type; -#endif - _LIBCPP_INLINE_VISIBILITY - size_t operator()(_Tp __v) const _NOEXCEPT - { - union - { - _Tp __t; - struct - { - size_t __a; - size_t __b; - size_t __c; - } __s; - } __u; - __u.__t = __v; - return __murmur2_or_cityhash()(&__u, sizeof(__u)); - } -}; - -_LIBCPP_SUPPRESS_DEPRECATED_PUSH -template -struct __scalar_hash<_Tp, 4> -#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) - : public unary_function<_Tp, size_t> -#endif -{ -_LIBCPP_SUPPRESS_DEPRECATED_POP -#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) - _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; - _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp argument_type; -#endif - _LIBCPP_INLINE_VISIBILITY - size_t operator()(_Tp __v) const _NOEXCEPT - { - union - { - _Tp __t; - struct - { - size_t __a; - size_t __b; - size_t __c; - size_t __d; - } __s; - } __u; - __u.__t = __v; - return __murmur2_or_cityhash()(&__u, sizeof(__u)); - } -}; - -struct _PairT { - size_t first; - size_t second; -}; - -_LIBCPP_INLINE_VISIBILITY -inline size_t __hash_combine(size_t __lhs, size_t __rhs) _NOEXCEPT { - typedef __scalar_hash<_PairT> _HashT; - const _PairT __p = {__lhs, __rhs}; - return _HashT()(__p); -} - -_LIBCPP_SUPPRESS_DEPRECATED_PUSH -template -struct _LIBCPP_TEMPLATE_VIS hash<_Tp*> -#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) - : public unary_function<_Tp*, size_t> -#endif -{ -_LIBCPP_SUPPRESS_DEPRECATED_POP -#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) - _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; - _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp* argument_type; -#endif - _LIBCPP_INLINE_VISIBILITY - size_t operator()(_Tp* __v) const _NOEXCEPT - { - union - { - _Tp* __t; - size_t __a; - } __u; - __u.__t = __v; - return __murmur2_or_cityhash()(&__u, sizeof(__u)); - } -}; - -_LIBCPP_SUPPRESS_DEPRECATED_PUSH -template <> -struct _LIBCPP_TEMPLATE_VIS hash -#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) - : public unary_function -#endif -{ -_LIBCPP_SUPPRESS_DEPRECATED_POP -#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) - _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; - _LIBCPP_DEPRECATED_IN_CXX17 typedef bool argument_type; -#endif - _LIBCPP_INLINE_VISIBILITY - size_t operator()(bool __v) const _NOEXCEPT {return static_cast(__v);} -}; - -_LIBCPP_SUPPRESS_DEPRECATED_PUSH -template <> -struct _LIBCPP_TEMPLATE_VIS hash -#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) - : public unary_function -#endif -{ -_LIBCPP_SUPPRESS_DEPRECATED_POP -#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) - _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; - _LIBCPP_DEPRECATED_IN_CXX17 typedef char argument_type; -#endif - _LIBCPP_INLINE_VISIBILITY - size_t operator()(char __v) const _NOEXCEPT {return static_cast(__v);} -}; - -_LIBCPP_SUPPRESS_DEPRECATED_PUSH -template <> -struct _LIBCPP_TEMPLATE_VIS hash -#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) - : public unary_function -#endif -{ -_LIBCPP_SUPPRESS_DEPRECATED_POP -#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) - _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; - _LIBCPP_DEPRECATED_IN_CXX17 typedef signed char argument_type; -#endif - _LIBCPP_INLINE_VISIBILITY - size_t operator()(signed char __v) const _NOEXCEPT {return static_cast(__v);} -}; - -_LIBCPP_SUPPRESS_DEPRECATED_PUSH -template <> -struct _LIBCPP_TEMPLATE_VIS hash -#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) - : public unary_function -#endif -{ -_LIBCPP_SUPPRESS_DEPRECATED_POP -#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) - _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; - _LIBCPP_DEPRECATED_IN_CXX17 typedef unsigned char argument_type; -#endif - _LIBCPP_INLINE_VISIBILITY - size_t operator()(unsigned char __v) const _NOEXCEPT {return static_cast(__v);} -}; - -#ifndef _LIBCPP_HAS_NO_CHAR8_T -_LIBCPP_SUPPRESS_DEPRECATED_PUSH -template <> -struct _LIBCPP_TEMPLATE_VIS hash -#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) - : public unary_function -#endif -{ -_LIBCPP_SUPPRESS_DEPRECATED_POP -#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) - _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; - _LIBCPP_DEPRECATED_IN_CXX17 typedef char8_t argument_type; -#endif - _LIBCPP_INLINE_VISIBILITY - size_t operator()(char8_t __v) const _NOEXCEPT {return static_cast(__v);} -}; -#endif // !_LIBCPP_HAS_NO_CHAR8_T - -#ifndef _LIBCPP_HAS_NO_UNICODE_CHARS - -_LIBCPP_SUPPRESS_DEPRECATED_PUSH -template <> -struct _LIBCPP_TEMPLATE_VIS hash -#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) - : public unary_function -#endif -{ -_LIBCPP_SUPPRESS_DEPRECATED_POP -#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) - _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; - _LIBCPP_DEPRECATED_IN_CXX17 typedef char16_t argument_type; -#endif - _LIBCPP_INLINE_VISIBILITY - size_t operator()(char16_t __v) const _NOEXCEPT {return static_cast(__v);} -}; - -_LIBCPP_SUPPRESS_DEPRECATED_PUSH -template <> -struct _LIBCPP_TEMPLATE_VIS hash -#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) - : public unary_function -#endif -{ -_LIBCPP_SUPPRESS_DEPRECATED_POP -#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) - _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; - _LIBCPP_DEPRECATED_IN_CXX17 typedef char32_t argument_type; -#endif - _LIBCPP_INLINE_VISIBILITY - size_t operator()(char32_t __v) const _NOEXCEPT {return static_cast(__v);} -}; - -#endif // _LIBCPP_HAS_NO_UNICODE_CHARS - -_LIBCPP_SUPPRESS_DEPRECATED_PUSH -template <> -struct _LIBCPP_TEMPLATE_VIS hash -#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) - : public unary_function -#endif -{ -_LIBCPP_SUPPRESS_DEPRECATED_POP -#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) - _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; - _LIBCPP_DEPRECATED_IN_CXX17 typedef wchar_t argument_type; -#endif - _LIBCPP_INLINE_VISIBILITY - size_t operator()(wchar_t __v) const _NOEXCEPT {return static_cast(__v);} -}; - -_LIBCPP_SUPPRESS_DEPRECATED_PUSH -template <> -struct _LIBCPP_TEMPLATE_VIS hash -#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) - : public unary_function -#endif -{ -_LIBCPP_SUPPRESS_DEPRECATED_POP -#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) - _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; - _LIBCPP_DEPRECATED_IN_CXX17 typedef short argument_type; -#endif - _LIBCPP_INLINE_VISIBILITY - size_t operator()(short __v) const _NOEXCEPT {return static_cast(__v);} -}; - -_LIBCPP_SUPPRESS_DEPRECATED_PUSH -template <> -struct _LIBCPP_TEMPLATE_VIS hash -#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) - : public unary_function -#endif -{ -_LIBCPP_SUPPRESS_DEPRECATED_POP -#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) - _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; - _LIBCPP_DEPRECATED_IN_CXX17 typedef unsigned short argument_type; -#endif - _LIBCPP_INLINE_VISIBILITY - size_t operator()(unsigned short __v) const _NOEXCEPT {return static_cast(__v);} -}; - -_LIBCPP_SUPPRESS_DEPRECATED_PUSH -template <> -struct _LIBCPP_TEMPLATE_VIS hash -#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) - : public unary_function -#endif -{ -_LIBCPP_SUPPRESS_DEPRECATED_POP -#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) - _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; - _LIBCPP_DEPRECATED_IN_CXX17 typedef int argument_type; -#endif - _LIBCPP_INLINE_VISIBILITY - size_t operator()(int __v) const _NOEXCEPT {return static_cast(__v);} -}; - -_LIBCPP_SUPPRESS_DEPRECATED_PUSH -template <> -struct _LIBCPP_TEMPLATE_VIS hash -#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) - : public unary_function -#endif -{ -_LIBCPP_SUPPRESS_DEPRECATED_POP -#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) - _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; - _LIBCPP_DEPRECATED_IN_CXX17 typedef unsigned int argument_type; -#endif - _LIBCPP_INLINE_VISIBILITY - size_t operator()(unsigned int __v) const _NOEXCEPT {return static_cast(__v);} -}; - -_LIBCPP_SUPPRESS_DEPRECATED_PUSH -template <> -struct _LIBCPP_TEMPLATE_VIS hash -#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) - : public unary_function -#endif -{ -_LIBCPP_SUPPRESS_DEPRECATED_POP -#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) - _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; - _LIBCPP_DEPRECATED_IN_CXX17 typedef long argument_type; -#endif - _LIBCPP_INLINE_VISIBILITY - size_t operator()(long __v) const _NOEXCEPT {return static_cast(__v);} -}; - -_LIBCPP_SUPPRESS_DEPRECATED_PUSH -template <> -struct _LIBCPP_TEMPLATE_VIS hash -#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) - : public unary_function -#endif -{ -_LIBCPP_SUPPRESS_DEPRECATED_POP -#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) - _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; - _LIBCPP_DEPRECATED_IN_CXX17 typedef unsigned long argument_type; -#endif - _LIBCPP_INLINE_VISIBILITY - size_t operator()(unsigned long __v) const _NOEXCEPT {return static_cast(__v);} -}; - -template <> -struct _LIBCPP_TEMPLATE_VIS hash - : public __scalar_hash -{ -}; - -template <> -struct _LIBCPP_TEMPLATE_VIS hash - : public __scalar_hash -{ -}; - -#ifndef _LIBCPP_HAS_NO_INT128 - -template <> -struct _LIBCPP_TEMPLATE_VIS hash<__int128_t> - : public __scalar_hash<__int128_t> -{ -}; - -template <> -struct _LIBCPP_TEMPLATE_VIS hash<__uint128_t> - : public __scalar_hash<__uint128_t> -{ -}; - -#endif - -template <> -struct _LIBCPP_TEMPLATE_VIS hash - : public __scalar_hash -{ - _LIBCPP_INLINE_VISIBILITY - size_t operator()(float __v) const _NOEXCEPT - { - // -0.0 and 0.0 should return same hash - if (__v == 0.0f) - return 0; - return __scalar_hash::operator()(__v); - } -}; - -template <> -struct _LIBCPP_TEMPLATE_VIS hash - : public __scalar_hash -{ - _LIBCPP_INLINE_VISIBILITY - size_t operator()(double __v) const _NOEXCEPT - { - // -0.0 and 0.0 should return same hash - if (__v == 0.0) - return 0; - return __scalar_hash::operator()(__v); - } -}; - -template <> -struct _LIBCPP_TEMPLATE_VIS hash - : public __scalar_hash -{ - _LIBCPP_INLINE_VISIBILITY - size_t operator()(long double __v) const _NOEXCEPT - { - // -0.0 and 0.0 should return same hash - if (__v == 0.0L) - return 0; -#if defined(__i386__) || (defined(__x86_64__) && defined(__ILP32__)) - // Zero out padding bits - union - { - long double __t; - struct - { - size_t __a; - size_t __b; - size_t __c; - size_t __d; - } __s; - } __u; - __u.__s.__a = 0; - __u.__s.__b = 0; - __u.__s.__c = 0; - __u.__s.__d = 0; - __u.__t = __v; - return __u.__s.__a ^ __u.__s.__b ^ __u.__s.__c ^ __u.__s.__d; -#elif defined(__x86_64__) - // Zero out padding bits - union - { - long double __t; - struct - { - size_t __a; - size_t __b; - } __s; - } __u; - __u.__s.__a = 0; - __u.__s.__b = 0; - __u.__t = __v; - return __u.__s.__a ^ __u.__s.__b; -#else - return __scalar_hash::operator()(__v); -#endif - } -}; - -#if _LIBCPP_STD_VER > 11 - -_LIBCPP_SUPPRESS_DEPRECATED_PUSH -template ::value> -struct _LIBCPP_TEMPLATE_VIS __enum_hash -#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) - : public unary_function<_Tp, size_t> -#endif -{ -_LIBCPP_SUPPRESS_DEPRECATED_POP -#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) - _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; - _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp argument_type; -#endif - _LIBCPP_INLINE_VISIBILITY - size_t operator()(_Tp __v) const _NOEXCEPT - { - typedef typename underlying_type<_Tp>::type type; - return hash{}(static_cast(__v)); - } -}; -template -struct _LIBCPP_TEMPLATE_VIS __enum_hash<_Tp, false> { - __enum_hash() = delete; - __enum_hash(__enum_hash const&) = delete; - __enum_hash& operator=(__enum_hash const&) = delete; -}; - -template -struct _LIBCPP_TEMPLATE_VIS hash : public __enum_hash<_Tp> -{ -}; -#endif - -#if _LIBCPP_STD_VER > 14 - -_LIBCPP_SUPPRESS_DEPRECATED_PUSH -template <> -struct _LIBCPP_TEMPLATE_VIS hash -#if !defined(_LIBCPP_ABI_NO_BINDER_BASES) - : public unary_function -#endif -{ -_LIBCPP_SUPPRESS_DEPRECATED_POP -#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) - _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type; - _LIBCPP_DEPRECATED_IN_CXX17 typedef nullptr_t argument_type; -#endif - _LIBCPP_INLINE_VISIBILITY - size_t operator()(nullptr_t) const _NOEXCEPT { - return 662607004ull; - } -}; -#endif - -#ifndef _LIBCPP_CXX03_LANG -template -using __check_hash_requirements _LIBCPP_NODEBUG_TYPE = integral_constant::value && - is_move_constructible<_Hash>::value && - __invokable_r::value ->; - -template > -using __has_enabled_hash _LIBCPP_NODEBUG_TYPE = integral_constant::value && - is_default_constructible<_Hash>::value ->; - -#if _LIBCPP_STD_VER > 14 -template -using __enable_hash_helper_imp _LIBCPP_NODEBUG_TYPE = _Type; - -template -using __enable_hash_helper _LIBCPP_NODEBUG_TYPE = __enable_hash_helper_imp<_Type, - typename enable_if<__all<__has_enabled_hash<_Keys>::value...>::value>::type ->; -#else -template -using __enable_hash_helper _LIBCPP_NODEBUG_TYPE = _Type; -#endif - -#endif // !_LIBCPP_CXX03_LANG - -_LIBCPP_END_NAMESPACE_STD - -_LIBCPP_POP_MACROS - #endif // _LIBCPP_UTILITY diff --git a/libcxx/test/libcxx/utilities/utility/pairs/pairs.pair/pair.tuple_element.fail.cpp b/libcxx/test/libcxx/utilities/utility/pairs/pairs.pair/pair.tuple_element.fail.cpp --- a/libcxx/test/libcxx/utilities/utility/pairs/pairs.pair/pair.tuple_element.fail.cpp +++ b/libcxx/test/libcxx/utilities/utility/pairs/pairs.pair/pair.tuple_element.fail.cpp @@ -19,7 +19,7 @@ { typedef std::pair P; std::tuple_element<2, P>::type foo; // expected-note {{requested here}} - // expected-error-re@utility:* {{static_assert failed{{( due to requirement '2U[L]{0,2} < 2')?}} "Index out of bounds in std::tuple_element>"}} + // expected-error-re@*:* {{static_assert failed{{( due to requirement '2U[L]{0,2} < 2')?}} "Index out of bounds in std::tuple_element>"}} } return 0; diff --git a/libcxx/test/std/utilities/intseq/intseq.make/make_integer_seq.fail.cpp b/libcxx/test/std/utilities/intseq/intseq.make/make_integer_seq.fail.cpp --- a/libcxx/test/std/utilities/intseq/intseq.make/make_integer_seq.fail.cpp +++ b/libcxx/test/std/utilities/intseq/intseq.make/make_integer_seq.fail.cpp @@ -29,9 +29,9 @@ // std::make_integer_sequence is implemented using a compiler builtin if available. // this builtin has different diagnostic messages than the fallback implementation. #if TEST_HAS_BUILTIN(__make_integer_seq) && !defined(_LIBCPP_TESTING_FALLBACK_MAKE_INTEGER_SEQUENCE) - MakeSeqT i; // expected-error@utility:* {{integer sequences must have non-negative sequence length}} + MakeSeqT i; // expected-error@*:* {{integer sequences must have non-negative sequence length}} #else - MakeSeqT i; // expected-error@utility:* {{static_assert failed "std::make_integer_sequence must have a non-negative sequence length"}} + MakeSeqT i; // expected-error@*:* {{static_assert failed "std::make_integer_sequence must have a non-negative sequence length"}} #endif return 0; diff --git a/libcxx/test/std/utilities/memory/util.smartptr/util.smartptr.hash/enabled_hash.pass.cpp b/libcxx/test/std/utilities/memory/util.smartptr/util.smartptr.hash/enabled_hash.pass.cpp --- a/libcxx/test/std/utilities/memory/util.smartptr/util.smartptr.hash/enabled_hash.pass.cpp +++ b/libcxx/test/std/utilities/memory/util.smartptr/util.smartptr.hash/enabled_hash.pass.cpp @@ -15,6 +15,8 @@ #include +#include + #include "poisoned_hash_helper.h" #include "test_macros.h" diff --git a/libcxx/test/std/utilities/memory/util.smartptr/util.smartptr.hash/hash_shared_ptr.pass.cpp b/libcxx/test/std/utilities/memory/util.smartptr/util.smartptr.hash/hash_shared_ptr.pass.cpp --- a/libcxx/test/std/utilities/memory/util.smartptr/util.smartptr.hash/hash_shared_ptr.pass.cpp +++ b/libcxx/test/std/utilities/memory/util.smartptr/util.smartptr.hash/hash_shared_ptr.pass.cpp @@ -17,7 +17,9 @@ // }; #include + #include +#include #include "test_macros.h" diff --git a/libcxx/test/std/utilities/memory/util.smartptr/util.smartptr.hash/hash_unique_ptr.pass.cpp b/libcxx/test/std/utilities/memory/util.smartptr/util.smartptr.hash/hash_unique_ptr.pass.cpp --- a/libcxx/test/std/utilities/memory/util.smartptr/util.smartptr.hash/hash_unique_ptr.pass.cpp +++ b/libcxx/test/std/utilities/memory/util.smartptr/util.smartptr.hash/hash_unique_ptr.pass.cpp @@ -17,7 +17,9 @@ // }; #include + #include +#include #include "test_macros.h" diff --git a/libcxx/test/std/utilities/type.index/type.index.hash/enabled_hash.pass.cpp b/libcxx/test/std/utilities/type.index/type.index.hash/enabled_hash.pass.cpp --- a/libcxx/test/std/utilities/type.index/type.index.hash/enabled_hash.pass.cpp +++ b/libcxx/test/std/utilities/type.index/type.index.hash/enabled_hash.pass.cpp @@ -15,6 +15,8 @@ #include +#include + #include "poisoned_hash_helper.h" #include "test_macros.h" diff --git a/libcxx/test/std/utilities/utility/pairs/pair.astuple/tuple_element.fail.cpp b/libcxx/test/std/utilities/utility/pairs/pair.astuple/tuple_element.fail.cpp --- a/libcxx/test/std/utilities/utility/pairs/pair.astuple/tuple_element.fail.cpp +++ b/libcxx/test/std/utilities/utility/pairs/pair.astuple/tuple_element.fail.cpp @@ -17,7 +17,7 @@ int main(int, char**) { typedef std::pair T; - std::tuple_element<2, T>::type foo; // expected-error@utility:* {{Index out of bounds in std::tuple_element>}} + std::tuple_element<2, T>::type foo; // expected-error@*:* {{Index out of bounds in std::tuple_element>}} - return 0; + return 0; } diff --git a/libcxx/test/std/utilities/utility/utility.underlying/to_underlying.pass.cpp b/libcxx/test/std/utilities/utility/utility.underlying/to_underlying.pass.cpp --- a/libcxx/test/std/utilities/utility/utility.underlying/to_underlying.pass.cpp +++ b/libcxx/test/std/utilities/utility/utility.underlying/to_underlying.pass.cpp @@ -14,6 +14,7 @@ #include #include +#include #include #include "test_macros.h" diff --git a/libcxx/test/support/poisoned_hash_helper.h b/libcxx/test/support/poisoned_hash_helper.h --- a/libcxx/test/support/poisoned_hash_helper.h +++ b/libcxx/test/support/poisoned_hash_helper.h @@ -9,9 +9,9 @@ #ifndef SUPPORT_POISONED_HASH_HELPER_H #define SUPPORT_POISONED_HASH_HELPER_H -#include <__utility/move.h> // TODO: replace with when std::hash is moved out of the header #include #include +#include #include "test_macros.h" #include "test_workarounds.h"