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