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