28#include <memory_resource>
29#include <shared_mutex>
33#ifdef __has_cpp_attribute
34 #if __has_cpp_attribute(no_unique_address)
36 #define NO_UNIQUE_ADDRESS [[msvc::no_unique_address]]
38 #define NO_UNIQUE_ADDRESS [[no_unique_address]]
41 #define NO_UNIQUE_ADDRESS
44 #define NO_UNIQUE_ADDRESS
49 template<
typename ValueType =
void>
struct Fnv1aHash {
50 inline uint64_t operator()(
const ValueType& data)
const;
52 inline uint64_t operator()(ValueType&& data)
const;
55 static constexpr uint64_t fnvOffsetBasis{ 14695981039346656037ull };
56 static constexpr uint64_t fnvPrime{ 1099511628211ull };
58 inline uint64_t internalHashFunction(
const uint8_t* value,
size_t count)
const;
61 template<
typename KTy,
typename ValueType>
struct KeyAccessor {
62 KTy& operator()(ValueType& other) {
66 KTy& operator()(ValueType&& other) {
71 template<
typename KTy,
typename ValueType,
typename KATy = KeyAccessor<KTy, ValueType>>
class MemoryCore {
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>;
82 class MemoryCoreIterator {
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;
89 inline MemoryCoreIterator(MemoryCore* core,
size_t index) : core(core), index(index) {
92 inline MemoryCoreIterator& operator++() {
94 while (index < core->capacity && !core->data[index].operator
bool()) {
100 inline bool operator==(
const MemoryCoreIterator& other)
const {
101 return core == other.core && index == other.index;
104 inline bool operator!=(
const MemoryCoreIterator& other)
const {
105 return !(*
this == other);
108 inline reference operator*()
const {
109 return core->data[index];
117 using iterator = MemoryCoreIterator;
119 class SentinelHolder {
121 inline SentinelHolder() noexcept = default;
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;
128 inline operator
bool() const noexcept {
132 inline operator reference() noexcept {
136 inline void activate(value_type&& data)
noexcept {
137 object = std::forward<value_type>(data);
141 inline value_type&& disable() noexcept {
143 return std::move(
object);
151 using sentinel_allocator = std::pmr::polymorphic_allocator<SentinelHolder>;
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]);
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);
168 inline MemoryCore(MemoryCore&& other)
noexcept {
169 *
this = std::move(other);
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);
181 inline MemoryCore(
const MemoryCore& other)
noexcept {
185 inline void emplace(value_type&& value)
noexcept {
186 emplaceInternal(std::forward<value_type>(value));
189 inline void emplace(
const value_type& value)
noexcept {
190 emplaceInternal(value);
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 };
200 index = (index + 1) % capacity;
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 };
214 index = (index + 1) % capacity;
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) {
228 index = (index + 1) % capacity;
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) {
242 index = (index + 1) % capacity;
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();
256 if (size < capacity / 4 && capacity > 10) {
257 resize(capacity / 2);
261 index = (index + 1) % capacity;
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();
273 if (size < capacity / 4 && capacity > 10) {
274 resize(capacity / 2);
278 index = (index + 1) % capacity;
283 inline iterator begin() noexcept {
285 while (index < capacity) {
286 if (data[index].
operator bool()) {
287 return iterator{
this, index };
294 inline iterator end() noexcept {
295 return iterator{
this, capacity };
298 inline iterator begin() const noexcept {
300 while (index < capacity) {
301 if (data[index].
operator bool()) {
302 return iterator{
this, index };
309 inline iterator end() const noexcept {
310 return iterator{
this, capacity };
313 inline size_type getSize() const noexcept {
317 inline bool isEmpty() const noexcept {
321 inline bool isFull() const noexcept {
322 return static_cast<float>(size) >=
static_cast<float>(capacity) * 0.75f;
325 inline void reserve(
size_t newSize)
noexcept {
329 inline size_t getCapacity() const noexcept {
333 inline ~MemoryCore() noexcept {
334 if (data && capacity > 0) {
335 allocator.deallocate(data, capacity);
340 NO_UNIQUE_ADDRESS sentinel_allocator allocator{};
341 SentinelHolder* data{};
342 size_type capacity{};
345 inline void emplaceInternal(value_type&& value, uint64_t recursionLimit = 1000) noexcept {
347 resize(roundUpToCacheLine(capacity * 4), recursionLimit);
349 size_type index = key_hasher{}(key_accessor{}(value)) % capacity;
350 size_type currentIndex = index;
351 bool inserted =
false;
353 if (!data[currentIndex].
operator bool()) {
354 data[currentIndex].activate(std::forward<value_type>(value));
357 }
else if (key_accessor{}(data[currentIndex].operator reference()) == key_accessor{}(value)) {
358 data[currentIndex].activate(std::forward<value_type>(value));
361 currentIndex = (currentIndex + 1) % capacity;
362 if (currentIndex == index) {
363 resize(roundUpToCacheLine(capacity * 4), recursionLimit);
364 emplaceInternal(std::forward<value_type>(value), recursionLimit);
371 inline void emplaceInternal(
const value_type& value, uint64_t recursionLimit = 1000) noexcept {
373 resize(roundUpToCacheLine(capacity * 4), recursionLimit);
375 size_type index = key_hasher{}(key_accessor{}(value)) % capacity;
376 size_type currentIndex = index;
377 bool inserted =
false;
378 value_type newElement{ value };
380 if (!data[currentIndex].
operator bool()) {
381 data[currentIndex].activate(std::move(newElement));
384 }
else if (key_accessor{}(data[currentIndex].operator reference()) == key_accessor{}(value)) {
385 data[currentIndex].activate(std::move(newElement));
388 currentIndex = (currentIndex + 1) % capacity;
389 if (currentIndex == index) {
390 resize(roundUpToCacheLine(capacity * 4), recursionLimit);
391 emplaceInternal(value, recursionLimit);
398 inline void resize(size_type newCapacity, uint64_t recursionLimit = 1000) {
400 if (recursionLimit == 0) {
401 throw std::runtime_error{
"Sorry, but the max number of recursive resizes have been exceeded." };
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);
409 std::swap(data, newData.data);
410 std::swap(capacity, newData.capacity);
413 size_type roundUpToCacheLine(size_type size) {
414 const size_type multiple = 64 /
sizeof(
void*);
415 return (size + multiple - 1) / multiple * multiple;
419 template<
typename KTy,
typename ValueType,
typename KATy = KeyAccessor<KTy, ValueType>>
class UnorderedSet {
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;
429 inline UnorderedSet() : data{ 5 } {};
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;
436 inline iterator begin() noexcept {
437 return iterator(data.begin());
440 inline iterator end() noexcept {
441 return iterator(data.end());
444 inline void emplace(value_type&& value)
noexcept {
445 data.emplace(std::forward<value_type>(value));
448 inline void emplace(
const value_type& value)
noexcept {
452 inline bool contains(key_type&& key)
noexcept {
453 return data.contains(std::forward<key_type>(key));
456 inline bool contains(
const key_type& key)
noexcept {
457 return data.contains(key);
460 inline void erase(key_type&& key)
noexcept {
461 data.erase(std::forward<key_type>(key));
464 inline void erase(
const key_type& key)
noexcept {
468 inline iterator find(key_type&& key)
noexcept {
469 return data.find(std::forward<key_type>(key));
472 inline iterator find(
const key_type& key)
noexcept {
473 return data.find(key);
476 inline reference operator[](key_type&& key)
noexcept {
477 return *data.find(std::forward<key_type>(key));
480 inline reference operator[](
const key_type& key)
noexcept {
481 return *data.find(key);
484 inline size_type size() const noexcept {
485 return data.getSize();
488 inline void reserve(
size_t newSize)
noexcept {
489 data.reserve(newSize);
492 inline bool empty() const noexcept {
493 return data.isEmpty();
496 inline size_type capacity() const noexcept {
497 return data.getCapacity();
501 MemoryCore<key_type, value_type> data{};
The main namespace for this library.