1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
|
// SPDX-FileCopyrightText: Copyright 2026 Eden Emulator Project
// SPDX-License-Identifier: GPL-3.0-or-later
// SPDX-FileCopyrightText: 2005-2014 Daniel James
// SPDX-FileCopyrightText: 2016 Austin Appleby
// SPDX-License-Identifier: BSL-1.0
#pragma once
#include <array>
#include <climits>
#include <cstdint>
#include <functional>
#include <limits>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>
namespace Common {
/// The default hash of Common::unordered_map/set. std::hash of an integer or a pointer is a
/// byte-wise FNV-1a on MSVC, and boost's flat containers mix a hash that does not say it
/// avalanches anyway: pass those keys through (the GPU thread's page maps looked keys up
/// tens of thousands of times a second with it). Other keys keep std::hash.
template <class Key>
struct FastHash : std::hash<Key> {};
template <class Key>
requires std::is_integral_v<Key>
struct FastHash<Key> {
std::size_t operator()(Key key) const noexcept {
return static_cast<std::size_t>(key);
}
};
template <class T>
struct FastHash<T*> {
std::size_t operator()(T* pointer) const noexcept {
return reinterpret_cast<std::size_t>(pointer);
}
};
namespace detail {
template <typename T>
requires std::is_unsigned_v<T>
inline std::size_t HashValue(T val) {
const unsigned int size_t_bits = std::numeric_limits<std::size_t>::digits;
const unsigned int length =
(std::numeric_limits<T>::digits - 1) / static_cast<unsigned int>(size_t_bits);
std::size_t seed = 0;
for (unsigned int i = length * size_t_bits; i > 0; i -= size_t_bits) {
seed ^= static_cast<size_t>(val >> i) + (seed << 6) + (seed >> 2);
}
seed ^= static_cast<size_t>(val) + (seed << 6) + (seed >> 2);
return seed;
}
template <size_t Bits>
struct HashCombineImpl {
template <typename T>
static inline T fn(T seed, T value) {
seed ^= value + 0x9e3779b9 + (seed << 6) + (seed >> 2);
return seed;
}
};
template <>
struct HashCombineImpl<64> {
static inline std::uint64_t fn(std::uint64_t h, std::uint64_t k) {
const std::uint64_t m = (std::uint64_t(0xc6a4a793) << 32) + 0x5bd1e995;
const int r = 47;
k *= m;
k ^= k >> r;
k *= m;
h ^= k;
h *= m;
// Completely arbitrary number, to prevent 0's
// from hashing to 0.
h += 0xe6546b64;
return h;
}
};
} // namespace detail
template <typename T>
requires std::is_unsigned_v<T>
inline void HashCombine(std::size_t& seed, const T& v) {
seed = detail::HashCombineImpl<sizeof(std::size_t) * CHAR_BIT>::fn(seed, detail::HashValue(v));
}
template <typename T>
requires (!std::is_unsigned_v<T>)
inline void HashCombine(std::size_t& seed, const T& v) {
seed = detail::HashCombineImpl<sizeof(std::size_t) * CHAR_BIT>::fn(seed, std::hash<T>{}(v));
}
template <typename It>
inline std::size_t HashRange(It first, It last) {
std::size_t seed = 0;
for (; first != last; ++first) {
HashCombine<typename std::iterator_traits<It>::value_type>(seed, *first);
}
return seed;
}
template <typename T, size_t Size>
std::size_t HashValue(const std::array<T, Size>& v) {
return HashRange(v.cbegin(), v.cend());
}
template <typename T, typename Allocator>
std::size_t HashValue(const std::vector<T, Allocator>& v) {
return HashRange(v.cbegin(), v.cend());
}
} // namespace Common
namespace std {
template <typename... Args>
struct hash<std::tuple<Args...>> {
std::size_t operator()(const std::tuple<Args...>& t) const noexcept {
std::size_t seed = 0;
std::apply([&seed](const Args&... args) { (Common::HashCombine(seed, args), ...); }, t);
return seed;
}
};
template <class A, class B>
struct hash<std::pair<A, B>> {
std::size_t operator()(const std::pair<A, B>& p) const noexcept {
std::size_t seed = 0;
Common::HashCombine(seed, p.first);
Common::HashCombine(seed, p.second);
return seed;
}
};
} // namespace std
|
