From 5f21ebf42e670470b315a992b8a60f7c2e2bbbeb Mon Sep 17 00:00:00 2001
From: Steven Le Rouzic <steven.lerouzic@gmail.com>
Date: Tue, 14 Jan 2025 22:50:34 +0100
Subject: Add remove element to hash_set

---
 asl/hash_set.hpp             | 17 +++++++++++-
 asl/tests/hash_set_tests.cpp | 63 ++++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 77 insertions(+), 3 deletions(-)

(limited to 'asl')

diff --git a/asl/hash_set.hpp b/asl/hash_set.hpp
index 22e47e0..fa95a96 100644
--- a/asl/hash_set.hpp
+++ b/asl/hash_set.hpp
@@ -114,6 +114,8 @@ class hash_set
 
     isize_t find_slot(const T& value) const
     {
+        if (m_size <= 0) { return -1; };
+
         ASL_ASSERT(is_pow2(m_capacity));
 
         const isize_t capacity_mask = m_capacity - 1;
@@ -246,9 +248,22 @@ public:
 
     bool contains(const T& value) const
     {
-        if (m_size == 0) { return false; }
         return find_slot(value) >= 0;
     }
+
+    // @Todo Remove with something comparable, but not equal? How to hash?
+    // @Todo Same with contains
+    bool remove(const T& value)
+    {
+        isize_t slot = find_slot(value);
+        if (slot < 0) { return false; }
+
+        m_values[slot].destroy_unsafe(); // NOLINT(*-pointer-arithmetic)
+        m_tags[slot] = kTombstone; // NOLINT(*-pointer-arithmetic)
+        m_size -= 1;
+
+        return true;
+    }
 };
 
 } // namespace asl
diff --git a/asl/tests/hash_set_tests.cpp b/asl/tests/hash_set_tests.cpp
index e8d744b..e6a020a 100644
--- a/asl/tests/hash_set_tests.cpp
+++ b/asl/tests/hash_set_tests.cpp
@@ -1,5 +1,6 @@
 #include "asl/hash_set.hpp"
 #include "asl/testing/testing.hpp"
+#include "asl/tests/test_types.hpp"
 #include "asl/string.hpp"
 #include "asl/string_view.hpp"
 
@@ -53,7 +54,65 @@ ASL_TEST(a_bunch_of_ints)
     }
 }
 
-// @Todo Remove elements
+struct HashWithDestructor: public DestructorObserver
+{
+    int x;
+
+    HashWithDestructor(int x_, bool* ptr)
+        : DestructorObserver{ptr}
+        , x{x_}
+    {}
+
+    constexpr bool operator==(const HashWithDestructor& other) const
+    {
+        return x == other.x;
+    }
 
-// @Todo Test destructors
+    template<typename H>
+    friend H AslHashValue(H h, const HashWithDestructor& value)
+    {
+        return H::combine(ASL_MOVE(h), value.x);
+    }
+};
+
+ASL_TEST(destructor_and_remove)
+{
+    static constexpr int kCount = 200;
+    bool destroyed[kCount]{};
+
+    {
+        asl::hash_set<HashWithDestructor> set;
+
+        for (int i = 0; i < kCount; ++i)
+        {
+            set.insert(i, &destroyed[i]); // NOLINT
+        }
+
+        ASL_TEST_EXPECT(set.size() == kCount);
+
+        for (int i = 0; i < kCount; ++i)
+        {
+            ASL_TEST_EXPECT(!destroyed[i]); // NOLINT
+        }
+
+        for (int i = 0; i < kCount; i += 2)
+        {
+            // @Todo Remove with something comparable
+            ASL_TEST_EXPECT(set.remove(HashWithDestructor{i, nullptr}));
+        }
+
+        for (int i = 0; i < kCount; i += 2)
+        {
+            ASL_TEST_EXPECT(!set.contains(HashWithDestructor{i, nullptr}));
+            ASL_TEST_EXPECT(set.contains(HashWithDestructor{i+1, nullptr}));
+            ASL_TEST_EXPECT(destroyed[i]); // NOLINT
+            ASL_TEST_EXPECT(!destroyed[i + 1]); // NOLINT
+        }
+    }
+
+    for (int i = 0; i < kCount; ++i)
+    {
+        ASL_TEST_EXPECT(destroyed[i]); // NOLINT
+    }
+}
 
-- 
cgit