boost/boost/functional/hash/hash.hpp

   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 copy.
 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