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