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 |