1 // functional_hash.h header -*- C++ -*- 2 3 // Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc. 4 // 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 3, or (at your option) 9 // any later version. 10 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. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /** @file bits/functional_hash.h 26 * This is an internal header file, included by other library headers. 27 * You should not attempt to use it directly. 28 */ 29 30 #ifndef _FUNCTIONAL_HASH_H 31 #define _FUNCTIONAL_HASH_H 1 32 33 #pragma GCC system_header 34 35 #include <cstddef> 36 #include <bits/stl_function.h> 37 38 namespace std 39 { 40 /** @defgroup hashes Hashes 41 * @ingroup functors 42 * 43 * Hashing functors taking a variable type and returning a @c std::size_t. 44 * 45 * @{ 46 */ 47 48 /// Primary class template hash. 49 template<typename _Tp> 50 struct hash : public std::unary_function<_Tp, size_t> 51 { 52 size_t 53 operator()(_Tp __val) const; 54 }; 55 56 /// Partial specializations for pointer types. 57 template<typename _Tp> 58 struct hash<_Tp*> : public std::unary_function<_Tp*, size_t> 59 { 60 size_t 61 operator()(_Tp* __p) const 62 { return reinterpret_cast<size_t>(__p); } 63 }; 64 65 // Explicit specializations for integer types. 66 #define _Cxx_hashtable_define_trivial_hash(_Tp) \ 67 template<> \ 68 inline size_t \ 69 hash<_Tp>::operator()(_Tp __val) const \ 70 { return static_cast<size_t>(__val); } 71 72 /// Explicit specialization for bool. 73 _Cxx_hashtable_define_trivial_hash(bool); 74 75 /// Explicit specialization for char. 76 _Cxx_hashtable_define_trivial_hash(char); 77 78 /// Explicit specialization for signed char. 79 _Cxx_hashtable_define_trivial_hash(signed char); 80 81 /// Explicit specialization for unsigned char. 82 _Cxx_hashtable_define_trivial_hash(unsigned char); 83 84 /// Explicit specialization for wchar_t. 85 _Cxx_hashtable_define_trivial_hash(wchar_t); 86 87 /// Explicit specialization for char16_t. 88 _Cxx_hashtable_define_trivial_hash(char16_t); 89 90 /// Explicit specialization for char32_t. 91 _Cxx_hashtable_define_trivial_hash(char32_t); 92 93 /// Explicit specialization for short. 94 _Cxx_hashtable_define_trivial_hash(short); 95 96 /// Explicit specialization for int. 97 _Cxx_hashtable_define_trivial_hash(int); 98 99 /// Explicit specialization for long. 100 _Cxx_hashtable_define_trivial_hash(long); 101 102 /// Explicit specialization for long long. 103 _Cxx_hashtable_define_trivial_hash(long long); 104 105 /// Explicit specialization for unsigned short. 106 _Cxx_hashtable_define_trivial_hash(unsigned short); 107 108 /// Explicit specialization for unsigned int. 109 _Cxx_hashtable_define_trivial_hash(unsigned int); 110 111 /// Explicit specialization for unsigned long. 112 _Cxx_hashtable_define_trivial_hash(unsigned long); 113 114 /// Explicit specialization for unsigned long long. 115 _Cxx_hashtable_define_trivial_hash(unsigned long long); 116 117 #undef _Cxx_hashtable_define_trivial_hash 118 119 // Fowler / Noll / Vo (FNV) Hash (type FNV-1a) 120 121 // Dummy generic implementation (for sizeof(size_t) != 4, 8). 122 template<size_t> 123 struct _Fnv_hash_base 124 { 125 template<typename _Tp> 126 static size_t 127 hash(const _Tp* __ptr, size_t __clength, size_t __hash = 0) 128 { 129 const char* __cptr = reinterpret_cast<const char*>(__ptr); 130 for (; __clength; --__clength) 131 __hash = (__hash * 131) + *__cptr++; 132 return __hash; 133 } 134 }; 135 136 template<> 137 struct _Fnv_hash_base<4> 138 { 139 template<typename _Tp> 140 static size_t 141 hash(const _Tp* __ptr, size_t __clength, 142 size_t __hash = static_cast<size_t>(2166136261UL)) 143 { 144 const char* __cptr = reinterpret_cast<const char*>(__ptr); 145 for (; __clength; --__clength) 146 { 147 __hash ^= static_cast<size_t>(*__cptr++); 148 __hash *= static_cast<size_t>(16777619UL); 149 } 150 return __hash; 151 } 152 }; 153 154 template<> 155 struct _Fnv_hash_base<8> 156 { 157 template<typename _Tp> 158 static size_t 159 hash(const _Tp* __ptr, size_t __clength, 160 size_t __hash = static_cast<size_t>(14695981039346656037ULL)) 161 { 162 const char* __cptr = reinterpret_cast<const char*>(__ptr); 163 for (; __clength; --__clength) 164 { 165 __hash ^= static_cast<size_t>(*__cptr++); 166 __hash *= static_cast<size_t>(1099511628211ULL); 167 } 168 return __hash; 169 } 170 }; 171 172 struct _Fnv_hash 173 : public _Fnv_hash_base<sizeof(size_t)> 174 { 175 using _Fnv_hash_base<sizeof(size_t)>::hash; 176 177 template<typename _Tp> 178 static size_t 179 hash(const _Tp& __val) 180 { return hash(&__val, sizeof(__val)); } 181 182 template<typename _Tp> 183 static size_t 184 __hash_combine(const _Tp& __val, size_t __hash) 185 { return hash(&__val, sizeof(__val), __hash); } 186 }; 187 188 /// Specialization for float. 189 template<> 190 inline size_t 191 hash<float>::operator()(float __val) const 192 { 193 // 0 and -0 both hash to zero. 194 return __val != 0.0f ? std::_Fnv_hash::hash(__val) : 0; 195 } 196 197 /// Specialization for double. 198 template<> 199 inline size_t 200 hash<double>::operator()(double __val) const 201 { 202 // 0 and -0 both hash to zero. 203 return __val != 0.0 ? std::_Fnv_hash::hash(__val) : 0; 204 } 205 206 /// Specialization for long double. 207 template<> 208 _GLIBCXX_PURE size_t 209 hash<long double>::operator()(long double __val) const; 210 211 // @} group hashes 212 } 213 214 #endif // _FUNCTIONAL_HASH_H 215