]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 unsigned 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 | / static_cast<int>(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 unsigned 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 | / static_cast<int>(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 | inline void hash_combine_impl(boost::uint32_t& h1, | |
216 | boost::uint32_t k1) | |
217 | { | |
218 | const uint32_t c1 = 0xcc9e2d51; | |
219 | const uint32_t c2 = 0x1b873593; | |
220 | ||
221 | k1 *= c1; | |
222 | k1 = BOOST_FUNCTIONAL_HASH_ROTL32(k1,15); | |
223 | k1 *= c2; | |
224 | ||
225 | h1 ^= k1; | |
226 | h1 = BOOST_FUNCTIONAL_HASH_ROTL32(h1,13); | |
227 | h1 = h1*5+0xe6546b64; | |
228 | } | |
229 | ||
230 | ||
231 | // Don't define 64-bit hash combine on platforms without 64 bit integers, | |
232 | // and also not for 32-bit gcc as it warns about the 64-bit constant. | |
233 | #if !defined(BOOST_NO_INT64_T) && \ | |
234 | !(defined(__GNUC__) && ULONG_MAX == 0xffffffff) | |
235 | ||
236 | inline void hash_combine_impl(boost::uint64_t& h, | |
237 | boost::uint64_t k) | |
238 | { | |
239 | const boost::uint64_t m = UINT64_C(0xc6a4a7935bd1e995); | |
240 | const int r = 47; | |
241 | ||
242 | k *= m; | |
243 | k ^= k >> r; | |
244 | k *= m; | |
245 | ||
246 | h ^= k; | |
247 | h *= m; | |
248 | ||
249 | // Completely arbitrary number, to prevent 0's | |
250 | // from hashing to 0. | |
251 | h += 0xe6546b64; | |
252 | } | |
253 | ||
254 | #endif // BOOST_NO_INT64_T | |
255 | } | |
256 | ||
257 | template <typename T> | |
258 | typename boost::hash_detail::basic_numbers<T>::type hash_value(T v) | |
259 | { | |
260 | return static_cast<std::size_t>(v); | |
261 | } | |
262 | ||
263 | template <typename T> | |
264 | typename boost::hash_detail::long_numbers<T>::type hash_value(T v) | |
265 | { | |
266 | return hash_detail::hash_value_signed(v); | |
267 | } | |
268 | ||
269 | template <typename T> | |
270 | typename boost::hash_detail::ulong_numbers<T>::type hash_value(T v) | |
271 | { | |
272 | return hash_detail::hash_value_unsigned(v); | |
273 | } | |
274 | ||
275 | template <typename T> | |
276 | typename boost::enable_if<boost::is_enum<T>, std::size_t>::type | |
277 | hash_value(T v) | |
278 | { | |
279 | return static_cast<std::size_t>(v); | |
280 | } | |
281 | ||
282 | // Implementation by Alberto Barbati and Dave Harris. | |
283 | #if !BOOST_WORKAROUND(__DMC__, <= 0x848) | |
284 | template <class T> std::size_t hash_value(T* const& v) | |
285 | #else | |
286 | template <class T> std::size_t hash_value(T* v) | |
287 | #endif | |
288 | { | |
289 | #if defined(__VMS) && __INITIAL_POINTER_SIZE == 64 | |
290 | // for some reason ptrdiff_t on OpenVMS compiler with | |
291 | // 64 bit is not 64 bit !!! | |
292 | std::size_t x = static_cast<std::size_t>( | |
293 | reinterpret_cast<long long int>(v)); | |
294 | #else | |
295 | std::size_t x = static_cast<std::size_t>( | |
296 | reinterpret_cast<std::ptrdiff_t>(v)); | |
297 | #endif | |
298 | return x + (x >> 3); | |
299 | } | |
300 | ||
301 | #if defined(BOOST_MSVC) | |
302 | #pragma warning(push) | |
303 | #if BOOST_MSVC <= 1400 | |
304 | #pragma warning(disable:4267) // 'argument' : conversion from 'size_t' to | |
305 | // 'unsigned int', possible loss of data | |
306 | // A misguided attempt to detect 64-bit | |
307 | // incompatability. | |
308 | #endif | |
309 | #endif | |
310 | ||
311 | template <class T> | |
312 | inline void hash_combine(std::size_t& seed, T const& v) | |
313 | { | |
314 | boost::hash<T> hasher; | |
315 | return boost::hash_detail::hash_combine_impl(seed, hasher(v)); | |
316 | } | |
317 | ||
318 | #if defined(BOOST_MSVC) | |
319 | #pragma warning(pop) | |
320 | #endif | |
321 | ||
322 | template <class It> | |
323 | inline std::size_t hash_range(It first, It last) | |
324 | { | |
325 | std::size_t seed = 0; | |
326 | ||
327 | for(; first != last; ++first) | |
328 | { | |
329 | hash_combine(seed, *first); | |
330 | } | |
331 | ||
332 | return seed; | |
333 | } | |
334 | ||
335 | template <class It> | |
336 | inline void hash_range(std::size_t& seed, It first, It last) | |
337 | { | |
338 | for(; first != last; ++first) | |
339 | { | |
340 | hash_combine(seed, *first); | |
341 | } | |
342 | } | |
343 | ||
344 | #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x551)) | |
345 | template <class T> | |
346 | inline std::size_t hash_range(T* first, T* last) | |
347 | { | |
348 | std::size_t seed = 0; | |
349 | ||
350 | for(; first != last; ++first) | |
351 | { | |
352 | boost::hash<T> hasher; | |
353 | seed ^= hasher(*first) + 0x9e3779b9 + (seed<<6) + (seed>>2); | |
354 | } | |
355 | ||
356 | return seed; | |
357 | } | |
358 | ||
359 | template <class T> | |
360 | inline void hash_range(std::size_t& seed, T* first, T* last) | |
361 | { | |
362 | for(; first != last; ++first) | |
363 | { | |
364 | boost::hash<T> hasher; | |
365 | seed ^= hasher(*first) + 0x9e3779b9 + (seed<<6) + (seed>>2); | |
366 | } | |
367 | } | |
368 | #endif | |
369 | ||
370 | #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) | |
371 | template< class T, unsigned N > | |
372 | inline std::size_t hash_value(const T (&x)[N]) | |
373 | { | |
374 | return hash_range(x, x + N); | |
375 | } | |
376 | ||
377 | template< class T, unsigned N > | |
378 | inline std::size_t hash_value(T (&x)[N]) | |
379 | { | |
380 | return hash_range(x, x + N); | |
381 | } | |
382 | #endif | |
383 | ||
384 | template <class Ch, class A> | |
385 | inline std::size_t hash_value( | |
386 | std::basic_string<Ch, std::BOOST_HASH_CHAR_TRAITS<Ch>, A> const& v) | |
387 | { | |
388 | return hash_range(v.begin(), v.end()); | |
389 | } | |
390 | ||
391 | template <typename T> | |
392 | typename boost::hash_detail::float_numbers<T>::type hash_value(T v) | |
393 | { | |
394 | return boost::hash_detail::float_hash_value(v); | |
395 | } | |
396 | ||
397 | #if !defined(BOOST_NO_CXX11_HDR_TYPEINDEX) | |
398 | inline std::size_t hash_value(std::type_index v) | |
399 | { | |
400 | return v.hash_code(); | |
401 | } | |
402 | #endif | |
403 | ||
404 | // | |
405 | // boost::hash | |
406 | // | |
407 | ||
408 | // Define the specializations required by the standard. The general purpose | |
409 | // boost::hash is defined later in extensions.hpp if | |
410 | // BOOST_HASH_NO_EXTENSIONS is not defined. | |
411 | ||
412 | // BOOST_HASH_SPECIALIZE - define a specialization for a type which is | |
413 | // passed by copy. | |
414 | // | |
415 | // BOOST_HASH_SPECIALIZE_REF - define a specialization for a type which is | |
416 | // passed by const reference. | |
417 | // | |
418 | // These are undefined later. | |
419 | ||
420 | #define BOOST_HASH_SPECIALIZE(type) \ | |
421 | template <> struct hash<type> \ | |
422 | : public std::unary_function<type, std::size_t> \ | |
423 | { \ | |
424 | std::size_t operator()(type v) const \ | |
425 | { \ | |
426 | return boost::hash_value(v); \ | |
427 | } \ | |
428 | }; | |
429 | ||
430 | #define BOOST_HASH_SPECIALIZE_REF(type) \ | |
431 | template <> struct hash<type> \ | |
432 | : public std::unary_function<type, std::size_t> \ | |
433 | { \ | |
434 | std::size_t operator()(type const& v) const \ | |
435 | { \ | |
436 | return boost::hash_value(v); \ | |
437 | } \ | |
438 | }; | |
439 | ||
440 | BOOST_HASH_SPECIALIZE(bool) | |
441 | BOOST_HASH_SPECIALIZE(char) | |
442 | BOOST_HASH_SPECIALIZE(signed char) | |
443 | BOOST_HASH_SPECIALIZE(unsigned char) | |
444 | #if !defined(BOOST_NO_INTRINSIC_WCHAR_T) | |
445 | BOOST_HASH_SPECIALIZE(wchar_t) | |
446 | #endif | |
447 | BOOST_HASH_SPECIALIZE(short) | |
448 | BOOST_HASH_SPECIALIZE(unsigned short) | |
449 | BOOST_HASH_SPECIALIZE(int) | |
450 | BOOST_HASH_SPECIALIZE(unsigned int) | |
451 | BOOST_HASH_SPECIALIZE(long) | |
452 | BOOST_HASH_SPECIALIZE(unsigned long) | |
453 | ||
454 | BOOST_HASH_SPECIALIZE(float) | |
455 | BOOST_HASH_SPECIALIZE(double) | |
456 | BOOST_HASH_SPECIALIZE(long double) | |
457 | ||
458 | BOOST_HASH_SPECIALIZE_REF(std::string) | |
459 | #if !defined(BOOST_NO_STD_WSTRING) | |
460 | BOOST_HASH_SPECIALIZE_REF(std::wstring) | |
461 | #endif | |
462 | ||
463 | #if !defined(BOOST_NO_LONG_LONG) | |
464 | BOOST_HASH_SPECIALIZE(boost::long_long_type) | |
465 | BOOST_HASH_SPECIALIZE(boost::ulong_long_type) | |
466 | #endif | |
467 | ||
468 | #if defined(BOOST_HAS_INT128) | |
469 | BOOST_HASH_SPECIALIZE(boost::int128_type) | |
470 | BOOST_HASH_SPECIALIZE(boost::uint128_type) | |
471 | #endif | |
472 | ||
473 | #if !defined(BOOST_NO_CXX11_HDR_TYPEINDEX) | |
474 | BOOST_HASH_SPECIALIZE(std::type_index) | |
475 | #endif | |
476 | ||
477 | #undef BOOST_HASH_SPECIALIZE | |
478 | #undef BOOST_HASH_SPECIALIZE_REF | |
479 | ||
480 | // Specializing boost::hash for pointers. | |
481 | ||
482 | #if !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) | |
483 | ||
484 | template <class T> | |
485 | struct hash<T*> | |
486 | : public std::unary_function<T*, std::size_t> | |
487 | { | |
488 | std::size_t operator()(T* v) const | |
489 | { | |
490 | #if !BOOST_WORKAROUND(__SUNPRO_CC, <= 0x590) | |
491 | return boost::hash_value(v); | |
492 | #else | |
493 | std::size_t x = static_cast<std::size_t>( | |
494 | reinterpret_cast<std::ptrdiff_t>(v)); | |
495 | ||
496 | return x + (x >> 3); | |
497 | #endif | |
498 | } | |
499 | }; | |
500 | ||
501 | #else | |
502 | ||
503 | // For compilers without partial specialization, we define a | |
504 | // boost::hash for all remaining types. But hash_impl is only defined | |
505 | // for pointers in 'extensions.hpp' - so when BOOST_HASH_NO_EXTENSIONS | |
506 | // is defined there will still be a compile error for types not supported | |
507 | // in the standard. | |
508 | ||
509 | namespace hash_detail | |
510 | { | |
511 | template <bool IsPointer> | |
512 | struct hash_impl; | |
513 | ||
514 | template <> | |
515 | struct hash_impl<true> | |
516 | { | |
517 | template <class T> | |
518 | struct inner | |
519 | : public std::unary_function<T, std::size_t> | |
520 | { | |
521 | std::size_t operator()(T val) const | |
522 | { | |
523 | #if !BOOST_WORKAROUND(__SUNPRO_CC, <= 590) | |
524 | return boost::hash_value(val); | |
525 | #else | |
526 | std::size_t x = static_cast<std::size_t>( | |
527 | reinterpret_cast<std::ptrdiff_t>(val)); | |
528 | ||
529 | return x + (x >> 3); | |
530 | #endif | |
531 | } | |
532 | }; | |
533 | }; | |
534 | } | |
535 | ||
536 | template <class T> struct hash | |
537 | : public boost::hash_detail::hash_impl<boost::is_pointer<T>::value> | |
538 | ::BOOST_NESTED_TEMPLATE inner<T> | |
539 | { | |
540 | }; | |
541 | ||
542 | #endif | |
543 | } | |
544 | ||
545 | #undef BOOST_HASH_CHAR_TRAITS | |
546 | #undef BOOST_FUNCTIONAL_HASH_ROTL32 | |
547 | ||
548 | #if defined(BOOST_MSVC) | |
549 | #pragma warning(pop) | |
550 | #endif | |
551 | ||
552 | #endif // BOOST_FUNCTIONAL_HASH_HASH_HPP | |
553 | ||
554 | // Include this outside of the include guards in case the file is included | |
555 | // twice - once with BOOST_HASH_NO_EXTENSIONS defined, and then with it | |
556 | // undefined. | |
557 | ||
558 | #if !defined(BOOST_HASH_NO_EXTENSIONS) \ | |
559 | && !defined(BOOST_FUNCTIONAL_HASH_EXTENSIONS_HPP) | |
560 | #include <boost/functional/hash/extensions.hpp> | |
561 | #endif |