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