1/////////////////////////////////////////////////////////////////////////////
2//
3// Copyright 2005-2014 Daniel James.
4// Copyright 2021, 2022 Peter Dimov.
5// Copyright 2024 Ion Gaztaņaga.
6// Distributed under the Boost Software License, Version 1.0.
7// https://www.boost.org/LICENSE_1_0.txt
8//
9// Based on Peter Dimov's proposal
10// http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1756.pdf
11// issue 6.18.
12//
13// The original C++11 implementation was done by Peter Dimov
14// The C++03 porting was done by Ion Gaztanaga.
15//
16// The goal of this header is to avoid Intrusive's hard dependency on ContainerHash,
17// which adds additional dependencies and the minimum supported C++ standard can
18// differ between both libraries. However, a compatibility protocol is used so that
19// users compatible with ContainerHash are also compatible with Intrusive:
20//
21// - If users define `hash_value` (as required by boost::hash) for their classes
22// are automatically compatible with Intrusive unordered containers.
23//
24// - If users include boost/container_hash/hash.hpp in their headers, Intrusive
25// unordered containers will take advantage of boost::hash compatibility hash functions
26// (such as hashing functions for range-compatible types, standard containers, etc.)
27//
28// See http://www.boost.org/libs/intrusive for documentation.
29//
30/////////////////////////////////////////////////////////////////////////////
31
32#ifndef BOOST_INTRUSIVE_HASH_HASH_HPP
33#define BOOST_INTRUSIVE_HASH_HASH_HPP
34
35#include <boost/intrusive/detail/config_begin.hpp>
36#include <boost/intrusive/detail/workaround.hpp>
37#include <boost/intrusive/detail/hash_integral.hpp>
38#include <boost/intrusive/detail/hash_mix.hpp>
39#include <boost/intrusive/detail/hash_combine.hpp>
40#include <boost/cstdint.hpp>
41#include <climits>
42#include <cstring>
43#include <cfloat>
44#include <boost/intrusive/detail/mpl.hpp>
45
46namespace boost {
47
48template<class T>
49struct hash;
50
51} //namespace boost
52
53//Fallback function to call boost::hash if scalar type and ADL fail.
54//The user must include boost/container_hash/hash.hpp when to make this call work,
55//this allows boost::intrusive to be compatible with boost::hash without
56//a mandatory physical (header inclusion) dependency
57namespace boost_intrusive_adl
58{
59 template<class T>
60 inline std::size_t hash_value(const T& v)
61 {
62 return boost::hash<T>()(v);
63 }
64}
65
66namespace boost {
67namespace intrusive {
68namespace detail {
69
70//ADL-based lookup hash call
71template <class T>
72inline typename detail::disable_if_c<detail::is_scalar<T>::value, std::size_t>::type
73 hash_value_dispatch(const T& v)
74{
75 //Try ADL lookup, if it fails, boost_intrusive_adl::hash_value will retry with boost::hash
76 using boost_intrusive_adl::hash_value;
77 return hash_value(v);
78}
79
80template <typename T>
81typename enable_if_c<is_enum<T>::value, std::size_t>::type
82 hash_value( T v )
83{
84 return static_cast<std::size_t>( v );
85}
86
87////////////////////////////////////////////////////////////
88//
89// floating point types
90//
91////////////////////////////////////////////////////////////
92
93template<class T, std::size_t Bits = sizeof(T) * CHAR_BIT>
94struct hash_float_impl;
95
96// float
97template<class T> struct hash_float_impl<T, 32>
98{
99 static std::size_t fn( T v )
100 {
101 boost::uint32_t w;
102 std::memcpy( dest: &w, src: &v, n: sizeof( v ) );
103
104 return w;
105 }
106};
107
108// double
109template<class T> struct hash_float_impl<T, 64>
110{
111 static std::size_t fn( T v )
112 {
113 boost::uint64_t w;
114 std::memcpy( dest: &w, src: &v, n: sizeof( v ) );
115
116 return hash_value( v: w );
117 }
118};
119
120// 80 bit long double in 12 bytes
121template<class T> struct hash_float_impl<T, 96>
122{
123 static std::size_t fn( T v )
124 {
125 boost::uint64_t w[ 2 ] = {};
126 std::memcpy( dest: &w, src: &v, n: 80 / CHAR_BIT );
127
128 std::size_t seed = 0;
129
130 seed = hash_value( v: w[0] ) + (hash_mix)( v: seed );
131 seed = hash_value( v: w[1] ) + (hash_mix)( v: seed );
132
133 return seed;
134 }
135};
136
137#if (LDBL_MAX_10_EXP == 4932)
138
139// 80 bit long double in 16 bytes
140template<class T> struct hash_float_impl<T, 128>
141{
142 static std::size_t fn( T v )
143 {
144 boost::uint64_t w[ 2 ] = {};
145 std::memcpy( dest: &w, src: &v, n: 80 / CHAR_BIT );
146
147 std::size_t seed = 0;
148
149 seed = hash_value( v: w[0] ) + (hash_mix)( v: seed );
150 seed = hash_value( v: w[1] ) + (hash_mix)( v: seed );
151
152 return seed;
153 }
154};
155
156#elif (LDBL_MAX_10_EXP > 4932)
157// 128 bit long double
158template<class T> struct hash_float_impl<T, 128>
159{
160 static std::size_t fn( T v )
161 {
162 boost::uint64_t w[ 2 ];
163 std::memcpy( &w, &v, sizeof( v ) );
164
165 std::size_t seed = 0;
166
167 #if defined(__FLOAT_WORD_ORDER__) && defined(__ORDER_BIG_ENDIAN__) && __FLOAT_WORD_ORDER__ == __ORDER_BIG_ENDIAN__
168
169 seed = hash_value( w[1] ) + (hash_mix)( seed );
170 seed = hash_value( w[0] ) + (hash_mix)( seed );
171
172 #else
173
174 seed = hash_value( w[0] ) + (hash_mix)( seed );
175 seed = hash_value( w[1] ) + (hash_mix)( seed );
176
177 #endif
178 return seed;
179 }
180};
181#endif //#if (LDBL_MAX_10_EXP == 4932)
182
183template <typename T>
184typename enable_if_c<is_floating_point<T>::value, std::size_t>::type
185 hash_value( T v )
186{
187 return boost::intrusive::detail::hash_float_impl<T>::fn( v + 0 );
188}
189
190////////////////////////////////////////////////////////////
191//
192// pointer types
193//
194////////////////////////////////////////////////////////////
195// `x + (x >> 3)` adjustment by Alberto Barbati and Dave Harris.
196template <class T> std::size_t hash_value( T* const& v )
197{
198 std::size_t x = reinterpret_cast<std::size_t>( v );
199 return hash_value( v: x + (x >> 3) );
200}
201
202////////////////////////////////////////////////////////////
203//
204// std::nullptr_t
205//
206////////////////////////////////////////////////////////////
207#if !defined(BOOST_NO_CXX11_NULLPTR)
208template <typename T>
209typename enable_if_c<is_same<T, std::nullptr_t>::value, std::size_t>::type
210 hash_value( T const &)
211{
212 return (hash_value)( v: static_cast<void*>( nullptr ) );
213}
214 #endif
215
216////////////////////////////////////////////////////////////
217//
218// Array types
219//
220////////////////////////////////////////////////////////////
221
222//Forward declaration or internal hash functor, for array iteration
223template<class T>
224struct internal_hash_functor;
225
226template<class T, std::size_t N>
227inline std::size_t hash_value_dispatch( T const (&x)[ N ] )
228{
229 std::size_t seed = 0;
230 for(std::size_t i = 0; i != N; ++i){
231 hash_combine_size_t(seed, internal_hash_functor<T>()(x[i]));
232 }
233 return seed;
234}
235
236template<class T, std::size_t N>
237inline std::size_t hash_value_dispatch( T (&x)[ N ] )
238{
239 std::size_t seed = 0;
240 for (std::size_t i = 0; i != N; ++i) {
241 hash_combine_size_t(seed, internal_hash_functor<T>()(x[i]));
242 }
243 return seed;
244}
245
246////////////////////////////////////////////////////////////
247//
248// Scalar types, calls proper overload
249//
250////////////////////////////////////////////////////////////
251template <class T>
252inline typename detail::enable_if_c<detail::is_scalar<T>::value, std::size_t>::type
253 hash_value_dispatch(const T &v)
254{
255 return boost::intrusive::detail::hash_value(v);
256}
257
258//Internal "anonymous" hash functor, first selects between "built-in" scalar/array types
259//and ADL-based lookup
260
261template<class T>
262struct internal_hash_functor
263{
264 inline std::size_t operator()(T const& val) const
265 {
266 return ::boost::intrusive::detail::hash_value_dispatch(val);
267 }
268};
269
270} // namespace detail {
271} // namespace intrusive {
272} // namespace boost
273
274#include <boost/intrusive/detail/config_end.hpp>
275
276#endif // #ifndef BOOST_INTRUSIVE_HASH_HASH_HPP
277
278

source code of boost/libs/intrusive/include/boost/intrusive/detail/hash.hpp