1 | |
2 | // Copyright 2005-2014 Daniel James. |
3 | // Distributed under the Boost Software License, Version 1.0. (See accompanying |
4 | // file LICENSE_1_0.txt or copy at http://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 | // This also contains public domain code from MurmurHash. From the |
11 | // MurmurHash header: |
12 | |
13 | // MurmurHash3 was written by Austin Appleby, and is placed in the public |
14 | // domain. The author hereby disclaims copyright to this source code. |
15 | |
16 | #if !defined(BOOST_FUNCTIONAL_HASH_HASH_HPP) |
17 | #define BOOST_FUNCTIONAL_HASH_HASH_HPP |
18 | |
19 | #include <boost/functional/hash/hash_fwd.hpp> |
20 | #include <functional> |
21 | #include <boost/functional/hash/detail/hash_float.hpp> |
22 | #include <string> |
23 | #include <boost/limits.hpp> |
24 | #include <boost/type_traits/is_enum.hpp> |
25 | #include <boost/type_traits/is_integral.hpp> |
26 | #include <boost/utility/enable_if.hpp> |
27 | #include <boost/cstdint.hpp> |
28 | |
29 | #if defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) |
30 | #include <boost/type_traits/is_pointer.hpp> |
31 | #endif |
32 | |
33 | #if !defined(BOOST_NO_CXX11_HDR_TYPEINDEX) |
34 | #include <typeindex> |
35 | #endif |
36 | |
37 | #if defined(BOOST_MSVC) |
38 | #pragma warning(push) |
39 | |
40 | #if BOOST_MSVC >= 1400 |
41 | #pragma warning(disable:6295) // Ill-defined for-loop : 'unsigned int' values |
42 | // are always of range '0' to '4294967295'. |
43 | // Loop executes infinitely. |
44 | #endif |
45 | |
46 | #endif |
47 | |
48 | #if BOOST_WORKAROUND(__GNUC__, < 3) \ |
49 | && !defined(__SGI_STL_PORT) && !defined(_STLPORT_VERSION) |
50 | #define BOOST_HASH_CHAR_TRAITS string_char_traits |
51 | #else |
52 | #define BOOST_HASH_CHAR_TRAITS char_traits |
53 | #endif |
54 | |
55 | #if defined(_MSC_VER) |
56 | # define BOOST_FUNCTIONAL_HASH_ROTL32(x, r) _rotl(x,r) |
57 | #else |
58 | # define BOOST_FUNCTIONAL_HASH_ROTL32(x, r) (x << r) | (x >> (32 - r)) |
59 | #endif |
60 | |
61 | namespace boost |
62 | { |
63 | namespace hash_detail |
64 | { |
65 | struct enable_hash_value { typedef std::size_t type; }; |
66 | |
67 | template <typename T> struct basic_numbers {}; |
68 | template <typename T> struct long_numbers; |
69 | template <typename T> struct ulong_numbers; |
70 | template <typename T> struct float_numbers {}; |
71 | |
72 | template <> struct basic_numbers<bool> : |
73 | boost::hash_detail::enable_hash_value {}; |
74 | template <> struct basic_numbers<char> : |
75 | boost::hash_detail::enable_hash_value {}; |
76 | template <> struct basic_numbers<unsigned char> : |
77 | boost::hash_detail::enable_hash_value {}; |
78 | template <> struct basic_numbers<signed char> : |
79 | boost::hash_detail::enable_hash_value {}; |
80 | template <> struct basic_numbers<short> : |
81 | boost::hash_detail::enable_hash_value {}; |
82 | template <> struct basic_numbers<unsigned short> : |
83 | boost::hash_detail::enable_hash_value {}; |
84 | template <> struct basic_numbers<int> : |
85 | boost::hash_detail::enable_hash_value {}; |
86 | template <> struct basic_numbers<unsigned int> : |
87 | boost::hash_detail::enable_hash_value {}; |
88 | template <> struct basic_numbers<long> : |
89 | boost::hash_detail::enable_hash_value {}; |
90 | template <> struct basic_numbers<unsigned long> : |
91 | boost::hash_detail::enable_hash_value {}; |
92 | |
93 | #if !defined(BOOST_NO_INTRINSIC_WCHAR_T) |
94 | template <> struct basic_numbers<wchar_t> : |
95 | boost::hash_detail::enable_hash_value {}; |
96 | #endif |
97 | |
98 | // long_numbers is defined like this to allow for separate |
99 | // specialization for long_long and int128_type, in case |
100 | // they conflict. |
101 | template <typename T> struct long_numbers2 {}; |
102 | template <typename T> struct ulong_numbers2 {}; |
103 | template <typename T> struct long_numbers : long_numbers2<T> {}; |
104 | template <typename T> struct ulong_numbers : ulong_numbers2<T> {}; |
105 | |
106 | #if !defined(BOOST_NO_LONG_LONG) |
107 | template <> struct long_numbers<boost::long_long_type> : |
108 | boost::hash_detail::enable_hash_value {}; |
109 | template <> struct ulong_numbers<boost::ulong_long_type> : |
110 | boost::hash_detail::enable_hash_value {}; |
111 | #endif |
112 | |
113 | #if defined(BOOST_HAS_INT128) |
114 | template <> struct long_numbers2<boost::int128_type> : |
115 | boost::hash_detail::enable_hash_value {}; |
116 | template <> struct ulong_numbers2<boost::uint128_type> : |
117 | boost::hash_detail::enable_hash_value {}; |
118 | #endif |
119 | |
120 | template <> struct float_numbers<float> : |
121 | boost::hash_detail::enable_hash_value {}; |
122 | template <> struct float_numbers<double> : |
123 | boost::hash_detail::enable_hash_value {}; |
124 | template <> struct float_numbers<long double> : |
125 | boost::hash_detail::enable_hash_value {}; |
126 | } |
127 | |
128 | template <typename T> |
129 | typename boost::hash_detail::basic_numbers<T>::type hash_value(T); |
130 | template <typename T> |
131 | typename boost::hash_detail::long_numbers<T>::type hash_value(T); |
132 | template <typename T> |
133 | typename boost::hash_detail::ulong_numbers<T>::type hash_value(T); |
134 | |
135 | template <typename T> |
136 | typename boost::enable_if<boost::is_enum<T>, std::size_t>::type |
137 | hash_value(T); |
138 | |
139 | #if !BOOST_WORKAROUND(__DMC__, <= 0x848) |
140 | template <class T> std::size_t hash_value(T* const&); |
141 | #else |
142 | template <class T> std::size_t hash_value(T*); |
143 | #endif |
144 | |
145 | #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) |
146 | template< class T, unsigned N > |
147 | std::size_t hash_value(const T (&x)[N]); |
148 | |
149 | template< class T, unsigned N > |
150 | std::size_t hash_value(T (&x)[N]); |
151 | #endif |
152 | |
153 | template <class Ch, class A> |
154 | std::size_t hash_value( |
155 | std::basic_string<Ch, std::BOOST_HASH_CHAR_TRAITS<Ch>, A> const&); |
156 | |
157 | template <typename T> |
158 | typename boost::hash_detail::float_numbers<T>::type hash_value(T); |
159 | |
160 | #if !defined(BOOST_NO_CXX11_HDR_TYPEINDEX) |
161 | std::size_t hash_value(std::type_index); |
162 | #endif |
163 | |
164 | // Implementation |
165 | |
166 | namespace hash_detail |
167 | { |
168 | template <class T> |
169 | inline std::size_t hash_value_signed(T val) |
170 | { |
171 | const int size_t_bits = std::numeric_limits<std::size_t>::digits; |
172 | // ceiling(std::numeric_limits<T>::digits / size_t_bits) - 1 |
173 | const int length = (std::numeric_limits<T>::digits - 1) |
174 | / size_t_bits; |
175 | |
176 | std::size_t seed = 0; |
177 | T positive = val < 0 ? -1 - val : val; |
178 | |
179 | // Hopefully, this loop can be unrolled. |
180 | for(unsigned int i = length * size_t_bits; i > 0; i -= size_t_bits) |
181 | { |
182 | seed ^= (std::size_t) (positive >> i) + (seed<<6) + (seed>>2); |
183 | } |
184 | seed ^= (std::size_t) val + (seed<<6) + (seed>>2); |
185 | |
186 | return seed; |
187 | } |
188 | |
189 | template <class T> |
190 | inline std::size_t hash_value_unsigned(T val) |
191 | { |
192 | const int size_t_bits = std::numeric_limits<std::size_t>::digits; |
193 | // ceiling(std::numeric_limits<T>::digits / size_t_bits) - 1 |
194 | const int length = (std::numeric_limits<T>::digits - 1) |
195 | / size_t_bits; |
196 | |
197 | std::size_t seed = 0; |
198 | |
199 | // Hopefully, this loop can be unrolled. |
200 | for(unsigned int i = length * size_t_bits; i > 0; i -= size_t_bits) |
201 | { |
202 | seed ^= (std::size_t) (val >> i) + (seed<<6) + (seed>>2); |
203 | } |
204 | seed ^= (std::size_t) val + (seed<<6) + (seed>>2); |
205 | |
206 | return seed; |
207 | } |
208 | |
209 | template <typename SizeT> |
210 | inline void hash_combine_impl(SizeT& seed, SizeT value) |
211 | { |
212 | seed ^= value + 0x9e3779b9 + (seed<<6) + (seed>>2); |
213 | } |
214 | |
215 | template <typename SizeT> |
216 | inline void hash_combine_impl(boost::uint32_t& h1, |
217 | boost::uint32_t k1) |
218 | { |
219 | const uint32_t c1 = 0xcc9e2d51; |
220 | const uint32_t c2 = 0x1b873593; |
221 | |
222 | k1 *= c1; |
223 | k1 = BOOST_FUNCTIONAL_HASH_ROTL32(k1,15); |
224 | k1 *= c2; |
225 | |
226 | h1 ^= k1; |
227 | h1 = BOOST_FUNCTIONAL_HASH_ROTL32(h1,13); |
228 | h1 = h1*5+0xe6546b64; |
229 | } |
230 | |
231 | |
232 | // Don't define 64-bit hash combine on platforms with 64 bit integers, |
233 | // and also not for 32-bit gcc as it warns about the 64-bit constant. |
234 | #if !defined(BOOST_NO_INT64_T) && \ |
235 | !(defined(__GNUC__) && ULONG_MAX == 0xffffffff) |
236 | |
237 | template <typename SizeT> |
238 | inline void hash_combine_impl(boost::uint64_t& h, |
239 | boost::uint64_t k) |
240 | { |
241 | const uint64_t m = UINT64_C(0xc6a4a7935bd1e995); |
242 | const int r = 47; |
243 | |
244 | k *= m; |
245 | k ^= k >> r; |
246 | k *= m; |
247 | |
248 | h ^= k; |
249 | h *= m; |
250 | } |
251 | |
252 | #endif // BOOST_NO_INT64_T |
253 | } |
254 | |
255 | template <typename T> |
256 | typename boost::hash_detail::basic_numbers<T>::type hash_value(T v) |
257 | { |
258 | return static_cast<std::size_t>(v); |
259 | } |
260 | |
261 | template <typename T> |
262 | typename boost::hash_detail::long_numbers<T>::type hash_value(T v) |
263 | { |
264 | return hash_detail::hash_value_signed(v); |
265 | } |
266 | |
267 | template <typename T> |
268 | typename boost::hash_detail::ulong_numbers<T>::type hash_value(T v) |
269 | { |
270 | return hash_detail::hash_value_unsigned(v); |
271 | } |
272 | |
273 | template <typename T> |
274 | typename boost::enable_if<boost::is_enum<T>, std::size_t>::type |
275 | hash_value(T v) |
276 | { |
277 | return static_cast<std::size_t>(v); |
278 | } |
279 | |
280 | // Implementation by Alberto Barbati and Dave Harris. |
281 | #if !BOOST_WORKAROUND(__DMC__, <= 0x848) |
282 | template <class T> std::size_t hash_value(T* const& v) |
283 | #else |
284 | template <class T> std::size_t hash_value(T* v) |
285 | #endif |
286 | { |
287 | #if defined(__VMS) && __INITIAL_POINTER_SIZE == 64 |
288 | // for some reason ptrdiff_t on OpenVMS compiler with |
289 | // 64 bit is not 64 bit !!! |
290 | std::size_t x = static_cast<std::size_t>( |
291 | reinterpret_cast<long long int>(v)); |
292 | #else |
293 | std::size_t x = static_cast<std::size_t>( |
294 | reinterpret_cast<std::ptrdiff_t>(v)); |
295 | #endif |
296 | return x + (x >> 3); |
297 | } |
298 | |
299 | #if defined(BOOST_MSVC) |
300 | #pragma warning(push) |
301 | #if BOOST_MSVC <= 1400 |
302 | #pragma warning(disable:4267) // 'argument' : conversion from 'size_t' to |
303 | // 'unsigned int', possible loss of data |
304 | // A misguided attempt to detect 64-bit |
305 | // incompatability. |
306 | #endif |
307 | #endif |
308 | |
309 | template <class T> |
310 | inline void hash_combine(std::size_t& seed, T const& v) |
311 | { |
312 | boost::hash<T> hasher; |
313 | return boost::hash_detail::hash_combine_impl(seed, hasher(v)); |
314 | } |
315 | |
316 | #if defined(BOOST_MSVC) |
317 | #pragma warning(pop) |
318 | #endif |
319 | |
320 | template <class It> |
321 | inline std::size_t hash_range(It first, It last) |
322 | { |
323 | std::size_t seed = 0; |
324 | |
325 | for(; first != last; ++first) |
326 | { |
327 | hash_combine(seed, *first); |
328 | } |
329 | |
330 | return seed; |
331 | } |
332 | |
333 | template <class It> |
334 | inline void hash_range(std::size_t& seed, It first, It last) |
335 | { |
336 | for(; first != last; ++first) |
337 | { |
338 | hash_combine(seed, *first); |
339 | } |
340 | } |
341 | |
342 | #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x551)) |
343 | template <class T> |
344 | inline std::size_t hash_range(T* first, T* last) |
345 | { |
346 | std::size_t seed = 0; |
347 | |
348 | for(; first != last; ++first) |
349 | { |
350 | boost::hash<T> hasher; |
351 | seed ^= hasher(*first) + 0x9e3779b9 + (seed<<6) + (seed>>2); |
352 | } |
353 | |
354 | return seed; |
355 | } |
356 | |
357 | template <class T> |
358 | inline void hash_range(std::size_t& seed, T* first, T* last) |
359 | { |
360 | for(; first != last; ++first) |
361 | { |
362 | boost::hash<T> hasher; |
363 | seed ^= hasher(*first) + 0x9e3779b9 + (seed<<6) + (seed>>2); |
364 | } |
365 | } |
366 | #endif |
367 | |
368 | #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) |
369 | template< class T, unsigned N > |
370 | inline std::size_t hash_value(const T (&x)[N]) |
371 | { |
372 | return hash_range(x, x + N); |
373 | } |
374 | |
375 | template< class T, unsigned N > |
376 | inline std::size_t hash_value(T (&x)[N]) |
377 | { |
378 | return hash_range(x, x + N); |
379 | } |
380 | #endif |
381 | |
382 | template <class Ch, class A> |
383 | inline std::size_t hash_value( |
384 | std::basic_string<Ch, std::BOOST_HASH_CHAR_TRAITS<Ch>, A> const& v) |
385 | { |
386 | return hash_range(v.begin(), v.end()); |
387 | } |
388 | |
389 | template <typename T> |
390 | typename boost::hash_detail::float_numbers<T>::type hash_value(T v) |
391 | { |
392 | return boost::hash_detail::float_hash_value(v); |
393 | } |
394 | |
395 | #if !defined(BOOST_NO_CXX11_HDR_TYPEINDEX) |
396 | inline std::size_t hash_value(std::type_index v) |
397 | { |
398 | return v.hash_code(); |
399 | } |
400 | #endif |
401 | |
402 | // |
403 | // boost::hash |
404 | // |
405 | |
406 | // Define the specializations required by the standard. The general purpose |
407 | // boost::hash is defined later in extensions.hpp if |
408 | // BOOST_HASH_NO_EXTENSIONS is not defined. |
409 | |
410 | // BOOST_HASH_SPECIALIZE - define a specialization for a type which is |
411 | // passed by copy. |
412 | // |
413 | // BOOST_HASH_SPECIALIZE_REF - define a specialization for a type which is |
414 | // passed by const reference. |
415 | // |
416 | // These are undefined later. |
417 | |
418 | #define BOOST_HASH_SPECIALIZE(type) \ |
419 | template <> struct hash<type> \ |
420 | : public std::unary_function<type, std::size_t> \ |
421 | { \ |
422 | std::size_t operator()(type v) const \ |
423 | { \ |
424 | return boost::hash_value(v); \ |
425 | } \ |
426 | }; |
427 | |
428 | #define BOOST_HASH_SPECIALIZE_REF(type) \ |
429 | template <> struct hash<type> \ |
430 | : public std::unary_function<type, std::size_t> \ |
431 | { \ |
432 | std::size_t operator()(type const& v) const \ |
433 | { \ |
434 | return boost::hash_value(v); \ |
435 | } \ |
436 | }; |
437 | |
438 | BOOST_HASH_SPECIALIZE(bool) |
439 | BOOST_HASH_SPECIALIZE(char) |
440 | BOOST_HASH_SPECIALIZE(signed char) |
441 | BOOST_HASH_SPECIALIZE(unsigned char) |
442 | #if !defined(BOOST_NO_INTRINSIC_WCHAR_T) |
443 | BOOST_HASH_SPECIALIZE(wchar_t) |
444 | #endif |
445 | BOOST_HASH_SPECIALIZE(short) |
446 | BOOST_HASH_SPECIALIZE(unsigned short) |
447 | BOOST_HASH_SPECIALIZE(int) |
448 | BOOST_HASH_SPECIALIZE(unsigned int) |
449 | BOOST_HASH_SPECIALIZE(long) |
450 | BOOST_HASH_SPECIALIZE(unsigned long) |
451 | |
452 | BOOST_HASH_SPECIALIZE(float) |
453 | BOOST_HASH_SPECIALIZE(double) |
454 | BOOST_HASH_SPECIALIZE(long double) |
455 | |
456 | BOOST_HASH_SPECIALIZE_REF(std::string) |
457 | #if !defined(BOOST_NO_STD_WSTRING) |
458 | BOOST_HASH_SPECIALIZE_REF(std::wstring) |
459 | #endif |
460 | |
461 | #if !defined(BOOST_NO_LONG_LONG) |
462 | BOOST_HASH_SPECIALIZE(boost::long_long_type) |
463 | BOOST_HASH_SPECIALIZE(boost::ulong_long_type) |
464 | #endif |
465 | |
466 | #if defined(BOOST_HAS_INT128) |
467 | BOOST_HASH_SPECIALIZE(boost::int128_type) |
468 | BOOST_HASH_SPECIALIZE(boost::uint128_type) |
469 | #endif |
470 | |
471 | #if !defined(BOOST_NO_CXX11_HDR_TYPEINDEX) |
472 | BOOST_HASH_SPECIALIZE(std::type_index) |
473 | #endif |
474 | |
475 | #undef BOOST_HASH_SPECIALIZE |
476 | #undef BOOST_HASH_SPECIALIZE_REF |
477 | |
478 | // Specializing boost::hash for pointers. |
479 | |
480 | #if !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) |
481 | |
482 | template <class T> |
483 | struct hash<T*> |
484 | : public std::unary_function<T*, std::size_t> |
485 | { |
486 | std::size_t operator()(T* v) const |
487 | { |
488 | #if !BOOST_WORKAROUND(__SUNPRO_CC, <= 0x590) |
489 | return boost::hash_value(v); |
490 | #else |
491 | std::size_t x = static_cast<std::size_t>( |
492 | reinterpret_cast<std::ptrdiff_t>(v)); |
493 | |
494 | return x + (x >> 3); |
495 | #endif |
496 | } |
497 | }; |
498 | |
499 | #else |
500 | |
501 | // For compilers without partial specialization, we define a |
502 | // boost::hash for all remaining types. But hash_impl is only defined |
503 | // for pointers in 'extensions.hpp' - so when BOOST_HASH_NO_EXTENSIONS |
504 | // is defined there will still be a compile error for types not supported |
505 | // in the standard. |
506 | |
507 | namespace hash_detail |
508 | { |
509 | template <bool IsPointer> |
510 | struct hash_impl; |
511 | |
512 | template <> |
513 | struct hash_impl<true> |
514 | { |
515 | template <class T> |
516 | struct inner |
517 | : public std::unary_function<T, std::size_t> |
518 | { |
519 | std::size_t operator()(T val) const |
520 | { |
521 | #if !BOOST_WORKAROUND(__SUNPRO_CC, <= 590) |
522 | return boost::hash_value(val); |
523 | #else |
524 | std::size_t x = static_cast<std::size_t>( |
525 | reinterpret_cast<std::ptrdiff_t>(val)); |
526 | |
527 | return x + (x >> 3); |
528 | #endif |
529 | } |
530 | }; |
531 | }; |
532 | } |
533 | |
534 | template <class T> struct hash |
535 | : public boost::hash_detail::hash_impl<boost::is_pointer<T>::value> |
536 | ::BOOST_NESTED_TEMPLATE inner<T> |
537 | { |
538 | }; |
539 | |
540 | #endif |
541 | } |
542 | |
543 | #undef BOOST_HASH_CHAR_TRAITS |
544 | #undef BOOST_FUNCTIONAL_HASH_ROTL32 |
545 | |
546 | #if defined(BOOST_MSVC) |
547 | #pragma warning(pop) |
548 | #endif |
549 | |
550 | #endif // BOOST_FUNCTIONAL_HASH_HASH_HPP |
551 | |
552 | // Include this outside of the include guards in case the file is included |
553 | // twice - once with BOOST_HASH_NO_EXTENSIONS defined, and then with it |
554 | // undefined. |
555 | |
556 | #if !defined(BOOST_HASH_NO_EXTENSIONS) \ |
557 | && !defined(BOOST_FUNCTIONAL_HASH_EXTENSIONS_HPP) |
558 | #include <boost/functional/hash/extensions.hpp> |
559 | #endif |
560 | |