00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035 #ifndef _TR1_FUNCTIONAL_HASH_H
00036 #define _TR1_FUNCTIONAL_HASH_H 1
00037
00038 #include <string>
00039 #include <cmath>
00040
00041 namespace std
00042 {
00043 _GLIBCXX_BEGIN_NAMESPACE(tr1)
00044
00045
00046
00047 template<typename T>
00048 struct hash;
00049
00050 #define _TR1_hashtable_define_trivial_hash(_Tp) \
00051 template<> \
00052 struct hash<_Tp> \
00053 : public std::unary_function<_Tp, std::size_t> \
00054 { \
00055 std::size_t \
00056 operator()(_Tp __val) const \
00057 { return static_cast<std::size_t>(__val); } \
00058 }
00059
00060 _TR1_hashtable_define_trivial_hash(bool);
00061 _TR1_hashtable_define_trivial_hash(char);
00062 _TR1_hashtable_define_trivial_hash(signed char);
00063 _TR1_hashtable_define_trivial_hash(unsigned char);
00064 _TR1_hashtable_define_trivial_hash(wchar_t);
00065 _TR1_hashtable_define_trivial_hash(short);
00066 _TR1_hashtable_define_trivial_hash(int);
00067 _TR1_hashtable_define_trivial_hash(long);
00068 _TR1_hashtable_define_trivial_hash(long long);
00069 _TR1_hashtable_define_trivial_hash(unsigned short);
00070 _TR1_hashtable_define_trivial_hash(unsigned int);
00071 _TR1_hashtable_define_trivial_hash(unsigned long);
00072 _TR1_hashtable_define_trivial_hash(unsigned long long);
00073
00074 #undef _TR1_hashtable_define_trivial_hash
00075
00076 template<typename _Tp>
00077 struct hash<_Tp*>
00078 : public std::unary_function<_Tp*, std::size_t>
00079 {
00080 std::size_t
00081 operator()(_Tp* __p) const
00082 { return reinterpret_cast<std::size_t>(__p); }
00083 };
00084
00085
00086
00087
00088
00089 template<std::size_t = sizeof(std::size_t)>
00090 struct _Fnv_hash
00091 {
00092 static std::size_t
00093 hash(const char* __first, std::size_t __length)
00094 {
00095 std::size_t __result = 0;
00096 for (; __length > 0; --__length)
00097 __result = (__result * 131) + *__first++;
00098 return __result;
00099 }
00100 };
00101
00102 template<>
00103 struct _Fnv_hash<4>
00104 {
00105 static std::size_t
00106 hash(const char* __first, std::size_t __length)
00107 {
00108 std::size_t __result = static_cast<std::size_t>(2166136261UL);
00109 for (; __length > 0; --__length)
00110 {
00111 __result ^= static_cast<std::size_t>(*__first++);
00112 __result *= static_cast<std::size_t>(16777619UL);
00113 }
00114 return __result;
00115 }
00116 };
00117
00118 template<>
00119 struct _Fnv_hash<8>
00120 {
00121 static std::size_t
00122 hash(const char* __first, std::size_t __length)
00123 {
00124 std::size_t __result =
00125 static_cast<std::size_t>(14695981039346656037ULL);
00126 for (; __length > 0; --__length)
00127 {
00128 __result ^= static_cast<std::size_t>(*__first++);
00129 __result *= static_cast<std::size_t>(1099511628211ULL);
00130 }
00131 return __result;
00132 }
00133 };
00134
00135
00136
00137
00138 template<>
00139 struct hash<std::string>
00140 : public std::unary_function<std::string, std::size_t>
00141 {
00142 std::size_t
00143 operator()(const std::string& __s) const
00144 { return _Fnv_hash<>::hash(__s.data(), __s.length()); }
00145 };
00146
00147 #ifdef _GLIBCXX_USE_WCHAR_T
00148 template<>
00149 struct hash<std::wstring>
00150 : public std::unary_function<std::wstring, std::size_t>
00151 {
00152 std::size_t
00153 operator()(const std::wstring& __s) const
00154 {
00155 return _Fnv_hash<>::hash(reinterpret_cast<const char*>(__s.data()),
00156 __s.length() * sizeof(wchar_t));
00157 }
00158 };
00159 #endif
00160
00161 template<>
00162 struct hash<float>
00163 : public std::unary_function<float, std::size_t>
00164 {
00165 std::size_t
00166 operator()(float __fval) const
00167 {
00168 std::size_t __result = 0;
00169
00170
00171 if (__fval != 0.0f)
00172 __result = _Fnv_hash<>::hash(reinterpret_cast<const char*>(&__fval),
00173 sizeof(__fval));
00174 return __result;
00175 }
00176 };
00177
00178 template<>
00179 struct hash<double>
00180 : public std::unary_function<double, std::size_t>
00181 {
00182 std::size_t
00183 operator()(double __dval) const
00184 {
00185 std::size_t __result = 0;
00186
00187
00188 if (__dval != 0.0)
00189 __result = _Fnv_hash<>::hash(reinterpret_cast<const char*>(&__dval),
00190 sizeof(__dval));
00191 return __result;
00192 }
00193 };
00194
00195
00196
00197 template<>
00198 struct hash<long double>
00199 : public std::unary_function<long double, std::size_t>
00200 {
00201 std::size_t
00202 operator()(long double __ldval) const
00203 {
00204 std::size_t __result = 0;
00205
00206 int __exponent;
00207 __ldval = std::frexp(__ldval, &__exponent);
00208 __ldval = __ldval < 0.0l ? -(__ldval + 0.5l) : __ldval;
00209
00210 const long double __mult =
00211 std::numeric_limits<std::size_t>::max() + 1.0l;
00212 __ldval *= __mult;
00213
00214
00215
00216 const std::size_t __hibits = (std::size_t)__ldval;
00217 __ldval = (__ldval - (long double)__hibits) * __mult;
00218
00219 const std::size_t __coeff =
00220 (std::numeric_limits<std::size_t>::max()
00221 / std::numeric_limits<long double>::max_exponent);
00222
00223 __result = __hibits + (std::size_t)__ldval + __coeff * __exponent;
00224
00225 return __result;
00226 }
00227 };
00228
00229 _GLIBCXX_END_NAMESPACE
00230 }
00231
00232 #endif