1 | // Copyright 2005-2014 Daniel James. |
2 | // Copyright 2021, 2022 Peter Dimov. |
3 | // Distributed under the Boost Software License, Version 1.0. |
4 | // https://www.boost.org/LICENSE_1_0.txt |
5 | |
6 | // Based on Peter Dimov's proposal |
7 | // http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1756.pdf |
8 | // issue 6.18. |
9 | |
10 | #ifndef BOOST_FUNCTIONAL_HASH_HASH_HPP |
11 | #define BOOST_FUNCTIONAL_HASH_HASH_HPP |
12 | |
13 | #include <boost/container_hash/hash_fwd.hpp> |
14 | #include <boost/container_hash/is_range.hpp> |
15 | #include <boost/container_hash/is_contiguous_range.hpp> |
16 | #include <boost/container_hash/is_unordered_range.hpp> |
17 | #include <boost/container_hash/is_described_class.hpp> |
18 | #include <boost/container_hash/detail/hash_integral.hpp> |
19 | #include <boost/container_hash/detail/hash_tuple_like.hpp> |
20 | #include <boost/container_hash/detail/hash_mix.hpp> |
21 | #include <boost/container_hash/detail/hash_range.hpp> |
22 | #include <boost/describe/bases.hpp> |
23 | #include <boost/describe/members.hpp> |
24 | #include <type_traits> |
25 | #include <cstdint> |
26 | |
27 | #if defined(BOOST_DESCRIBE_CXX14) |
28 | # include <boost/mp11/algorithm.hpp> |
29 | #endif |
30 | |
31 | #include <string> |
32 | #include <iterator> |
33 | #include <complex> |
34 | #include <utility> |
35 | #include <limits> |
36 | #include <climits> |
37 | #include <cstring> |
38 | |
39 | #if !defined(BOOST_NO_CXX11_SMART_PTR) |
40 | # include <memory> |
41 | #endif |
42 | |
43 | #if !defined(BOOST_NO_CXX11_HDR_TYPEINDEX) |
44 | #include <typeindex> |
45 | #endif |
46 | |
47 | #if !defined(BOOST_NO_CXX11_HDR_SYSTEM_ERROR) |
48 | #include <system_error> |
49 | #endif |
50 | |
51 | #if !defined(BOOST_NO_CXX17_HDR_OPTIONAL) |
52 | #include <optional> |
53 | #endif |
54 | |
55 | #if !defined(BOOST_NO_CXX17_HDR_VARIANT) |
56 | #include <variant> |
57 | #endif |
58 | |
59 | #if !defined(BOOST_NO_CXX17_HDR_STRING_VIEW) |
60 | # include <string_view> |
61 | #endif |
62 | |
63 | namespace boost |
64 | { |
65 | |
66 | // |
67 | // boost::hash_value |
68 | // |
69 | |
70 | // integral types |
71 | // in detail/hash_integral.hpp |
72 | |
73 | // enumeration types |
74 | |
75 | template <typename T> |
76 | typename std::enable_if<std::is_enum<T>::value, std::size_t>::type |
77 | hash_value( T v ) |
78 | { |
79 | // This should in principle return the equivalent of |
80 | // |
81 | // boost::hash_value( to_underlying(v) ); |
82 | // |
83 | // However, the C++03 implementation of underlying_type, |
84 | // |
85 | // conditional<is_signed<T>, make_signed<T>, make_unsigned<T>>::type::type |
86 | // |
87 | // generates a legitimate -Wconversion warning in is_signed, |
88 | // because -1 is not a valid enum value when all the enumerators |
89 | // are nonnegative. |
90 | // |
91 | // So the legacy implementation will have to do for now. |
92 | |
93 | return static_cast<std::size_t>( v ); |
94 | } |
95 | |
96 | // floating point types |
97 | |
98 | namespace hash_detail |
99 | { |
100 | template<class T, |
101 | std::size_t Bits = sizeof(T) * CHAR_BIT, |
102 | int Digits = std::numeric_limits<T>::digits> |
103 | struct hash_float_impl; |
104 | |
105 | // float |
106 | template<class T, int Digits> struct hash_float_impl<T, 32, Digits> |
107 | { |
108 | static std::size_t fn( T v ) |
109 | { |
110 | std::uint32_t w; |
111 | std::memcpy( dest: &w, src: &v, n: sizeof( v ) ); |
112 | |
113 | return w; |
114 | } |
115 | }; |
116 | |
117 | // double |
118 | template<class T, int Digits> struct hash_float_impl<T, 64, Digits> |
119 | { |
120 | static std::size_t fn( T v ) |
121 | { |
122 | std::uint64_t w; |
123 | std::memcpy( dest: &w, src: &v, n: sizeof( v ) ); |
124 | |
125 | return hash_value( v: w ); |
126 | } |
127 | }; |
128 | |
129 | // 80 bit long double in 12 bytes |
130 | template<class T> struct hash_float_impl<T, 96, 64> |
131 | { |
132 | static std::size_t fn( T v ) |
133 | { |
134 | std::uint64_t w[ 2 ] = {}; |
135 | std::memcpy( dest: &w, src: &v, n: 80 / CHAR_BIT ); |
136 | |
137 | std::size_t seed = 0; |
138 | |
139 | seed = hash_value( v: w[0] ) + hash_detail::hash_mix( v: seed ); |
140 | seed = hash_value( v: w[1] ) + hash_detail::hash_mix( v: seed ); |
141 | |
142 | return seed; |
143 | } |
144 | }; |
145 | |
146 | // 80 bit long double in 16 bytes |
147 | template<class T> struct hash_float_impl<T, 128, 64> |
148 | { |
149 | static std::size_t fn( T v ) |
150 | { |
151 | std::uint64_t w[ 2 ] = {}; |
152 | std::memcpy( dest: &w, src: &v, n: 80 / CHAR_BIT ); |
153 | |
154 | std::size_t seed = 0; |
155 | |
156 | seed = hash_value( v: w[0] ) + hash_detail::hash_mix( v: seed ); |
157 | seed = hash_value( v: w[1] ) + hash_detail::hash_mix( v: seed ); |
158 | |
159 | return seed; |
160 | } |
161 | }; |
162 | |
163 | // 128 bit long double |
164 | template<class T, int Digits> struct hash_float_impl<T, 128, Digits> |
165 | { |
166 | static std::size_t fn( T v ) |
167 | { |
168 | std::uint64_t w[ 2 ]; |
169 | std::memcpy( dest: &w, src: &v, n: sizeof( v ) ); |
170 | |
171 | std::size_t seed = 0; |
172 | |
173 | #if defined(__FLOAT_WORD_ORDER__) && defined(__ORDER_BIG_ENDIAN__) && __FLOAT_WORD_ORDER__ == __ORDER_BIG_ENDIAN__ |
174 | |
175 | seed = hash_value( w[1] ) + hash_detail::hash_mix( seed ); |
176 | seed = hash_value( w[0] ) + hash_detail::hash_mix( seed ); |
177 | |
178 | #else |
179 | |
180 | seed = hash_value( v: w[0] ) + hash_detail::hash_mix( v: seed ); |
181 | seed = hash_value( v: w[1] ) + hash_detail::hash_mix( v: seed ); |
182 | |
183 | #endif |
184 | return seed; |
185 | } |
186 | }; |
187 | |
188 | } // namespace hash_detail |
189 | |
190 | template <typename T> |
191 | typename std::enable_if<std::is_floating_point<T>::value, std::size_t>::type |
192 | hash_value( T v ) |
193 | { |
194 | return boost::hash_detail::hash_float_impl<T>::fn( v + 0 ); |
195 | } |
196 | |
197 | // pointer types |
198 | |
199 | // `x + (x >> 3)` adjustment by Alberto Barbati and Dave Harris. |
200 | template <class T> std::size_t hash_value( T* const& v ) |
201 | { |
202 | std::uintptr_t x = reinterpret_cast<std::uintptr_t>( v ); |
203 | return boost::hash_value( v: x + (x >> 3) ); |
204 | } |
205 | |
206 | // array types |
207 | |
208 | template<class T, std::size_t N> |
209 | inline std::size_t hash_value( T const (&x)[ N ] ) |
210 | { |
211 | return boost::hash_range( x, x + N ); |
212 | } |
213 | |
214 | template<class T, std::size_t N> |
215 | inline std::size_t hash_value( T (&x)[ N ] ) |
216 | { |
217 | return boost::hash_range( x, x + N ); |
218 | } |
219 | |
220 | // complex |
221 | |
222 | template <class T> |
223 | std::size_t hash_value( std::complex<T> const& v ) |
224 | { |
225 | std::size_t re = boost::hash<T>()( v.real() ); |
226 | std::size_t im = boost::hash<T>()( v.imag() ); |
227 | |
228 | return re + hash_detail::hash_mix( v: im ); |
229 | } |
230 | |
231 | // pair |
232 | |
233 | template <class A, class B> |
234 | std::size_t hash_value( std::pair<A, B> const& v ) |
235 | { |
236 | std::size_t seed = 0; |
237 | |
238 | boost::hash_combine( seed, v.first ); |
239 | boost::hash_combine( seed, v.second ); |
240 | |
241 | return seed; |
242 | } |
243 | |
244 | // ranges (list, set, deque...) |
245 | |
246 | template <typename T> |
247 | typename std::enable_if<container_hash::is_range<T>::value && !container_hash::is_contiguous_range<T>::value && !container_hash::is_unordered_range<T>::value, std::size_t>::type |
248 | hash_value( T const& v ) |
249 | { |
250 | return boost::hash_range( v.begin(), v.end() ); |
251 | } |
252 | |
253 | // contiguous ranges (string, vector, array) |
254 | |
255 | template <typename T> |
256 | typename std::enable_if<container_hash::is_contiguous_range<T>::value, std::size_t>::type |
257 | hash_value( T const& v ) |
258 | { |
259 | return boost::hash_range( v.data(), v.data() + v.size() ); |
260 | } |
261 | |
262 | // unordered ranges (unordered_set, unordered_map) |
263 | |
264 | template <typename T> |
265 | typename std::enable_if<container_hash::is_unordered_range<T>::value, std::size_t>::type |
266 | hash_value( T const& v ) |
267 | { |
268 | return boost::hash_unordered_range( v.begin(), v.end() ); |
269 | } |
270 | |
271 | #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) && ( \ |
272 | ( defined(_MSVC_STL_VERSION) && _MSVC_STL_VERSION < 142 ) || \ |
273 | ( !defined(_MSVC_STL_VERSION) && defined(_CPPLIB_VER) && _CPPLIB_VER >= 520 ) ) |
274 | |
275 | // resolve ambiguity with unconstrained stdext::hash_value in <xhash> :-/ |
276 | |
277 | template<template<class...> class L, class... T> |
278 | typename std::enable_if<container_hash::is_range<L<T...>>::value && !container_hash::is_contiguous_range<L<T...>>::value && !container_hash::is_unordered_range<L<T...>>::value, std::size_t>::type |
279 | hash_value( L<T...> const& v ) |
280 | { |
281 | return boost::hash_range( v.begin(), v.end() ); |
282 | } |
283 | |
284 | // contiguous ranges (string, vector, array) |
285 | |
286 | template<template<class...> class L, class... T> |
287 | typename std::enable_if<container_hash::is_contiguous_range<L<T...>>::value, std::size_t>::type |
288 | hash_value( L<T...> const& v ) |
289 | { |
290 | return boost::hash_range( v.data(), v.data() + v.size() ); |
291 | } |
292 | |
293 | template<template<class, std::size_t> class L, class T, std::size_t N> |
294 | typename std::enable_if<container_hash::is_contiguous_range<L<T, N>>::value, std::size_t>::type |
295 | hash_value( L<T, N> const& v ) |
296 | { |
297 | return boost::hash_range( v.data(), v.data() + v.size() ); |
298 | } |
299 | |
300 | // unordered ranges (unordered_set, unordered_map) |
301 | |
302 | template<template<class...> class L, class... T> |
303 | typename std::enable_if<container_hash::is_unordered_range<L<T...>>::value, std::size_t>::type |
304 | hash_value( L<T...> const& v ) |
305 | { |
306 | return boost::hash_unordered_range( v.begin(), v.end() ); |
307 | } |
308 | |
309 | #endif |
310 | |
311 | // described classes |
312 | |
313 | #if defined(BOOST_DESCRIBE_CXX14) |
314 | |
315 | #if defined(_MSC_VER) && _MSC_VER == 1900 |
316 | # pragma warning(push) |
317 | # pragma warning(disable: 4100) // unreferenced formal parameter |
318 | #endif |
319 | |
320 | template <typename T> |
321 | typename std::enable_if<container_hash::is_described_class<T>::value, std::size_t>::type |
322 | hash_value( T const& v ) |
323 | { |
324 | static_assert( !std::is_union<T>::value, "described unions are not supported" ); |
325 | |
326 | std::size_t r = 0; |
327 | |
328 | using Bd = describe::describe_bases<T, describe::mod_any_access>; |
329 | |
330 | mp11::mp_for_each<Bd>([&](auto D){ |
331 | |
332 | using B = typename decltype(D)::type; |
333 | boost::hash_combine( r, (B const&)v ); |
334 | |
335 | }); |
336 | |
337 | using Md = describe::describe_members<T, describe::mod_any_access>; |
338 | |
339 | mp11::mp_for_each<Md>([&](auto D){ |
340 | |
341 | boost::hash_combine( r, v.*D.pointer ); |
342 | |
343 | }); |
344 | |
345 | return r; |
346 | } |
347 | |
348 | #if defined(_MSC_VER) && _MSC_VER == 1900 |
349 | # pragma warning(pop) |
350 | #endif |
351 | |
352 | #endif |
353 | |
354 | // std::unique_ptr, std::shared_ptr |
355 | |
356 | #if !defined(BOOST_NO_CXX11_SMART_PTR) |
357 | |
358 | template <typename T> |
359 | std::size_t hash_value( std::shared_ptr<T> const& x ) |
360 | { |
361 | return boost::hash_value( x.get() ); |
362 | } |
363 | |
364 | template <typename T, typename Deleter> |
365 | std::size_t hash_value( std::unique_ptr<T, Deleter> const& x ) |
366 | { |
367 | return boost::hash_value( x.get() ); |
368 | } |
369 | |
370 | #endif |
371 | |
372 | // std::type_index |
373 | |
374 | #if !defined(BOOST_NO_CXX11_HDR_TYPEINDEX) |
375 | |
376 | inline std::size_t hash_value( std::type_index const& v ) |
377 | { |
378 | return v.hash_code(); |
379 | } |
380 | |
381 | #endif |
382 | |
383 | // std::error_code, std::error_condition |
384 | |
385 | #if !defined(BOOST_NO_CXX11_HDR_SYSTEM_ERROR) |
386 | |
387 | inline std::size_t hash_value( std::error_code const& v ) |
388 | { |
389 | std::size_t seed = 0; |
390 | |
391 | boost::hash_combine( seed, v: v.value() ); |
392 | boost::hash_combine( seed, v: &v.category() ); |
393 | |
394 | return seed; |
395 | } |
396 | |
397 | inline std::size_t hash_value( std::error_condition const& v ) |
398 | { |
399 | std::size_t seed = 0; |
400 | |
401 | boost::hash_combine( seed, v: v.value() ); |
402 | boost::hash_combine( seed, v: &v.category() ); |
403 | |
404 | return seed; |
405 | } |
406 | |
407 | #endif |
408 | |
409 | // std::nullptr_t |
410 | |
411 | #if !defined(BOOST_NO_CXX11_NULLPTR) |
412 | |
413 | template <typename T> |
414 | typename std::enable_if<std::is_same<T, std::nullptr_t>::value, std::size_t>::type |
415 | hash_value( T const& /*v*/ ) |
416 | { |
417 | return boost::hash_value( v: static_cast<void*>( nullptr ) ); |
418 | } |
419 | |
420 | #endif |
421 | |
422 | // std::optional |
423 | |
424 | #if !defined(BOOST_NO_CXX17_HDR_OPTIONAL) |
425 | |
426 | template <typename T> |
427 | std::size_t hash_value( std::optional<T> const& v ) |
428 | { |
429 | if( !v ) |
430 | { |
431 | // Arbitrary value for empty optional. |
432 | return 0x12345678; |
433 | } |
434 | else |
435 | { |
436 | return boost::hash<T>()(*v); |
437 | } |
438 | } |
439 | |
440 | #endif |
441 | |
442 | // std::variant |
443 | |
444 | #if !defined(BOOST_NO_CXX17_HDR_VARIANT) |
445 | |
446 | inline std::size_t hash_value( std::monostate ) |
447 | { |
448 | return 0x87654321; |
449 | } |
450 | |
451 | template <typename... Types> |
452 | std::size_t hash_value( std::variant<Types...> const& v ) |
453 | { |
454 | std::size_t seed = 0; |
455 | |
456 | hash_combine( seed, v.index() ); |
457 | std::visit( [&seed](auto&& x) { hash_combine(seed, x); }, v ); |
458 | |
459 | return seed; |
460 | } |
461 | |
462 | #endif |
463 | |
464 | // |
465 | // boost::hash_combine |
466 | // |
467 | |
468 | template <class T> |
469 | inline void hash_combine( std::size_t& seed, T const& v ) |
470 | { |
471 | seed = boost::hash_detail::hash_mix( v: seed + 0x9e3779b9 + boost::hash<T>()( v ) ); |
472 | } |
473 | |
474 | // |
475 | // boost::hash_range |
476 | // |
477 | |
478 | template <class It> |
479 | inline void hash_range( std::size_t& seed, It first, It last ) |
480 | { |
481 | seed = hash_detail::hash_range( seed, first, last ); |
482 | } |
483 | |
484 | template <class It> |
485 | inline std::size_t hash_range( It first, It last ) |
486 | { |
487 | std::size_t seed = 0; |
488 | |
489 | hash_range( seed, first, last ); |
490 | |
491 | return seed; |
492 | } |
493 | |
494 | // |
495 | // boost::hash_unordered_range |
496 | // |
497 | |
498 | template <class It> |
499 | inline void hash_unordered_range( std::size_t& seed, It first, It last ) |
500 | { |
501 | std::size_t r = 0; |
502 | std::size_t const s2( seed ); |
503 | |
504 | for( ; first != last; ++first ) |
505 | { |
506 | std::size_t s3( s2 ); |
507 | |
508 | hash_combine<typename std::iterator_traits<It>::value_type>( s3, *first ); |
509 | |
510 | r += s3; |
511 | } |
512 | |
513 | seed += r; |
514 | } |
515 | |
516 | template <class It> |
517 | inline std::size_t hash_unordered_range( It first, It last ) |
518 | { |
519 | std::size_t seed = 0; |
520 | |
521 | hash_unordered_range( seed, first, last ); |
522 | |
523 | return seed; |
524 | } |
525 | |
526 | // |
527 | // boost::hash |
528 | // |
529 | |
530 | template <class T> struct hash |
531 | { |
532 | typedef T argument_type; |
533 | typedef std::size_t result_type; |
534 | |
535 | std::size_t operator()( T const& val ) const |
536 | { |
537 | return hash_value( val ); |
538 | } |
539 | }; |
540 | |
541 | #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) && ( \ |
542 | ( defined(_MSVC_STL_VERSION) && _MSVC_STL_VERSION < 142 ) || \ |
543 | ( !defined(_MSVC_STL_VERSION) && defined(_CPPLIB_VER) && _CPPLIB_VER >= 520 ) ) |
544 | |
545 | // Dinkumware has stdext::hash_value for basic_string in <xhash> :-/ |
546 | |
547 | template<class E, class T, class A> struct hash< std::basic_string<E, T, A> > |
548 | { |
549 | typedef std::basic_string<E, T, A> argument_type; |
550 | typedef std::size_t result_type; |
551 | |
552 | std::size_t operator()( std::basic_string<E, T, A> const& val ) const |
553 | { |
554 | return boost::hash_value( val ); |
555 | } |
556 | }; |
557 | |
558 | #endif |
559 | |
560 | // boost::unordered::hash_is_avalanching |
561 | |
562 | namespace unordered |
563 | { |
564 | template<class T> struct hash_is_avalanching; |
565 | template<class Ch> struct hash_is_avalanching< boost::hash< std::basic_string<Ch> > >: std::is_integral<Ch> {}; |
566 | |
567 | #if !defined(BOOST_NO_CXX17_HDR_STRING_VIEW) |
568 | |
569 | template<class Ch> struct hash_is_avalanching< boost::hash< std::basic_string_view<Ch> > >: std::is_integral<Ch> {}; |
570 | |
571 | #endif |
572 | } // namespace unordered |
573 | |
574 | } // namespace boost |
575 | |
576 | #endif // #ifndef BOOST_FUNCTIONAL_HASH_HASH_HPP |
577 | |