1 | // functional_hash.h header -*- C++ -*- |
---|---|

2 | |

3 | // Copyright (C) 2007-2021 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 <type_traits> |

36 | #include <bits/hash_bytes.h> |

37 | |

38 | namespace std _GLIBCXX_VISIBILITY(default) |

39 | { |

40 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |

41 | |

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 | */ |

49 | |

50 | template<typename _Result, typename _Arg> |

51 | struct __hash_base |

52 | { |

53 | typedef _Result result_type _GLIBCXX17_DEPRECATED; |

54 | typedef _Arg argument_type _GLIBCXX17_DEPRECATED; |

55 | }; |

56 | |

57 | /// Primary class template hash. |

58 | template<typename _Tp> |

59 | struct hash; |

60 | |

61 | template<typename _Tp, typename = void> |

62 | struct __poison_hash |

63 | { |

64 | static constexpr bool __enable_hash_call = false; |

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 | { |

74 | static constexpr bool __enable_hash_call = true; |

75 | }; |

76 | |

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 | |

105 | /// Partial specializations for pointer types. |

106 | template<typename _Tp> |

107 | struct hash<_Tp*> : public __hash_base<size_t, _Tp*> |

108 | { |

109 | size_t |

110 | operator()(_Tp* __p) const noexcept |

111 | { return reinterpret_cast<size_t>(__p); } |

112 | }; |

113 | |

114 | // Explicit specializations for integer types. |

115 | #define _Cxx_hashtable_define_trivial_hash(_Tp) \ |

116 | template<> \ |

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 | }; |

123 | |

124 | /// Explicit specialization for bool. |

125 | _Cxx_hashtable_define_trivial_hash(bool) |

126 | |

127 | /// Explicit specialization for char. |

128 | _Cxx_hashtable_define_trivial_hash(char) |

129 | |

130 | /// Explicit specialization for signed char. |

131 | _Cxx_hashtable_define_trivial_hash(signed char) |

132 | |

133 | /// Explicit specialization for unsigned char. |

134 | _Cxx_hashtable_define_trivial_hash(unsigned char) |

135 | |

136 | /// Explicit specialization for wchar_t. |

137 | _Cxx_hashtable_define_trivial_hash(wchar_t) |

138 | |

139 | #ifdef _GLIBCXX_USE_CHAR8_T |

140 | /// Explicit specialization for char8_t. |

141 | _Cxx_hashtable_define_trivial_hash(char8_t) |

142 | #endif |

143 | |

144 | /// Explicit specialization for char16_t. |

145 | _Cxx_hashtable_define_trivial_hash(char16_t) |

146 | |

147 | /// Explicit specialization for char32_t. |

148 | _Cxx_hashtable_define_trivial_hash(char32_t) |

149 | |

150 | /// Explicit specialization for short. |

151 | _Cxx_hashtable_define_trivial_hash(short) |

152 | |

153 | /// Explicit specialization for int. |

154 | _Cxx_hashtable_define_trivial_hash(int) |

155 | |

156 | /// Explicit specialization for long. |

157 | _Cxx_hashtable_define_trivial_hash(long) |

158 | |

159 | /// Explicit specialization for long long. |

160 | _Cxx_hashtable_define_trivial_hash(long long) |

161 | |

162 | /// Explicit specialization for unsigned short. |

163 | _Cxx_hashtable_define_trivial_hash(unsigned short) |

164 | |

165 | /// Explicit specialization for unsigned int. |

166 | _Cxx_hashtable_define_trivial_hash(unsigned int) |

167 | |

168 | /// Explicit specialization for unsigned long. |

169 | _Cxx_hashtable_define_trivial_hash(unsigned long) |

170 | |

171 | /// Explicit specialization for unsigned long long. |

172 | _Cxx_hashtable_define_trivial_hash(unsigned long long) |

173 | |

174 | #ifdef __GLIBCXX_TYPE_INT_N_0 |

175 | _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_0) |

176 | _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_0 unsigned) |

177 | #endif |

178 | #ifdef __GLIBCXX_TYPE_INT_N_1 |

179 | _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_1) |

