libstdc++
|
00001 // functional_hash.h header -*- C++ -*- 00002 00003 // Copyright (C) 2007-2019 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** @file bits/functional_hash.h 00026 * This is an internal header file, included by other library headers. 00027 * Do not attempt to use it directly. @headername{functional} 00028 */ 00029 00030 #ifndef _FUNCTIONAL_HASH_H 00031 #define _FUNCTIONAL_HASH_H 1 00032 00033 #pragma GCC system_header 00034 00035 #include <bits/hash_bytes.h> 00036 00037 namespace std _GLIBCXX_VISIBILITY(default) 00038 { 00039 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00040 00041 /** @defgroup hashes Hashes 00042 * @ingroup functors 00043 * 00044 * Hashing functors taking a variable type and returning a @c std::size_t. 00045 * 00046 * @{ 00047 */ 00048 00049 template<typename _Result, typename _Arg> 00050 struct __hash_base 00051 { 00052 typedef _Result result_type _GLIBCXX17_DEPRECATED; 00053 typedef _Arg argument_type _GLIBCXX17_DEPRECATED; 00054 }; 00055 00056 /// Primary class template hash. 00057 template<typename _Tp> 00058 struct hash; 00059 00060 template<typename _Tp, typename = void> 00061 struct __poison_hash 00062 { 00063 static constexpr bool __enable_hash_call = false; 00064 private: 00065 // Private rather than deleted to be non-trivially-copyable. 00066 __poison_hash(__poison_hash&&); 00067 ~__poison_hash(); 00068 }; 00069 00070 template<typename _Tp> 00071 struct __poison_hash<_Tp, __void_t<decltype(hash<_Tp>()(declval<_Tp>()))>> 00072 { 00073 static constexpr bool __enable_hash_call = true; 00074 }; 00075 00076 // Helper struct for SFINAE-poisoning non-enum types. 00077 template<typename _Tp, bool = is_enum<_Tp>::value> 00078 struct __hash_enum 00079 { 00080 private: 00081 // Private rather than deleted to be non-trivially-copyable. 00082 __hash_enum(__hash_enum&&); 00083 ~__hash_enum(); 00084 }; 00085 00086 // Helper struct for hash with enum types. 00087 template<typename _Tp> 00088 struct __hash_enum<_Tp, true> : public __hash_base<size_t, _Tp> 00089 { 00090 size_t 00091 operator()(_Tp __val) const noexcept 00092 { 00093 using __type = typename underlying_type<_Tp>::type; 00094 return hash<__type>{}(static_cast<__type>(__val)); 00095 } 00096 }; 00097 00098 /// Primary class template hash, usable for enum types only. 00099 // Use with non-enum types still SFINAES. 00100 template<typename _Tp> 00101 struct hash : __hash_enum<_Tp> 00102 { }; 00103 00104 /// Partial specializations for pointer types. 00105 template<typename _Tp> 00106 struct hash<_Tp*> : public __hash_base<size_t, _Tp*> 00107 { 00108 size_t 00109 operator()(_Tp* __p) const noexcept 00110 { return reinterpret_cast<size_t>(__p); } 00111 }; 00112 00113 // Explicit specializations for integer types. 00114 #define _Cxx_hashtable_define_trivial_hash(_Tp) \ 00115 template<> \ 00116 struct hash<_Tp> : public __hash_base<size_t, _Tp> \ 00117 { \ 00118 size_t \ 00119 operator()(_Tp __val) const noexcept \ 00120 { return static_cast<size_t>(__val); } \ 00121 }; 00122 00123 /// Explicit specialization for bool. 00124 _Cxx_hashtable_define_trivial_hash(bool) 00125 00126 /// Explicit specialization for char. 00127 _Cxx_hashtable_define_trivial_hash(char) 00128 00129 /// Explicit specialization for signed char. 00130 _Cxx_hashtable_define_trivial_hash(signed char) 00131 00132 /// Explicit specialization for unsigned char. 00133 _Cxx_hashtable_define_trivial_hash(unsigned char) 00134 00135 /// Explicit specialization for wchar_t. 00136 _Cxx_hashtable_define_trivial_hash(wchar_t) 00137 00138 #ifdef _GLIBCXX_USE_CHAR8_T 00139 /// Explicit specialization for char8_t. 00140 _Cxx_hashtable_define_trivial_hash(char8_t) 00141 #endif 00142 00143 /// Explicit specialization for char16_t. 00144 _Cxx_hashtable_define_trivial_hash(char16_t) 00145 00146 /// Explicit specialization for char32_t. 00147 _Cxx_hashtable_define_trivial_hash(char32_t) 00148 00149 /// Explicit specialization for short. 00150 _Cxx_hashtable_define_trivial_hash(short) 00151 00152 /// Explicit specialization for int. 00153 _Cxx_hashtable_define_trivial_hash(int) 00154 00155 /// Explicit specialization for long. 00156 _Cxx_hashtable_define_trivial_hash(long) 00157 00158 /// Explicit specialization for long long. 00159 _Cxx_hashtable_define_trivial_hash(long long) 00160 00161 /// Explicit specialization for unsigned short. 00162 _Cxx_hashtable_define_trivial_hash(unsigned short) 00163 00164 /// Explicit specialization for unsigned int. 00165 _Cxx_hashtable_define_trivial_hash(unsigned int) 00166 00167 /// Explicit specialization for unsigned long. 00168 _Cxx_hashtable_define_trivial_hash(unsigned long) 00169 00170 /// Explicit specialization for unsigned long long. 00171 _Cxx_hashtable_define_trivial_hash(unsigned long long) 00172 00173 #ifdef __GLIBCXX_TYPE_INT_N_0 00174 _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_0) 00175 _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_0 unsigned) 00176 #endif 00177 #ifdef __GLIBCXX_TYPE_INT_N_1 00178 _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_1) 00179 _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_1 unsigned) 00180 #endif 00181 #ifdef __GLIBCXX_TYPE_INT_N_2 00182 _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_2) 00183 _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_2 unsigned) 00184 #endif 00185 #ifdef __GLIBCXX_TYPE_INT_N_3 00186 _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_3) 00187 _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_3 unsigned) 00188 #endif 00189 00190 #undef _Cxx_hashtable_define_trivial_hash 00191 00192 struct _Hash_impl 00193 { 00194 static size_t 00195 hash(const void* __ptr, size_t __clength, 00196 size_t __seed = static_cast<size_t>(0xc70f6907UL)) 00197 { return _Hash_bytes(__ptr, __clength, __seed); } 00198 00199 template<typename _Tp> 00200 static size_t 00201 hash(const _Tp& __val) 00202 { return hash(&__val, sizeof(__val)); } 00203 00204 template<typename _Tp> 00205 static size_t 00206 __hash_combine(const _Tp& __val, size_t __hash) 00207 { return hash(&__val, sizeof(__val), __hash); } 00208 }; 00209 00210 // A hash function similar to FNV-1a (see PR59406 for how it differs). 00211 struct _Fnv_hash_impl 00212 { 00213 static size_t 00214 hash(const void* __ptr, size_t __clength, 00215 size_t __seed = static_cast<size_t>(2166136261UL)) 00216 { return _Fnv_hash_bytes(__ptr, __clength, __seed); } 00217 00218 template<typename _Tp> 00219 static size_t 00220 hash(const _Tp& __val) 00221 { return hash(&__val, sizeof(__val)); } 00222 00223 template<typename _Tp> 00224 static size_t 00225 __hash_combine(const _Tp& __val, size_t __hash) 00226 { return hash(&__val, sizeof(__val), __hash); } 00227 }; 00228 00229 /// Specialization for float. 00230 template<> 00231 struct hash<float> : public __hash_base<size_t, float> 00232 { 00233 size_t 00234 operator()(float __val) const noexcept 00235 { 00236 // 0 and -0 both hash to zero. 00237 return __val != 0.0f ? std::_Hash_impl::hash(__val) : 0; 00238 } 00239 }; 00240 00241 /// Specialization for double. 00242 template<> 00243 struct hash<double> : public __hash_base<size_t, double> 00244 { 00245 size_t 00246 operator()(double __val) const noexcept 00247 { 00248 // 0 and -0 both hash to zero. 00249 return __val != 0.0 ? std::_Hash_impl::hash(__val) : 0; 00250 } 00251 }; 00252 00253 /// Specialization for long double. 00254 template<> 00255 struct hash<long double> 00256 : public __hash_base<size_t, long double> 00257 { 00258 _GLIBCXX_PURE size_t 00259 operator()(long double __val) const noexcept; 00260 }; 00261 00262 #if __cplusplus >= 201703L 00263 template<> 00264 struct hash<nullptr_t> : public __hash_base<size_t, nullptr_t> 00265 { 00266 size_t 00267 operator()(nullptr_t) const noexcept 00268 { return 0; } 00269 }; 00270 #endif 00271 00272 // @} group hashes 00273 00274 // Hint about performance of hash functor. If not fast the hash-based 00275 // containers will cache the hash code. 00276 // Default behavior is to consider that hashers are fast unless specified 00277 // otherwise. 00278 template<typename _Hash> 00279 struct __is_fast_hash : public std::true_type 00280 { }; 00281 00282 template<> 00283 struct __is_fast_hash<hash<long double>> : public std::false_type 00284 { }; 00285 00286 _GLIBCXX_END_NAMESPACE_VERSION 00287 } // namespace 00288 00289 #endif // _FUNCTIONAL_HASH_H