More work on hash maps.

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};
         }