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