Warning: This file is not a C or C++ file. It does not have highlighting.

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

Warning: This file is not a C or C++ file. It does not have highlighting.

source code of libcxx/include/__cxx03/__functional/hash.h