OSSIA
Open Scenario System for Interactive Application
Loading...
Searching...
No Matches
hash.hpp
1#pragma once
2#include <ossia/detail/config.hpp>
3#include <ossia/detail/math.hpp>
4
5#include <ankerl/unordered_dense.h>
6
7#include <cinttypes>
8#include <cstdint>
9#include <memory>
10#include <string>
11#include <string_view>
12
13namespace ossia
14{
15
16struct string_hash
17{
18 using is_transparent = std::true_type;
19 using is_avalanching = std::true_type;
20 std::size_t operator()(const std::string& s) const noexcept
21 {
22 return ankerl::unordered_dense::hash<std::string>{}(s);
23 }
24
25 std::size_t operator()(std::string_view s) const noexcept
26 {
27 return ankerl::unordered_dense::hash<std::string_view>{}(s);
28 }
29
30 template <std::size_t N>
31 std::size_t operator()(const char (&s)[N]) const noexcept
32 {
33 return ankerl::unordered_dense::hash<std::string_view>{}(std::string_view{s, N - 1});
34 }
35};
36
37// https://stackoverflow.com/q/20953390/1495627
38struct egur_hash
39{
40 using is_transparent = std::true_type;
41
42 template <typename T>
43 OSSIA_INLINE OSSIA_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK std::size_t
44 operator()(const T* val) const noexcept
45 {
46 static const constexpr std::size_t shift = constexpr_log2(1 + sizeof(T));
47 return (size_t)(val) >> shift;
48 }
49
50 template <typename T>
51 OSSIA_INLINE OSSIA_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK std::size_t
52 operator()(const std::shared_ptr<T>& val) const noexcept
53 {
54 static const constexpr std::size_t shift = constexpr_log2(1 + sizeof(T));
55 return (size_t)(val.get()) >> shift;
56 }
57};
58
59template <std::size_t ApproximateObjectSizeof>
60struct unknown_pointer_hash
61{
62 using is_transparent = std::true_type;
63
64 template <typename T>
65 OSSIA_INLINE OSSIA_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK std::size_t
66 operator()(const T* val) const noexcept
67 {
68 static const constexpr std::size_t shift
69 = constexpr_log2(1 + ApproximateObjectSizeof);
70 return (size_t)(val) >> shift;
71 }
72
73 template <typename T>
74 OSSIA_INLINE OSSIA_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK std::size_t
75 operator()(const std::shared_ptr<T>& val) const noexcept
76 {
77 static const constexpr std::size_t shift
78 = constexpr_log2(1 + ApproximateObjectSizeof);
79 return (size_t)(val.get()) >> shift;
80 }
81};
82
83template<typename T> struct is_shared_ptr : std::false_type {};
84template<typename T> struct is_shared_ptr<std::shared_ptr<T>> : std::true_type {};
85
86
87template <typename T>
88struct hash : ankerl::unordered_dense::hash<T> { };
89
90template <typename T>
91requires std::is_pointer_v<T>
92struct hash<T> : egur_hash { };
93
94template <typename T>
95requires is_shared_ptr<T>::value
96struct hash<T> : egur_hash { };
97
98template <>
99struct hash<std::string> : string_hash { };
100template <>
101struct hash<std::string_view> : string_hash { };
102
103// Invalid overloads
104template <>
105struct hash<const char*>;
106template <>
107struct hash<char*>;
108
109
110
111struct string_equal
112{
113 using is_transparent = std::true_type;
114 bool operator()(const std::string& s, const std::string& s2) const noexcept
115 {
116 return s == s2;
117 }
118 bool operator()(std::string_view s, const std::string& s2) const noexcept
119 {
120 return s == s2;
121 }
122 bool operator()(const std::string& s, std::string_view s2) const noexcept
123 {
124 return s == s2;
125 }
126 bool operator()(std::string_view s, std::string_view s2) const noexcept
127 {
128 return s == s2;
129 }
130
131 template <std::size_t N>
132 bool operator()(const std::string& s, const char (&s2)[N]) const noexcept
133 {
134 return operator()(s, std::string_view{s2, N-1});
135 }
136
137 template <std::size_t N>
138 bool operator()(std::string_view s, const char (&s2)[N]) const noexcept
139 {
140 return operator()(s, std::string_view{s2, N-1});
141 }
142
143 template <std::size_t N>
144 bool operator()(const char (&s)[N], const std::string& s2) const noexcept
145 {
146 return operator()(std::string_view{s, N-1}, s2);
147 }
148
149 template <std::size_t N>
150 bool operator()(const char (&s)[N], std::string_view s2) const noexcept
151 {
152 return operator()(std::string_view{s, N-1}, s2);
153 }
154};
155
156
157struct pointer_equal
158{
159 using is_transparent = std::true_type;
160 template<typename U, typename V>
161 OSSIA_INLINE
162 bool operator()(const U* lhs, const V* rhs) const noexcept { return lhs == rhs; }
163
164 template<typename U, typename V>
165 OSSIA_INLINE
166 bool operator()(const std::shared_ptr<U>& lhs, const V* rhs) const noexcept
167 {
168 return lhs.get() == rhs;
169 }
170
171 template<typename U, typename V>
172 OSSIA_INLINE
173 bool operator()(const U* lhs, const std::shared_ptr<V>& rhs) const noexcept
174 {
175 return lhs == rhs.get();
176 }
177
178 template<typename U, typename V>
179 OSSIA_INLINE
180 bool
181 operator()(const std::shared_ptr<U>& lhs, const std::shared_ptr<V>& rhs) const noexcept
182 {
183 return lhs == rhs;
184 }
185};
186
187template <typename T>
188struct equal_to : std::equal_to<T> { };
189
190template <>
191struct equal_to<std::string> : string_equal { };
192template <>
193struct equal_to<std::string_view> : string_equal { };
194
195template <typename T>
196requires std::is_pointer_v<T>
197struct equal_to<T> : pointer_equal { };
198
199template <typename T>
200requires is_shared_ptr<T>::value
201struct equal_to<T> : pointer_equal { };
202
203// hash_combine_impl taken from boost
204template <typename T>
205OSSIA_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK constexpr inline void
206hash_combine(std::size_t& seed, const T& k) noexcept
207{
208 using namespace std;
209 seed ^= hash<T>{}(k) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
210}
211
212template <typename T>
213OSSIA_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK constexpr inline void
214hash_combine(std::size_t& seed, const T* k) noexcept
215{
216 using namespace std;
217 seed ^= egur_hash{}(k) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
218}
219
220OSSIA_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
221constexpr inline void hash_combine(uint64_t& seed, uint8_t k) noexcept
222{
223 seed ^= k + 0x9e3779b9 + (seed << 6) + (seed >> 2);
224}
225
226OSSIA_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
227constexpr inline void hash_combine(uint64_t& seed, int8_t k) noexcept
228{
229 seed ^= k + 0x9e3779b9 + (seed << 6) + (seed >> 2);
230}
231
232OSSIA_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
233constexpr inline void hash_combine(uint64_t& seed, uint16_t k) noexcept
234{
235 seed ^= k + 0x9e3779b9 + (seed << 6) + (seed >> 2);
236}
237
238OSSIA_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
239constexpr inline void hash_combine(uint64_t& seed, int16_t k) noexcept
240{
241 seed ^= k + 0x9e3779b9 + (seed << 6) + (seed >> 2);
242}
243
244OSSIA_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
245constexpr inline void hash_combine(uint64_t& seed, uint32_t k) noexcept
246{
247 seed ^= k + 0x9e3779b9 + (seed << 6) + (seed >> 2);
248}
249
250OSSIA_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
251constexpr inline void hash_combine(uint64_t& seed, int32_t k) noexcept
252{
253 seed ^= k + 0x9e3779b9 + (seed << 6) + (seed >> 2);
254}
255
256OSSIA_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
257constexpr inline void hash_combine(uint64_t& seed, int64_t k) noexcept
258{
259 seed ^= k + 0x9e3779b9 + (seed << 6) + (seed >> 2);
260}
261
262OSSIA_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
263constexpr inline void hash_combine(uint32_t& seed, uint8_t k) noexcept
264{
265 seed ^= k + 0x9e3779b9 + (seed << 6) + (seed >> 2);
266}
267
268OSSIA_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
269constexpr inline void hash_combine(uint32_t& seed, int8_t k) noexcept
270{
271 seed ^= k + 0x9e3779b9 + (seed << 6) + (seed >> 2);
272}
273
274OSSIA_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
275constexpr inline void hash_combine(uint32_t& seed, uint16_t k) noexcept
276{
277 seed ^= k + 0x9e3779b9 + (seed << 6) + (seed >> 2);
278}
279
280OSSIA_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
281constexpr inline void hash_combine(uint32_t& seed, int16_t k) noexcept
282{
283 seed ^= k + 0x9e3779b9 + (seed << 6) + (seed >> 2);
284}
285
286OSSIA_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
287constexpr inline void hash_combine(uint32_t& seed, int32_t k) noexcept
288{
289 seed ^= k + 0x9e3779b9 + (seed << 6) + (seed >> 2);
290}
291
292OSSIA_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
293constexpr inline void hash_combine(uint32_t& seed, uint64_t k) noexcept
294{
295 seed ^= k + 0x9e3779b9 + (seed << 6) + (seed >> 2);
296}
297
298OSSIA_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
299constexpr inline void hash_combine(uint32_t& seed, int64_t k) noexcept
300{
301 seed ^= k + 0x9e3779b9 + (seed << 6) + (seed >> 2);
302}
303
304OSSIA_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
305constexpr inline void hash_combine(uint32_t& h1, uint32_t k1) noexcept
306{
307 constexpr auto rotl32
308 = [](uint32_t x, int8_t r) noexcept { return (x << r) | (x >> (32 - r)); };
309
310 constexpr uint32_t c1 = 0xcc9e2d51;
311 constexpr uint32_t c2 = 0x1b873593;
312
313 k1 *= c1;
314 k1 = rotl32(k1, 15);
315 k1 *= c2;
316
317 h1 ^= k1;
318 h1 = rotl32(h1, 13);
319 h1 = h1 * 5 + 0xe6546b64;
320}
321
322OSSIA_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
323constexpr inline void hash_combine(uint64_t& h, uint64_t k) noexcept
324{
325 constexpr auto m = UINT64_C(0xc6a4a7935bd1e995);
326 constexpr int r = 47;
327
328 k *= m;
329 k ^= k >> r;
330 k *= m;
331
332 h ^= k;
333 h *= m;
334
335 // Completely arbitrary number, to prevent 0's
336 // from hashing to 0.
337 h += 0xe6546b64;
338}
339}
ossia
Definition git_info.h:7