diff options
| author | Steven Le Rouzic <steven.lerouzic@gmail.com> | 2025-01-14 22:50:34 +0100 |
|---|---|---|
| committer | Steven Le Rouzic <steven.lerouzic@gmail.com> | 2025-01-14 22:50:34 +0100 |
| commit | 5f21ebf42e670470b315a992b8a60f7c2e2bbbeb (patch) | |
| tree | 9e8408aedec5639205f13d474222b8c311ef77b7 /asl | |
| parent | 1c00f6ed444dab15430a955e41cf155049e3cec4 (diff) | |
Add remove element to hash_set
Diffstat (limited to 'asl')
| -rw-r--r-- | asl/hash_set.hpp | 17 | ||||
| -rw-r--r-- | asl/tests/hash_set_tests.cpp | 63 |
2 files changed, 77 insertions, 3 deletions
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
+ }
+}
|