DiscordCoreAPI
A Discord bot library written in C++, with custom asynchronous coroutines.
Loading...
Searching...
No Matches
Hash.hpp
Go to the documentation of this file.
1/*
2 MIT License
3
4 DiscordCoreAPI, A bot library for Discord, written in C++, and featuring explicit multithreading through the usage of custom, asynchronous C++ CoRoutines.
5
6 Copyright 2022, 2023 Chris M. (RealTimeChris)
7
8 Permission is hereby granted, free of charge, to any person obtaining a copy
9 of this software and associated documentation files (the "Software"), to deal
10 in the Software without restriction, including without limitation the rights
11 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
12 copies of the Software, and to permit persons to whom the Software is
13 furnished to do so, subject to the following conditions:
14
15 The above copyright notice and this permission notice shall be included in all
16 copies or substantial portions of the Software.
17
18 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
21 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
22 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
23 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
24 SOFTWARE.
25*/
26/// Hash.hpp - Header file for the hash related stuff.
27/// May 12, 2021
28/// https://discordcoreapi.com
29/// \file Hash.hpp
30
31#pragma once
32
33#include <memory_resource>
34#include <exception>
35#include <vector>
36
37namespace DiscordCoreAPI {
38
39 namespace DiscordCoreInternal {
40 struct EventDelegateToken;
41 }
42
43 class EtfSerializer;
44
45 template<typename ValueType>
46 concept EtfSerializerT = std::same_as<ValueType, EtfSerializer>;
47
48 template<typename ValueType>
49 concept BoolT = std::same_as<std::decay_t<ValueType>, bool> && !EtfSerializerT<ValueType> && !std::integral<ValueType>;
50
51 template<typename ValueType>
52 concept EnumT = std::is_enum<std::decay_t<ValueType>>::value;
53
54 template<typename ValueType>
55 concept IntegerT = std::integral<std::decay_t<ValueType>> && !BoolT<std::decay_t<ValueType>>;
56
57 class GuildMemberCacheData;
58 struct VoiceStateDataLight;
59 struct VoiceStateData;
60 class GuildMemberData;
61
62 template<typename ValueType>
63 concept VoiceStateT = std::same_as<ValueType, VoiceStateDataLight>;
64
65 template<typename ValueType>
66 concept GuildMemberT = std::same_as<ValueType, GuildMemberCacheData> || std::same_as<ValueType, GuildMemberData>;
67
68 template<typename ValueType>
69 concept HasId = requires(ValueType value) { value.id; };
70
71 template<typename ValueType>
72 concept HasTwoId = VoiceStateT<ValueType> || GuildMemberT<ValueType>;
73
74 template<typename ValueType>
75 concept EventDelegateTokenT = std::same_as<ValueType, DiscordCoreInternal::EventDelegateToken>;
76
77 struct ObjectCompare {
78 template<typename ValueType01, typename ValueType02> inline bool operator()(const ValueType01& lhs, const ValueType02& rhs) const {
79 return lhs == rhs;
80 }
81
82 template<typename ValueType01, typename ValueType02> inline bool operator()(ValueType01& lhs, ValueType02& rhs) {
83 return lhs == rhs;
84 }
85 };
86
87 inline uint64_t internalHashFunction(const void* value, uint64_t count) {
88 static constexpr uint64_t fnvOffsetBasis{ 0xcbf29ce484222325 };
89 static constexpr uint64_t fnvPrime{ 0x00000100000001B3 };
90 uint64_t hash{ fnvOffsetBasis };
91 for (uint64_t x = 0; x < count; ++x) {
92 hash ^= static_cast<const uint8_t*>(value)[x];
93 hash *= fnvPrime;
94 }
95 return hash;
96 }
97
98 class TwoIdKey {
99 public:
100 template<GuildMemberT ValueType> TwoIdKey(const ValueType& other);
101 template<VoiceStateT ValueType> TwoIdKey(const ValueType& other);
102
103 Snowflake idOne{};
104 Snowflake idTwo{};
105 };
106
107 template<typename ValueType> struct KeyHasher;
108
109 template<HasId ValueType> struct KeyHasher<ValueType> {
110 inline uint64_t operator()(const ValueType& other) const {
111 return internalHashFunction(&other.id.operator const uint64_t&(), sizeof(uint64_t));
112 }
113 };
114
115 template<uint64_t size> struct KeyHasher<char[size]> {
116 inline uint64_t operator()(const char (&other)[size]) const {
117 return internalHashFunction(other, std::char_traits<char>::length(other));
118 }
119 };
120
121 template<IntegerT ValueType> struct KeyHasher<ValueType> {
122 inline uint64_t operator()(const ValueType& other) const {
123 return internalHashFunction(&other, sizeof(other));
124 }
125 };
126
127 template<> struct KeyHasher<TwoIdKey> {
128 inline uint64_t operator()(const TwoIdKey& other) const {
129 uint64_t values[2]{};
130 values[0] = other.idOne.operator const uint64_t&();
131 values[1] = other.idTwo.operator const uint64_t&();
132 return internalHashFunction(values, sizeof(uint64_t) * std::size(values));
133 }
134 };
135
136 template<EnumT ValueType> struct KeyHasher<ValueType> {
137 inline uint64_t operator()(const ValueType& other) const {
138 return internalHashFunction(&other, sizeof(other));
139 }
140 };
141
142 template<jsonifier_internal::string_t ValueType> struct KeyHasher<ValueType> {
143 inline uint64_t operator()(const ValueType& other) const {
144 return internalHashFunction(other.data(), other.size());
145 }
146 };
147
148 template<> struct KeyHasher<Snowflake> {
149 inline uint64_t operator()(const Snowflake& data) const {
150 return internalHashFunction(&data.operator const uint64_t&(), sizeof(uint64_t));
151 }
152 };
153
154 template<> struct KeyHasher<jsonifier::vector<std::string>> {
155 inline uint64_t operator()(const jsonifier::vector<std::string>& data) const {
156 std::string newString{};
157 for (auto& value: data) {
158 newString.append(value);
159 }
160 return internalHashFunction(newString.data(), newString.size());
161 }
162 };
163
164 template<HasTwoId ValueType> struct KeyHasher<ValueType> {
165 inline uint64_t operator()(const ValueType& other) const {
166 return KeyHasher<TwoIdKey>{}.operator()(TwoIdKey{ other });
167 }
168 };
169
170 template<jsonifier_internal::unique_ptr_t ValueType> struct KeyHasher<ValueType> {
171 inline uint64_t operator()(const ValueType& other) const {
172 return KeyHasher<typename ValueType::element_type>{}.operator()(*other);
173 }
174 };
175
176 struct KeyAccessor {
177 template<GuildMemberT ValueType> uint64_t operator()(const ValueType& other) const {
178 return KeyHasher<ValueType>{}.operator()(other);
179 }
180
181 template<VoiceStateT ValueType> uint64_t operator()(const ValueType& other) const {
182 return KeyHasher<ValueType>{}.operator()(other);
183 }
184
185 uint64_t operator()(const Snowflake& other) const {
186 return KeyHasher<Snowflake>{}.operator()(other);
187 }
188
189 uint64_t operator()(const TwoIdKey& other) const {
190 return KeyHasher<TwoIdKey>{}.operator()(other);
191 }
192
193 template<uint64_t size> inline uint64_t operator()(const char (&other)[size]) const {
194 return KeyHasher<char[size]>{}.operator()(other);
195 }
196
197 template<jsonifier_internal::string_t ValueType> uint64_t operator()(const ValueType& other) const {
198 return KeyHasher<ValueType>{}.operator()(other);
199 }
200
201 template<HasId ValueType> uint64_t operator()(const ValueType& other) const {
202 return KeyHasher<ValueType>{}.operator()(other);
203 }
204
205 template<jsonifier_internal::unique_ptr_t ValueType> uint64_t operator()(const ValueType& other) const {
206 return KeyHasher<ValueType>{}.operator()(other);
207 }
208
209 uint64_t operator()(const jsonifier::vector<std::string>& other) const {
210 return KeyHasher<jsonifier::vector<std::string>>{}.operator()(other);
211 }
212 };
213
214 inline constexpr int8_t minLookups{ 0 };
215
216 template<typename ValueType> struct HashPolicy {
217 template<typename KeyType> inline uint64_t indexForHash(KeyType&& key) const {
218 return KeyHasher<std::remove_cvref_t<KeyType>>{}.operator()(key) & (static_cast<const ValueType*>(this)->capacityVal - 1);
219 }
220
221 static inline int8_t log2(uint64_t value) {
222 static constexpr int8_t table[64] = { 63, 0, 58, 1, 59, 47, 53, 2, 60, 39, 48, 27, 54, 33, 42, 3, 61, 51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22, 4, 62, 57,
223 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21, 56, 45, 25, 31, 35, 16, 9, 12, 44, 24, 15, 8, 23, 7, 6, 5 };
224 value |= value >> 1;
225 value |= value >> 2;
226 value |= value >> 4;
227 value |= value >> 8;
228 value |= value >> 16;
229 value |= value >> 32;
230 return table[((value - (value >> 1)) * 0x07EDD5E59A4E28C2) >> 58];
231 }
232
233 static inline uint64_t nextPowerOfTwo(uint64_t size) {
234 --size;
235 size |= size >> 1;
236 size |= size >> 2;
237 size |= size >> 4;
238 size |= size >> 8;
239 size |= size >> 16;
240 size |= size >> 32;
241 ++size;
242 return size;
243 }
244
245 static int8_t computeMaxLookAheadDistance(uint64_t num_buckets) {
246 int8_t desired = log2(num_buckets);
247 return std::max(minLookups, desired);
248 }
249 };
250
251 template<typename FirstType, typename SecondType> class Pair {
252 public:
253 using first_type = FirstType;
254 using second_type = SecondType;
255
256 first_type first;
257 second_type second;
258
259 template<typename FirstTypeNew, typename SecondTypeNew> inline Pair(FirstTypeNew&& firstNew, SecondTypeNew&& secondNew)
260 : first{ std::forward<FirstTypeNew>(firstNew) }, second{ std::forward<SecondTypeNew>(secondNew) } {
261 }
262
263 template<typename FirstTypeNew> inline Pair(FirstTypeNew&& firstNew) : first{ std::forward<FirstTypeNew>(firstNew) } {
264 }
265
266 template<typename... Args> inline Pair(Args&&... args) : Pair{ std::forward<Args>(args)... } {
267 }
268
269 inline bool operator==(const Pair& other) const {
270 return first == other.first && second == other.second;
271 }
272 };
273
274 template<typename ValueTypeInternal> class HashIterator {
275 public:
276 using iterator_category = std::forward_iterator_tag;
277 using value_type_internal = ValueTypeInternal;
278 using value_type = ValueTypeInternal::value_type;
279 using reference = value_type&;
280 using pointer = value_type*;
281 using pointer_internal = value_type_internal*;
282 using size_type = uint64_t;
283
284 inline HashIterator() noexcept = default;
285
286 inline HashIterator(pointer_internal valueNew, size_type currentIndexNew) : value{ valueNew }, currentIndex{ currentIndexNew } {};
287
288 inline HashIterator& operator++() {
289 skipEmptySlots();
290 return *this;
291 }
292
293 inline pointer getRawPtr() {
294 return &value->data[currentIndex];
295 }
296
297 inline bool operator==(const HashIterator&) const {
298 return !value || value->sentinelVector[currentIndex] == -1;
299 }
300
301 inline pointer operator->() {
302 return &value->data[currentIndex];
303 }
304
305 inline reference operator*() {
306 return value->data[currentIndex];
307 }
308
309 protected:
310 pointer_internal value{};
311 size_type currentIndex{};
312
313 void skipEmptySlots() {
314 ++currentIndex;
315 while (value && value->sentinelVector[currentIndex] == 0) {
316 ++currentIndex;
317 };
318 }
319 };
320}