From 0ee5725793f62e6b0386b66d21aee5eebfd7be13 Mon Sep 17 00:00:00 2001
From: Steven Le Rouzic <steven.lerouzic@gmail.com>
Date: Wed, 15 Jan 2025 23:50:56 +0100
Subject: Add copy & move for hash_set

---
 asl/hash_set.hpp             | 100 +++++++++++++++++++++++++++++++++++++------
 asl/tests/hash_set_tests.cpp |  49 +++++++++++++++++++++
 2 files changed, 137 insertions(+), 12 deletions(-)

(limited to 'asl')

diff --git a/asl/hash_set.hpp b/asl/hash_set.hpp
index d48a865..c3fb38d 100644
--- a/asl/hash_set.hpp
+++ b/asl/hash_set.hpp
@@ -47,7 +47,7 @@ template<
     key_hasher<T> KeyHasher = default_key_hasher<T>,
     key_comparator<T> KeyComparator = default_key_comparator<T>
 >
-requires move_constructible<T> && move_assignable<T>
+requires moveable<T>
 class hash_set
 {
     static constexpr uint8_t kHasValue  = 0x80;
@@ -73,6 +73,14 @@ class hash_set
         return (m_capacity >> 1) + (m_capacity >> 2);
     }
 
+    static isize_t size_to_capacity(isize_t size)
+    {
+        ASL_ASSERT(size > 0);
+        return max<isize_t>(
+            kMinCapacity,
+            static_cast<isize_t>(round_up_pow2((static_cast<uint64_t>(size) * 4 + 2) / 3)));
+    }
+
     static void insert_inner(
         T&& value,
         uint8_t* tags,
@@ -177,10 +185,15 @@ class hash_set
 
         return -1;
     }
-
+    
     void grow_and_rehash()
     {
-        isize_t new_capacity = max(kMinCapacity, m_capacity * 2);
+        grow_and_rehash(max(kMinCapacity, m_capacity * 2));
+    }
+
+    void grow_and_rehash(isize_t new_capacity)
+    {
+        ASL_ASSERT(new_capacity >= kMinCapacity && is_pow2(new_capacity) && new_capacity > m_capacity);
         
         auto* new_tags = reinterpret_cast<uint8_t*>(m_allocator.alloc(layout::array<uint8_t>(new_capacity)));
         auto* new_values = reinterpret_cast<maybe_uninit<T>*>(m_allocator.alloc(layout::array<maybe_uninit<T>>(new_capacity)));
@@ -188,18 +201,21 @@ class hash_set
 
         isize_t new_size = 0;
 
-        // NOLINTBEGIN(*-pointer-arithmetic)
-        for (isize_t i = 0; i < m_capacity; ++i)
+        if (m_size > 0)
         {
-            if ((m_tags[i] & kHasValue) == 0) { continue; }
+            // NOLINTBEGIN(*-pointer-arithmetic)
+            for (isize_t i = 0; i < m_capacity; ++i)
+            {
+                if ((m_tags[i] & kHasValue) == 0) { continue; }
 
-            insert_inner(ASL_MOVE(m_values[i].as_init_unsafe()), new_tags, new_values, new_capacity, &new_size);
+                insert_inner(ASL_MOVE(m_values[i].as_init_unsafe()), new_tags, new_values, new_capacity, &new_size);
 
-            // Destroy now so that destroy() has less things to do
-            m_values[i].destroy_unsafe();
-            m_tags[i] = kTombstone;
+                // Destroy now so that destroy() has less things to do
+                m_values[i].destroy_unsafe();
+                m_tags[i] = kTombstone;
+            }
+            // NOLINTEND(*-pointer-arithmetic)
         }
-        // NOLINTEND(*-pointer-arithmetic)
 
         ASL_ASSERT(new_size == m_size);
 
@@ -229,6 +245,27 @@ class hash_set
         }
     }
 
