Index: include/__functional_base =================================================================== --- include/__functional_base +++ include/__functional_base @@ -16,6 +16,7 @@ #include #include #include +#include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header @@ -23,13 +24,6 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template -struct _LIBCPP_TEMPLATE_VIS unary_function -{ - typedef _Arg argument_type; - typedef _Result result_type; -}; - template struct _LIBCPP_TEMPLATE_VIS binary_function { Index: include/functional =================================================================== --- include/functional +++ include/functional @@ -485,6 +485,7 @@ #include #include #include +#include #include <__functional_base> @@ -2339,247 +2340,6 @@ #endif // _LIBCPP_HAS_NO_VARIADICS -template <> -struct _LIBCPP_TEMPLATE_VIS hash - : public unary_function -{ - _LIBCPP_INLINE_VISIBILITY - size_t operator()(bool __v) const _NOEXCEPT {return static_cast(__v);} -}; - -template <> -struct _LIBCPP_TEMPLATE_VIS hash - : public unary_function -{ - _LIBCPP_INLINE_VISIBILITY - size_t operator()(char __v) const _NOEXCEPT {return static_cast(__v);} -}; - -template <> -struct _LIBCPP_TEMPLATE_VIS hash - : public unary_function -{ - _LIBCPP_INLINE_VISIBILITY - size_t operator()(signed char __v) const _NOEXCEPT {return static_cast(__v);} -}; - -template <> -struct _LIBCPP_TEMPLATE_VIS hash - : public unary_function -{ - _LIBCPP_INLINE_VISIBILITY - size_t operator()(unsigned char __v) const _NOEXCEPT {return static_cast(__v);} -}; - -#ifndef _LIBCPP_HAS_NO_UNICODE_CHARS - -template <> -struct _LIBCPP_TEMPLATE_VIS hash - : public unary_function -{ - _LIBCPP_INLINE_VISIBILITY - size_t operator()(char16_t __v) const _NOEXCEPT {return static_cast(__v);} -}; - -template <> -struct _LIBCPP_TEMPLATE_VIS hash - : public unary_function -{ - _LIBCPP_INLINE_VISIBILITY - size_t operator()(char32_t __v) const _NOEXCEPT {return static_cast(__v);} -}; - -#endif // _LIBCPP_HAS_NO_UNICODE_CHARS - -template <> -struct _LIBCPP_TEMPLATE_VIS hash - : public unary_function -{ - _LIBCPP_INLINE_VISIBILITY - size_t operator()(wchar_t __v) const _NOEXCEPT {return static_cast(__v);} -}; - -template <> -struct _LIBCPP_TEMPLATE_VIS hash - : public unary_function -{ - _LIBCPP_INLINE_VISIBILITY - size_t operator()(short __v) const _NOEXCEPT {return static_cast(__v);} -}; - -template <> -struct _LIBCPP_TEMPLATE_VIS hash - : public unary_function -{ - _LIBCPP_INLINE_VISIBILITY - size_t operator()(unsigned short __v) const _NOEXCEPT {return static_cast(__v);} -}; - -template <> -struct _LIBCPP_TEMPLATE_VIS hash - : public unary_function -{ - _LIBCPP_INLINE_VISIBILITY - size_t operator()(int __v) const _NOEXCEPT {return static_cast(__v);} -}; - -template <> -struct _LIBCPP_TEMPLATE_VIS hash - : public unary_function -{ - _LIBCPP_INLINE_VISIBILITY - size_t operator()(unsigned int __v) const _NOEXCEPT {return static_cast(__v);} -}; - -template <> -struct _LIBCPP_TEMPLATE_VIS hash - : public unary_function -{ - _LIBCPP_INLINE_VISIBILITY - size_t operator()(long __v) const _NOEXCEPT {return static_cast(__v);} -}; - -template <> -struct _LIBCPP_TEMPLATE_VIS hash - : public unary_function -{ - _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) - 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) - 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) - return 0; -#if defined(__i386__) - // 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 - -template ::value> -struct _LIBCPP_TEMPLATE_VIS __enum_hash - : public unary_function<_Tp, size_t> -{ - _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 #define __cpp_lib_invoke 201411 Index: include/memory =================================================================== --- include/memory +++ include/memory @@ -3021,360 +3021,13 @@ #endif // _LIBCPP_STD_VER > 11 -template -inline _LIBCPP_INLINE_VISIBILITY -_Size -__loadword(const void* __p) -{ - _Size __r; - std::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> -{ - _Size operator()(const void* __key, _Size __len); -}; - -// murmur2 -template -_Size -__murmur2_or_cityhash<_Size, 32>::operator()(const void* __key, _Size __len) _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK -{ - 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; - case 2: - __h ^= __data[1] << 8; - case 1: - __h ^= __data[0]; - __h *= __m; - } - __h ^= __h >> 13; - __h *= __m; - __h ^= __h >> 15; - return __h; -} - -template -struct __murmur2_or_cityhash<_Size, 64> -{ - _Size operator()(const void* __key, _Size __len); - - 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) { - 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) { - 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) { - 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) { - __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) { - 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) { - _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) _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK -{ - 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)); - std::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; - -template -struct __scalar_hash<_Tp, 0> - : public unary_function<_Tp, size_t> -{ - _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; - } -}; - -template -struct __scalar_hash<_Tp, 1> - : public unary_function<_Tp, size_t> -{ - _LIBCPP_INLINE_VISIBILITY - size_t operator()(_Tp __v) const _NOEXCEPT - { - union - { - _Tp __t; - size_t __a; - } __u; - __u.__t = __v; - return __u.__a; - } -}; - -template -struct __scalar_hash<_Tp, 2> - : public unary_function<_Tp, size_t> -{ - _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)); - } -}; - -template -struct __scalar_hash<_Tp, 3> - : public unary_function<_Tp, size_t> -{ - _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)); - } -}; - -template -struct __scalar_hash<_Tp, 4> - : public unary_function<_Tp, size_t> -{ - _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); -} - -template -struct _LIBCPP_TEMPLATE_VIS hash<_Tp*> - : public unary_function<_Tp*, size_t> -{ - _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)); - } -}; - template +#ifdef _LIBCPP_CXX03_LANG struct _LIBCPP_TEMPLATE_VIS hash > +#else +struct _LIBCPP_TEMPLATE_VIS hash<__enable_hash_helper< + unique_ptr<_Tp, _Dp>, typename unique_ptr<_Tp, _Dp>::pointer>> +#endif { typedef unique_ptr<_Tp, _Dp> argument_type; typedef size_t result_type; @@ -5540,6 +5193,7 @@ { typedef shared_ptr<_Tp> argument_type; typedef size_t result_type; + _LIBCPP_INLINE_VISIBILITY result_type operator()(const argument_type& __ptr) const _NOEXCEPT { Index: include/new =================================================================== --- include/new +++ include/new @@ -145,7 +145,7 @@ #endif // defined(_LIBCPP_BUILDING_NEW) || (_LIBCPP_STD_VER > 11) -#if !defined(_LIBCPP_HAS_NO_ALIGNED_ALLOCATION) || _LIBCPP_STD_VER > 14 +#ifndef _LIBCPP_HAS_NO_ALIGNED_ALLOCATION #ifndef _LIBCPP_CXX03_LANG enum class _LIBCPP_ENUM_VIS align_val_t : size_t { }; #else Index: include/optional =================================================================== --- include/optional +++ include/optional @@ -1295,7 +1295,9 @@ } template -struct _LIBCPP_TEMPLATE_VIS hash > +struct _LIBCPP_TEMPLATE_VIS hash< + __enable_hash_helper, remove_const_t<_Tp>> +> { typedef optional<_Tp> argument_type; typedef size_t result_type; @@ -1303,7 +1305,7 @@ _LIBCPP_INLINE_VISIBILITY result_type operator()(const argument_type& __opt) const _NOEXCEPT { - return static_cast(__opt) ? hash<_Tp>()(*__opt) : 0; + return static_cast(__opt) ? hash>()(*__opt) : 0; } }; Index: include/utility =================================================================== --- include/utility +++ include/utility @@ -198,6 +198,9 @@ #include <__tuple> #include #include +#include +#include +#include #include <__debug> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -930,6 +933,643 @@ #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; + std::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> +{ + _Size operator()(const void* __key, _Size __len); +}; + +// murmur2 +template +_Size +__murmur2_or_cityhash<_Size, 32>::operator()(const void* __key, _Size __len) _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK +{ + 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; + case 2: + __h ^= __data[1] << 8; + case 1: + __h ^= __data[0]; + __h *= __m; + } + __h ^= __h >> 13; + __h *= __m; + __h ^= __h >> 15; + return __h; +} + +template +struct __murmur2_or_cityhash<_Size, 64> +{ + _Size operator()(const void* __key, _Size __len); + + 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) { + 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) { + 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) { + 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) { + __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) { + 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) { + _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) _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK +{ + 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)); + std::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; + +template +struct __scalar_hash<_Tp, 0> + : public unary_function<_Tp, size_t> +{ + _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; + } +}; + +template +struct __scalar_hash<_Tp, 1> + : public unary_function<_Tp, size_t> +{ + _LIBCPP_INLINE_VISIBILITY + size_t operator()(_Tp __v) const _NOEXCEPT + { + union + { + _Tp __t; + size_t __a; + } __u; + __u.__t = __v; + return __u.__a; + } +}; + +template +struct __scalar_hash<_Tp, 2> + : public unary_function<_Tp, size_t> +{ + _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)); + } +}; + +template +struct __scalar_hash<_Tp, 3> + : public unary_function<_Tp, size_t> +{ + _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)); + } +}; + +template +struct __scalar_hash<_Tp, 4> + : public unary_function<_Tp, size_t> +{ + _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); +} + +template +struct _LIBCPP_TEMPLATE_VIS hash<_Tp*> + : public unary_function<_Tp*, size_t> +{ + _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)); + } +}; + + +template <> +struct _LIBCPP_TEMPLATE_VIS hash + : public unary_function +{ + _LIBCPP_INLINE_VISIBILITY + size_t operator()(bool __v) const _NOEXCEPT {return static_cast(__v);} +}; + +template <> +struct _LIBCPP_TEMPLATE_VIS hash + : public unary_function +{ + _LIBCPP_INLINE_VISIBILITY + size_t operator()(char __v) const _NOEXCEPT {return static_cast(__v);} +}; + +template <> +struct _LIBCPP_TEMPLATE_VIS hash + : public unary_function +{ + _LIBCPP_INLINE_VISIBILITY + size_t operator()(signed char __v) const _NOEXCEPT {return static_cast(__v);} +}; + +template <> +struct _LIBCPP_TEMPLATE_VIS hash + : public unary_function +{ + _LIBCPP_INLINE_VISIBILITY + size_t operator()(unsigned char __v) const _NOEXCEPT {return static_cast(__v);} +}; + +#ifndef _LIBCPP_HAS_NO_UNICODE_CHARS + +template <> +struct _LIBCPP_TEMPLATE_VIS hash + : public unary_function +{ + _LIBCPP_INLINE_VISIBILITY + size_t operator()(char16_t __v) const _NOEXCEPT {return static_cast(__v);} +}; + +template <> +struct _LIBCPP_TEMPLATE_VIS hash + : public unary_function +{ + _LIBCPP_INLINE_VISIBILITY + size_t operator()(char32_t __v) const _NOEXCEPT {return static_cast(__v);} +}; + +#endif // _LIBCPP_HAS_NO_UNICODE_CHARS + +template <> +struct _LIBCPP_TEMPLATE_VIS hash + : public unary_function +{ + _LIBCPP_INLINE_VISIBILITY + size_t operator()(wchar_t __v) const _NOEXCEPT {return static_cast(__v);} +}; + +template <> +struct _LIBCPP_TEMPLATE_VIS hash + : public unary_function +{ + _LIBCPP_INLINE_VISIBILITY + size_t operator()(short __v) const _NOEXCEPT {return static_cast(__v);} +}; + +template <> +struct _LIBCPP_TEMPLATE_VIS hash + : public unary_function +{ + _LIBCPP_INLINE_VISIBILITY + size_t operator()(unsigned short __v) const _NOEXCEPT {return static_cast(__v);} +}; + +template <> +struct _LIBCPP_TEMPLATE_VIS hash + : public unary_function +{ + _LIBCPP_INLINE_VISIBILITY + size_t operator()(int __v) const _NOEXCEPT {return static_cast(__v);} +}; + +template <> +struct _LIBCPP_TEMPLATE_VIS hash + : public unary_function +{ + _LIBCPP_INLINE_VISIBILITY + size_t operator()(unsigned int __v) const _NOEXCEPT {return static_cast(__v);} +}; + +template <> +struct _LIBCPP_TEMPLATE_VIS hash + : public unary_function +{ + _LIBCPP_INLINE_VISIBILITY + size_t operator()(long __v) const _NOEXCEPT {return static_cast(__v);} +}; + +template <> +struct _LIBCPP_TEMPLATE_VIS hash + : public unary_function +{ + _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) + 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) + 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) + return 0; +#if defined(__i386__) + // 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 + +template ::value> +struct _LIBCPP_TEMPLATE_VIS __enum_hash + : public unary_function<_Tp, size_t> +{ + _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 + +template <> +struct _LIBCPP_TEMPLATE_VIS hash + : public unary_function +{ + _LIBCPP_INLINE_VISIBILITY + size_t operator()(nullptr_t) const _NOEXCEPT { + return 662607004ull; + } +}; +#endif + +#ifndef _LIBCPP_CXX03_LANG +template > +using __has_enabled_hash = integral_constant::value && + is_copy_constructible<_Hash>::value && + is_move_constructible<_Hash>::value && + __invokable_r::value +>; + +#if _LIBCPP_STD_VER > 14 +template +using __enable_hash_helper_imp = _Type; + +template +using __enable_hash_helper = __enable_hash_helper_imp<_Type, + typename enable_if<__all<__has_enabled_hash<_Keys>::value...>::value>::type +>; +#else +template +using __enable_hash_helper = _Type; +#endif + +#endif // !_LIBCPP_CXX03_LANG + _LIBCPP_END_NAMESPACE_STD #endif // _LIBCPP_UTILITY Index: include/variant =================================================================== --- include/variant +++ include/variant @@ -1534,7 +1534,8 @@ } template -struct _LIBCPP_TEMPLATE_VIS hash> { +struct _LIBCPP_TEMPLATE_VIS hash< + __enable_hash_helper, remove_const_t<_Types>...>> { using argument_type = variant<_Types...>; using result_type = size_t; @@ -1547,7 +1548,8 @@ : __variant::__visit_alt( [](const auto& __alt) { using __alt_type = decay_t; - using __value_type = typename __alt_type::__value_type; + using __value_type = remove_const_t< + typename __alt_type::__value_type>; return hash<__value_type>{}(__alt.__value); }, __v); Index: test/libcxx/test/config.py =================================================================== --- test/libcxx/test/config.py +++ test/libcxx/test/config.py @@ -423,15 +423,6 @@ if not std: # Choose the newest possible language dialect if none is given. possible_stds = ['c++1z', 'c++14', 'c++11', 'c++03'] - if self.cxx.type == 'gcc': - maj_v, _, _ = self.cxx.version - maj_v = int(maj_v) - if maj_v < 7: - possible_stds.remove('c++1z') - # FIXME: How many C++14 tests actually fail under GCC 5 and 6? - # Should we XFAIL them individually instead? - if maj_v <= 6: - possible_stds.remove('c++14') for s in possible_stds: if self.cxx.hasCompileFlag('-std=%s' % s): std = s Index: test/std/containers/sequences/vector.bool/enabled_hash.pass.cpp =================================================================== --- /dev/null +++ test/std/containers/sequences/vector.bool/enabled_hash.pass.cpp @@ -0,0 +1,28 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03 + +// + +// Test that provides all of the arithmetic, enum, and pointer +// hash specializations. + +#include + +#include "poisoned_hash_helper.hpp" +#include "min_allocator.h" + +int main() { + test_library_hash_specializations_available(); + { + test_hash_enabled_for_type >(); + test_hash_enabled_for_type>>(); + } +} Index: test/std/diagnostics/syserr/syserr.hash/enabled_hash.pass.cpp =================================================================== --- /dev/null +++ test/std/diagnostics/syserr/syserr.hash/enabled_hash.pass.cpp @@ -0,0 +1,27 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03 + +// + +// Test that provides all of the arithmetic, enum, and pointer +// hash specializations. + +#include + +#include "poisoned_hash_helper.hpp" + +int main() { + test_library_hash_specializations_available(); + { + test_hash_enabled_for_type(); + test_hash_enabled_for_type(); + } +} Index: test/std/strings/basic.string.hash/enabled_hashes.pass.cpp =================================================================== --- /dev/null +++ test/std/strings/basic.string.hash/enabled_hashes.pass.cpp @@ -0,0 +1,31 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03 + +// + +// Test that provides all of the arithmetic, enum, and pointer +// hash specializations. + +#include + +#include "poisoned_hash_helper.hpp" + +int main() { + test_library_hash_specializations_available(); + { + test_hash_enabled_for_type(); + test_hash_enabled_for_type(); +#ifndef _LIBCPP_HAS_NO_UNICODE_CHARS + test_hash_enabled_for_type(); + test_hash_enabled_for_type(); +#endif + } +} Index: test/std/strings/string.view/string.view.hash/enabled_hashes.pass.cpp =================================================================== --- /dev/null +++ test/std/strings/string.view/string.view.hash/enabled_hashes.pass.cpp @@ -0,0 +1,31 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03 + +// + +// Test that provides all of the arithmetic, enum, and pointer +// hash specializations. + +#include + +#include "poisoned_hash_helper.hpp" + +int main() { + test_library_hash_specializations_available(); + { + test_hash_enabled_for_type(); + test_hash_enabled_for_type(); +#ifndef _LIBCPP_HAS_NO_UNICODE_CHARS + test_hash_enabled_for_type(); + test_hash_enabled_for_type(); +#endif + } +} Index: test/std/strings/string.view/string.view.hash/string_view.pass.cpp =================================================================== --- test/std/strings/string.view/string.view.hash/string_view.pass.cpp +++ test/std/strings/string.view/string.view.hash/string_view.pass.cpp @@ -19,29 +19,38 @@ // Not very portable #include +#include #include #include using std::string_view; -template +template void test() { - typedef std::hash H; - static_assert((std::is_same::value), "" ); + typedef std::hash H; + static_assert((std::is_same::value), "" ); static_assert((std::is_same::value), "" ); - H h; -// std::string g1 = "1234567890"; -// std::string g2 = "1234567891"; - typedef typename T::value_type char_type; + + typedef typename SV::value_type char_type; + typedef std::basic_string String; + typedef std::hash SH; + char_type g1 [ 10 ]; char_type g2 [ 10 ]; for ( int i = 0; i < 10; ++i ) g1[i] = g2[9-i] = static_cast('0' + i); - T s1(g1, 10); - T s2(g2, 10); + H h; + SH sh; + SV s1(g1, 10); + String ss1(s1); + SV s2(g2, 10); + String ss2(s2); + assert(h(s1) == h(s1)); assert(h(s1) != h(s2)); + assert(sh(ss1) == h(s1)); + assert(sh(ss2) == h(s2)); } int main() Index: test/std/thread/thread.threads/thread.thread.class/thread.thread.id/enabled_hashes.pass.cpp =================================================================== --- /dev/null +++ test/std/thread/thread.threads/thread.thread.class/thread.thread.id/enabled_hashes.pass.cpp @@ -0,0 +1,27 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: libcpp-has-no-threads +// UNSUPPORTED: c++98, c++03 + +// + +// Test that provides all of the arithmetic, enum, and pointer +// hash specializations. + +#include + +#include "poisoned_hash_helper.hpp" + +int main() { + test_library_hash_specializations_available(); + { + test_hash_enabled_for_type(); + } +} Index: test/std/thread/thread.threads/thread.thread.class/thread.thread.id/thread_id.pass.cpp =================================================================== --- test/std/thread/thread.threads/thread.thread.class/thread.thread.id/thread_id.pass.cpp +++ test/std/thread/thread.threads/thread.thread.class/thread.thread.id/thread_id.pass.cpp @@ -9,7 +9,7 @@ // // UNSUPPORTED: libcpp-has-no-threads -// +// // template // struct hash Index: test/std/utilities/function.objects/unord.hash/enabled_hashes.pass.cpp =================================================================== --- /dev/null +++ test/std/utilities/function.objects/unord.hash/enabled_hashes.pass.cpp @@ -0,0 +1,23 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03 + +// + +// Test that provides all of the arithmetic, enum, and pointer +// hash specializations. + +#include + +#include "poisoned_hash_helper.hpp" + +int main() { + test_library_hash_specializations_available(); +} Index: test/std/utilities/memory/util.smartptr/util.smartptr.hash/enabled_hash.pass.cpp =================================================================== --- /dev/null +++ test/std/utilities/memory/util.smartptr/util.smartptr.hash/enabled_hash.pass.cpp @@ -0,0 +1,23 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03 + +// + +// Test that provides all of the arithmetic, enum, and pointer +// hash specializations. + +#include + +#include "poisoned_hash_helper.hpp" + +int main() { + test_library_hash_specializations_available(); +} Index: test/std/utilities/memory/util.smartptr/util.smartptr.hash/hash_shared_ptr.pass.cpp =================================================================== --- test/std/utilities/memory/util.smartptr/util.smartptr.hash/hash_shared_ptr.pass.cpp +++ test/std/utilities/memory/util.smartptr/util.smartptr.hash/hash_shared_ptr.pass.cpp @@ -20,11 +20,25 @@ #include #include +#if TEST_STD_VER >= 11 +#include "poisoned_hash_helper.hpp" + +struct A {}; +#endif + int main() { + { int* ptr = new int; std::shared_ptr p(ptr); std::hash > f; std::size_t h = f(p); assert(h == std::hash()(ptr)); + } +#if TEST_STD_VER >= 11 + { + test_hash_enabled_for_type>(); + test_hash_enabled_for_type>(); + } +#endif } Index: test/std/utilities/memory/util.smartptr/util.smartptr.hash/hash_unique_ptr.pass.cpp =================================================================== --- test/std/utilities/memory/util.smartptr/util.smartptr.hash/hash_unique_ptr.pass.cpp +++ test/std/utilities/memory/util.smartptr/util.smartptr.hash/hash_unique_ptr.pass.cpp @@ -20,11 +20,76 @@ #include #include +#include "test_macros.h" + +#if TEST_STD_VER >= 11 +#include "poisoned_hash_helper.hpp" +#include "deleter_types.h" +#include "min_allocator.h" + +template +void test_enabled_with_deleter() { + using UPtr = std::unique_ptr; + using pointer = typename UPtr::pointer; + using RawDel = typename std::decay::type; + RawDel d(1); + UPtr p(nullptr, std::forward(d)); + test_hash_enabled_for_type(p); + test_hash_enabled_for_type(); +} + +template +void test_disabled_with_deleter() { + using UPtr = std::unique_ptr; + using pointer = typename UPtr::pointer; + test_hash_disabled_for_type(); + test_hash_disabled_for_type(); +} + +template +struct std::hash>> { + size_t operator()(min_pointer> p) const { + if (!p) return 0; + return std::hash{}(std::addressof(*p)); + } +}; + +struct A {}; + +#endif // TEST_STD_VER >= 11 + int main() { + { int* ptr = new int; std::unique_ptr p(ptr); std::hash > f; std::size_t h = f(p); assert(h == std::hash()(ptr)); + } +#if TEST_STD_VER >= 11 + { + test_enabled_with_deleter>(); + test_enabled_with_deleter>(); + test_enabled_with_deleter>(); + test_enabled_with_deleter>(); + test_enabled_with_deleter&>(); + test_enabled_with_deleter&>(); + test_enabled_with_deleter const&>(); + test_enabled_with_deleter const&>(); + } + { + test_enabled_with_deleter>(); + test_enabled_with_deleter>(); + test_enabled_with_deleter>(); + test_enabled_with_deleter>(); + +#if TEST_STD_VER > 14 + test_disabled_with_deleter>(); + test_disabled_with_deleter>(); + test_disabled_with_deleter>(); + test_disabled_with_deleter>(); +#endif + } +#endif } Index: test/std/utilities/optional/optional.hash/enabled_hash.pass.cpp =================================================================== --- /dev/null +++ test/std/utilities/optional/optional.hash/enabled_hash.pass.cpp @@ -0,0 +1,26 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03, c++11, c++14 + +// + +// Test that provides all of the arithmetic, enum, and pointer +// hash specializations. + +#include + +#include "poisoned_hash_helper.hpp" + +int main() { + test_library_hash_specializations_available(); + { + + } +} Index: test/std/utilities/optional/optional.hash/hash.pass.cpp =================================================================== --- test/std/utilities/optional/optional.hash/hash.pass.cpp +++ test/std/utilities/optional/optional.hash/hash.pass.cpp @@ -17,6 +17,15 @@ #include #include +#include "poisoned_hash_helper.hpp" + +struct A {}; +struct B {}; + +template <> +struct std::hash { + size_t operator()(B const&) { return 0; } +}; int main() { @@ -45,4 +54,16 @@ opt = std::unique_ptr(new int(3)); assert(std::hash>{}(opt) == std::hash{}(*opt)); } + { + test_hash_enabled_for_type >(); + test_hash_enabled_for_type >(); + test_hash_enabled_for_type >(); + test_hash_enabled_for_type >(); + + test_hash_disabled_for_type>(); + test_hash_disabled_for_type>(); + + test_hash_enabled_for_type>(); + test_hash_enabled_for_type>(); + } } Index: test/std/utilities/template.bitset/bitset.hash/enabled_hash.pass.cpp =================================================================== --- /dev/null +++ test/std/utilities/template.bitset/bitset.hash/enabled_hash.pass.cpp @@ -0,0 +1,29 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03 + +// + +// Test that provides all of the arithmetic, enum, and pointer +// hash specializations. + +#include + +#include "poisoned_hash_helper.hpp" + +int main() { + test_library_hash_specializations_available(); + { + test_hash_enabled_for_type >(); + test_hash_enabled_for_type >(); + test_hash_enabled_for_type >(); + test_hash_enabled_for_type >(); + } +} Index: test/std/utilities/type.index/type.index.hash/enabled_hash.pass.cpp =================================================================== --- /dev/null +++ test/std/utilities/type.index/type.index.hash/enabled_hash.pass.cpp @@ -0,0 +1,23 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03 + +// + +// Test that provides all of the arithmetic, enum, and pointer +// hash specializations. + +#include + +#include "poisoned_hash_helper.hpp" + +int main() { + test_library_hash_specializations_available(); +} Index: test/std/utilities/type.index/type.index.synopsis/hash_type_index.pass.cpp =================================================================== --- test/std/utilities/type.index/type.index.synopsis/hash_type_index.pass.cpp +++ test/std/utilities/type.index/type.index.synopsis/hash_type_index.pass.cpp @@ -18,9 +18,19 @@ #include #include +#include "test_macros.h" +#if TEST_STD_VER >= 11 +#include "poisoned_hash_helper.hpp" +#endif + int main() { + { typedef std::hash H; static_assert((std::is_same::value), "" ); static_assert((std::is_same::value), "" ); + } + { + test_hash_enabled_for_type(std::type_index(typeid(int))); + } } Index: test/std/utilities/variant/variant.hash/enabled_hash.pass.cpp =================================================================== --- /dev/null +++ test/std/utilities/variant/variant.hash/enabled_hash.pass.cpp @@ -0,0 +1,23 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03, c++11, c++14 + +// + +// Test that provides all of the arithmetic, enum, and pointer +// hash specializations. + +#include + +#include "poisoned_hash_helper.hpp" + +int main() { + test_library_hash_specializations_available(); +} Index: test/std/utilities/variant/variant.hash/hash.pass.cpp =================================================================== --- test/std/utilities/variant/variant.hash/hash.pass.cpp +++ test/std/utilities/variant/variant.hash/hash.pass.cpp @@ -21,6 +21,7 @@ #include "test_macros.h" #include "variant_test_helpers.hpp" +#include "poisoned_hash_helper.hpp" #ifndef TEST_HAS_NO_EXCEPTIONS namespace std { @@ -103,6 +104,9 @@ ASSERT_SAME_TYPE(decltype(h(m1)), std::size_t); static_assert(std::is_copy_constructible::value, ""); } + { + test_hash_enabled_for_type(); + } } void test_hash_variant_duplicate_elements() { @@ -117,8 +121,34 @@ LIBCPP_ASSERT(h(v1) != h(v2)); } +struct A {}; +struct B {}; + +template <> +struct std::hash { + size_t operator()(B const&) const { + return 0; + } +}; + +void test_hash_variant_enabled() { + { + test_hash_enabled_for_type >(); + test_hash_enabled_for_type >(); + } + { + test_hash_disabled_for_type>(); + test_hash_disabled_for_type>(); + } + { + test_hash_enabled_for_type>(); + test_hash_enabled_for_type>(); + } +} + int main() { test_hash_variant(); test_hash_variant_duplicate_elements(); test_hash_monostate(); + test_hash_variant_enabled(); } Index: test/support/deleter_types.h =================================================================== --- test/support/deleter_types.h +++ test/support/deleter_types.h @@ -21,6 +21,7 @@ #include #include "test_macros.h" +#include "min_allocator.h" #if TEST_STD_VER >= 11 @@ -379,4 +380,63 @@ y = std::move(t); } +#if TEST_STD_VER >= 11 + +template +class PointerDeleter +{ + PointerDeleter(const PointerDeleter&); + PointerDeleter& operator=(const PointerDeleter&); + +public: + typedef min_pointer> pointer; + + PointerDeleter() = default; + PointerDeleter(PointerDeleter&&) = default; + PointerDeleter& operator=(PointerDeleter&&) = default; + explicit PointerDeleter(int) {} + + template + PointerDeleter(PointerDeleter&&, + typename std::enable_if::value>::type* = 0) + {} + + void operator()(pointer p) { if (p) { delete std::addressof(*p); }} + +private: + template + PointerDeleter(const PointerDeleter&, + typename std::enable_if::value>::type* = 0); +}; + + +template +class PointerDeleter +{ + PointerDeleter(const PointerDeleter&); + PointerDeleter& operator=(const PointerDeleter&); + +public: + typedef min_pointer > pointer; + + PointerDeleter() = default; + PointerDeleter(PointerDeleter&&) = default; + PointerDeleter& operator=(PointerDeleter&&) = default; + explicit PointerDeleter(int) {} + + template + PointerDeleter(PointerDeleter&&, + typename std::enable_if::value>::type* = 0) + {} + + void operator()(pointer p) { if (p) { delete [] std::addressof(*p); }} + +private: + template + PointerDeleter(const PointerDeleter&, + typename std::enable_if::value>::type* = 0); +}; + +#endif // TEST_STD_VER >= 11 + #endif // SUPPORT_DELETER_TYPES_H Index: test/support/min_allocator.h =================================================================== --- test/support/min_allocator.h +++ test/support/min_allocator.h @@ -136,31 +136,31 @@ #include -template class min_pointer; -template class min_pointer; -template <> class min_pointer; -template <> class min_pointer; +template > class min_pointer; +template class min_pointer; +template class min_pointer; +template class min_pointer; template class min_allocator; -template <> -class min_pointer +template +class min_pointer { const void* ptr_; public: min_pointer() TEST_NOEXCEPT = default; min_pointer(std::nullptr_t) TEST_NOEXCEPT : ptr_(nullptr) {} template - min_pointer(min_pointer p) TEST_NOEXCEPT : ptr_(p.ptr_) {} + min_pointer(min_pointer p) TEST_NOEXCEPT : ptr_(p.ptr_) {} explicit operator bool() const {return ptr_ != nullptr;} friend bool operator==(min_pointer x, min_pointer y) {return x.ptr_ == y.ptr_;} friend bool operator!=(min_pointer x, min_pointer y) {return !(x == y);} - template friend class min_pointer; + template friend class min_pointer; }; -template <> -class min_pointer +template +class min_pointer { void* ptr_; public: @@ -172,16 +172,16 @@ !std::is_const::value >::type > - min_pointer(min_pointer p) TEST_NOEXCEPT : ptr_(p.ptr_) {} + min_pointer(min_pointer p) TEST_NOEXCEPT : ptr_(p.ptr_) {} explicit operator bool() const {return ptr_ != nullptr;} friend bool operator==(min_pointer x, min_pointer y) {return x.ptr_ == y.ptr_;} friend bool operator!=(min_pointer x, min_pointer y) {return !(x == y);} - template friend class min_pointer; + template friend class min_pointer; }; -template +template class min_pointer { T* ptr_; @@ -190,7 +190,7 @@ public: min_pointer() TEST_NOEXCEPT = default; min_pointer(std::nullptr_t) TEST_NOEXCEPT : ptr_(nullptr) {} - explicit min_pointer(min_pointer p) TEST_NOEXCEPT : ptr_(static_cast(p.ptr_)) {} + explicit min_pointer(min_pointer p) TEST_NOEXCEPT : ptr_(static_cast(p.ptr_)) {} explicit operator bool() const {return ptr_ != nullptr;} @@ -247,12 +247,12 @@ friend bool operator==(min_pointer x, min_pointer y) {return x.ptr_ == y.ptr_;} friend bool operator!=(min_pointer x, min_pointer y) {return !(x == y);} - template friend class min_pointer; + template friend class min_pointer; template friend class min_allocator; }; -template -class min_pointer +template +class min_pointer { const T* ptr_; @@ -260,8 +260,8 @@ public: min_pointer() TEST_NOEXCEPT = default; min_pointer(std::nullptr_t) : ptr_(nullptr) {} - min_pointer(min_pointer p) : ptr_(p.ptr_) {} - explicit min_pointer(min_pointer p) : ptr_(static_cast(p.ptr_)) {} + min_pointer(min_pointer p) : ptr_(p.ptr_) {} + explicit min_pointer(min_pointer p) : ptr_(static_cast(p.ptr_)) {} explicit operator bool() const {return ptr_ != nullptr;} @@ -318,37 +318,37 @@ friend bool operator==(min_pointer x, min_pointer y) {return x.ptr_ == y.ptr_;} friend bool operator!=(min_pointer x, min_pointer y) {return !(x == y);} - template friend class min_pointer; + template friend class min_pointer; }; -template +template inline bool -operator==(min_pointer x, std::nullptr_t) +operator==(min_pointer x, std::nullptr_t) { return !static_cast(x); } -template +template inline bool -operator==(std::nullptr_t, min_pointer x) +operator==(std::nullptr_t, min_pointer x) { return !static_cast(x); } -template +template inline bool -operator!=(min_pointer x, std::nullptr_t) +operator!=(min_pointer x, std::nullptr_t) { return static_cast(x); } -template +template inline bool -operator!=(std::nullptr_t, min_pointer x) +operator!=(std::nullptr_t, min_pointer x) { return static_cast(x); } Index: test/support/poisoned_hash_helper.hpp =================================================================== --- /dev/null +++ test/support/poisoned_hash_helper.hpp @@ -0,0 +1,244 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +#ifndef SUPPORT_POISONED_HASH_HELPER_HPP +#define SUPPORT_POISONED_HASH_HELPER_HPP + +#include +#include + +#include "test_macros.h" + +#if TEST_STD_VER < 11 +#error this header may only be used in C++11 or newer +#endif + +template struct TypeList; + +// Test that the specified Hash meets the requirements of an enabled hash +template +void test_hash_enabled(InputKey const& key = InputKey{}); + +template +void test_hash_enabled_for_type(InputKey const& key = InputKey{}) { + return test_hash_enabled, T, InputKey>(key); +} + +// Test that the specified Hash meets the requirements of a disabled hash. +template +void test_hash_disabled(); + +template +void test_hash_disabled_for_type() { + return test_hash_disabled, T>(); +} + +namespace PoisonedHashDetail { + enum Enum {}; + enum EnumClass : bool {}; + struct Class {}; +} + +// Each header that declares the template hash provides enabled +// specializations of hash for nullptr t and all cv-unqualified +// arithmetic, enumeration, and pointer types. +using LibraryHashTypes = TypeList< +#if TEST_STD_VER > 14 + decltype(nullptr), +#endif + bool, + char, + signed char, + unsigned char, + wchar_t, +#ifndef _LIBCPP_HAS_NO_UNICODE_CHARS + char16_t, + char32_t, +#endif + short, + unsigned short, + int, + unsigned int, + long, + unsigned long, + long long, + unsigned long long, +#ifndef _LIBCPP_HAS_NO_INT128 + __int128_t, + __uint128_t, +#endif + float, + double, + long double, +#if TEST_STD_VER >= 14 + // Enum types + PoisonedHashDetail::Enum, + PoisonedHashDetail::EnumClass, +#endif + // pointer types + void*, + void const*, + PoisonedHashDetail::Class* + >; + + +// Test that each of the library hash specializations for arithmetic types, +// enum types, and pointer types are available and enabled. +template +void test_library_hash_specializations_available(Types = Types{}); + + +namespace PoisonedHashDetail { + +template +constexpr bool instantiate(int) { return true; } +template constexpr bool instantiate(long) { return true; } +template constexpr bool instantiate() { return instantiate(0); } + +template +struct ConvertibleToSimple { + operator To() const { + return To{}; + } +}; + +template +struct ConvertibleTo { + To to{}; + operator To&() & { return to; } + operator To const&() const & { return to; } + operator To&&() && { return std::move(to); } + operator To const&&() const && { return std::move(to); } +}; + +template ::type> +constexpr bool can_hash(int) { + return std::is_same::value; +} +template constexpr bool can_hash(long) { return false; } +template constexpr bool can_hash() { return can_hash(0); } + +} // namespace PoisonedHashDetail + +template +void test_hash_enabled(InputKey const& key) { + using namespace PoisonedHashDetail; + + static_assert(std::is_destructible::value, ""); + // Enabled hash requirements + static_assert(std::is_default_constructible::value, ""); + static_assert(std::is_copy_constructible::value, ""); + static_assert(std::is_move_constructible::value, ""); + static_assert(std::is_copy_assignable::value, ""); + static_assert(std::is_move_assignable::value, ""); + +#if TEST_STD_VER > 14 + static_assert(std::is_swappable::value, ""); +#elif defined(_LIBCPP_VERSION) + static_assert(std::__is_swappable::value, ""); +#endif + + // Hashable requirements + using CKey = ConvertibleTo; + static_assert(can_hash(), ""); + static_assert(can_hash(), ""); + static_assert(can_hash(), ""); + static_assert(can_hash(), ""); + static_assert(can_hash(), ""); + static_assert(can_hash(), ""); + + static_assert(can_hash&)>(), ""); + static_assert(can_hash const&)>(), ""); + static_assert(can_hash&&)>(), ""); + + static_assert(can_hash&)>(), ""); + static_assert(can_hash const&)>(), ""); + static_assert(can_hash &&)>(), ""); + static_assert(can_hash const&&)>(), ""); + + const Hash h; + assert(h(key) == h(key)); + +} + +template +void test_hash_disabled() { + using namespace PoisonedHashDetail; + + // Disabled hash requirements + static_assert(!std::is_default_constructible::value, ""); + static_assert(!std::is_copy_constructible::value, ""); + static_assert(!std::is_move_constructible::value, ""); + static_assert(!std::is_copy_assignable::value, ""); + static_assert(!std::is_move_assignable::value, ""); + + static_assert(!std::is_function< + typename std::remove_pointer< + typename std::remove_reference::type + >::type + >::value, ""); + + // Hashable requirements + using CKey = ConvertibleTo; + static_assert(!can_hash(), ""); + static_assert(!can_hash(), ""); + static_assert(!can_hash(), ""); + static_assert(!can_hash(), ""); + static_assert(!can_hash(), ""); + static_assert(!can_hash(), ""); + + static_assert(!can_hash&)>(), ""); + static_assert(!can_hash const&)>(), ""); + static_assert(!can_hash&&)>(), ""); + + static_assert(!can_hash&)>(), ""); + static_assert(!can_hash const&)>(), ""); + static_assert(!can_hash &&)>(), ""); + static_assert(!can_hash const&&)>(), ""); +} + + +template +struct TypeList { + template