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