1 

     2 //  Copyright Daniel James 2005-2006. Use, modification, and distribution are

     3 //  subject to 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  * © Portions copyright (c) 2006-2007 Nokia Corporation.  All rights reserved.

    11 */

    12 #if !defined(BOOST_FUNCTIONAL_HASH_HASH_HPP)

    13 #define BOOST_FUNCTIONAL_HASH_HASH_HPP

    14 

    15 #include <boost/functional/hash_fwd.hpp>

    16 #include <functional>

    17 #include <boost/functional/detail/hash_float.hpp>

    18 #include <boost/functional/detail/container_fwd.hpp>

    19 #include <string>

    20 

    21 #if defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)

    22 #include <boost/type_traits/is_pointer.hpp>

    23 #endif

    24 

    25 #if defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)

    26 #include <boost/type_traits/is_array.hpp>

    27 #endif

    28 

    29 #if BOOST_WORKAROUND(BOOST_MSVC, < 1300)

    30 #include <boost/type_traits/is_const.hpp>

    31 #endif

    32 

    33 namespace boost

    34 {

    35 #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x551))

    36     // Borland complains about an ambiguous function overload

    37     // when compiling boost::hash<bool>.

    38     std::size_t hash_value(bool);

    39 #endif

    40     

    41     std::size_t hash_value(int);

    42     std::size_t hash_value(unsigned int);

    43     std::size_t hash_value(long);

    44     std::size_t hash_value(unsigned long);

    45 

    46 #if defined(BOOST_MSVC) && defined(_WIN64)

    47     // On 64-bit windows std::size_t is a typedef for unsigned long long, which

    48     // isn't due to be supported until Boost 1.35. So add support here.

    49     // (Technically, Boost.Hash isn't actually documented as supporting

    50     // std::size_t. But it would be pretty silly not to).

    51     std::size_t hash_value(std::size_t);

    52 #endif

    53 

    54 #if !BOOST_WORKAROUND(__DMC__, <= 0x848)

    55     template <class T> std::size_t hash_value(T* const&);

    56 #else

    57     template <class T> std::size_t hash_value(T*);

    58 #endif

    59 

    60 #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)

    61     template< class T, unsigned N >

    62     std::size_t hash_value(const T (&array)[N]);

    63 

    64     template< class T, unsigned N >

    65     std::size_t hash_value(T (&array)[N]);

    66 #endif

    67 

    68     std::size_t hash_value(float v);

    69     std::size_t hash_value(double v);

    70     std::size_t hash_value(long double v);

    71 

    72     template <class Ch, class A>

    73     std::size_t hash_value(std::basic_string<Ch, std::BOOST_HASH_CHAR_TRAITS<Ch>, A> const&);

    74 

    75     template <class A, class B>

    76     std::size_t hash_value(std::pair<A, B> const&);

    77     template <class T, class A>

    78     std::size_t hash_value(std::vector<T, A> const&);

    79     template <class T, class A>

    80     std::size_t hash_value(std::list<T, A> const& v);

    81     template <class T, class A>

    82     std::size_t hash_value(std::deque<T, A> const& v);

    83     template <class K, class C, class A>

    84     std::size_t hash_value(std::set<K, C, A> const& v);

    85     template <class K, class C, class A>

    86     std::size_t hash_value(std::multiset<K, C, A> const& v);

    87     template <class K, class T, class C, class A>

    88     std::size_t hash_value(std::map<K, T, C, A> const& v);

    89     template <class K, class T, class C, class A>

    90     std::size_t hash_value(std::multimap<K, T, C, A> const& v);

    91 

    92     // Implementation

    93 

    94 #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x551))

    95     inline std::size_t hash_value(bool v)

    96     {

    97         return static_cast<std::size_t>(v);

    98     }

    99 #endif

   100 

   101     inline std::size_t hash_value(int v)

   102     {

   103         return static_cast<std::size_t>(v);

   104     }

   105 

   106     inline std::size_t hash_value(unsigned int v)

   107     {

   108         return static_cast<std::size_t>(v);

   109     }

   110 

   111     inline std::size_t hash_value(long v)

   112     {

   113         return static_cast<std::size_t>(v);

   114     }

   115 

   116     inline std::size_t hash_value(unsigned long v)

   117     {

   118         return static_cast<std::size_t>(v);

   119     }

   120 

   121 #if defined(_M_X64) && defined(_WIN64)

   122     inline std::size_t hash_value(long long v)

   123     {

   124         return v;

   125     }

   126 

   127     inline std::size_t hash_value(unsigned long long v)

   128     {

   129         return v;

   130     }

   131 #endif

   132 

   133     // Implementation by Alberto Barbati and Dave Harris.

   134 #if !BOOST_WORKAROUND(__DMC__, <= 0x848)

   135     template <class T> std::size_t hash_value(T* const& v)

   136 #else

   137     template <class T> std::size_t hash_value(T* v)

   138 #endif

   139     {

   140         std::size_t x = static_cast<std::size_t>(

   141            reinterpret_cast<std::ptrdiff_t>(v));

   142         return x + (x >> 3);

   143     }

   144 

   145 #if BOOST_WORKAROUND(BOOST_MSVC, < 1300)

   146     template <class T>

   147     inline void hash_combine(std::size_t& seed, T& v)

   148 #else

   149     template <class T>

   150     inline void hash_combine(std::size_t& seed, T const& v)

   151 #endif

   152     {

   153         boost::hash<T> hasher;

   154         seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);

   155     }

   156 

   157     template <class It>

   158     inline std::size_t hash_range(It first, It last)

   159     {

   160         std::size_t seed = 0;

   161 

   162         for(; first != last; ++first)

   163         {

   164             hash_combine(seed, *first);

   165         }

   166 

   167         return seed;

   168     }

   169 

   170     template <class It>

   171     inline void hash_range(std::size_t& seed, It first, It last)

   172     {

   173         for(; first != last; ++first)

   174         {

   175             hash_combine(seed, *first);

   176         }

   177     }

   178 

   179 #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x551))

   180     template <class T>

   181     inline std::size_t hash_range(T* first, T* last)

   182     {

   183         std::size_t seed = 0;

   184 

   185         for(; first != last; ++first)

   186         {

   187             boost::hash<T> hasher;

   188             seed ^= hasher(*first) + 0x9e3779b9 + (seed<<6) + (seed>>2);

   189         }

   190 

   191         return seed;

   192     }

   193 

   194     template <class T>

   195     inline void hash_range(std::size_t& seed, T* first, T* last)

   196     {

   197         for(; first != last; ++first)

   198         {

   199             boost::hash<T> hasher;

   200             seed ^= hasher(*first) + 0x9e3779b9 + (seed<<6) + (seed>>2);

   201         }

   202     }

   203 #endif

   204 

   205 #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)

   206     template< class T, unsigned N >

   207     inline std::size_t hash_value(const T (&array)[N])

   208     {

   209         return hash_range(array, array + N);

   210     }

   211 

   212     template< class T, unsigned N >

   213     inline std::size_t hash_value(T (&array)[N])

   214     {

   215         return hash_range(array, array + N);

   216     }

   217 #endif

   218 

   219     template <class Ch, class A>

   220     inline std::size_t hash_value(std::basic_string<Ch, std::BOOST_HASH_CHAR_TRAITS<Ch>, A> const& v)

   221     {

   222         return hash_range(v.begin(), v.end());

   223     }

   224 

   225     inline std::size_t hash_value(float v)

   226     {

   227         return boost::hash_detail::float_hash_value(v);

   228     }

   229 

   230     inline std::size_t hash_value(double v)

   231     {

   232         return boost::hash_detail::float_hash_value(v);

   233     }

   234 

   235 #ifndef __SYMBIAN32__ //long double not supported

   236     inline std::size_t hash_value(long double v)

   237     {

   238         return boost::hash_detail::float_hash_value(v);

   239     }

   240 #endif

   241     template <class A, class B>

   242     std::size_t hash_value(std::pair<A, B> const& v)

   243     {

   244         std::size_t seed = 0;

   245         hash_combine(seed, v.first);

   246         hash_combine(seed, v.second);

   247         return seed;

   248     }

   249 

   250     template <class T, class A>

   251     std::size_t hash_value(std::vector<T, A> const& v)

   252     {

   253         return hash_range(v.begin(), v.end());

   254     }

   255 

   256     template <class T, class A>

   257     std::size_t hash_value(std::list<T, A> const& v)

   258     {

   259         return hash_range(v.begin(), v.end());

   260     }

   261 

   262     template <class T, class A>

   263     std::size_t hash_value(std::deque<T, A> const& v)

   264     {

   265         return hash_range(v.begin(), v.end());

   266     }

   267 

   268     template <class K, class C, class A>

   269     std::size_t hash_value(std::set<K, C, A> const& v)

   270     {

   271         return hash_range(v.begin(), v.end());

   272     }

   273 

   274     template <class K, class C, class A>

   275     std::size_t hash_value(std::multiset<K, C, A> const& v)

   276     {

   277         return hash_range(v.begin(), v.end());

   278     }

   279 

   280     template <class K, class T, class C, class A>

   281     std::size_t hash_value(std::map<K, T, C, A> const& v)

   282     {

   283         return hash_range(v.begin(), v.end());

   284     }

   285 

   286     template <class K, class T, class C, class A>

   287     std::size_t hash_value(std::multimap<K, T, C, A> const& v)

   288     {

   289         return hash_range(v.begin(), v.end());

   290     }

   291 

   292     //

   293     // boost::hash

   294     //

   295 

   296 #if !BOOST_WORKAROUND(BOOST_MSVC, < 1300)

   297 #define BOOST_HASH_SPECIALIZE(type) \

   298     template <> struct hash<type> \

   299          : public std::unary_function<type, std::size_t> \

   300     { \

   301         std::size_t operator()(type v) const \

   302         { \

   303             return boost::hash_value(v); \

   304         } \

   305     };

   306 

   307 #define BOOST_HASH_SPECIALIZE_REF(type) \

   308     template <> struct hash<type> \

   309          : public std::unary_function<type, std::size_t> \

   310     { \

   311         std::size_t operator()(type const& v) const \

   312         { \

   313             return boost::hash_value(v); \

   314         } \

   315     };

   316 #else

   317 #define BOOST_HASH_SPECIALIZE(type) \

   318     template <> struct hash<type> \

   319          : public std::unary_function<type, std::size_t> \

   320     { \

   321         std::size_t operator()(type v) const \

   322         { \

   323             return boost::hash_value(v); \

   324         } \

   325     }; \

   326     \

   327     template <> struct hash<const type> \

   328          : public std::unary_function<const type, std::size_t> \

   329     { \

   330         std::size_t operator()(const type v) const \

   331         { \

   332             return boost::hash_value(v); \

   333         } \

   334     };

   335 

   336 #define BOOST_HASH_SPECIALIZE_REF(type) \

   337     template <> struct hash<type> \

   338          : public std::unary_function<type, std::size_t> \

   339     { \

   340         std::size_t operator()(type const& v) const \

   341         { \

   342             return boost::hash_value(v); \

   343         } \

   344     }; \

   345     \

   346     template <> struct hash<const type> \

   347          : public std::unary_function<const type, std::size_t> \

   348     { \

   349         std::size_t operator()(type const& v) const \

   350         { \

   351             return boost::hash_value(v); \

   352         } \

   353     };

   354 #endif

   355 

   356     BOOST_HASH_SPECIALIZE(bool)

   357     BOOST_HASH_SPECIALIZE(char)

   358     BOOST_HASH_SPECIALIZE(signed char)

   359     BOOST_HASH_SPECIALIZE(unsigned char)

   360 #if !defined(BOOST_NO_INTRINSIC_WCHAR_T) || defined(__SYMBIAN32__)

   361     BOOST_HASH_SPECIALIZE(wchar_t)

   362 #endif

   363     BOOST_HASH_SPECIALIZE(short)

   364     BOOST_HASH_SPECIALIZE(unsigned short)

   365     BOOST_HASH_SPECIALIZE(int)

   366     BOOST_HASH_SPECIALIZE(unsigned int)

   367     BOOST_HASH_SPECIALIZE(long)

   368     BOOST_HASH_SPECIALIZE(unsigned long)

   369 

   370     BOOST_HASH_SPECIALIZE(float)

   371     BOOST_HASH_SPECIALIZE(double)

   372     BOOST_HASH_SPECIALIZE(long double)

   373 

   374     BOOST_HASH_SPECIALIZE_REF(std::string)

   375 #if !defined(BOOST_NO_STD_WSTRING)

   376     BOOST_HASH_SPECIALIZE_REF(std::wstring)

   377 #endif

   378 

   379 #undef BOOST_HASH_SPECIALIZE

   380 #undef BOOST_HASH_SPECIALIZE_REF

   381 

   382 #if !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)

   383     template <class T>

   384     struct hash<T*>

   385         : public std::unary_function<T*, std::size_t>

   386     {

   387         std::size_t operator()(T* v) const \

   388         { \

   389             return boost::hash_value(v); \

   390         } \

   391     };

   392 #else

   393     namespace hash_detail

   394     {

   395         template <bool IsPointer>

   396         struct hash_impl;

   397 

   398         template <>

   399         struct hash_impl<true>

   400         {

   401             template <class T>

   402             struct inner

   403                 : public std::unary_function<T, std::size_t>

   404             {

   405                 std::size_t operator()(T val) const

   406                 {

   407                     return boost::hash_value(val);

   408                 }

   409             };

   410         };

   411     }

   412 

   413     template <class T> struct hash

   414         : public boost::hash_detail::hash_impl<boost::is_pointer<T>::value>

   415             ::BOOST_NESTED_TEMPLATE inner<T>

   416     {

   417     };

   418 #endif

   419 }

   420 

   421 #endif // BOOST_FUNCTIONAL_HASH_HASH_HPP

   422 

   423 ////////////////////////////////////////////////////////////////////////////////

   424 

   425 #if !defined(BOOST_HASH_NO_EXTENSIONS) \

   426     && !defined(BOOST_FUNCTIONAL_HASH_EXTENSIONS_HPP)

   427 #define BOOST_FUNCTIONAL_HASH_EXTENSIONS_HPP

   428 

   429 namespace boost

   430 {

   431 

   432 #if defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)

   433     namespace hash_detail

   434     {

   435         template <bool IsArray>

   436         struct call_hash_impl

   437         {

   438             template <class T>

   439             struct inner

   440             {

   441                 static std::size_t call(T const& v)

   442                 {

   443                     using namespace boost;

   444                     return hash_value(v);

   445                 }

   446             };

   447         };

   448 

   449         template <>

   450         struct call_hash_impl<true>

   451         {

   452             template <class Array>

   453             struct inner

   454             {

   455 #if !BOOST_WORKAROUND(BOOST_MSVC, < 1300)

   456                 static std::size_t call(Array const& v)

   457 #else

   458                 static std::size_t call(Array& v)

   459 #endif

   460                 {

   461                     const int size = sizeof(v) / sizeof(*v);

   462                     return boost::hash_range(v, v + size);

   463                 }

   464             };

   465         };

   466 

   467         template <class T>

   468         struct call_hash

   469             : public call_hash_impl<boost::is_array<T>::value>

   470                 ::BOOST_NESTED_TEMPLATE inner<T>

   471         {

   472         };

   473     }

   474 #endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING

   475 

   476 #if !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)

   477 

   478     template <class T> struct hash

   479         : std::unary_function<T, std::size_t>

   480     {

   481 #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)

   482         std::size_t operator()(T const& val) const

   483         {

   484             return hash_value(val);

   485         }

   486 #else

   487         std::size_t operator()(T const& val) const

   488         {

   489             return hash_detail::call_hash<T>::call(val);

   490         }

   491 #endif

   492     };

   493 

   494 #if BOOST_WORKAROUND(__DMC__, <= 0x848)

   495     template <class T, unsigned int n> struct hash<T[n]>

   496         : std::unary_function<T[n], std::size_t>

   497     {

   498         std::size_t operator()(const T* val) const

   499         {

   500             return boost::hash_range(val, val+n);

   501         }

   502     };

   503 #endif

   504 

   505 #else // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION

   506 

   507     // On compilers without partial specialization, boost::hash<T>

   508     // has already been declared to deal with pointers, so just

   509     // need to supply the non-pointer version.

   510 

   511     namespace hash_detail

   512     {

   513         template <bool IsPointer>

   514         struct hash_impl;

   515 

   516 #if !BOOST_WORKAROUND(BOOST_MSVC, < 1300)

   517 

   518         template <>

   519         struct hash_impl<false>

   520         {

   521             template <class T>

   522             struct inner

   523                 : std::unary_function<T, std::size_t>

   524             {

   525 #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)

   526                 std::size_t operator()(T const& val) const

   527                 {

   528                     return hash_value(val);

   529                 }

   530 #else

   531                 std::size_t operator()(T const& val) const

   532                 {

   533                     return hash_detail::call_hash<T>::call(val);

   534                 }

   535 #endif

   536             };

   537         };

   538 

   539 #else // Visual C++ 6.5

   540 

   541     // There's probably a more elegant way to Visual C++ 6.5 to work

   542     // but I don't know what it is.

   543 

   544         template <bool IsConst>

   545         struct hash_impl_msvc

   546         {

   547             template <class T>

   548             struct inner

   549                 : public std::unary_function<T, std::size_t>

   550             {

   551                 std::size_t operator()(T const& val) const

   552                 {

   553                     return hash_detail::call_hash<T const>::call(val);

   554                 }

   555 

   556                 std::size_t operator()(T& val) const

   557                 {

   558                     return hash_detail::call_hash<T>::call(val);

   559                 }

   560             };

   561         };

   562 

   563         template <>

   564         struct hash_impl_msvc<true>

   565         {

   566             template <class T>

   567             struct inner

   568                 : public std::unary_function<T, std::size_t>

   569             {

   570                 std::size_t operator()(T& val) const

   571                 {

   572                     return hash_detail::call_hash<T>::call(val);

   573                 }

   574             };

   575         };

   576         

   577         template <class T>

   578         struct hash_impl_msvc2

   579             : public hash_impl_msvc<boost::is_const<T>::value>

   580                     ::BOOST_NESTED_TEMPLATE inner<T> {};

   581         

   582         template <>

   583         struct hash_impl<false>

   584         {

   585             template <class T>

   586             struct inner : public hash_impl_msvc2<T> {};

   587         };

   588 

   589 #endif // Visual C++ 6.5

   590     }

   591 #endif  // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION

   592 }

   593 

   594 #endif

   595