1 // TR1 functional -*- C++ -*-
3 // Copyright (C) 2007 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 2, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING. If not, write to the Free
18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
21 // As a special exception, you may use this file as part of a free software
22 // library without restriction. Specifically, if other files instantiate
23 // templates or use macros or inline functions from this file, or you compile
24 // this file and link it with other files to produce an executable, this
25 // file does not by itself cause the resulting executable to be covered by
26 // the GNU General Public License. This exception does not however
27 // invalidate any other reasons why the executable file might be covered by
28 // the GNU General Public License.
30 /** @file tr1/functional_hash.h
31 * This is an internal header file, included by other library headers.
32 * You should not attempt to use it directly.
35 #ifndef _TR1_FUNCTIONAL_HASH_H
36 #define _TR1_FUNCTIONAL_HASH_H 1
39 #include <cmath> // for std::frexp
43 _GLIBCXX_BEGIN_NAMESPACE(tr1)
45 // Definition of default hash function std::tr1::hash<>. The types for
46 // which std::tr1::hash<T> is defined is in clause 6.3.3. of the PDTR.
50 #define _TR1_hashtable_define_trivial_hash(_Tp) \
53 : public std::unary_function<_Tp, std::size_t> \
56 operator()(_Tp __val) const \
57 { return static_cast<std::size_t>(__val); } \
60 _TR1_hashtable_define_trivial_hash(bool);
61 _TR1_hashtable_define_trivial_hash(char);
62 _TR1_hashtable_define_trivial_hash(signed char);
63 _TR1_hashtable_define_trivial_hash(unsigned char);
64 _TR1_hashtable_define_trivial_hash(wchar_t);
65 _TR1_hashtable_define_trivial_hash(short);
66 _TR1_hashtable_define_trivial_hash(int);
67 _TR1_hashtable_define_trivial_hash(long);
68 _TR1_hashtable_define_trivial_hash(long long);
69 _TR1_hashtable_define_trivial_hash(unsigned short);
70 _TR1_hashtable_define_trivial_hash(unsigned int);
71 _TR1_hashtable_define_trivial_hash(unsigned long);
72 _TR1_hashtable_define_trivial_hash(unsigned long long);
74 #undef _TR1_hashtable_define_trivial_hash
76 template<typename _Tp>
78 : public std::unary_function<_Tp*, std::size_t>
81 operator()(_Tp* __p) const
82 { return reinterpret_cast<std::size_t>(__p); }
85 // Fowler / Noll / Vo (FNV) Hash (type FNV-1a)
86 // (used by the next specializations of std::tr1::hash<>)
88 // Dummy generic implementation (for sizeof(size_t) != 4, 8).
89 template<std::size_t = sizeof(std::size_t)>
93 hash(const char* __first, std::size_t __length)
95 std::size_t __result = 0;
96 for (; __length > 0; --__length)
97 __result = (__result * 131) + *__first++;
106 hash(const char* __first, std::size_t __length)
108 std::size_t __result = static_cast<std::size_t>(2166136261UL);
109 for (; __length > 0; --__length)
111 __result ^= static_cast<std::size_t>(*__first++);
112 __result *= static_cast<std::size_t>(16777619UL);
122 hash(const char* __first, std::size_t __length)
124 std::size_t __result =
125 static_cast<std::size_t>(14695981039346656037ULL);
126 for (; __length > 0; --__length)
128 __result ^= static_cast<std::size_t>(*__first++);
129 __result *= static_cast<std::size_t>(1099511628211ULL);
135 // XXX String and floating point hashes probably shouldn't be inline
136 // member functions, since are nontrivial. Once we have the framework
137 // for TR1 .cc files, these should go in one.
139 struct hash<std::string>
140 : public std::unary_function<std::string, std::size_t>
143 operator()(const std::string& __s) const
144 { return _Fnv_hash<>::hash(__s.data(), __s.length()); }
147 #ifdef _GLIBCXX_USE_WCHAR_T
149 struct hash<std::wstring>
150 : public std::unary_function<std::wstring, std::size_t>
153 operator()(const std::wstring& __s) const
155 return _Fnv_hash<>::hash(reinterpret_cast<const char*>(__s.data()),
156 __s.length() * sizeof(wchar_t));
163 : public std::unary_function<float, std::size_t>
166 operator()(float __fval) const
168 std::size_t __result = 0;
170 // 0 and -0 both hash to zero.
172 __result = _Fnv_hash<>::hash(reinterpret_cast<const char*>(&__fval),
180 : public std::unary_function<double, std::size_t>
183 operator()(double __dval) const
185 std::size_t __result = 0;
187 // 0 and -0 both hash to zero.
189 __result = _Fnv_hash<>::hash(reinterpret_cast<const char*>(&__dval),
195 // For long double, careful with random padding bits (e.g., on x86,
196 // 10 bytes -> 12 bytes) and resort to frexp.
198 struct hash<long double>
199 : public std::unary_function<long double, std::size_t>
202 operator()(long double __ldval) const
204 std::size_t __result = 0;
207 __ldval = std::frexp(__ldval, &__exponent);
208 __ldval = __ldval < 0.0l ? -(__ldval + 0.5l) : __ldval;
210 const long double __mult =
211 std::numeric_limits<std::size_t>::max() + 1.0l;
214 // Try to use all the bits of the mantissa (really necessary only
215 // on 32-bit targets, at least for 80-bit floating point formats).
216 const std::size_t __hibits = (std::size_t)__ldval;
217 __ldval = (__ldval - (long double)__hibits) * __mult;
219 const std::size_t __coeff =
220 (std::numeric_limits<std::size_t>::max()
221 / std::numeric_limits<long double>::max_exponent);
223 __result = __hibits + (std::size_t)__ldval + __coeff * __exponent;
229 _GLIBCXX_END_NAMESPACE