xref: /freebsd/contrib/llvm-project/libcxx/include/__functional/hash.h (revision 13ec1e3155c7e9bf037b12af186351b7fa9b9450) 
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 <__functional/unary_function.h>
14 #include <__tuple>
15 #include <__utility/forward.h>
16 #include <__utility/move.h>
17 #include <__utility/pair.h>
18 #include <__utility/swap.h>
19 #include <cstdint>
20 #include <cstring>
21 #include <cstddef>
22 #include <limits>
23 #include <type_traits>
24 
25 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
26 #pragma GCC system_header
27 #endif
28 
29 _LIBCPP_PUSH_MACROS
30 #include <__undef_macros>
31 
32 _LIBCPP_BEGIN_NAMESPACE_STD
33 
34 template <class _Size>
35 inline _LIBCPP_INLINE_VISIBILITY
36 _Size
37 __loadword(const void* __p)
38 {
39     _Size __r;
40     _VSTD::memcpy(&__r, __p, sizeof(__r));
41     return __r;
42 }
43 
44 // We use murmur2 when size_t is 32 bits, and cityhash64 when size_t
45 // is 64 bits.  This is because cityhash64 uses 64bit x 64bit
46 // multiplication, which can be very slow on 32-bit systems.
47 template <class _Size, size_t = sizeof(_Size)*__CHAR_BIT__>
48 struct __murmur2_or_cityhash;
49 
50 template <class _Size>
51 struct __murmur2_or_cityhash<_Size, 32>
52 {
53     inline _Size operator()(const void* __key, _Size __len)
54          _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK;
55 };
56 
57 // murmur2
58 template <class _Size>
59 _Size
60 __murmur2_or_cityhash<_Size, 32>::operator()(const void* __key, _Size __len)
61 {
62     const _Size __m = 0x5bd1e995;
63     const _Size __r = 24;
64     _Size __h = __len;
65     const unsigned char* __data = static_cast<const unsigned char*>(__key);
66     for (; __len >= 4; __data += 4, __len -= 4)
67     {
68         _Size __k = __loadword<_Size>(__data);
69         __k *= __m;
70         __k ^= __k >> __r;
71         __k *= __m;
72         __h *= __m;
73         __h ^= __k;
74     }
75     switch (__len)
76     {
77     case 3:
78         __h ^= static_cast<_Size>(__data[2] << 16);
79         _LIBCPP_FALLTHROUGH();
80     case 2:
81         __h ^= static_cast<_Size>(__data[1] << 8);
82         _LIBCPP_FALLTHROUGH();
83     case 1:
84         __h ^= __data[0];
85         __h *= __m;
86     }
87     __h ^= __h >> 13;
88     __h *= __m;
89     __h ^= __h >> 15;
90     return __h;
91 }
92 
93 template <class _Size>
94 struct __murmur2_or_cityhash<_Size, 64>
95 {
96     inline _Size operator()(const void* __key, _Size __len)  _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK;
97 
98  private:
99   // Some primes between 2^63 and 2^64.
100   static const _Size __k0 = 0xc3a5c85c97cb3127ULL;
101   static const _Size __k1 = 0xb492b66fbe98f273ULL;
102   static const _Size __k2 = 0x9ae16a3b2f90404fULL;
103   static const _Size __k3 = 0xc949d7c7509e6557ULL;
104 
105   static _Size __rotate(_Size __val, int __shift) {
106     return __shift == 0 ? __val : ((__val >> __shift) | (__val << (64 - __shift)));
107   }
108 
109   static _Size __rotate_by_at_least_1(_Size __val, int __shift) {
110     return (__val >> __shift) | (__val << (64 - __shift));
111   }
112 
113   static _Size __shift_mix(_Size __val) {
114     return __val ^ (__val >> 47);
115   }
116 
117   static _Size __hash_len_16(_Size __u, _Size __v)
118      _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
119   {
120     const _Size __mul = 0x9ddfea08eb382d69ULL;
121     _Size __a = (__u ^ __v) * __mul;
122     __a ^= (__a >> 47);
123     _Size __b = (__v ^ __a) * __mul;
124     __b ^= (__b >> 47);
125     __b *= __mul;
126     return __b;
127   }
128 
129   static _Size __hash_len_0_to_16(const char* __s, _Size __len)
130      _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
131   {
132     if (__len > 8) {
133       const _Size __a = __loadword<_Size>(__s);
134       const _Size __b = __loadword<_Size>(__s + __len - 8);
135       return __hash_len_16(__a, __rotate_by_at_least_1(__b + __len, __len)) ^ __b;
136     }
137     if (__len >= 4) {
138       const uint32_t __a = __loadword<uint32_t>(__s);
139       const uint32_t __b = __loadword<uint32_t>(__s + __len - 4);
140       return __hash_len_16(__len + (__a << 3), __b);
141     }
142     if (__len > 0) {
143       const unsigned char __a = static_cast<unsigned char>(__s[0]);
144       const unsigned char __b = static_cast<unsigned char>(__s[__len >> 1]);
145       const unsigned char __c = static_cast<unsigned char>(__s[__len - 1]);
146       const uint32_t __y = static_cast<uint32_t>(__a) +
147                            (static_cast<uint32_t>(__b) << 8);
148       const uint32_t __z = __len + (static_cast<uint32_t>(__c) << 2);
149       return __shift_mix(__y * __k2 ^ __z * __k3) * __k2;
150     }
151     return __k2;
152   }
153 
154   static _Size __hash_len_17_to_32(const char *__s, _Size __len)
155      _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
156   {
157     const _Size __a = __loadword<_Size>(__s) * __k1;
158     const _Size __b = __loadword<_Size>(__s + 8);
159     const _Size __c = __loadword<_Size>(__s + __len - 8) * __k2;
160     const _Size __d = __loadword<_Size>(__s + __len - 16) * __k0;
161     return __hash_len_16(__rotate(__a - __b, 43) + __rotate(__c, 30) + __d,
162                          __a + __rotate(__b ^ __k3, 20) - __c + __len);
163   }
164 
165   // Return a 16-byte hash for 48 bytes.  Quick and dirty.
166   // Callers do best to use "random-looking" values for a and b.
167   static pair<_Size, _Size> __weak_hash_len_32_with_seeds(
168       _Size __w, _Size __x, _Size __y, _Size __z, _Size __a, _Size __b)
169         _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
170   {
171     __a += __w;
172     __b = __rotate(__b + __a + __z, 21);
173     const _Size __c = __a;
174     __a += __x;
175     __a += __y;
176     __b += __rotate(__a, 44);
177     return pair<_Size, _Size>(__a + __z, __b + __c);
178   }
179 
180   // Return a 16-byte hash for s[0] ... s[31], a, and b.  Quick and dirty.
181   static pair<_Size, _Size> __weak_hash_len_32_with_seeds(
182       const char* __s, _Size __a, _Size __b)
183     _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
184   {
185     return __weak_hash_len_32_with_seeds(__loadword<_Size>(__s),
186                                          __loadword<_Size>(__s + 8),
187                                          __loadword<_Size>(__s + 16),
188                                          __loadword<_Size>(__s + 24),
189                                          __a,
190                                          __b);
191   }
192 
193   // Return an 8-byte hash for 33 to 64 bytes.
194   static _Size __hash_len_33_to_64(const char *__s, size_t __len)
195     _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
196   {
197     _Size __z = __loadword<_Size>(__s + 24);
198     _Size __a = __loadword<_Size>(__s) +
199                 (__len + __loadword<_Size>(__s + __len - 16)) * __k0;
200     _Size __b = __rotate(__a + __z, 52);
201     _Size __c = __rotate(__a, 37);
202     __a += __loadword<_Size>(__s + 8);
203     __c += __rotate(__a, 7);
204     __a += __loadword<_Size>(__s + 16);
205     _Size __vf = __a + __z;
206     _Size __vs = __b + __rotate(__a, 31) + __c;
207     __a = __loadword<_Size>(__s + 16) + __loadword<_Size>(__s + __len - 32);
208     __z += __loadword<_Size>(__s + __len - 8);
209     __b = __rotate(__a + __z, 52);
210     __c = __rotate(__a, 37);
211     __a += __loadword<_Size>(__s + __len - 24);
212     __c += __rotate(__a, 7);
213     __a += __loadword<_Size>(__s + __len - 16);
214     _Size __wf = __a + __z;
215     _Size __ws = __b + __rotate(__a, 31) + __c;
216     _Size __r = __shift_mix((__vf + __ws) * __k2 + (__wf + __vs) * __k0);
217     return __shift_mix(__r * __k0 + __vs) * __k2;
218   }
219 };
220 
221 // cityhash64
222 template <class _Size>
223 _Size
224 __murmur2_or_cityhash<_Size, 64>::operator()(const void* __key, _Size __len)
225 {
226   const char* __s = static_cast<const char*>(__key);
227   if (__len <= 32) {
228     if (__len <= 16) {
229       return __hash_len_0_to_16(__s, __len);
230     } else {
231       return __hash_len_17_to_32(__s, __len);
232     }
233   } else if (__len <= 64) {
234     return __hash_len_33_to_64(__s, __len);
235   }
236 
237   // For strings over 64 bytes we hash the end first, and then as we
238   // loop we keep 56 bytes of state: v, w, x, y, and z.
239   _Size __x = __loadword<_Size>(__s + __len - 40);
240   _Size __y = __loadword<_Size>(__s + __len - 16) +
241               __loadword<_Size>(__s + __len - 56);
242   _Size __z = __hash_len_16(__loadword<_Size>(__s + __len - 48) + __len,
243                           __loadword<_Size>(__s + __len - 24));
244   pair<_Size, _Size> __v = __weak_hash_len_32_with_seeds(__s + __len - 64, __len, __z);
245   pair<_Size, _Size> __w = __weak_hash_len_32_with_seeds(__s + __len - 32, __y + __k1, __x);
246   __x = __x * __k1 + __loadword<_Size>(__s);
247 
248   // Decrease len to the nearest multiple of 64, and operate on 64-byte chunks.
249   __len = (__len - 1) & ~static_cast<_Size>(63);
250   do {
251     __x = __rotate(__x + __y + __v.first + __loadword<_Size>(__s + 8), 37) * __k1;
252     __y = __rotate(__y + __v.second + __loadword<_Size>(__s + 48), 42) * __k1;
253     __x ^= __w.second;
254     __y += __v.first + __loadword<_Size>(__s + 40);
255     __z = __rotate(__z + __w.first, 33) * __k1;
256     __v = __weak_hash_len_32_with_seeds(__s, __v.second * __k1, __x + __w.first);
257     __w = __weak_hash_len_32_with_seeds(__s + 32, __z + __w.second,
258                                         __y + __loadword<_Size>(__s + 16));
259     _VSTD::swap(__z, __x);
260     __s += 64;
261     __len -= 64;
262   } while (__len != 0);
263   return __hash_len_16(
264       __hash_len_16(__v.first, __w.first) + __shift_mix(__y) * __k1 + __z,
265       __hash_len_16(__v.second, __w.second) + __x);
266 }
267 
268 template <class _Tp, size_t = sizeof(_Tp) / sizeof(size_t)>
269 struct __scalar_hash;
270 
271 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
272 template <class _Tp>
273 struct __scalar_hash<_Tp, 0>
274 #if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
275     : public unary_function<_Tp, size_t>
276 #endif
277 {
278 _LIBCPP_SUPPRESS_DEPRECATED_POP
279 #if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
280     _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type;
281     _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp argument_type;
282 #endif
283     _LIBCPP_INLINE_VISIBILITY
284     size_t operator()(_Tp __v) const _NOEXCEPT
285     {
286         union
287         {
288             _Tp    __t;
289             size_t __a;
290         } __u;
291         __u.__a = 0;
292         __u.__t = __v;
293         return __u.__a;
294     }
295 };
296 
297 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
298 template <class _Tp>
299 struct __scalar_hash<_Tp, 1>
300 #if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
301     : public unary_function<_Tp, size_t>
302 #endif
303 {
304 _LIBCPP_SUPPRESS_DEPRECATED_POP
305 #if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
306     _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type;
307     _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp argument_type;
308 #endif
309     _LIBCPP_INLINE_VISIBILITY
310     size_t operator()(_Tp __v) const _NOEXCEPT
311     {
312         union
313         {
314             _Tp    __t;
315             size_t __a;
316         } __u;
317         __u.__t = __v;
318         return __u.__a;
319     }
320 };
321 
322 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
323 template <class _Tp>
324 struct __scalar_hash<_Tp, 2>
325 #if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
326     : public unary_function<_Tp, size_t>
327 #endif
328 {
329 _LIBCPP_SUPPRESS_DEPRECATED_POP
330 #if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
331     _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type;
332     _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp argument_type;
333 #endif
334     _LIBCPP_INLINE_VISIBILITY
335     size_t operator()(_Tp __v) const _NOEXCEPT
336     {
337         union
338         {
339             _Tp __t;
340             struct
341             {
342                 size_t __a;
343                 size_t __b;
344             } __s;
345         } __u;
346         __u.__t = __v;
347         return __murmur2_or_cityhash<size_t>()(&__u, sizeof(__u));
348     }
349 };
350 
351 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
352 template <class _Tp>
353 struct __scalar_hash<_Tp, 3>
354 #if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
355     : public unary_function<_Tp, size_t>
356 #endif
357 {
358 _LIBCPP_SUPPRESS_DEPRECATED_POP
359 #if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
360     _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type;
361     _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp argument_type;
362 #endif
363     _LIBCPP_INLINE_VISIBILITY
364     size_t operator()(_Tp __v) const _NOEXCEPT
365     {
366         union
367         {
368             _Tp __t;
369             struct
370             {
371                 size_t __a;
372                 size_t __b;
373                 size_t __c;
374             } __s;
375         } __u;
376         __u.__t = __v;
377         return __murmur2_or_cityhash<size_t>()(&__u, sizeof(__u));
378     }
379 };
380 
381 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
382 template <class _Tp>
383 struct __scalar_hash<_Tp, 4>
384 #if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
385     : public unary_function<_Tp, size_t>
386 #endif
387 {
388 _LIBCPP_SUPPRESS_DEPRECATED_POP
389 #if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
390     _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type;
391     _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp argument_type;
392 #endif
393     _LIBCPP_INLINE_VISIBILITY
394     size_t operator()(_Tp __v) const _NOEXCEPT
395     {
396         union
397         {
398             _Tp __t;
399             struct
400             {
401                 size_t __a;
402                 size_t __b;
403                 size_t __c;
404                 size_t __d;
405             } __s;
406         } __u;
407         __u.__t = __v;
408         return __murmur2_or_cityhash<size_t>()(&__u, sizeof(__u));
409     }
410 };
411 
412 struct _PairT {
413   size_t first;
414   size_t second;
415 };
416 
417 _LIBCPP_INLINE_VISIBILITY
418 inline size_t __hash_combine(size_t __lhs, size_t __rhs) _NOEXCEPT {
419     typedef __scalar_hash<_PairT> _HashT;
420     const _PairT __p = {__lhs, __rhs};
421     return _HashT()(__p);
422 }
423 
424 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
425 template<class _Tp>
426 struct _LIBCPP_TEMPLATE_VIS hash<_Tp*>
427 #if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
428     : public unary_function<_Tp*, size_t>
429 #endif
430 {
431 _LIBCPP_SUPPRESS_DEPRECATED_POP
432 #if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
433     _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type;
434     _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp* argument_type;
435 #endif
436     _LIBCPP_INLINE_VISIBILITY
437     size_t operator()(_Tp* __v) const _NOEXCEPT
438     {
439         union
440         {
441             _Tp* __t;
442             size_t __a;
443         } __u;
444         __u.__t = __v;
445         return __murmur2_or_cityhash<size_t>()(&__u, sizeof(__u));
446     }
447 };
448 
449 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
450 template <>
451 struct _LIBCPP_TEMPLATE_VIS hash<bool>
452 #if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
453     : public unary_function<bool, size_t>
454 #endif
455 {
456 _LIBCPP_SUPPRESS_DEPRECATED_POP
457 #if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
458     _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type;
459     _LIBCPP_DEPRECATED_IN_CXX17 typedef bool argument_type;
460 #endif
461     _LIBCPP_INLINE_VISIBILITY
462     size_t operator()(bool __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
463 };
464 
465 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
466 template <>
467 struct _LIBCPP_TEMPLATE_VIS hash<char>
468 #if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
469     : public unary_function<char, size_t>
470 #endif
471 {
472 _LIBCPP_SUPPRESS_DEPRECATED_POP
473 #if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
474     _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type;
475     _LIBCPP_DEPRECATED_IN_CXX17 typedef char argument_type;
476 #endif
477     _LIBCPP_INLINE_VISIBILITY
478     size_t operator()(char __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
479 };
480 
481 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
482 template <>
483 struct _LIBCPP_TEMPLATE_VIS hash<signed char>
484 #if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
485     : public unary_function<signed char, size_t>
486 #endif
487 {
488 _LIBCPP_SUPPRESS_DEPRECATED_POP
489 #if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
490     _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type;
491     _LIBCPP_DEPRECATED_IN_CXX17 typedef signed char argument_type;
492 #endif
493     _LIBCPP_INLINE_VISIBILITY
494     size_t operator()(signed char __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
495 };
496 
497 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
498 template <>
499 struct _LIBCPP_TEMPLATE_VIS hash<unsigned char>
500 #if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
501     : public unary_function<unsigned char, size_t>
502 #endif
503 {
504 _LIBCPP_SUPPRESS_DEPRECATED_POP
505 #if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
506     _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type;
507     _LIBCPP_DEPRECATED_IN_CXX17 typedef unsigned char argument_type;
508 #endif
509     _LIBCPP_INLINE_VISIBILITY
510     size_t operator()(unsigned char __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
511 };
512 
513 #ifndef _LIBCPP_HAS_NO_CHAR8_T
514 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
515 template <>
516 struct _LIBCPP_TEMPLATE_VIS hash<char8_t>
517 #if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
518     : public unary_function<char8_t, size_t>
519 #endif
520 {
521 _LIBCPP_SUPPRESS_DEPRECATED_POP
522 #if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
523     _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type;
524     _LIBCPP_DEPRECATED_IN_CXX17 typedef char8_t argument_type;
525 #endif
526     _LIBCPP_INLINE_VISIBILITY
527     size_t operator()(char8_t __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
528 };
529 #endif // !_LIBCPP_HAS_NO_CHAR8_T
530 
531 #ifndef _LIBCPP_HAS_NO_UNICODE_CHARS
532 
533 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
534 template <>
535 struct _LIBCPP_TEMPLATE_VIS hash<char16_t>
536 #if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
537     : public unary_function<char16_t, size_t>
538 #endif
539 {
540 _LIBCPP_SUPPRESS_DEPRECATED_POP
541 #if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
542     _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type;
543     _LIBCPP_DEPRECATED_IN_CXX17 typedef char16_t argument_type;
544 #endif
545     _LIBCPP_INLINE_VISIBILITY
546     size_t operator()(char16_t __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
547 };
548 
549 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
550 template <>
551 struct _LIBCPP_TEMPLATE_VIS hash<char32_t>
552 #if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
553     : public unary_function<char32_t, size_t>
554 #endif
555 {
556 _LIBCPP_SUPPRESS_DEPRECATED_POP
557 #if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
558     _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type;
559     _LIBCPP_DEPRECATED_IN_CXX17 typedef char32_t argument_type;
560 #endif
561     _LIBCPP_INLINE_VISIBILITY
562     size_t operator()(char32_t __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
563 };
564 
565 #endif // _LIBCPP_HAS_NO_UNICODE_CHARS
566 
567 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
568 template <>
569 struct _LIBCPP_TEMPLATE_VIS hash<wchar_t>
570 #if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
571     : public unary_function<wchar_t, size_t>
572 #endif
573 {
574 _LIBCPP_SUPPRESS_DEPRECATED_POP
575 #if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
576     _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type;
577     _LIBCPP_DEPRECATED_IN_CXX17 typedef wchar_t argument_type;
578 #endif
579     _LIBCPP_INLINE_VISIBILITY
580     size_t operator()(wchar_t __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
581 };
582 
583 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
584 template <>
585 struct _LIBCPP_TEMPLATE_VIS hash<short>
586 #if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
587     : public unary_function<short, size_t>
588 #endif
589 {
590 _LIBCPP_SUPPRESS_DEPRECATED_POP
591 #if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
592     _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type;
593     _LIBCPP_DEPRECATED_IN_CXX17 typedef short argument_type;
594 #endif
595     _LIBCPP_INLINE_VISIBILITY
596     size_t operator()(short __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
597 };
598 
599 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
600 template <>
601 struct _LIBCPP_TEMPLATE_VIS hash<unsigned short>
602 #if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
603     : public unary_function<unsigned short, size_t>
604 #endif
605 {
606 _LIBCPP_SUPPRESS_DEPRECATED_POP
607 #if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
608     _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type;
609     _LIBCPP_DEPRECATED_IN_CXX17 typedef unsigned short argument_type;
610 #endif
611     _LIBCPP_INLINE_VISIBILITY
612     size_t operator()(unsigned short __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
613 };
614 
615 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
616 template <>
617 struct _LIBCPP_TEMPLATE_VIS hash<int>
618 #if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
619     : public unary_function<int, size_t>
620 #endif
621 {
622 _LIBCPP_SUPPRESS_DEPRECATED_POP
623 #if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
624     _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type;
625     _LIBCPP_DEPRECATED_IN_CXX17 typedef int argument_type;
626 #endif
627     _LIBCPP_INLINE_VISIBILITY
628     size_t operator()(int __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
629 };
630 
631 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
632 template <>
633 struct _LIBCPP_TEMPLATE_VIS hash<unsigned int>
634 #if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
635     : public unary_function<unsigned int, size_t>
636 #endif
637 {
638 _LIBCPP_SUPPRESS_DEPRECATED_POP
639 #if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
640     _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type;
641     _LIBCPP_DEPRECATED_IN_CXX17 typedef unsigned int argument_type;
642 #endif
643     _LIBCPP_INLINE_VISIBILITY
644     size_t operator()(unsigned int __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
645 };
646 
647 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
648 template <>
649 struct _LIBCPP_TEMPLATE_VIS hash<long>
650 #if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
651     : public unary_function<long, size_t>
652 #endif
653 {
654 _LIBCPP_SUPPRESS_DEPRECATED_POP
655 #if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
656     _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type;
657     _LIBCPP_DEPRECATED_IN_CXX17 typedef long argument_type;
658 #endif
659     _LIBCPP_INLINE_VISIBILITY
660     size_t operator()(long __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
661 };
662 
663 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
664 template <>
665 struct _LIBCPP_TEMPLATE_VIS hash<unsigned long>
666 #if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
667     : public unary_function<unsigned long, size_t>
668 #endif
669 {
670 _LIBCPP_SUPPRESS_DEPRECATED_POP
671 #if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
672     _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type;
673     _LIBCPP_DEPRECATED_IN_CXX17 typedef unsigned long argument_type;
674 #endif
675     _LIBCPP_INLINE_VISIBILITY
676     size_t operator()(unsigned long __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
677 };
678 
679 template <>
680 struct _LIBCPP_TEMPLATE_VIS hash<long long>
681     : public __scalar_hash<long long>
682 {
683 };
684 
685 template <>
686 struct _LIBCPP_TEMPLATE_VIS hash<unsigned long long>
687     : public __scalar_hash<unsigned long long>
688 {
689 };
690 
691 #ifndef _LIBCPP_HAS_NO_INT128
692 
693 template <>
694 struct _LIBCPP_TEMPLATE_VIS hash<__int128_t>
695     : public __scalar_hash<__int128_t>
696 {
697 };
698 
699 template <>
700 struct _LIBCPP_TEMPLATE_VIS hash<__uint128_t>
701     : public __scalar_hash<__uint128_t>
702 {
703 };
704 
705 #endif
706 
707 template <>
708 struct _LIBCPP_TEMPLATE_VIS hash<float>
709     : public __scalar_hash<float>
710 {
711     _LIBCPP_INLINE_VISIBILITY
712     size_t operator()(float __v) const _NOEXCEPT
713     {
714         // -0.0 and 0.0 should return same hash
715        if (__v == 0.0f)
716            return 0;
717         return __scalar_hash<float>::operator()(__v);
718     }
719 };
720 
721 template <>
722 struct _LIBCPP_TEMPLATE_VIS hash<double>
723     : public __scalar_hash<double>
724 {
725     _LIBCPP_INLINE_VISIBILITY
726     size_t operator()(double __v) const _NOEXCEPT
727     {
728         // -0.0 and 0.0 should return same hash
729        if (__v == 0.0)
730            return 0;
731         return __scalar_hash<double>::operator()(__v);
732     }
733 };
734 
735 template <>
736 struct _LIBCPP_TEMPLATE_VIS hash<long double>
737     : public __scalar_hash<long double>
738 {
739     _LIBCPP_INLINE_VISIBILITY
740     size_t operator()(long double __v) const _NOEXCEPT
741     {
742         // -0.0 and 0.0 should return same hash
743         if (__v == 0.0L)
744             return 0;
745 #if defined(__i386__) || (defined(__x86_64__) && defined(__ILP32__))
746         // Zero out padding bits
747         union
748         {
749             long double __t;
750             struct
751             {
752                 size_t __a;
753                 size_t __b;
754                 size_t __c;
755                 size_t __d;
756             } __s;
757         } __u;
758         __u.__s.__a = 0;
759         __u.__s.__b = 0;
760         __u.__s.__c = 0;
761         __u.__s.__d = 0;
762         __u.__t = __v;
763         return __u.__s.__a ^ __u.__s.__b ^ __u.__s.__c ^ __u.__s.__d;
764 #elif defined(__x86_64__)
765         // Zero out padding bits
766         union
767         {
768             long double __t;
769             struct
770             {
771                 size_t __a;
772                 size_t __b;
773             } __s;
774         } __u;
775         __u.__s.__a = 0;
776         __u.__s.__b = 0;
777         __u.__t = __v;
778         return __u.__s.__a ^ __u.__s.__b;
779 #else
780         return __scalar_hash<long double>::operator()(__v);
781 #endif
782     }
783 };
784 
785 #if _LIBCPP_STD_VER > 11
786 
787 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
788 template <class _Tp, bool = is_enum<_Tp>::value>
789 struct _LIBCPP_TEMPLATE_VIS __enum_hash
790 #if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
791     : public unary_function<_Tp, size_t>
792 #endif
793 {
794 _LIBCPP_SUPPRESS_DEPRECATED_POP
795 #if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
796     _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type;
797     _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp argument_type;
798 #endif
799     _LIBCPP_INLINE_VISIBILITY
800     size_t operator()(_Tp __v) const _NOEXCEPT
801     {
802         typedef typename underlying_type<_Tp>::type type;
803         return hash<type>{}(static_cast<type>(__v));
804     }
805 };
806 template <class _Tp>
807 struct _LIBCPP_TEMPLATE_VIS __enum_hash<_Tp, false> {
808     __enum_hash() = delete;
809     __enum_hash(__enum_hash const&) = delete;
810     __enum_hash& operator=(__enum_hash const&) = delete;
811 };
812 
813 template <class _Tp>
814 struct _LIBCPP_TEMPLATE_VIS hash : public __enum_hash<_Tp>
815 {
816 };
817 #endif
818 
819 #if _LIBCPP_STD_VER > 14
820 
821 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
822 template <>
823 struct _LIBCPP_TEMPLATE_VIS hash<nullptr_t>
824 #if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
825   : public unary_function<nullptr_t, size_t>
826 #endif
827 {
828 _LIBCPP_SUPPRESS_DEPRECATED_POP
829 #if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
830     _LIBCPP_DEPRECATED_IN_CXX17 typedef size_t result_type;
831     _LIBCPP_DEPRECATED_IN_CXX17 typedef nullptr_t argument_type;
832 #endif
833     _LIBCPP_INLINE_VISIBILITY
834     size_t operator()(nullptr_t) const _NOEXCEPT {
835         return 662607004ull;
836     }
837 };
838 #endif
839 
840 #ifndef _LIBCPP_CXX03_LANG
841 template <class _Key, class _Hash>
842 using __check_hash_requirements _LIBCPP_NODEBUG_TYPE  = integral_constant<bool,
843     is_copy_constructible<_Hash>::value &&
844     is_move_constructible<_Hash>::value &&
845     __invokable_r<size_t, _Hash, _Key const&>::value
846 >;
847 
848 template <class _Key, class _Hash = hash<_Key> >
849 using __has_enabled_hash _LIBCPP_NODEBUG_TYPE = integral_constant<bool,
850     __check_hash_requirements<_Key, _Hash>::value &&
851     is_default_constructible<_Hash>::value
852 >;
853 
854 #if _LIBCPP_STD_VER > 14
855 template <class _Type, class>
856 using __enable_hash_helper_imp _LIBCPP_NODEBUG_TYPE  = _Type;
857 
858 template <class _Type, class ..._Keys>
859 using __enable_hash_helper _LIBCPP_NODEBUG_TYPE  = __enable_hash_helper_imp<_Type,
860   typename enable_if<__all<__has_enabled_hash<_Keys>::value...>::value>::type
861 >;
862 #else
863 template <class _Type, class ...>
864 using __enable_hash_helper _LIBCPP_NODEBUG_TYPE = _Type;
865 #endif
866 
867 #endif // !_LIBCPP_CXX03_LANG
868 
869 _LIBCPP_END_NAMESPACE_STD
870 
871 _LIBCPP_POP_MACROS
872 
873 #endif // _LIBCPP___FUNCTIONAL_HASH_H
874