source: NonGTP/Boost/boost/functional/hash/hash.hpp @ 857

Revision 857, 9.0 KB checked in by igarcia, 19 years ago (diff)
RevLine 
[857]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
32namespace 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
Note: See TracBrowser for help on using the repository browser.