boost/boost/functional/hash/extensions.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 // This implements the extensions to the standard.
  11 // It's undocumented, so you shouldn't use it....
  12
  13 #if !defined(BOOST_FUNCTIONAL_HASH_EXTENSIONS_HPP)
  14 #define BOOST_FUNCTIONAL_HASH_EXTENSIONS_HPP
  15
  16 #include <boost/functional/hash/hash.hpp>
  17 #include <boost/detail/container_fwd.hpp>
  18 #include <boost/utility/enable_if.hpp>
  19 #include <boost/static_assert.hpp>
  20 #include <boost/preprocessor/repetition/repeat_from_to.hpp>
  21 #include <boost/preprocessor/repetition/enum_params.hpp>
  22
  23 #if !defined(BOOST_NO_CXX11_HDR_ARRAY)
  24 #   include <array>
  25 #endif
  26
  27 #if !defined(BOOST_NO_CXX11_HDR_TUPLE)
  28 #   include <tuple>
  29 #endif
  30
  31 #if !defined(BOOST_NO_CXX11_HDR_MEMORY)
  32 #   include <memory>
  33 #endif
  34
  35 #if defined(_MSC_VER) && (_MSC_VER >= 1020)
  36 # pragma once
  37 #endif
  38
  39 #if defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)
  40 #include <boost/type_traits/is_array.hpp>
  41 #endif
  42
  43 #if BOOST_WORKAROUND(BOOST_MSVC, < 1300)
  44 #include <boost/type_traits/is_const.hpp>
  45 #endif
  46
  47 namespace boost
  48 {
  49     template <class A, class B>
  50     std::size_t hash_value(std::pair<A, B> const&);
  51     template <class T, class A>
  52     std::size_t hash_value(std::vector<T, A> const&);
  53     template <class T, class A>
  54     std::size_t hash_value(std::list<T, A> const& v);
  55     template <class T, class A>
  56     std::size_t hash_value(std::deque<T, A> const& v);
  57     template <class K, class C, class A>
  58     std::size_t hash_value(std::set<K, C, A> const& v);
  59     template <class K, class C, class A>
  60     std::size_t hash_value(std::multiset<K, C, A> const& v);
  61     template <class K, class T, class C, class A>
  62     std::size_t hash_value(std::map<K, T, C, A> const& v);
  63     template <class K, class T, class C, class A>
  64     std::size_t hash_value(std::multimap<K, T, C, A> const& v);
  65
  66     template <class T>
  67     std::size_t hash_value(std::complex<T> const&);
  68
  69     template <class A, class B>
  70     std::size_t hash_value(std::pair<A, B> const& v)
  71     {
  72         std::size_t seed = 0;
  73         boost::hash_combine(seed, v.first);
  74         boost::hash_combine(seed, v.second);
  75         return seed;
  76     }
  77
  78     template <class T, class A>
  79     std::size_t hash_value(std::vector<T, A> const& v)
  80     {
  81         return boost::hash_range(v.begin(), v.end());
  82     }
  83
  84     template <class T, class A>
  85     std::size_t hash_value(std::list<T, A> const& v)
  86     {
  87         return boost::hash_range(v.begin(), v.end());
  88     }
  89
  90     template <class T, class A>
  91     std::size_t hash_value(std::deque<T, A> const& v)
  92     {
  93         return boost::hash_range(v.begin(), v.end());
  94     }
  95
  96     template <class K, class C, class A>
  97     std::size_t hash_value(std::set<K, C, A> const& v)
  98     {
  99         return boost::hash_range(v.begin(), v.end());
 100     }
 101
 102     template <class K, class C, class A>
 103     std::size_t hash_value(std::multiset<K, C, A> const& v)
 104     {
 105         return boost::hash_range(v.begin(), v.end());
 106     }
 107
 108     template <class K, class T, class C, class A>
 109     std::size_t hash_value(std::map<K, T, C, A> const& v)
 110     {
 111         return boost::hash_range(v.begin(), v.end());
 112     }
 113
 114     template <class K, class T, class C, class A>
 115     std::size_t hash_value(std::multimap<K, T, C, A> const& v)
 116     {
 117         return boost::hash_range(v.begin(), v.end());
 118     }
 119
 120     template <class T>
 121     std::size_t hash_value(std::complex<T> const& v)
 122     {
 123         boost::hash<T> hasher;
 124         std::size_t seed = hasher(v.imag());
 125         seed ^= hasher(v.real()) + (seed<<6) + (seed>>2);
 126         return seed;
 127     }
 128
 129 #if !defined(BOOST_NO_CXX11_HDR_ARRAY)
 130     template <class T, std::size_t N>
 131     std::size_t hash_value(std::array<T, N> const& v)
 132     {
 133         return boost::hash_range(v.begin(), v.end());
 134     }
 135 #endif
 136
 137 #if !defined(BOOST_NO_CXX11_HDR_TUPLE)
 138     namespace hash_detail {
 139         template <std::size_t I, typename T>
 140         inline typename boost::enable_if_c<(I == std::tuple_size<T>::value),
 141                 void>::type
 142             hash_combine_tuple(std::size_t&, T const&)
 143         {
 144         }
 145
 146         template <std::size_t I, typename T>
 147         inline typename boost::enable_if_c<(I < std::tuple_size<T>::value),
 148                 void>::type
 149             hash_combine_tuple(std::size_t& seed, T const& v)
 150         {
 151             boost::hash_combine(seed, std::get<I>(v));
 152             boost::hash_detail::hash_combine_tuple<I + 1>(seed, v);
 153         }
 154
 155         template <typename T>
 156         inline std::size_t hash_tuple(T const& v)
 157         {
 158             std::size_t seed = 0;
 159             boost::hash_detail::hash_combine_tuple<0>(seed, v);
 160             return seed;
 161         }
 162     }
 163
 164 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 165     template <typename... T>
 166     inline std::size_t hash_value(std::tuple<T...> const& v)
 167     {
 168         return boost::hash_detail::hash_tuple(v);
 169     }
 170 #else
 171
 172     inline std::size_t hash_value(std::tuple<> const& v)
 173     {
 174         return boost::hash_detail::hash_tuple(v);
 175     }
 176
 177 #   define BOOST_HASH_TUPLE_F(z, n, _)                                      \
 178     template<                                                               \
 179         BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)                            \
 180     >                                                                       \
 181     inline std::size_t hash_value(std::tuple<                               \
 182         BOOST_PP_ENUM_PARAMS_Z(z, n, A)                                     \
 183     > const& v)                                                             \
 184     {                                                                       \
 185         return boost::hash_detail::hash_tuple(v);                           \
 186     }
 187
 188     BOOST_PP_REPEAT_FROM_TO(1, 11, BOOST_HASH_TUPLE_F, _)
 189 #   undef BOOST_HASH_TUPLE_F
 190 #endif
 191
 192 #endif
 193
 194 #if !defined(BOOST_NO_CXX11_SMART_PTR)
 195     template <typename T>
 196     inline std::size_t hash_value(std::shared_ptr<T> const& x) {
 197         return boost::hash_value(x.get());
 198     }
 199
 200     template <typename T, typename Deleter>
 201     inline std::size_t hash_value(std::unique_ptr<T, Deleter> const& x) {
 202         return boost::hash_value(x.get());
 203     }
 204 #endif
 205
 206     //
 207     // call_hash_impl
 208     //
 209
 210     // On compilers without function template ordering, this deals with arrays.
 211
 212 #if defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)
 213     namespace hash_detail
 214     {
 215         template <bool IsArray>
 216         struct call_hash_impl
 217         {
 218             template <class T>
 219             struct inner
 220             {
 221                 static std::size_t call(T const& v)
 222                 {
 223                     using namespace boost;
 224                     return hash_value(v);
 225                 }
 226             };
 227         };
 228
 229         template <>
 230         struct call_hash_impl<true>
 231         {
 232             template <class Array>
 233             struct inner
 234             {
 235 #if !BOOST_WORKAROUND(BOOST_MSVC, < 1300)
 236                 static std::size_t call(Array const& v)
 237 #else
 238                 static std::size_t call(Array& v)
 239 #endif
 240                 {
 241                     const int size = sizeof(v) / sizeof(*v);
 242                     return boost::hash_range(v, v + size);
 243                 }
 244             };
 245         };
 246
 247         template <class T>
 248         struct call_hash
 249             : public call_hash_impl<boost::is_array<T>::value>
 250                 ::BOOST_NESTED_TEMPLATE inner<T>
 251         {
 252         };
 253     }
 254 #endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 255
 256     //
 257     // boost::hash
 258     //
 259
 260
 261 #if !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
 262
 263     template <class T> struct hash
 264         : std::unary_function<T, std::size_t>
 265     {
 266 #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)
 267         std::size_t operator()(T const& val) const
 268         {
 269             return hash_value(val);
 270         }
 271 #else
 272         std::size_t operator()(T const& val) const
 273         {
 274             return hash_detail::call_hash<T>::call(val);
 275         }
 276 #endif
 277     };
 278
 279 #if BOOST_WORKAROUND(__DMC__, <= 0x848)
 280     template <class T, unsigned int n> struct hash<T[n]>
 281         : std::unary_function<T[n], std::size_t>
 282     {
 283         std::size_t operator()(const T* val) const
 284         {
 285             return boost::hash_range(val, val+n);
 286         }
 287     };
 288 #endif
 289
 290 #else // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
 291
 292     // On compilers without partial specialization, boost::hash<T>
 293     // has already been declared to deal with pointers, so just
 294     // need to supply the non-pointer version of hash_impl.
 295
 296     namespace hash_detail
 297     {
 298         template <bool IsPointer>
 299         struct hash_impl;
 300
 301 #if !BOOST_WORKAROUND(BOOST_MSVC, < 1300)
 302
 303         template <>
 304         struct hash_impl<false>
 305         {
 306             template <class T>
 307             struct inner
 308                 : std::unary_function<T, std::size_t>
 309             {
 310 #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)
 311                 std::size_t operator()(T const& val) const
 312                 {
 313                     return hash_value(val);
 314                 }
 315 #else
 316                 std::size_t operator()(T const& val) const
 317                 {
 318                     return hash_detail::call_hash<T>::call(val);
 319                 }
 320 #endif
 321             };
 322         };
 323
 324 #else // Visual C++ 6.5
 325
 326         // Visual C++ 6.5 has problems with nested member functions and
 327         // applying const to const types in templates. So we get this:
 328
 329         template <bool IsConst>
 330         struct hash_impl_msvc
 331         {
 332             template <class T>
 333             struct inner
 334                 : public std::unary_function<T, std::size_t>
 335             {
 336                 std::size_t operator()(T const& val) const
 337                 {
 338                     return hash_detail::call_hash<T const>::call(val);
 339                 }
 340
 341                 std::size_t operator()(T& val) const
 342                 {
 343                     return hash_detail::call_hash<T>::call(val);
 344                 }
 345             };
 346         };
 347
 348         template <>
 349         struct hash_impl_msvc<true>
 350         {
 351             template <class T>
 352             struct inner
 353                 : public std::unary_function<T, std::size_t>
 354             {
 355                 std::size_t operator()(T& val) const
 356                 {
 357                     return hash_detail::call_hash<T>::call(val);
 358                 }
 359             };
 360         };
 361
 362         template <class T>
 363         struct hash_impl_msvc2
 364             : public hash_impl_msvc<boost::is_const<T>::value>
 365                     ::BOOST_NESTED_TEMPLATE inner<T> {};
 366
 367         template <>
 368         struct hash_impl<false>
 369         {
 370             template <class T>
 371             struct inner : public hash_impl_msvc2<T> {};
 372         };
 373
 374 #endif // Visual C++ 6.5
 375     }
 376 #endif  // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
 377 }
 378
 379 #endif