From e6d9330a978373ffc24209b5edf03eda6491f818 Mon Sep 17 00:00:00 2001
From: Dominick Allen <djallen@librehumanitas.org>
Date: Wed, 2 Apr 2025 06:43:43 -0500
Subject: Add more testing for hash maps.

---
 include/fud_hash.hpp          |   3 ++
 include/fud_hash_map.hpp      | 113 ++++++++++++++++++++++++++++++++++++++----
 include/fud_hash_map_impl.hpp |   6 +++
 3 files changed, 112 insertions(+), 10 deletions(-)

(limited to 'include')

diff --git a/include/fud_hash.hpp b/include/fud_hash.hpp
index a472171..8567e1f 100644
--- a/include/fud_hash.hpp
+++ b/include/fud_hash.hpp
@@ -36,6 +36,9 @@ namespace fud::detail {
 
 constexpr uint64_t roundToNearest2(uint64_t inputValue) noexcept
 {
+    if (inputValue == 0) {
+        return 1;
+    }
     uint64_t outputValue = inputValue - 1;
     constexpr uint8_t max2PowerShift = 32;
     for (uint8_t shift = 1; shift <= max2PowerShift; shift *= 2) {
diff --git a/include/fud_hash_map.hpp b/include/fud_hash_map.hpp
index dd6d080..9220876 100644
--- a/include/fud_hash_map.hpp
+++ b/include/fud_hash_map.hpp
@@ -194,10 +194,49 @@ class HashMap {
         return FudStatus::Success;
     }
 
-    FudStatus replace(const Key& key, const Value& value);
-    FudStatus replace(const Key& key, Value&& value);
-    FudStatus replace(Key&& key, const Value& value);
-    FudStatus replace(Key&& key, Value&& value);
+    FudStatus update(const Key& key, const Value& value)
+    {
+        auto hashIndexOption = lookup(key);
+        if (hashIndexOption.isNone()) {
+            return insert(key, value);
+        }
+        auto hashIndex{hashIndexOption.take()};
+        m_data[hashIndex].value() = value;
+        return FudStatus::Success;
+    }
+
+    FudStatus update(const Key& key, Value&& value)
+    {
+        auto hashIndexOption = lookup(key);
+        if (hashIndexOption.isNone()) {
+            return insert(key, std::move(value));
+        }
+        auto hashIndex{hashIndexOption.take()};
+        m_data[hashIndex].value() = std::move(value);
+        return FudStatus::Success;
+    }
+
+    FudStatus update(Key&& key, const Value& value)
+    {
+        auto hashIndexOption = lookup(key);
+        if (hashIndexOption.isNone()) {
+            return insert(std::move(key), value);
+        }
+        auto hashIndex{hashIndexOption.take()};
+        m_data[hashIndex].value() = value;
+        return FudStatus::Success;
+    }
+
+    FudStatus update(Key&& key, Value&& value)
+    {
+        auto hashIndexOption = lookup(key);
+        if (hashIndexOption.isNone()) {
+            return insert(std::move(key), std::move(value));
+        }
+        auto hashIndex{hashIndexOption.take()};
+        m_data[hashIndex].value() = std::move(value);
+        return FudStatus::Success;
+    }
 
     FudStatus remove(const Key& key)
     {
@@ -223,10 +262,61 @@ class HashMap {
         return FudStatus::Success;
     }
 
-    Option<Value> extract(const Key& key);
-    Option<Value> extract(Key& key);
-    Node extractPair(const Key& key);
-    Node extractPair(Key& key);
+    Option<Value> extract(const Key& key)
+    {
+        auto hashIndexOption = lookup(key);
+        if (hashIndexOption.isNone()) {
+            return NullOpt;
+        }
+
+        auto hashIndex{hashIndexOption.value()};
+        Option<Value> value{std::move(m_data[hashIndex].takeValue())};
+        m_data[hashIndex].tombstone();
+
+        return value;
+    }
+
+    Option<Value> extract(Key&& key)
+    {
+        auto hashIndexOption = lookup(std::move(key));
+        if (hashIndexOption.isNone()) {
+            return NullOpt;
+        }
+
+        auto hashIndex{hashIndexOption.value()};
+        Option<Value> value{std::move(m_data[hashIndex].takeValue())};
+        m_data[hashIndex].tombstone();
+
+        return value;
+    }
+
+    KeyValuePair extractPair(const Key& key)
+    {
+        auto hashIndexOption = lookup(key);
+        if (hashIndexOption.isNone()) {
+            return NullOpt;
+        }
+
+        auto hashIndex{hashIndexOption.value()};
+        KeyValuePair kvPair{key, m_data[hashIndex].takeValue()};
+        m_data[hashIndex].tombstone();
+
+        return kvPair;
+    }
+
+    KeyValuePair extractPair(Key&& key)
+    {
+        auto hashIndexOption = lookup(key);
+        if (hashIndexOption.isNone()) {
+            return NullOpt;
+        }
+
+        auto hashIndex{hashIndexOption.value()};
+        KeyValuePair kvPair{std::move(key), m_data[hashIndex].takeValue()};
+        m_data[hashIndex].tombstone();
+
+        return kvPair;
+    }
 
     Option<Value> get(const Key& key)
     {
@@ -328,7 +418,7 @@ class HashMap {
         return status;
     }
 
-    Result<Value, FudStatus> exchange(const Key& key, const Value& value);
+    Result<Option<Value>, FudStatus> exchange(const Key& key, const Value& value);
 
   protected:
     [[nodiscard]] double loadFactor() const
@@ -398,6 +488,9 @@ class HashMap {
 
     Option<size_t> lookup(const Key& key) const
     {
+        if (m_count == 0 || m_buckets == 0 || m_data == nullptr) {
+            return NullOpt;
+        }
         const auto hash = m_hasher(key, m_seed);
         const auto nearestPowerOf2 = detail::roundToNearest2(m_buckets);
         size_t probe = 0;
@@ -419,7 +512,7 @@ class HashMap {
             }
         }
 
-        if (collision and m_data[hashIndex].key() == key) {
+        if (collision and hashIndex < m_buckets and m_data[hashIndex].key() == key) {
             return hashIndex;
         }
 
diff --git a/include/fud_hash_map_impl.hpp b/include/fud_hash_map_impl.hpp
index e4b79c4..6e224f9 100644
--- a/include/fud_hash_map_impl.hpp
+++ b/include/fud_hash_map_impl.hpp
@@ -151,6 +151,12 @@ struct MapEntry {
         return *std::bit_cast<Value*>(m_valueData.data());
     }
 
+    [[nodiscard]] Value&& takeValue() &
+    {
+        fudAssert(hasValue());
+        return std::move(*std::bit_cast<Value*>(m_valueData.data()));
+    }
+
     constexpr void tombstone() noexcept
     {
         destroy(true);
-- 
cgit v1.2.3