More work on hash maps.

6 files changed, 390 insertions, 85 deletions

diff --git a/include/fud_algorithm.hpp b/include/fud_algorithm.hpp
index 82e98cb..ef55d21 100644
--- a/include/fud_algorithm.hpp
+++ b/include/fud_algorithm.hpp
@@ -18,6 +18,7 @@
 #ifndef FUD_ALGORITHM_HPP
 #define FUD_ALGORITHM_HPP
 
+#include "fud_algorithm_no_dep.hpp" // IWYU pragma: export
 #include "fud_option.hpp"
 #include "fud_span.hpp"
 
@@ -26,32 +27,6 @@
 
 namespace fud {
 
-template<typename T>
-concept LessThanComparable =
-    requires(T lhs, T rhs) {
-        { lhs < rhs } -> std::convertible_to<bool>;
-};
-
-template <LessThanComparable T>
-inline const T& min(const T& lhs, const T& rhs) {
-    if (lhs < rhs) {
-        // NOLINTNEXTLINE(bugprone-return-const-ref-from-parameter)
-        return lhs;
-    }
-    // NOLINTNEXTLINE(bugprone-return-const-ref-from-parameter)
-    return rhs;
-}
-
-template <LessThanComparable T>
-inline const T& max(const T& lhs, const T& rhs) {
-    if (lhs < rhs) {
-        // NOLINTNEXTLINE(bugprone-return-const-ref-from-parameter)
-        return rhs;
-    }
-    // NOLINTNEXTLINE(bugprone-return-const-ref-from-parameter)
-    return lhs;
-}
-
 template <std::integral T>
 class Iota {
   public:
diff --git a/include/fud_algorithm_no_dep.hpp b/include/fud_algorithm_no_dep.hpp
new file mode 100644
index 0000000..a69761c
--- /dev/null
+++ b/include/fud_algorithm_no_dep.hpp
@@ -0,0 +1,72 @@
+/*
+ * libfud
+ * Copyright 2025 Dominick Allen
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/** \file This file breaks a dependency chain; min and max are intended to be part of fud_algorithm.
+ *
+ * Consumers are encouraged to include fud_algorithm.hpp instead.
+ */
+
+#ifndef FUD_ALGORITHM_NO_DEP_HPP
+#define FUD_ALGORITHM_NO_DEP_HPP
+
+#include <concepts>
+#include <utility>
+
+namespace fud {
+
+// NOLINTBEGIN(bugprone-return-const-ref-from-parameter)
+
+template <typename T>
+concept LessThanComparable = requires(T lhs, T rhs) {
+    { lhs < rhs } -> std::convertible_to<bool>;
+};
+
+template <LessThanComparable T>
+constexpr const T& min(const T& lhs, const T& rhs)
+{
+    if (lhs < rhs) {
+        return lhs;
+    }
+    return rhs;
+}
+
+template <LessThanComparable T>
+constexpr const T& max(const T& lhs, const T& rhs)
+{
+    if (lhs < rhs) {
+        return rhs;
+    }
+    return lhs;
+}
+
+template <typename T, typename... Args>
+constexpr const T& max(const T& first, const T& second, Args&&... args)
+{
+    return max(first, max(second, std::forward<Args>(args)...));
+}
+
+template <typename T, typename... Args>
+constexpr const T& min(const T& first, const T& second, Args&&... args)
+{
+    return min(first, min(second, std::forward<Args>(args)...));
+}
+
+// NOLINTEND(bugprone-return-const-ref-from-parameter)
+
+} // namespace fud
+
+#endif
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};
         }
