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
63namespace 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

source code of boost/libs/container_hash/include/boost/container_hash/hash.hpp