463 lines · c
1//===----------------------------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef _LIBCPP___FUNCTIONAL_HASH_H10#define _LIBCPP___FUNCTIONAL_HASH_H11 12#include <__config>13#include <__cstddef/nullptr_t.h>14#include <__functional/unary_function.h>15#include <__fwd/functional.h>16#include <__memory/addressof.h>17#include <__type_traits/conjunction.h>18#include <__type_traits/enable_if.h>19#include <__type_traits/invoke.h>20#include <__type_traits/is_constructible.h>21#include <__type_traits/is_enum.h>22#include <__type_traits/is_floating_point.h>23#include <__type_traits/is_integral.h>24#include <__type_traits/is_unqualified.h>25#include <__type_traits/underlying_type.h>26#include <__utility/pair.h>27#include <__utility/swap.h>28#include <cstdint>29#include <cstring>30 31#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)32# pragma GCC system_header33#endif34 35_LIBCPP_BEGIN_NAMESPACE_STD36 37template <class _Size>38inline _LIBCPP_HIDE_FROM_ABI _Size __loadword(const void* __p) {39 _Size __r;40 std::memcpy(std::addressof(__r), __p, sizeof(__r));41 return __r;42}43 44// We use murmur2 when size_t is 32 bits, and cityhash64 when size_t45// is 64 bits. This is because cityhash64 uses 64bit x 64bit46// multiplication, which can be very slow on 32-bit systems.47template <class _Size, size_t = sizeof(_Size) * __CHAR_BIT__>48struct __murmur2_or_cityhash;49 50template <class _Size>51struct __murmur2_or_cityhash<_Size, 32> {52 _LIBCPP_HIDE_FROM_ABI _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK _Size53 operator()(const void* __key, _Size __len) const {54 // murmur255 const _Size __m = 0x5bd1e995;56 const _Size __r = 24;57 _Size __h = __len;58 const unsigned char* __data = static_cast<const unsigned char*>(__key);59 for (; __len >= 4; __data += 4, __len -= 4) {60 _Size __k = std::__loadword<_Size>(__data);61 __k *= __m;62 __k ^= __k >> __r;63 __k *= __m;64 __h *= __m;65 __h ^= __k;66 }67 switch (__len) {68 case 3:69 __h ^= static_cast<_Size>(__data[2] << 16);70 [[__fallthrough__]];71 case 2:72 __h ^= static_cast<_Size>(__data[1] << 8);73 [[__fallthrough__]];74 case 1:75 __h ^= __data[0];76 __h *= __m;77 }78 __h ^= __h >> 13;79 __h *= __m;80 __h ^= __h >> 15;81 return __h;82 }83};84 85template <class _Size>86struct __murmur2_or_cityhash<_Size, 64> {87 // cityhash6488 _LIBCPP_HIDE_FROM_ABI _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK _Size89 operator()(const void* __key, _Size __len) const {90 const char* __s = static_cast<const char*>(__key);91 if (__len <= 32) {92 if (__len <= 16) {93 return __hash_len_0_to_16(__s, __len);94 } else {95 return __hash_len_17_to_32(__s, __len);96 }97 } else if (__len <= 64) {98 return __hash_len_33_to_64(__s, __len);99 }100 101 // For strings over 64 bytes we hash the end first, and then as we102 // loop we keep 56 bytes of state: v, w, x, y, and z.103 _Size __x = std::__loadword<_Size>(__s + __len - 40);104 _Size __y = std::__loadword<_Size>(__s + __len - 16) + std::__loadword<_Size>(__s + __len - 56);105 _Size __z =106 __hash_len_16(std::__loadword<_Size>(__s + __len - 48) + __len, std::__loadword<_Size>(__s + __len - 24));107 pair<_Size, _Size> __v = __weak_hash_len_32_with_seeds(__s + __len - 64, __len, __z);108 pair<_Size, _Size> __w = __weak_hash_len_32_with_seeds(__s + __len - 32, __y + __k1, __x);109 __x = __x * __k1 + std::__loadword<_Size>(__s);110 111 // Decrease len to the nearest multiple of 64, and operate on 64-byte chunks.112 __len = (__len - 1) & ~static_cast<_Size>(63);113 do {114 __x = __rotate(__x + __y + __v.first + std::__loadword<_Size>(__s + 8), 37) * __k1;115 __y = __rotate(__y + __v.second + std::__loadword<_Size>(__s + 48), 42) * __k1;116 __x ^= __w.second;117 __y += __v.first + std::__loadword<_Size>(__s + 40);118 __z = __rotate(__z + __w.first, 33) * __k1;119 __v = __weak_hash_len_32_with_seeds(__s, __v.second * __k1, __x + __w.first);120 __w = __weak_hash_len_32_with_seeds(__s + 32, __z + __w.second, __y + std::__loadword<_Size>(__s + 16));121 std::swap(__z, __x);122 __s += 64;123 __len -= 64;124 } while (__len != 0);125 return __hash_len_16(__hash_len_16(__v.first, __w.first) + __shift_mix(__y) * __k1 + __z,126 __hash_len_16(__v.second, __w.second) + __x);127 }128 129private:130 // Some primes between 2^63 and 2^64.131 static const _Size __k0 = 0xc3a5c85c97cb3127ULL;132 static const _Size __k1 = 0xb492b66fbe98f273ULL;133 static const _Size __k2 = 0x9ae16a3b2f90404fULL;134 static const _Size __k3 = 0xc949d7c7509e6557ULL;135 136 _LIBCPP_HIDE_FROM_ABI static _Size __rotate(_Size __val, int __shift) {137 return __shift == 0 ? __val : ((__val >> __shift) | (__val << (64 - __shift)));138 }139 140 _LIBCPP_HIDE_FROM_ABI static _Size __rotate_by_at_least_1(_Size __val, int __shift) {141 return (__val >> __shift) | (__val << (64 - __shift));142 }143 144 _LIBCPP_HIDE_FROM_ABI static _Size __shift_mix(_Size __val) { return __val ^ (__val >> 47); }145 146 _LIBCPP_HIDE_FROM_ABI _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK static _Size __hash_len_16(_Size __u, _Size __v) {147 const _Size __mul = 0x9ddfea08eb382d69ULL;148 _Size __a = (__u ^ __v) * __mul;149 __a ^= (__a >> 47);150 _Size __b = (__v ^ __a) * __mul;151 __b ^= (__b >> 47);152 __b *= __mul;153 return __b;154 }155 156 _LIBCPP_HIDE_FROM_ABI _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK static _Size157 __hash_len_0_to_16(const char* __s, _Size __len) {158 if (__len > 8) {159 const _Size __a = std::__loadword<_Size>(__s);160 const _Size __b = std::__loadword<_Size>(__s + __len - 8);161 return __hash_len_16(__a, __rotate_by_at_least_1(__b + __len, __len)) ^ __b;162 }163 if (__len >= 4) {164 const uint32_t __a = std::__loadword<uint32_t>(__s);165 const uint32_t __b = std::__loadword<uint32_t>(__s + __len - 4);166#ifdef _LIBCPP_ABI_FIX_CITYHASH_IMPLEMENTATION167 return __hash_len_16(__len + (static_cast<_Size>(__a) << 3), __b);168#else169 return __hash_len_16(__len + (__a << 3), __b);170#endif171 }172 if (__len > 0) {173 const unsigned char __a = static_cast<unsigned char>(__s[0]);174 const unsigned char __b = static_cast<unsigned char>(__s[__len >> 1]);175 const unsigned char __c = static_cast<unsigned char>(__s[__len - 1]);176 const uint32_t __y = static_cast<uint32_t>(__a) + (static_cast<uint32_t>(__b) << 8);177 const uint32_t __z = __len + (static_cast<uint32_t>(__c) << 2);178 return __shift_mix(__y * __k2 ^ __z * __k3) * __k2;179 }180 return __k2;181 }182 183 _LIBCPP_HIDE_FROM_ABI _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK static _Size184 __hash_len_17_to_32(const char* __s, _Size __len) {185 const _Size __a = std::__loadword<_Size>(__s) * __k1;186 const _Size __b = std::__loadword<_Size>(__s + 8);187 const _Size __c = std::__loadword<_Size>(__s + __len - 8) * __k2;188 const _Size __d = std::__loadword<_Size>(__s + __len - 16) * __k0;189 return __hash_len_16(190 __rotate(__a - __b, 43) + __rotate(__c, 30) + __d, __a + __rotate(__b ^ __k3, 20) - __c + __len);191 }192 193 // Return a 16-byte hash for 48 bytes. Quick and dirty.194 // Callers do best to use "random-looking" values for a and b.195 _LIBCPP_HIDE_FROM_ABI _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK static pair<_Size, _Size>196 __weak_hash_len_32_with_seeds(_Size __w, _Size __x, _Size __y, _Size __z, _Size __a, _Size __b) {197 __a += __w;198 __b = __rotate(__b + __a + __z, 21);199 const _Size __c = __a;200 __a += __x;201 __a += __y;202 __b += __rotate(__a, 44);203 return pair<_Size, _Size>(__a + __z, __b + __c);204 }205 206 // Return a 16-byte hash for s[0] ... s[31], a, and b. Quick and dirty.207 _LIBCPP_HIDE_FROM_ABI _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK static pair<_Size, _Size>208 __weak_hash_len_32_with_seeds(const char* __s, _Size __a, _Size __b) {209 return __weak_hash_len_32_with_seeds(210 std::__loadword<_Size>(__s),211 std::__loadword<_Size>(__s + 8),212 std::__loadword<_Size>(__s + 16),213 std::__loadword<_Size>(__s + 24),214 __a,215 __b);216 }217 218 // Return an 8-byte hash for 33 to 64 bytes.219 _LIBCPP_HIDE_FROM_ABI _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK static _Size220 __hash_len_33_to_64(const char* __s, size_t __len) {221 _Size __z = std::__loadword<_Size>(__s + 24);222 _Size __a = std::__loadword<_Size>(__s) + (__len + std::__loadword<_Size>(__s + __len - 16)) * __k0;223 _Size __b = __rotate(__a + __z, 52);224 _Size __c = __rotate(__a, 37);225 __a += std::__loadword<_Size>(__s + 8);226 __c += __rotate(__a, 7);227 __a += std::__loadword<_Size>(__s + 16);228 _Size __vf = __a + __z;229 _Size __vs = __b + __rotate(__a, 31) + __c;230 __a = std::__loadword<_Size>(__s + 16) + std::__loadword<_Size>(__s + __len - 32);231 __z += std::__loadword<_Size>(__s + __len - 8);232 __b = __rotate(__a + __z, 52);233 __c = __rotate(__a, 37);234 __a += std::__loadword<_Size>(__s + __len - 24);235 __c += __rotate(__a, 7);236 __a += std::__loadword<_Size>(__s + __len - 16);237 _Size __wf = __a + __z;238 _Size __ws = __b + __rotate(__a, 31) + __c;239 _Size __r = __shift_mix((__vf + __ws) * __k2 + (__wf + __vs) * __k0);240 return __shift_mix(__r * __k0 + __vs) * __k2;241 }242};243 244#if _LIBCPP_AVAILABILITY_HAS_HASH_MEMORY245[[__gnu__::__pure__]] _LIBCPP_EXPORTED_FROM_ABI size_t __hash_memory(_LIBCPP_NOESCAPE const void*, size_t) _NOEXCEPT;246#else247_LIBCPP_HIDE_FROM_ABI inline size_t __hash_memory(const void* __ptr, size_t __size) _NOEXCEPT {248 return __murmur2_or_cityhash<size_t>()(__ptr, __size);249}250#endif251 252template <class _Tp, size_t = sizeof(_Tp) / sizeof(size_t)>253struct __scalar_hash;254 255template <class _Tp>256struct __scalar_hash<_Tp, 0> : public __unary_function<_Tp, size_t> {257 _LIBCPP_HIDE_FROM_ABI size_t operator()(_Tp __v) const _NOEXCEPT {258 union {259 _Tp __t;260 size_t __a;261 } __u;262 __u.__a = 0;263 __u.__t = __v;264 return __u.__a;265 }266};267 268template <class _Tp>269struct __scalar_hash<_Tp, 1> : public __unary_function<_Tp, size_t> {270 _LIBCPP_HIDE_FROM_ABI size_t operator()(_Tp __v) const _NOEXCEPT {271 union {272 _Tp __t;273 size_t __a;274 } __u;275 __u.__t = __v;276 return __u.__a;277 }278};279 280template <class _Tp>281struct __scalar_hash<_Tp, 2> : public __unary_function<_Tp, size_t> {282 _LIBCPP_HIDE_FROM_ABI size_t operator()(_Tp __v) const _NOEXCEPT {283 union {284 _Tp __t;285 struct {286 size_t __a;287 size_t __b;288 } __s;289 } __u;290 __u.__t = __v;291 return std::__hash_memory(std::addressof(__u), sizeof(__u));292 }293};294 295template <class _Tp>296struct __scalar_hash<_Tp, 3> : public __unary_function<_Tp, size_t> {297 _LIBCPP_HIDE_FROM_ABI size_t operator()(_Tp __v) const _NOEXCEPT {298 union {299 _Tp __t;300 struct {301 size_t __a;302 size_t __b;303 size_t __c;304 } __s;305 } __u;306 __u.__t = __v;307 return std::__hash_memory(std::addressof(__u), sizeof(__u));308 }309};310 311template <class _Tp>312struct __scalar_hash<_Tp, 4> : public __unary_function<_Tp, size_t> {313 _LIBCPP_HIDE_FROM_ABI size_t operator()(_Tp __v) const _NOEXCEPT {314 union {315 _Tp __t;316 struct {317 size_t __a;318 size_t __b;319 size_t __c;320 size_t __d;321 } __s;322 } __u;323 __u.__t = __v;324 return std::__hash_memory(std::addressof(__u), sizeof(__u));325 }326};327 328struct _PairT {329 size_t first;330 size_t second;331};332 333_LIBCPP_HIDE_FROM_ABI inline size_t __hash_combine(size_t __lhs, size_t __rhs) _NOEXCEPT {334 typedef __scalar_hash<_PairT> _HashT;335 const _PairT __p = {__lhs, __rhs};336 return _HashT()(__p);337}338 339template <class _Tp>340struct hash<_Tp*> : public __unary_function<_Tp*, size_t> {341 _LIBCPP_HIDE_FROM_ABI size_t operator()(_Tp* __v) const _NOEXCEPT {342 union {343 _Tp* __t;344 size_t __a;345 } __u;346 __u.__t = __v;347 return std::__hash_memory(std::addressof(__u), sizeof(__u));348 }349};350 351template <class _Tp, class = void>352struct __hash_impl {353 __hash_impl() = delete;354 __hash_impl(__hash_impl const&) = delete;355 __hash_impl& operator=(__hash_impl const&) = delete;356};357 358template <class _Tp>359struct __hash_impl<_Tp, __enable_if_t<is_enum<_Tp>::value && __is_unqualified_v<_Tp> > >360 : __unary_function<_Tp, size_t> {361 _LIBCPP_HIDE_FROM_ABI size_t operator()(_Tp __v) const _NOEXCEPT {362 using type = __underlying_type_t<_Tp>;363 return hash<type>()(static_cast<type>(__v));364 }365};366 367template <class _Tp>368struct __hash_impl<369 _Tp,370 __enable_if_t<is_integral<_Tp>::value && __is_unqualified_v<_Tp> && (sizeof(_Tp) <= sizeof(size_t))> >371 : __unary_function<_Tp, size_t> {372 _LIBCPP_HIDE_FROM_ABI size_t operator()(_Tp __v) const _NOEXCEPT { return static_cast<size_t>(__v); }373};374 375template <class _Tp>376struct __hash_impl<_Tp,377 __enable_if_t<is_integral<_Tp>::value && __is_unqualified_v<_Tp> && (sizeof(_Tp) > sizeof(size_t))> >378 : __scalar_hash<_Tp> {};379 380template <class _Tp>381struct __hash_impl<_Tp, __enable_if_t<is_floating_point<_Tp>::value && __is_unqualified_v<_Tp> > >382 : __scalar_hash<_Tp> {383 _LIBCPP_HIDE_FROM_ABI size_t operator()(_Tp __v) const _NOEXCEPT {384 // -0.0 and 0.0 should return same hash385 if (__v == 0.0f)386 return 0;387 return __scalar_hash<_Tp>::operator()(__v);388 }389};390 391template <>392struct __hash_impl<long double> : __scalar_hash<long double> {393 _LIBCPP_HIDE_FROM_ABI size_t operator()(long double __v) const _NOEXCEPT {394 // -0.0 and 0.0 should return same hash395 if (__v == 0.0L)396 return 0;397#if defined(__i386__) || (defined(__x86_64__) && defined(__ILP32__))398 // Zero out padding bits399 union {400 long double __t;401 struct {402 size_t __a;403 size_t __b;404 size_t __c;405 size_t __d;406 } __s;407 } __u;408 __u.__s.__a = 0;409 __u.__s.__b = 0;410 __u.__s.__c = 0;411 __u.__s.__d = 0;412 __u.__t = __v;413 return __u.__s.__a ^ __u.__s.__b ^ __u.__s.__c ^ __u.__s.__d;414#elif defined(__x86_64__)415 // Zero out padding bits416 union {417 long double __t;418 struct {419 size_t __a;420 size_t __b;421 } __s;422 } __u;423 __u.__s.__a = 0;424 __u.__s.__b = 0;425 __u.__t = __v;426 return __u.__s.__a ^ __u.__s.__b;427#else428 return __scalar_hash<long double>::operator()(__v);429#endif430 }431};432 433template <class _Tp>434struct hash : public __hash_impl<_Tp> {};435 436template <>437struct hash<nullptr_t> : public __unary_function<nullptr_t, size_t> {438 _LIBCPP_HIDE_FROM_ABI size_t operator()(nullptr_t) const _NOEXCEPT { return 662607004ull; }439};440 441#ifndef _LIBCPP_CXX03_LANG442template <class _Key, class _Hash>443using __check_hash_requirements _LIBCPP_NODEBUG =444 integral_constant<bool,445 is_copy_constructible<_Hash>::value && is_move_constructible<_Hash>::value &&446 __is_invocable_r_v<size_t, _Hash, _Key const&> >;447 448template <class _Key, class _Hash = hash<_Key> >449using __has_enabled_hash _LIBCPP_NODEBUG =450 integral_constant<bool, __check_hash_requirements<_Key, _Hash>::value && is_default_constructible<_Hash>::value >;451 452template <class _Type, class>453using __enable_hash_helper_imp _LIBCPP_NODEBUG = _Type;454 455template <class _Type, class... _Keys>456using __enable_hash_helper _LIBCPP_NODEBUG =457 __enable_hash_helper_imp<_Type, __enable_if_t<__all<__has_enabled_hash<_Keys>::value...>::value> >;458#endif // !_LIBCPP_CXX03_LANG459 460_LIBCPP_END_NAMESPACE_STD461 462#endif // _LIBCPP___FUNCTIONAL_HASH_H463