1 | // functional_hash.h header -*- C++ -*- |
2 | |
3 | // Copyright (C) 2007-2017 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; |
53 | typedef _Arg argument_type; |
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 | |