boost/boost/functional/hash/hash.hpp

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