+    void copy_from(const hash_set& other)
+    {
+        if (other.size() > 0)
+        {
+            isize_t min_capacity = size_to_capacity(other.size());
+            if (m_capacity < min_capacity)
+            {
+                grow_and_rehash(min_capacity);
+            }
+            ASL_ASSERT(m_capacity >= min_capacity);
+
+            for (isize_t i = 0; i < other.m_capacity; ++i)
+            {
+                if ((other.m_tags[i] & kHasValue) != 0) // NOLINT(*-pointer-arithmetic)
+                {
+                    insert(other.m_values[i].as_init_unsafe()); // NOLINT(*-pointer-arithmetic)
+                }
+            }
+        }
+    }
+
 public:
     constexpr hash_set() requires default_constructible<Allocator>
         : m_allocator{}
@@ -238,7 +275,46 @@ public:
         : m_allocator{ASL_MOVE(allocator)}
     {}
 
-    // @Todo Copy, move
+    hash_set(const hash_set& other)
+        requires copy_constructible<Allocator> && copyable<T>
+        : hash_set{other.m_allocator}
+    {
+        copy_from(other);
+    }
+
+    hash_set& operator=(const hash_set& other)
+        requires copyable<T>
+    {
+        if (&other != this)
+        {
+            clear();
+            copy_from(other);
+        }
+        return *this;
+    }
+
+    hash_set(hash_set&& other)
+        requires move_constructible<Allocator>
+        : m_tags{exchange(other.m_tags, nullptr)}
+        , m_values{exchange(other.m_values, nullptr)}
+        , m_capacity{exchange(other.m_capacity, 0)}
+        , m_size{exchange(other.m_size, 0)}
+        , m_allocator{ASL_MOVE(other.m_allocator)}
+    {}
+
+    hash_set& operator=(hash_set&& other)
+    {
+        if (&other != this)
+        {
+            destroy();
+            m_tags = exchange(other.m_tags, nullptr);
+            m_values = exchange(other.m_values, nullptr);
+            m_capacity = exchange(other.m_capacity, 0);
+            m_size = exchange(other.m_size, 0);
+            m_allocator = ASL_MOVE(other.m_allocator);
+        }
+        return *this;
+    }
 
     ~hash_set()
     {
diff --git a/asl/tests/hash_set_tests.cpp b/asl/tests/hash_set_tests.cpp
index 9df9463..56cb07a 100644
--- a/asl/tests/hash_set_tests.cpp
+++ b/asl/tests/hash_set_tests.cpp
@@ -134,3 +134,52 @@ ASL_TEST(destructor_and_remove)
     }
 }
 
+ASL_TEST(copy)
+{
+    asl::hash_set<int> set1;
+    
+    for (int i = 0; i < 100; ++i)
+    {
+        set1.insert(i);
+    }
+
+    asl::hash_set<int> set2 = set1;
+    asl::hash_set<int> set3;
+    set3 = set1;
+
+    ASL_TEST_EXPECT(set2.size() == 100);
+    ASL_TEST_EXPECT(set3.size() == 100);
+    
+    for (int i = 0; i < 100; ++i)
+    {
+        ASL_TEST_EXPECT(set2.contains(i));
+        ASL_TEST_EXPECT(set3.contains(i));
+    }
+}
+
+ASL_TEST(move)
+{
+    asl::hash_set<int> set1;
+    
+    for (int i = 0; i < 100; ++i)
+    {
+        set1.insert(i);
+    }
+
+    asl::hash_set<int> set2 = ASL_MOVE(set1);
+
+    ASL_TEST_EXPECT(set2.size() == 100);
+    for (int i = 0; i < 100; ++i)
+    {
+        ASL_TEST_EXPECT(set2.contains(i));
+    }
+
+    set1 = ASL_MOVE(set2);
+
+    ASL_TEST_EXPECT(set1.size() == 100);
+    for (int i = 0; i < 100; ++i)
+    {
+        ASL_TEST_EXPECT(set1.contains(i));
+    }
+}
+
-- 
cgit