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