Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / functional / hash / hash.hpp
1
2 //  (C) Copyright Daniel James 2005.
3 //  Use, modification and distribution are subject to the
4 //  Boost Software License, Version 1.0. (See accompanying file
5 //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 //
7 //  Based on Peter Dimov's proposal
8 //  http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1756.pdf
9 //  issue 6.18. 
10
11 #if !defined(BOOST_FUNCTIONAL_HASH_HASH_HPP)
12 #define BOOST_FUNCTIONAL_HASH_HASH_HPP
13
14 #if defined(_MSC_VER) && (_MSC_VER >= 1020)
15 # pragma once
16 #endif
17
18 #include <boost/config.hpp>
19 #include <cstddef>
20 #include <cmath>
21 #include <string>
22 #include <functional>
23 #include <errno.h>
24 #include <boost/limits.hpp>
25 #include <boost/functional/detail/float_functions.hpp>
26 #include <boost/detail/workaround.hpp>
27
28 #if defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)
29 #include <boost/type_traits/is_array.hpp>
30 #endif
31
32 namespace boost
33 {
34 #if defined(__BORLANDC__)
35     // Borland complains about an ambiguous function overload
36     // when compiling boost::hash<bool>.
37     std::size_t hash_value(bool);
38 #endif
39     
40     std::size_t hash_value(int);
41     std::size_t hash_value(unsigned int);
42     std::size_t hash_value(long);
43     std::size_t hash_value(unsigned long);
44
45     template <class T> std::size_t hash_value(T* const&);
46
47 #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)
48     template< class T, unsigned N >
49     std::size_t hash_value(const T (&array)[N]);
50
51     template< class T, unsigned N >
52     std::size_t hash_value(T (&array)[N]);
53 #endif
54
55     std::size_t hash_value(float v);
56     std::size_t hash_value(double v);
57     std::size_t hash_value(long double v);
58
59 #if BOOST_WORKAROUND(__GNUC__, < 3) && !defined(__SGI_STL_PORT) && !defined(_STLPORT_VERSION)
60     template <class Ch, class A>
61     std::size_t hash_value(std::basic_string<Ch, std::string_char_traits<Ch>, A> const&);
62 #else
63     template <class Ch, class A>
64     std::size_t hash_value(std::basic_string<Ch, std::char_traits<Ch>, A> const&);
65 #endif
66
67     template <class It> std::size_t hash_range(It first, It last);
68     template <class It> void hash_range(std::size_t&, It first, It last);
69 #if defined(__BORLANDC__)
70     template <class T> inline std::size_t hash_range(T*, T*);
71     template <class T> inline void hash_range(std::size_t&, T*, T*);
72 #endif
73
74 #if defined(BOOST_MSVC) && BOOST_MSVC < 1300
75     template <class T> void hash_combine(std::size_t& seed, T& v);
76 #else
77     template <class T> void hash_combine(std::size_t& seed, T const& v);
78 #endif
79
80     // Implementation
81
82 #if defined(__BORLANDC__)
83     inline std::size_t hash_value(bool v)
84     {
85         return static_cast<std::size_t>(v);
86     }
87 #endif
88
89     inline std::size_t hash_value(int v)
90     {
91         return static_cast<std::size_t>(v);
92     }
93
94     inline std::size_t hash_value(unsigned int v)
95     {
96         return static_cast<std::size_t>(v);
97     }
98
99     inline std::size_t hash_value(long v)
100     {
101         return static_cast<std::size_t>(v);
102     }
103
104     inline std::size_t hash_value(unsigned long v)
105     {
106         return static_cast<std::size_t>(v);
107     }
108
109     // Implementation by Alberto Barbati and Dave Harris.
110     template <class T> std::size_t hash_value(T* const& v)
111     {
112         std::size_t x = static_cast<std::size_t>(
113            reinterpret_cast<std::ptrdiff_t>(v));
114         return x + (x >> 3);
115     }
116
117     namespace hash_detail
118     {
119 #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)
120         // This allows boost::hash to be specialised for classes in the
121         // standard namespace. It appears that a strict two phase template
122         // implementation only finds overloads that are in the current
123         // namespace at the point of definition (at instantiation
124         // it only finds new overloads via. ADL on the dependant paramters or
125         // something like that).
126         template <class T>
127         struct call_hash
128         {
129             static std::size_t call(T const& v)
130             {
131                 using namespace boost;
132                 return hash_value(v);
133             }
134         };
135 #else // BOOST_NO_FUNCTION_TEMPLATE_ORDERING
136         template <bool IsArray>
137         struct call_hash_impl
138         {
139             template <class T>
140             struct inner
141             {
142                 static std::size_t call(T const& v)
143                 {
144                     using namespace boost;
145                     return hash_value(v);
146                 }
147             };
148         };
149
150         template <>
151         struct call_hash_impl<true>
152         {
153             template <class Array>
154             struct inner
155             {
156 #if defined(BOOST_MSVC) && BOOST_MSVC < 1300
157                 static std::size_t call(Array& v)
158 #else
159                 static std::size_t call(Array const& v)
160 #endif
161                 {
162                     const int size = sizeof(v) / sizeof(*v);
163                     return boost::hash_range(v, v + size);
164                 }
165             };
166         };
167
168         template <class T>
169         struct call_hash
170             : public call_hash_impl<boost::is_array<T>::value>
171                 ::BOOST_NESTED_TEMPLATE inner<T>
172         {
173         };
174 #endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING
175     }
176
177 #if defined(BOOST_MSVC) && BOOST_MSVC < 1300
178     template <class T>
179     inline void hash_combine(std::size_t& seed, T& v)
180 #else
181     template <class T>
182     inline void hash_combine(std::size_t& seed, T const& v)
183 #endif
184     {
185         seed ^= hash_detail::call_hash<T>::call(v)
186             + 0x9e3779b9 + (seed<<6) + (seed>>2);
187     }
188
189     template <class It>
190     inline std::size_t hash_range(It first, It last)
191     {
192         std::size_t seed = 0;
193
194         for(; first != last; ++first)
195         {
196             hash_combine(seed, *first);
197         }
198
199         return seed;
200     }
201
202     template <class It>
203     inline void hash_range(std::size_t& seed, It first, It last)
204     {
205         for(; first != last; ++first)
206         {
207             hash_combine(seed, *first);
208         }
209     }
210
211 #if defined(__BORLANDC__)
212     template <class T>
213     inline std::size_t hash_range(T* first, T* last)
214     {
215         std::size_t seed = 0;
216
217         for(; first != last; ++first)
218         {
219             seed ^= hash_detail::call_hash<T>::call(*first)
220                 + 0x9e3779b9 + (seed<<6) + (seed>>2);
221         }
222
223         return seed;
224     }
225
226     template <class T>
227     inline void hash_range(std::size_t& seed, T* first, T* last)
228     {
229         for(; first != last; ++first)
230         {
231             seed ^= hash_detail::call_hash<T>::call(*first)
232                 + 0x9e3779b9 + (seed<<6) + (seed>>2);
233         }
234     }
235 #endif
236
237 #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)
238     template< class T, unsigned N >
239     inline std::size_t hash_value(const T (&array)[N])
240     {
241         return hash_range(array, array + N);
242     }
243
244     template< class T, unsigned N >
245     inline std::size_t hash_value(T (&array)[N])
246     {
247         return hash_range(array, array + N);
248     }
249 #endif
250
251 #if BOOST_WORKAROUND(__GNUC__, < 3) && !defined(__SGI_STL_PORT) && !defined(_STLPORT_VERSION)
252     template <class Ch, class A>
253     inline std::size_t hash_value(std::basic_string<Ch, std::string_char_traits<Ch>, A> const& v)
254 #else
255     template <class Ch, class A>
256     inline std::size_t hash_value(std::basic_string<Ch, std::char_traits<Ch>, A> const& v)
257 #endif
258     {
259         return hash_range(v.begin(), v.end());
260     }
261
262     namespace hash_detail
263     {
264         template <class T>
265         inline std::size_t float_hash_value(T v)
266         {
267             int exp = 0;
268             errno = 0;
269             v = boost::hash_detail::call_frexp(v, &exp);
270             if(errno) return 0;
271
272             std::size_t seed = 0;
273
274             std::size_t const length
275                 = (std::numeric_limits<T>::digits +
276                         std::numeric_limits<int>::digits - 1)
277                 / std::numeric_limits<int>::digits;
278
279             for(std::size_t i = 0; i < length; ++i)
280             {
281                 v = boost::hash_detail::call_ldexp(v, std::numeric_limits<int>::digits);
282                 int const part = static_cast<int>(v);
283                 v -= part;
284                 boost::hash_combine(seed, part);
285             }
286
287             boost::hash_combine(seed, exp);
288
289             return seed;
290         }
291     }
292
293     inline std::size_t hash_value(float v)
294     {
295         return boost::hash_detail::float_hash_value(v);
296     }
297
298     inline std::size_t hash_value(double v)
299     {
300         return boost::hash_detail::float_hash_value(v);
301     }
302
303     inline std::size_t hash_value(long double v)
304     {
305         return boost::hash_detail::float_hash_value(v);
306     }
307
308     // boost::hash
309
310     template <class T> struct hash
311         : std::unary_function<T, std::size_t>
312     {
313         std::size_t operator()(T const& val) const
314         {
315             return hash_detail::call_hash<T>::call(val);
316         }
317
318 #if defined(BOOST_MSVC) && BOOST_MSVC < 1300
319         std::size_t operator()(T& val) const
320         {
321             return hash_detail::call_hash<T>::call(val);
322         }
323 #endif        
324     };
325 }
326
327 #endif
328