DiscordCoreAPI
A Discord bot library written in C++, with custom asynchronous coroutines.
Loading...
Searching...
No Matches
UnorderedSet.hpp
1/*
2 DiscordCoreAPI, A bot library for Discord, written in C++, and featuring explicit multithreading through the usage of custom, asynchronous C++ CoRoutines.
3
4 Copyright 2021, 2022, 2023 Chris M. (RealTimeChris)
5
6 This library is free software; you can redistribute it and/or
7 modify it under the terms of the GNU Lesser General Public
8 License as published by the Free Software Foundation; either
9 version 2.1 of the License, or (at your option) 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 GNU
14 Lesser General Public License for more details.
15
16 You should have received a copy of the GNU Lesser General Public
17 License along with this library; if not, write to the Free Software
18 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
19 USA
20*/
21/// Https.hpp - Header file for the "Https Stuff".
22/// May 12, 2021
23/// https://discordcoreapi.com
24/// \file Https.hpp
25
26#pragma once
27
28#include <memory_resource>
29#include <shared_mutex>
30#include <vector>
31#include <stack>
32
33#ifdef __has_cpp_attribute
34 #if __has_cpp_attribute(no_unique_address)
35 #ifdef _MSC_VER
36 #define NO_UNIQUE_ADDRESS [[msvc::no_unique_address]]
37 #else
38 #define NO_UNIQUE_ADDRESS [[no_unique_address]]
39 #endif
40 #else
41 #define NO_UNIQUE_ADDRESS
42 #endif
43#else
44 #define NO_UNIQUE_ADDRESS
45#endif
46
47namespace DiscordCoreAPI {
48
49 template<typename ValueType = void> struct Fnv1aHash {
50 inline uint64_t operator()(const ValueType& data) const;
51
52 inline uint64_t operator()(ValueType&& data) const;
53
54 protected:
55 static constexpr uint64_t fnvOffsetBasis{ 14695981039346656037ull };
56 static constexpr uint64_t fnvPrime{ 1099511628211ull };
57
58 inline uint64_t internalHashFunction(const uint8_t* value, size_t count) const;
59 };
60
61 template<typename KTy, typename ValueType> struct KeyAccessor {
62 KTy& operator()(ValueType& other) {
63 return other.id;
64 }
65
66 KTy& operator()(ValueType&& other) {
67 return other.id;
68 }
69 };
70
71 template<typename KTy, typename ValueType, typename KATy = KeyAccessor<KTy, ValueType>> class MemoryCore {
72 public:
73 using key_type = KTy;
74 using value_type = ValueType;
75 using key_accessor = KATy;
76 using reference = value_type&;
77 using const_reference = const value_type&;
78 using pointer = value_type*;
79 using size_type = size_t;
80 using key_hasher = Fnv1aHash<key_type>;
81
82 class MemoryCoreIterator {
83 public:
84 using value_type = typename MemoryCore::value_type;
85 using reference = typename MemoryCore::reference;
86 using pointer = typename MemoryCore::pointer;
87 using iterator_category = std::forward_iterator_tag;
88
89 inline MemoryCoreIterator(MemoryCore* core, size_t index) : core(core), index(index) {
90 }
91
92 inline MemoryCoreIterator& operator++() {
93 index++;
94 while (index < core->capacity && !core->data[index].operator bool()) {
95 index++;
96 }
97 return *this;
98 }
99
100 inline bool operator==(const MemoryCoreIterator& other) const {
101 return core == other.core && index == other.index;
102 }
103
104 inline bool operator!=(const MemoryCoreIterator& other) const {
105 return !(*this == other);
106 }
107
108 inline reference operator*() const {
109 return core->data[index];
110 }
111
112 protected:
113 MemoryCore* core;
114 size_t index;
115 };
116
117 using iterator = MemoryCoreIterator;
118
119 class SentinelHolder {
120 public:
121 inline SentinelHolder() noexcept = default;
122
123 inline SentinelHolder& operator=(SentinelHolder&& other) = delete;
124 inline SentinelHolder(SentinelHolder&& other) = delete;
125 inline SentinelHolder& operator=(const SentinelHolder& other) = delete;
126 inline SentinelHolder(const SentinelHolder& other) = delete;
127
128 inline operator bool() const noexcept {
129 return isItActive;
130 }
131
132 inline operator reference() noexcept {
133 return object;
134 }
135
136 inline void activate(value_type&& data) noexcept {
137 object = std::forward<value_type>(data);
138 isItActive = true;
139 }
140
141 inline value_type&& disable() noexcept {
142 isItActive = false;
143 return std::move(object);
144 }
145
146 protected:
147 bool isItActive{};
148 value_type object{};
149 };
150
151 using sentinel_allocator = std::pmr::polymorphic_allocator<SentinelHolder>;
152
153 inline MemoryCore(size_type newCapacity) : capacity(newCapacity), size(0), data(allocator.allocate(newCapacity)) {
154 for (size_t x = 0; x < newCapacity; ++x) {
155 allocator.construct(&data[x]);
156 }
157 };
158
159 inline MemoryCore& operator=(MemoryCore&& other) noexcept {
160 if (this != &other) {
161 std::swap(capacity, other.capacity);
162 std::swap(data, other.data);
163 std::swap(size, other.size);
164 }
165 return *this;
166 }
167
168 inline MemoryCore(MemoryCore&& other) noexcept {
169 *this = std::move(other);
170 }
171
172 inline MemoryCore& operator=(const MemoryCore& other) noexcept {
173 if (this != &other) {
174 reserve(other.capacity);
175 std::copy(other.data, other.data + other.capacity, data);
176 size = other.size;
177 }
178 return *this;
179 }
180
181 inline MemoryCore(const MemoryCore& other) noexcept {
182 *this = other;
183 }
184
185 inline void emplace(value_type&& value) noexcept {
186 emplaceInternal(std::forward<value_type>(value));
187 }
188
189 inline void emplace(const value_type& value) noexcept {
190 emplaceInternal(value);
191 }
192
193 inline iterator find(key_type&& key) noexcept {
194 size_type index = key_hasher{}(key) % capacity;
195 size_type currentIndex{};
196 while (currentIndex < capacity) {
197 if (data[index].operator bool() && key_accessor{}(data[index].operator reference()) == key) {
198 return iterator{ this, index };
199 }
200 index = (index + 1) % capacity;
201 ++currentIndex;
202 }
203
204 return end();
205 }
206
207 inline iterator find(const key_type& key) noexcept {
208 size_type index = key_hasher{}(key) % capacity;
209 size_type currentIndex{};
210 while (currentIndex < capacity) {
211 if (data[index].operator bool() && key_accessor{}(data[index].operator reference()) == key) {
212 return iterator{ this, index };
213 }
214 index = (index + 1) % capacity;
215 ++currentIndex;
216 }
217
218 return end();
219 }
220
221 inline bool contains(key_type&& key) noexcept {
222 size_type index = key_hasher{}(key) % capacity;
223 size_type currentIndex{};
224 while (currentIndex < capacity) {
225 if (data[index].operator bool() && key_accessor{}(data[index].operator reference()) == key) {
226 return true;
227 }
228 index = (index + 1) % capacity;
229 ++currentIndex;
230 }
231
232 return false;
233 }
234
235 inline bool contains(const key_type& key) noexcept {
236 size_type index = key_hasher{}(key) % capacity;
237 size_type currentIndex{};
238 while (currentIndex < capacity) {
239 if (data[index].operator bool() && key_accessor{}(data[index].operator reference()) == key) {
240 return true;
241 }
242 index = (index + 1) % capacity;
243 ++currentIndex;
244 }
245
246 return false;
247 }
248
249 inline void erase(key_type&& key) noexcept {
250 size_type index = key_hasher{}(key) % capacity;
251 size_type currentIndex{};
252 while (currentIndex < capacity) {
253 if (data[index].operator bool() && key_accessor{}(data[index].operator reference()) == key) {
254 data[index].disable();
255 size--;
256 if (size < capacity / 4 && capacity > 10) {
257 resize(capacity / 2);
258 }
259 return;
260 }
261 index = (index + 1) % capacity;
262 ++currentIndex;
263 }
264 }
265
266 inline void erase(const key_type& key) noexcept {
267 size_type index = key_hasher{}(key) % capacity;
268 size_type currentIndex{};
269 while (currentIndex < capacity) {
270 if (data[index].operator bool() && key_accessor{}(data[index].operator reference()) == key) {
271 data[index].disable();
272 size--;
273 if (size < capacity / 4 && capacity > 10) {
274 resize(capacity / 2);
275 }
276 return;
277 }
278 index = (index + 1) % capacity;
279 ++currentIndex;
280 }
281 }
282
283 inline iterator begin() noexcept {
284 size_type index{};
285 while (index < capacity) {
286 if (data[index].operator bool()) {
287 return iterator{ this, index };
288 }
289 ++index;
290 }
291 return end();
292 }
293
294 inline iterator end() noexcept {
295 return iterator{ this, capacity };
296 }
297
298 inline iterator begin() const noexcept {
299 size_type index{};
300 while (index < capacity) {
301 if (data[index].operator bool()) {
302 return iterator{ this, index };
303 }
304 ++index;
305 }
306 return end();
307 }
308
309 inline iterator end() const noexcept {
310 return iterator{ this, capacity };
311 }
312
313 inline size_type getSize() const noexcept {
314 return size;
315 }
316
317 inline bool isEmpty() const noexcept {
318 return size == 0;
319 }
320
321 inline bool isFull() const noexcept {
322 return static_cast<float>(size) >= static_cast<float>(capacity) * 0.75f;
323 }
324
325 inline void reserve(size_t newSize) noexcept {
326 resize(newSize);
327 }
328
329 inline size_t getCapacity() const noexcept {
330 return capacity;
331 }
332
333 inline ~MemoryCore() noexcept {
334 if (data && capacity > 0) {
335 allocator.deallocate(data, capacity);
336 }
337 };
338
339 protected:
340 NO_UNIQUE_ADDRESS sentinel_allocator allocator{};
341 SentinelHolder* data{};
342 size_type capacity{};
343 size_type size{};
344
345 inline void emplaceInternal(value_type&& value, uint64_t recursionLimit = 1000) noexcept {
346 if (isFull()) {
347 resize(roundUpToCacheLine(capacity * 4), recursionLimit);
348 }
349 size_type index = key_hasher{}(key_accessor{}(value)) % capacity;
350 size_type currentIndex = index;
351 bool inserted = false;
352 while (!inserted) {
353 if (!data[currentIndex].operator bool()) {
354 data[currentIndex].activate(std::forward<value_type>(value));
355 size++;
356 inserted = true;
357 } else if (key_accessor{}(data[currentIndex].operator reference()) == key_accessor{}(value)) {
358 data[currentIndex].activate(std::forward<value_type>(value));
359 inserted = true;
360 } else {
361 currentIndex = (currentIndex + 1) % capacity;
362 if (currentIndex == index) {
363 resize(roundUpToCacheLine(capacity * 4), recursionLimit);
364 emplaceInternal(std::forward<value_type>(value), recursionLimit);
365 return;
366 }
367 }
368 }
369 }
370
371 inline void emplaceInternal(const value_type& value, uint64_t recursionLimit = 1000) noexcept {
372 if (isFull()) {
373 resize(roundUpToCacheLine(capacity * 4), recursionLimit);
374 }
375 size_type index = key_hasher{}(key_accessor{}(value)) % capacity;
376 size_type currentIndex = index;
377 bool inserted = false;
378 value_type newElement{ value };
379 while (!inserted) {
380 if (!data[currentIndex].operator bool()) {
381 data[currentIndex].activate(std::move(newElement));
382 size++;
383 inserted = true;
384 } else if (key_accessor{}(data[currentIndex].operator reference()) == key_accessor{}(value)) {
385 data[currentIndex].activate(std::move(newElement));
386 inserted = true;
387 } else {
388 currentIndex = (currentIndex + 1) % capacity;
389 if (currentIndex == index) {
390 resize(roundUpToCacheLine(capacity * 4), recursionLimit);
391 emplaceInternal(value, recursionLimit);
392 return;
393 }
394 }
395 }
396 }
397
398 inline void resize(size_type newCapacity, uint64_t recursionLimit = 1000) {
399 --recursionLimit;
400 if (recursionLimit == 0) {
401 throw std::runtime_error{ "Sorry, but the max number of recursive resizes have been exceeded." };
402 }
403 MemoryCore<key_type, value_type> newData{ newCapacity };
404 for (size_type x = 0; x < capacity; x++) {
405 if (data[x].operator bool()) {
406 newData.emplaceInternal(data[x].disable(), recursionLimit);
407 }
408 }
409 std::swap(data, newData.data);
410 std::swap(capacity, newData.capacity);
411 }
412
413 size_type roundUpToCacheLine(size_type size) {
414 const size_type multiple = 64 / sizeof(void*);
415 return (size + multiple - 1) / multiple * multiple;
416 }
417 };
418
419 template<typename KTy, typename ValueType, typename KATy = KeyAccessor<KTy, ValueType>> class UnorderedSet {
420 public:
421 using key_type = KTy;
422 using value_type = ValueType;
423 using reference = value_type&;
424 using const_reference = const value_type&;
425 using pointer = value_type*;
426 using size_type = size_t;
427 using iterator = typename MemoryCore<key_type, value_type>::MemoryCoreIterator;
428
429 inline UnorderedSet() : data{ 5 } {};
430
431 inline UnorderedSet& operator=(UnorderedSet&& other) noexcept = default;
432 inline UnorderedSet(UnorderedSet&& other) noexcept = default;
433 inline UnorderedSet& operator=(const UnorderedSet& other) noexcept = default;
434 inline UnorderedSet(const UnorderedSet& other) noexcept = default;
435
436 inline iterator begin() noexcept {
437 return iterator(data.begin());
438 }
439
440 inline iterator end() noexcept {
441 return iterator(data.end());
442 }
443
444 inline void emplace(value_type&& value) noexcept {
445 data.emplace(std::forward<value_type>(value));
446 }
447
448 inline void emplace(const value_type& value) noexcept {
449 data.emplace(value);
450 }
451
452 inline bool contains(key_type&& key) noexcept {
453 return data.contains(std::forward<key_type>(key));
454 }
455
456 inline bool contains(const key_type& key) noexcept {
457 return data.contains(key);
458 }
459
460 inline void erase(key_type&& key) noexcept {
461 data.erase(std::forward<key_type>(key));
462 }
463
464 inline void erase(const key_type& key) noexcept {
465 data.erase(key);
466 }
467
468 inline iterator find(key_type&& key) noexcept {
469 return data.find(std::forward<key_type>(key));
470 }
471
472 inline iterator find(const key_type& key) noexcept {
473 return data.find(key);
474 }
475
476 inline reference operator[](key_type&& key) noexcept {
477 return *data.find(std::forward<key_type>(key));
478 }
479
480 inline reference operator[](const key_type& key) noexcept {
481 return *data.find(key);
482 }
483
484 inline size_type size() const noexcept {
485 return data.getSize();
486 }
487
488 inline void reserve(size_t newSize) noexcept {
489 data.reserve(newSize);
490 }
491
492 inline bool empty() const noexcept {
493 return data.isEmpty();
494 }
495
496 inline size_type capacity() const noexcept {
497 return data.getCapacity();
498 }
499
500 protected:
501 MemoryCore<key_type, value_type> data{};
502 };
503
504}
The main namespace for this library.