1 // functional_hash.h header -*- C++ -*- 2 3 // Copyright (C) 2007-2018 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 * Do not attempt to use it directly. @headername{functional} 28 */ 29 30 #ifndef _FUNCTIONAL_HASH_H 31 #define _FUNCTIONAL_HASH_H 1 32 33 #pragma GCC system_header 34 35 #include <bits/hash_bytes.h> 36 37 namespace std _GLIBCXX_VISIBILITY(default) 38 { 39 _GLIBCXX_BEGIN_NAMESPACE_VERSION 40 41 /** @defgroup hashes Hashes 42 * @ingroup functors 43 * 44 * Hashing functors taking a variable type and returning a @c std::size_t. 45 * 46 * @{ 47 */ 48 49 template<typename _Result, typename _Arg> 50 struct __hash_base 51 { 52 typedef _Result result_type _GLIBCXX17_DEPRECATED; 53 typedef _Arg argument_type _GLIBCXX17_DEPRECATED; 54 }; 55 56 /// Primary class template hash. 57 template<typename _Tp> 58 struct hash; 59 60 template<typename _Tp, typename = void> 61 struct __poison_hash 62 { 63 static constexpr bool __enable_hash_call = false; 64 private: 65 // Private rather than deleted to be non-trivially-copyable. 66 __poison_hash(__poison_hash&&); 67 ~__poison_hash(); 68 }; 69 70 template<typename _Tp> 71 struct __poison_hash<_Tp, __void_t<decltype(hash<_Tp>()(declval<_Tp>()))>> 72 { 73 static constexpr bool __enable_hash_call = true; 74 }; 75 76 // Helper struct for SFINAE-poisoning non-enum types. 77 template<typename _Tp, bool = is_enum<_Tp>::value> 78 struct __hash_enum 79 { 80 private: 81 // Private rather than deleted to be non-trivially-copyable. 82 __hash_enum(__hash_enum&&); 83 ~__hash_enum(); 84 }; 85 86 // Helper struct for hash with enum types. 87 template<typename _Tp> 88 struct __hash_enum<_Tp, true> : public __hash_base<size_t, _Tp> 89 { 90 size_t 91 operator()(_Tp __val) const noexcept 92 { 93 using __type = typename underlying_type<_Tp>::type; 94 return hash<__type>{}(static_cast<__type>(__val)); 95 } 96 }; 97 98 /// Primary class template hash, usable for enum types only. 99 // Use with non-enum types still SFINAES. 100 template<typename _Tp> 101 struct hash : __hash_enum<_Tp> 102 { }; 103 104 /// Partial specializations for pointer types. 105 template<typename _Tp> 106 struct hash<_Tp*> : public __hash_base<size_t, _Tp*> 107 { 108 size_t 109 operator()(_Tp* __p) const noexcept 110 { return reinterpret_cast<size_t>(__p); } 111 }; 112 113 // Explicit specializations for integer types. 114 #define _Cxx_hashtable_define_trivial_hash(_Tp) \ 115 template<> \ 116 struct hash<_Tp> : public __hash_base<size_t, _Tp> \ 117 { \ 118 size_t \ 119 operator()(_Tp __val) const noexcept \ 120 { return static_cast<size_t>(__val); } \ 121 }; 122 123 /// Explicit specialization for bool. 124 _Cxx_hashtable_define_trivial_hash(bool) 125 126 /// Explicit specialization for char. 127 _Cxx_hashtable_define_trivial_hash(char) 128 129 /// Explicit specialization for signed char. 130 _Cxx_hashtable_define_trivial_hash(signed char) 131 132 /// Explicit specialization for unsigned char. 133 _Cxx_hashtable_define_trivial_hash(unsigned char) 134 135 /// Explicit specialization for wchar_t. 136 _Cxx_hashtable_define_trivial_hash(wchar_t) 137 138 /// Explicit specialization for char16_t. 139 _Cxx_hashtable_define_trivial_hash(char16_t) 140 141 /// Explicit specialization for char32_t. 142 _Cxx_hashtable_define_trivial_hash(char32_t) 143 144 /// Explicit specialization for short. 145 _Cxx_hashtable_define_trivial_hash(short) 146 147 /// Explicit specialization for int. 148 _Cxx_hashtable_define_trivial_hash(int) 149 150 /// Explicit specialization for long. 151 _Cxx_hashtable_define_trivial_hash(long) 152 153 /// Explicit specialization for long long. 154 _Cxx_hashtable_define_trivial_hash(long long) 155 156 /// Explicit specialization for unsigned short. 157 _Cxx_hashtable_define_trivial_hash(unsigned short) 158 159 /// Explicit specialization for unsigned int. 160 _Cxx_hashtable_define_trivial_hash(unsigned int) 161 162 /// Explicit specialization for unsigned long. 163 _Cxx_hashtable_define_trivial_hash(unsigned long) 164 165 /// Explicit specialization for unsigned long long. 166 _Cxx_hashtable_define_trivial_hash(unsigned long long) 167 168 #ifdef __GLIBCXX_TYPE_INT_N_0 169 _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_0) 170 _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_0 unsigned) 171 #endif 172 #ifdef __GLIBCXX_TYPE_INT_N_1 173 _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_1) 174 _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_1 unsigned) 175 #endif 176 #ifdef __GLIBCXX_TYPE_INT_N_2 177 _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_2) 178 _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_2 unsigned) 179 #endif 180 #ifdef __GLIBCXX_TYPE_INT_N_3 181 _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_3) 182 _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_3 unsigned) 183 #endif 184 185 #undef _Cxx_hashtable_define_trivial_hash 186 187 struct _Hash_impl 188 { 189 static size_t 190 hash(const void* __ptr, size_t __clength, 191 size_t __seed = static_cast<size_t>(0xc70f6907UL)) 192 { return _Hash_bytes(__ptr, __clength, __seed); } 193 194 template<typename _Tp> 195 static size_t 196 hash(const _Tp& __val) 197 { return hash(&__val, sizeof(__val)); } 198 199 template<typename _Tp> 200 static size_t 201 __hash_combine(const _Tp& __val, size_t __hash) 202 { return hash(&__val, sizeof(__val), __hash); } 203 }; 204 205 // A hash function similar to FNV-1a (see PR59406 for how it differs). 206 struct _Fnv_hash_impl 207 { 208 static size_t 209 hash(const void* __ptr, size_t __clength, 210 size_t __seed = static_cast<size_t>(2166136261UL)) 211 { return _Fnv_hash_bytes(__ptr, __clength, __seed); } 212 213 template<typename _Tp> 214 static size_t 215 hash(const _Tp& __val) 216 { return hash(&__val, sizeof(__val)); } 217 218 template<typename _Tp> 219 static size_t 220 __hash_combine(const _Tp& __val, size_t __hash) 221 { return hash(&__val, sizeof(__val), __hash); } 222 }; 223 224 /// Specialization for float. 225 template<> 226 struct hash<float> : public __hash_base<size_t, float> 227 { 228 size_t 229 operator()(float __val) const noexcept 230 { 231 // 0 and -0 both hash to zero. 232 return __val != 0.0f ? std::_Hash_impl::hash(__val) : 0; 233 } 234 }; 235 236 /// Specialization for double. 237 template<> 238 struct hash<double> : public __hash_base<size_t, double> 239 { 240 size_t 241 operator()(double __val) const noexcept 242 { 243 // 0 and -0 both hash to zero. 244 return __val != 0.0 ? std::_Hash_impl::hash(__val) : 0; 245 } 246 }; 247 248 /// Specialization for long double. 249 template<> 250 struct hash<long double> 251 : public __hash_base<size_t, long double> 252 { 253 _GLIBCXX_PURE size_t 254 operator()(long double __val) const noexcept; 255 }; 256 257 // @} group hashes 258 259 // Hint about performance of hash functor. If not fast the hash-based 260 // containers will cache the hash code. 261 // Default behavior is to consider that hashers are fast unless specified 262 // otherwise. 263 template<typename _Hash> 264 struct __is_fast_hash : public std::true_type 265 { }; 266 267 template<> 268 struct __is_fast_hash<hash<long double>> : public std::false_type 269 { }; 270 271 _GLIBCXX_END_NAMESPACE_VERSION 272 } // namespace 273 274 #endif // _FUNCTIONAL_HASH_H 275