diff --git a/libcxx/include/__functional/hash.h b/libcxx/include/__functional/hash.h --- a/libcxx/include/__functional/hash.h +++ b/libcxx/include/__functional/hash.h @@ -35,7 +35,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD template -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_HIDE_FROM_ABI _Size __loadword(const void* __p) { @@ -53,50 +53,88 @@ template struct __murmur2_or_cityhash<_Size, 32> { - inline _Size operator()(const void* __key, _Size __len) - _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK; + _LIBCPP_HIDE_FROM_ABI _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK + _Size operator()(const void* __key, _Size __len) const { + // murmur2 + 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 = std::__loadword<_Size>(__data); + __k *= __m; + __k ^= __k >> __r; + __k *= __m; + __h *= __m; + __h ^= __k; + } + switch (__len) + { + case 3: + __h ^= static_cast<_Size>(__data[2] << 16); + _LIBCPP_FALLTHROUGH(); + case 2: + __h ^= static_cast<_Size>(__data[1] << 8); + _LIBCPP_FALLTHROUGH(); + case 1: + __h ^= __data[0]; + __h *= __m; + } + __h ^= __h >> 13; + __h *= __m; + __h ^= __h >> 15; + return __h; + } }; -// murmur2 template -_Size -__murmur2_or_cityhash<_Size, 32>::operator()(const void* __key, _Size __len) +struct __murmur2_or_cityhash<_Size, 64> { - 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 = std::__loadword<_Size>(__data); - __k *= __m; - __k ^= __k >> __r; - __k *= __m; - __h *= __m; - __h ^= __k; - } - switch (__len) - { - case 3: - __h ^= static_cast<_Size>(__data[2] << 16); - _LIBCPP_FALLTHROUGH(); - case 2: - __h ^= static_cast<_Size>(__data[1] << 8); - _LIBCPP_FALLTHROUGH(); - case 1: - __h ^= __data[0]; - __h *= __m; + // cityhash64 + _LIBCPP_HIDE_FROM_ABI _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK + _Size operator()(const void* __key, _Size __len) const { + 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); } - __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; + // 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 = std::__loadword<_Size>(__s + __len - 40); + _Size __y = std::__loadword<_Size>(__s + __len - 16) + + std::__loadword<_Size>(__s + __len - 56); + _Size __z = __hash_len_16(std::__loadword<_Size>(__s + __len - 48) + __len, + std::__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 + std::__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 + std::__loadword<_Size>(__s + 8), 37) * __k1; + __y = __rotate(__y + __v.second + std::__loadword<_Size>(__s + 48), 42) * __k1; + __x ^= __w.second; + __y += __v.first + std::__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 + std::__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); + } private: // Some primes between 2^63 and 2^64. @@ -105,21 +143,23 @@ static const _Size __k2 = 0x9ae16a3b2f90404fULL; static const _Size __k3 = 0xc949d7c7509e6557ULL; + _LIBCPP_HIDE_FROM_ABI static _Size __rotate(_Size __val, int __shift) { return __shift == 0 ? __val : ((__val >> __shift) | (__val << (64 - __shift))); } + _LIBCPP_HIDE_FROM_ABI static _Size __rotate_by_at_least_1(_Size __val, int __shift) { return (__val >> __shift) | (__val << (64 - __shift)); } + _LIBCPP_HIDE_FROM_ABI 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 - { + _LIBCPP_HIDE_FROM_ABI _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK + static _Size __hash_len_16(_Size __u, _Size __v) { const _Size __mul = 0x9ddfea08eb382d69ULL; _Size __a = (__u ^ __v) * __mul; __a ^= (__a >> 47); @@ -129,9 +169,8 @@ return __b; } - static _Size __hash_len_0_to_16(const char* __s, _Size __len) - _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK - { + _LIBCPP_HIDE_FROM_ABI _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK + static _Size __hash_len_0_to_16(const char* __s, _Size __len) { if (__len > 8) { const _Size __a = std::__loadword<_Size>(__s); const _Size __b = std::__loadword<_Size>(__s + __len - 8); @@ -154,9 +193,8 @@ return __k2; } - static _Size __hash_len_17_to_32(const char *__s, _Size __len) - _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK - { + _LIBCPP_HIDE_FROM_ABI _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK + static _Size __hash_len_17_to_32(const char *__s, _Size __len) { const _Size __a = std::__loadword<_Size>(__s) * __k1; const _Size __b = std::__loadword<_Size>(__s + 8); const _Size __c = std::__loadword<_Size>(__s + __len - 8) * __k2; @@ -167,9 +205,9 @@ // Return a 16-byte hash for 48 bytes. Quick and dirty. // Callers do best to use "random-looking" values for a and b. + _LIBCPP_HIDE_FROM_ABI _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK 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); @@ -181,9 +219,9 @@ } // Return a 16-byte hash for s[0] ... s[31], a, and b. Quick and dirty. + _LIBCPP_HIDE_FROM_ABI _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK 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(std::__loadword<_Size>(__s), std::__loadword<_Size>(__s + 8), @@ -194,9 +232,8 @@ } // 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 - { + _LIBCPP_HIDE_FROM_ABI _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK + static _Size __hash_len_33_to_64(const char *__s, size_t __len) { _Size __z = std::__loadword<_Size>(__s + 24); _Size __a = std::__loadword<_Size>(__s) + (__len + std::__loadword<_Size>(__s + __len - 16)) * __k0; @@ -221,53 +258,6 @@ } }; -// 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 = std::__loadword<_Size>(__s + __len - 40); - _Size __y = std::__loadword<_Size>(__s + __len - 16) + - std::__loadword<_Size>(__s + __len - 56); - _Size __z = __hash_len_16(std::__loadword<_Size>(__s + __len - 48) + __len, - std::__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 + std::__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 + std::__loadword<_Size>(__s + 8), 37) * __k1; - __y = __rotate(__y + __v.second + std::__loadword<_Size>(__s + 48), 42) * __k1; - __x ^= __w.second; - __y += __v.first + std::__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 + std::__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; @@ -275,7 +265,7 @@ struct __scalar_hash<_Tp, 0> : public __unary_function<_Tp, size_t> { - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_t operator()(_Tp __v) const _NOEXCEPT { union @@ -293,7 +283,7 @@ struct __scalar_hash<_Tp, 1> : public __unary_function<_Tp, size_t> { - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_t operator()(_Tp __v) const _NOEXCEPT { union @@ -310,7 +300,7 @@ struct __scalar_hash<_Tp, 2> : public __unary_function<_Tp, size_t> { - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_t operator()(_Tp __v) const _NOEXCEPT { union @@ -331,7 +321,7 @@ struct __scalar_hash<_Tp, 3> : public __unary_function<_Tp, size_t> { - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_t operator()(_Tp __v) const _NOEXCEPT { union @@ -353,7 +343,7 @@ struct __scalar_hash<_Tp, 4> : public __unary_function<_Tp, size_t> { - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_t operator()(_Tp __v) const _NOEXCEPT { union @@ -377,7 +367,7 @@ size_t second; }; -_LIBCPP_INLINE_VISIBILITY +_LIBCPP_HIDE_FROM_ABI inline size_t __hash_combine(size_t __lhs, size_t __rhs) _NOEXCEPT { typedef __scalar_hash<_PairT> _HashT; const _PairT __p = {__lhs, __rhs}; @@ -388,7 +378,7 @@ struct _LIBCPP_TEMPLATE_VIS hash<_Tp*> : public __unary_function<_Tp*, size_t> { - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_t operator()(_Tp* __v) const _NOEXCEPT { union @@ -405,7 +395,7 @@ struct _LIBCPP_TEMPLATE_VIS hash : public __unary_function { - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_t operator()(bool __v) const _NOEXCEPT {return static_cast(__v);} }; @@ -413,7 +403,7 @@ struct _LIBCPP_TEMPLATE_VIS hash : public __unary_function { - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_t operator()(char __v) const _NOEXCEPT {return static_cast(__v);} }; @@ -421,7 +411,7 @@ struct _LIBCPP_TEMPLATE_VIS hash : public __unary_function { - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_t operator()(signed char __v) const _NOEXCEPT {return static_cast(__v);} }; @@ -429,7 +419,7 @@ struct _LIBCPP_TEMPLATE_VIS hash : public __unary_function { - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_t operator()(unsigned char __v) const _NOEXCEPT {return static_cast(__v);} }; @@ -438,7 +428,7 @@ struct _LIBCPP_TEMPLATE_VIS hash : public __unary_function { - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_t operator()(char8_t __v) const _NOEXCEPT {return static_cast(__v);} }; #endif // !_LIBCPP_HAS_NO_CHAR8_T @@ -447,7 +437,7 @@ struct _LIBCPP_TEMPLATE_VIS hash : public __unary_function { - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_t operator()(char16_t __v) const _NOEXCEPT {return static_cast(__v);} }; @@ -455,7 +445,7 @@ struct _LIBCPP_TEMPLATE_VIS hash : public __unary_function { - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_t operator()(char32_t __v) const _NOEXCEPT {return static_cast(__v);} }; @@ -464,7 +454,7 @@ struct _LIBCPP_TEMPLATE_VIS hash : public __unary_function { - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_t operator()(wchar_t __v) const _NOEXCEPT {return static_cast(__v);} }; #endif // _LIBCPP_HAS_NO_WIDE_CHARACTERS @@ -473,7 +463,7 @@ struct _LIBCPP_TEMPLATE_VIS hash : public __unary_function { - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_t operator()(short __v) const _NOEXCEPT {return static_cast(__v);} }; @@ -481,7 +471,7 @@ struct _LIBCPP_TEMPLATE_VIS hash : public __unary_function { - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_t operator()(unsigned short __v) const _NOEXCEPT {return static_cast(__v);} }; @@ -489,7 +479,7 @@ struct _LIBCPP_TEMPLATE_VIS hash : public __unary_function { - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_t operator()(int __v) const _NOEXCEPT {return static_cast(__v);} }; @@ -497,7 +487,7 @@ struct _LIBCPP_TEMPLATE_VIS hash : public __unary_function { - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_t operator()(unsigned int __v) const _NOEXCEPT {return static_cast(__v);} }; @@ -505,7 +495,7 @@ struct _LIBCPP_TEMPLATE_VIS hash : public __unary_function { - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_t operator()(long __v) const _NOEXCEPT {return static_cast(__v);} }; @@ -513,7 +503,7 @@ struct _LIBCPP_TEMPLATE_VIS hash : public __unary_function { - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_t operator()(unsigned long __v) const _NOEXCEPT {return static_cast(__v);} }; @@ -549,7 +539,7 @@ struct _LIBCPP_TEMPLATE_VIS hash : public __scalar_hash { - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_t operator()(float __v) const _NOEXCEPT { // -0.0 and 0.0 should return same hash @@ -563,7 +553,7 @@ struct _LIBCPP_TEMPLATE_VIS hash : public __scalar_hash { - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_t operator()(double __v) const _NOEXCEPT { // -0.0 and 0.0 should return same hash @@ -577,7 +567,7 @@ struct _LIBCPP_TEMPLATE_VIS hash : public __scalar_hash { - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_t operator()(long double __v) const _NOEXCEPT { // -0.0 and 0.0 should return same hash @@ -627,7 +617,7 @@ struct _LIBCPP_TEMPLATE_VIS __enum_hash : public __unary_function<_Tp, size_t> { - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_t operator()(_Tp __v) const _NOEXCEPT { typedef typename underlying_type<_Tp>::type type; @@ -652,7 +642,7 @@ struct _LIBCPP_TEMPLATE_VIS hash : public __unary_function { - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_t operator()(nullptr_t) const _NOEXCEPT { return 662607004ull; }