180 | _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_1 unsigned) |

181 | #endif |

182 | #ifdef __GLIBCXX_TYPE_INT_N_2 |

183 | _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_2) |

184 | _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_2 unsigned) |

185 | #endif |

186 | #ifdef __GLIBCXX_TYPE_INT_N_3 |

187 | _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_3) |

188 | _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_3 unsigned) |

189 | #endif |

190 | |

191 | #undef _Cxx_hashtable_define_trivial_hash |

192 | |

193 | struct _Hash_impl |

194 | { |

195 | static size_t |

196 | hash(const void* __ptr, size_t __clength, |

197 | size_t __seed = static_cast<size_t>(0xc70f6907UL)) |

198 | { return _Hash_bytes(__ptr, len: __clength, __seed); } |

199 | |

200 | template<typename _Tp> |

201 | static size_t |

202 | hash(const _Tp& __val) |

203 | { return hash(&__val, sizeof(__val)); } |

204 | |

205 | template<typename _Tp> |

206 | static size_t |

207 | __hash_combine(const _Tp& __val, size_t __hash) |

208 | { return hash(&__val, sizeof(__val), __hash); } |

209 | }; |

210 | |

211 | // A hash function similar to FNV-1a (see PR59406 for how it differs). |

212 | struct _Fnv_hash_impl |

213 | { |

214 | static size_t |

215 | hash(const void* __ptr, size_t __clength, |

216 | size_t __seed = static_cast<size_t>(2166136261UL)) |

217 | { return _Fnv_hash_bytes(__ptr, len: __clength, __seed); } |

218 | |

219 | template<typename _Tp> |

220 | static size_t |

221 | hash(const _Tp& __val) |

222 | { return hash(&__val, sizeof(__val)); } |

223 | |

224 | template<typename _Tp> |

225 | static size_t |

226 | __hash_combine(const _Tp& __val, size_t __hash) |

227 | { return hash(&__val, sizeof(__val), __hash); } |

228 | }; |

229 | |

230 | /// Specialization for float. |

231 | template<> |

232 | struct hash<float> : public __hash_base<size_t, float> |

233 | { |

234 | size_t |

235 | operator()(float __val) const noexcept |

236 | { |

237 | // 0 and -0 both hash to zero. |

238 | return __val != 0.0f ? std::_Hash_impl::hash(__val) : 0; |

239 | } |

240 | }; |

241 | |

242 | /// Specialization for double. |

243 | template<> |

244 | struct hash<double> : public __hash_base<size_t, double> |

245 | { |

246 | size_t |

247 | operator()(double __val) const noexcept |

248 | { |

249 | // 0 and -0 both hash to zero. |

250 | return __val != 0.0 ? std::_Hash_impl::hash(__val) : 0; |

251 | } |

252 | }; |

253 | |

254 | /// Specialization for long double. |

255 | template<> |

256 | struct hash<long double> |

257 | : public __hash_base<size_t, long double> |

258 | { |

259 | _GLIBCXX_PURE size_t |

260 | operator()(long double __val) const noexcept; |

261 | }; |

262 | |

263 | #if __cplusplus >= 201703L |

264 | template<> |

265 | struct hash<nullptr_t> : public __hash_base<size_t, nullptr_t> |

266 | { |

267 | size_t |

268 | operator()(nullptr_t) const noexcept |

269 | { return 0; } |

270 | }; |

271 | #endif |

272 | |

273 | /// @} group hashes |

274 | |

275 | // Hint about performance of hash functor. If not fast the hash-based |

276 | // containers will cache the hash code. |

277 | // Default behavior is to consider that hashers are fast unless specified |

278 | // otherwise. |

279 | template<typename _Hash> |

280 | struct __is_fast_hash : public std::true_type |

281 | { }; |

282 | |

283 | template<> |

284 | struct __is_fast_hash<hash<long double>> : public std::false_type |

285 | { }; |

286 | |

287 | _GLIBCXX_END_NAMESPACE_VERSION |

288 | } // namespace |

289 | |

290 | #endif // _FUNCTIONAL_HASH_H |

291 |