diff options
Diffstat (limited to 'include/fud_hash_map.hpp')
| -rw-r--r-- | include/fud_hash_map.hpp | 160 |
1 files changed, 119 insertions, 41 deletions
diff --git a/include/fud_hash_map.hpp b/include/fud_hash_map.hpp index 7980bf4..dd6d080 100644 --- a/include/fud_hash_map.hpp +++ b/include/fud_hash_map.hpp @@ -20,6 +20,7 @@ #include "fud_allocator.hpp" #include "fud_hash.hpp" +#include "fud_hash_map_impl.hpp" #include "fud_option.hpp" #include "fud_result.hpp" #include "fud_status.hpp" @@ -33,29 +34,72 @@ constexpr double hashMapMaxLoadFactor = 0.6; /** \brief An open-address hash map using quadratic probing. * * Templates on a Hash object to facilitate a variety of hashing function implementations. */ -template <typename Key, typename Value, typename Hash = detail::DefaultHash<Key>> +template <typename Key, typename Value, typename Hash> class HashMap { + static_assert(!std::is_same_v<Key, option_detail::NullOptionType>); + static_assert(!std::is_same_v<Value, option_detail::NullOptionType>); + public: struct KeyValuePair { Key m_key; Value m_value; }; - using Node = Option<KeyValuePair>; + + using Entry = Option<KeyValuePair>; + using Node = detail::MapEntry<Key, Value>; static constexpr size_t NodeSize = sizeof(Node); static constexpr size_t Alignment = alignof(Node); constexpr HashMap() noexcept = default; - HashMap(const HashMap&) = delete; - HashMap(HashMap&&) = delete; - HashMap& operator=(const HashMap&) = delete; - HashMap& operator=(HashMap&&) = delete; - constexpr ~HashMap() noexcept + + /** \brief Construct a HashMap explicitly using the specified allocator. */ + constexpr explicit HashMap(Allocator& allocator) noexcept : m_allocator{&allocator} { + } + + constexpr HashMap(const HashMap& rhs) = delete; + + constexpr HashMap(HashMap&& rhs) noexcept : + m_allocator{rhs.m_allocator}, + m_data{rhs.m_data}, + m_count{rhs.m_count}, + m_buckets{rhs.m_buckets}, + m_seed{rhs.m_seed}, + m_hasher{std::move(rhs.m_hasher)} + { + rhs.m_allocator = nullptr; + rhs.m_data = nullptr; + rhs.m_count = 0; + rhs.m_buckets = 0; + } + + HashMap& operator=(const HashMap& rhs) = delete; + + HashMap& operator=(HashMap&& rhs) noexcept + { + if (&rhs == this) { + return *this; + } + static_cast<void>(cleanup()); + m_allocator = rhs.m_allocator; + m_data = rhs.m_data; + m_count = rhs.m_count; + m_buckets = rhs.m_buckets; + m_seed = rhs.m_seed; + m_hasher = std::move(rhs.m_hasher); + + rhs.m_allocator = nullptr; + rhs.m_data = nullptr; + rhs.m_count = 0; + rhs.m_buckets = 0; + + return *this; } - /** \brief Construct a HashMap explicitly using the specified allocator. */ - constexpr explicit HashMap(Allocator& allocator) noexcept : m_allocator{&allocator} + + constexpr ~HashMap() noexcept { + static_cast<void>(cleanup()); } [[nodiscard]] size_t size() noexcept @@ -68,8 +112,15 @@ class HashMap { return m_buckets; } - [[nodiscard]] bool contains(const Key& key) const; - [[nodiscard]] bool contains(Key&& key) const; + [[nodiscard]] bool contains(const Key& key) const + { + return lookup(key).hasValue(); + } + + [[nodiscard]] bool contains(Key&& key) const + { + return lookup(std::move(key)).hasValue(); + } FudStatus insert(const Key& key, const Value& value) { @@ -84,7 +135,7 @@ class HashMap { } auto hashIndex{hashIndexResult.takeOkay()}; m_data[hashIndex].~Node(); - auto* ptr = new (m_data + hashIndex) Node{{key, value}}; + auto* ptr = new (m_data + hashIndex) Node{key, value}; m_count++; return FudStatus::Success; } @@ -102,7 +153,7 @@ class HashMap { } auto hashIndex{hashIndexResult.takeOkay()}; m_data[hashIndex].~Node(); - auto* ptr = new (m_data + hashIndex) Node{{key, std::move(value)}}; + auto* ptr = new (m_data + hashIndex) Node{key, std::move(value)}; m_count++; return FudStatus::Success; } @@ -120,7 +171,7 @@ class HashMap { } auto hashIndex{hashIndexResult.takeOkay()}; m_data[hashIndex].~Node(); - auto* ptr = new (m_data + hashIndex) Node{{std::move(key), value}}; + auto* ptr = new (m_data + hashIndex) Node{std::move(key), value}; m_count++; return FudStatus::Success; } @@ -138,7 +189,7 @@ class HashMap { } auto hashIndex{hashIndexResult.takeOkay()}; m_data[hashIndex].~Node(); - auto* ptr = new (m_data + hashIndex) Node{{std::move(key), std::move(value)}}; + auto* ptr = new (m_data + hashIndex) Node{std::move(key), std::move(value)}; m_count++; return FudStatus::Success; } @@ -148,13 +199,34 @@ class HashMap { FudStatus replace(Key&& key, const Value& value); FudStatus replace(Key&& key, Value&& value); - FudStatus remove(const Key& key); - FudStatus remove(Key&& key); + FudStatus remove(const Key& key) + { + auto hashIndexOption = lookup(key); + if (hashIndexOption.isNone()) { + return FudStatus::NotFound; + } + + m_data[hashIndexOption.value()].tombstone(); + + return FudStatus::Success; + } + + FudStatus remove(Key&& key) + { + auto hashIndexOption = lookup(std::move(key)); + if (hashIndexOption.isNone()) { + return FudStatus::NotFound; + } + + m_data[hashIndexOption.value()].tombstone(); + + return FudStatus::Success; + } Option<Value> extract(const Key& key); Option<Value> extract(Key& key); - Option<KeyValuePair> extractPair(const Key& key); - Option<KeyValuePair> extractPair(Key& key); + Node extractPair(const Key& key); + Node extractPair(Key& key); Option<Value> get(const Key& key) { @@ -163,7 +235,7 @@ class HashMap { return NullOpt; } - return m_data[hashIndexOption.value()].value().m_value; + return m_data[hashIndexOption.value()].value(); } Option<Value&> getRef(const Key& key) const @@ -173,7 +245,7 @@ class HashMap { return NullOpt; } - return m_data[hashIndexOption.value()].value().m_value; + return m_data[hashIndexOption.value()].value(); } Option<const Value&> getConstRef(const Key& key) const @@ -183,7 +255,7 @@ class HashMap { return NullOpt; } - return m_data[hashIndexOption.value()].value().m_value; + return m_data[hashIndexOption.value()].value(); } [[nodiscard]] bool empty() const; @@ -225,14 +297,13 @@ class HashMap { auto* dataPtr = std::bit_cast<Node*>(dataPtrResult.takeOkay()); for (size_t index = 0; index < count; ++index) { - const auto* ptr = new (dataPtr + index) Node(NullOpt); + const auto* ptr = new (dataPtr + index) Node(); fudAssert(ptr != nullptr); } for (size_t index = 0; index < m_buckets; ++index) { if (m_data[index].hasValue()) { - const auto& key = m_data[index].value().m_key; - const auto hash = m_hasher(key, m_seed); + const auto& key = m_data[index].key(); auto newHashIndexResult = findEmptyBucket(key, count, dataPtr); if (newHashIndexResult.isError()) { m_allocator->deallocate(std::bit_cast<std::byte*>(dataPtr), requestedSize); @@ -259,7 +330,7 @@ class HashMap { Result<Value, FudStatus> exchange(const Key& key, const Value& value); - private: + protected: [[nodiscard]] double loadFactor() const { if (m_buckets == 0) { @@ -320,7 +391,7 @@ class HashMap { return status; } - [[nodiscard]] constexpr size_t calculateHashIndex(size_t hash, size_t probe) const + [[nodiscard]] static constexpr size_t calculateHashIndex(size_t hash, size_t probe) { return hash + ((probe + probe * probe) / 2); } @@ -335,20 +406,20 @@ class HashMap { while (collision and probe < m_buckets) { hashIndex = calculateHashIndex(hash, probe) % nearestPowerOf2; + probe++; if (hashIndex >= m_buckets) { - probe++; continue; } - collision = m_data[hashIndex].hasValue(); - if (collision and m_data[hashIndex].value().m_key == key) { - break; + collision = not m_data[hashIndex].isNone(); + if (m_data[hashIndex].isTombstone()) { + continue; } - if (collision) { - probe++; + if (collision and m_data[hashIndex].key() == key) { + break; } } - if (collision and m_data[hashIndex].value().m_key == key) { + if (collision and m_data[hashIndex].key() == key) { return hashIndex; } @@ -363,25 +434,32 @@ class HashMap { auto collision = true; size_t probe = 0; + bool foundFirstSlot{false}; + size_t firstHashIndex{}; while (collision and probe < buckets) { hashIndex = calculateHashIndex(hash, probe) % nearestPowerOf2; + probe++; if (hashIndex >= buckets) { - probe++; continue; } - collision = data[hashIndex].hasValue(); - if (collision and data[hashIndex].value().m_key == key) { - break; + collision = not data[hashIndex].isNone(); + if (not foundFirstSlot and data[hashIndex].isTombstone()) { + foundFirstSlot = true; + firstHashIndex = hashIndex; } - if (collision) { - probe++; + if (collision and data[hashIndex].key() == key) { + break; } } - if (collision and data[hashIndex].value().m_key == key) { + if (collision and data[hashIndex].key() == key) { return Error{FudStatus::Exists}; } + if (foundFirstSlot) { + return Okay{firstHashIndex}; + } + if (collision) { return Error{FudStatus::Failure}; } |