diff --git a/include/fud_hash_map_impl.hpp b/include/fud_hash_map_impl.hpp
new file mode 100644
index 0000000..e4b79c4
--- /dev/null
+++ b/include/fud_hash_map_impl.hpp
@@ -0,0 +1,180 @@
+/*
+ * libfud
+ * Copyright 2025 Dominick Allen
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef FUD_HASH_MAP_IMPL_HPP
+#define FUD_HASH_MAP_IMPL_HPP
+
+#include "fud_hash.hpp"
+
+namespace fud {
+
+template <typename Key, typename Value, typename Hash = detail::DefaultHash<Key>>
+class HashMap;
+
+} // namespace fud
+
+namespace fud::detail {
+
+enum class BucketState : uint8_t
+{
+    Disengaged,
+    Engaged,
+    Tombstoned
+};
+
+template <typename Key, typename Value>
+struct MapEntry {
+    static_assert(!std::is_same_v<Key, option_detail::NullOptionType>);
+    static_assert(!std::is_same_v<Value, option_detail::NullOptionType>);
+    static_assert(!std::is_reference_v<Key>);
+    static_assert(!std::is_reference_v<Value>);
+
+    constexpr MapEntry() noexcept : m_state{BucketState::Disengaged}
+    {
+    }
+
+    constexpr MapEntry(const Key& key, const Value& value) : m_state{BucketState::Engaged}
+    {
+        new (m_keyData.data()) Key(key);
+        new (m_valueData.data()) Value(value);
+    }
+
+    constexpr MapEntry(Key&& key, const Value& value) : m_state{BucketState::Engaged}
+    {
+        new (m_keyData.data()) Key(std::move(key));
+        new (m_valueData.data()) Value(value);
+    }
+
+    constexpr MapEntry(const Key& key, Value&& value) : m_state{BucketState::Engaged}
+    {
+        new (m_keyData.data()) Key(key);
+        new (m_valueData.data()) Value(std::move(value));
+    }
+
+    constexpr MapEntry(Key&& key, Value&& value) : m_state{BucketState::Engaged}
+    {
+        new (m_keyData.data()) Key(std::move(key));
+        new (m_valueData.data()) Value(std::move(value));
+    }
+
+    constexpr MapEntry(const MapEntry& rhs) noexcept :
+        m_keyData(rhs.m_keyData), m_valueData(rhs.m_valueData), m_state(rhs.m_state)
+    {
+    }
+
+    constexpr MapEntry(MapEntry&& rhs) noexcept :
+        m_keyData(std::move(rhs.m_keyData)), m_valueData(std::move(rhs.m_valueData)), m_state(rhs.m_state)
+    {
+        rhs.destroy(false);
+    }
+
+    constexpr MapEntry& operator=(const MapEntry& rhs) noexcept
+    {
+        if (&rhs == this) {
+            return *this;
+        }
+        destroy(false);
+        m_keyData = rhs.m_keyData;
+        m_valueData = rhs.m_valueData;
+        m_state = rhs.m_state;
+        return *this;
+    }
+
+    constexpr MapEntry& operator=(MapEntry&& rhs) noexcept
+    {
+        if (&rhs == this) {
+            return *this;
+        }
+        destroy(false);
+        m_keyData = rhs.m_keyData;
+        m_valueData = rhs.m_valueData;
+        m_state = rhs.m_state;
+        rhs.destroy(false);
+        return *this;
+    }
+
+    constexpr ~MapEntry() noexcept
+    {
+        destroy(false);
+    }
+
+    [[nodiscard]] constexpr bool hasValue() const
+    {
+        return m_state == BucketState::Engaged;
+    }
+
+    [[nodiscard]] constexpr bool isNone() const
+    {
+        return m_state == BucketState::Disengaged;
+    }
+
+    [[nodiscard]] constexpr bool isTombstone() const
+    {
+        return m_state == BucketState::Tombstoned;
+    }
+
+    [[nodiscard]] constexpr const Key& key() const&
+    {
+        fudAssert(hasValue());
+        return *std::bit_cast<const Key*>(m_keyData.data());
+    }
+
+    [[nodiscard]] constexpr const Value& value() const&
+    {
+        fudAssert(hasValue());
+        return *std::bit_cast<const Value*>(m_valueData.data());
+    }
+
+    [[nodiscard]] constexpr Key& key() &
+    {
+        fudAssert(hasValue());
+        return *std::bit_cast<Key*>(m_keyData.data());
+    }
+
+    [[nodiscard]] constexpr Value& value() &
+    {
+        fudAssert(hasValue());
+        return *std::bit_cast<Value*>(m_valueData.data());
+    }
+
+    constexpr void tombstone() noexcept
+    {
+        destroy(true);
+    }
+
+    constexpr void destroy(bool entomb) noexcept
+    {
+        if (m_state == BucketState::Engaged) {
+            std::bit_cast<Key*>(m_keyData.data())->~Key();
+            m_keyData.clear();
+            std::bit_cast<Value*>(m_valueData.data())->~Value();
+            m_valueData.clear();
+            m_state = entomb ? BucketState::Tombstoned : BucketState::Disengaged;
+        } else if (m_state == BucketState::Tombstoned and not entomb) {
+            m_state = BucketState::Disengaged;
+        }
+    }
+
+    static constexpr auto Align = max(alignof(Key), alignof(Value));
+    alignas(alignof(Key)) option_detail::DataArray<sizeof(Key)> m_keyData{};
+    alignas(alignof(Value)) option_detail::DataArray<sizeof(Value)> m_valueData{};
+    BucketState m_state{BucketState::Disengaged};
+};
+
+} // namespace fud::detail
+
+#endif
diff --git a/include/fud_option.hpp b/include/fud_option.hpp
index f2e86ca..d8b7114 100644
--- a/include/fud_option.hpp
+++ b/include/fud_option.hpp
@@ -19,6 +19,7 @@
 #define FUD_OPTION_HPP
 
 #include "fud_assert.hpp"
+#include "fud_algorithm_no_dep.hpp"
 
 #include <cstddef>
 #include <functional>
@@ -42,9 +43,8 @@ struct NullOptionType {
 
 template <size_t Size>
 struct DataArray {
-    // NOLINTBEGIN(cppcoreguidelines-avoid-c-arrays)
+    // NOLINTNEXTLINE(cppcoreguidelines-avoid-c-arrays)
     std::byte m_data[Size];
-    // NOLINTEND(cppcoreguidelines-avoid-c-arrays)
 
     constexpr std::byte* data() noexcept
     {
@@ -121,18 +121,6 @@ class Option {
         destroy();
     }
 
-    constexpr static Option take(T&& value) noexcept
-    {
-        Option option{};
-        option.m_engaged = true;
-        if constexpr (IsRef) {
-            new (option.m_data.data()) std::reference_wrapper<ValueType>(std::ref(value));
-        } else {
-            new (option.m_data.data()) ValueType(std::move(value));
-        }
-        return option;
-    }
-
     Option& operator=(const Option& rhs) noexcept
     {
         if (&rhs == this) {
@@ -153,6 +141,18 @@ class Option {
         return *this;
     }
 
+    constexpr static Option take(T&& value) noexcept
+    {
+        Option option{};
+        option.m_engaged = true;
+        if constexpr (IsRef) {
+            new (option.m_data.data()) std::reference_wrapper<ValueType>(std::ref(value));
+        } else {
+            new (option.m_data.data()) ValueType(std::move(value));
+        }
+        return option;
+    }
+
     [[nodiscard]] bool hasValue() const
     {
         return m_engaged;
@@ -249,7 +249,7 @@ class Option {
         m_data.clear();
     }
 
-    static constexpr auto Align = std::max(alignof(ValueType), alignof(std::reference_wrapper<ValueType>));
+    static constexpr auto Align = max(alignof(ValueType), alignof(std::reference_wrapper<ValueType>));
     alignas(Align) option_detail::DataArray<Size> m_data{};
 
     bool m_engaged;
diff --git a/include/fud_result.hpp b/include/fud_result.hpp
index 0394156..4e08323 100644
--- a/include/fud_result.hpp
+++ b/include/fud_result.hpp
@@ -18,6 +18,7 @@
 #ifndef FUD_RESULT_HPP
 #define FUD_RESULT_HPP
 
+#include "fud_algorithm_no_dep.hpp"
 #include "fud_assert.hpp"
 #include "fud_option.hpp"
 #include "fud_status.hpp"
@@ -25,7 +26,6 @@
 #include <cstdint>
 #include <new> // IWYU pragma: keep (placement new)
 #include <type_traits>
-#include <utility>
 
 namespace fud {
 
@@ -307,8 +307,8 @@ class [[nodiscard]] Result {
         }
     }
 
-    static constexpr auto Size = std::max(sizeof(T), sizeof(E));
-    static constexpr auto Align = std::max(alignof(T), alignof(E));
+    static constexpr auto Size = max(sizeof(T), sizeof(E));
+    static constexpr auto Align = max(alignof(T), alignof(E));
     alignas(Align) option_detail::DataArray<Size> m_data{};
 
     enum class Discriminant : uint8_t