Add TODO(#854)

[nothing.git] / src / hashset.c

diff --git a/src/hashset.c b/src/hashset.c
index 12f0ba9be327b86b827b05ec95b69b052fcdd2d0..50676726792c166e9e77046a043cc7cf45b7cd35 100644 (file)
--- a/src/hashset.c
+++ b/src/hashset.c
@@ -5,18 +5,20 @@
 #include "system/lt.h"
 #include "system/stacktrace.h"
 #include "system/nth_alloc.h"
-#include "linked_list.h"
 #include "hashset.h"
+#include "dynarray.h"
 
 struct HashSet
 {
     Lt *lt;
     size_t n;
     size_t element_size;
-    LinkedList **buckets;
+    size_t count;
+    Dynarray **buckets;
+    Dynarray *view;
 };
 
-static uint64_t fnv1(char *data, size_t size)
+static uint64_t fnv1(const char *data, size_t size)
 {
     uint64_t hash = 0xcbf29ce484222325;
 
@@ -31,20 +33,18 @@ static uint64_t fnv1(char *data, size_t size)
 HashSet *create_hashset(size_t element_size, size_t n)
 {
     Lt *lt = create_lt();
-    if (lt == NULL) {
-        return NULL;
-    }
 
-    HashSet *hash_set = PUSH_LT(lt, nth_alloc(sizeof(HashSet)), free);
+    HashSet *hash_set = PUSH_LT(lt, nth_calloc(1, sizeof(HashSet)), free);
     if (hash_set == NULL) {
         RETURN_LT(lt, NULL);
     }
     hash_set->lt = lt;
 
     hash_set->n = n;
+    hash_set->count = 0;
     hash_set->element_size = element_size;
 
-    hash_set->buckets = PUSH_LT(lt, nth_calloc(n, sizeof(LinkedList*)), free);
+    hash_set->buckets = PUSH_LT(lt, nth_calloc(n, sizeof(Dynarray*)), free);
     if (hash_set->buckets == NULL) {
         RETURN_LT(lt, NULL);
     }
@@ -52,13 +52,18 @@ HashSet *create_hashset(size_t element_size, size_t n)
     for (size_t i = 0; i < n; ++i) {
         hash_set->buckets[i] = PUSH_LT(
             lt,
-            create_linked_list(element_size),
-            destroy_linked_list);
+            create_dynarray(element_size),
+            destroy_dynarray);
         if (hash_set->buckets[i] == NULL) {
             RETURN_LT(lt, NULL);
         }
     }
 
+    hash_set->view = PUSH_LT(lt, create_dynarray(element_size), destroy_dynarray);
+    if (hash_set->view == NULL) {
+        RETURN_LT(lt, NULL);
+    }
+
     return hash_set;
 }
 
@@ -68,22 +73,7 @@ void destroy_hashset(HashSet *hashset)
     RETURN_LT0(hashset->lt);
 }
 
-int hashset_insert(HashSet *hashset, void *element)
-{
-    trace_assert(hashset);
-    trace_assert(element);
-
-    const uint64_t hash = fnv1(element, hashset->element_size);
-    const size_t i = hash % hashset->n;
-
-    if (linked_list_find(hashset->buckets[i], element) == NULL) {
-        linked_list_push_back(hashset->buckets[i], element);
-    }
-
-    return 0;
-}
-
-int hashset_remove(HashSet *hashset, void *element)
+int hashset_insert(HashSet *hashset, const void *element)
 {
     trace_assert(hashset);
     trace_assert(element);
@@ -91,16 +81,15 @@ int hashset_remove(HashSet *hashset, void *element)
     const uint64_t hash = fnv1(element, hashset->element_size);
     const size_t i = hash % hashset->n;
 
-    NodeLL *node = linked_list_find(hashset->buckets[i], element);
-
-    if (node != NULL) {
-        linked_list_remove(hashset->buckets[i], node);
+    if (!dynarray_contains(hashset->buckets[i], element)) {
+        dynarray_push(hashset->buckets[i], element);
+        hashset->count++;
     }
 
     return 0;
 }
 
-bool hashset_contains(HashSet *hashset, void *element)
+bool hashset_contains(HashSet *hashset, const void *element)
 {
     trace_assert(hashset);
     trace_assert(element);
@@ -108,7 +97,7 @@ bool hashset_contains(HashSet *hashset, void *element)
     const uint64_t hash = fnv1(element, hashset->element_size);
     const size_t i = hash % hashset->n;
 
-    return linked_list_find(hashset->buckets[i], element) != NULL;
+    return dynarray_contains(hashset->buckets[i], element);
 }
 
 void hashset_clear(HashSet *hashset)
@@ -116,25 +105,30 @@ void hashset_clear(HashSet *hashset)
     trace_assert(hashset);
 
     for (size_t i = 0; i < hashset->n; ++i) {
-        linked_list_clear(hashset->buckets[i]);
+        dynarray_clear(hashset->buckets[i]);
     }
-}
 
-size_t hashset_count(HashSet *hashset)
-{
-    trace_assert(hashset);
-    return 0;
+    hashset->count = 0;
 }
+size_t hashset_count(HashSet *hashset)
 
-HashSetIterator *hashset_begin(HashSet *hashset)
 {
     trace_assert(hashset);
-    return NULL;
+    return hashset->count;
 }
 
-HashSetIterator *hashset_next(HashSet *hashset, HashSetIterator *iter)
+void *hashset_values(HashSet *hashset)
 {
-    trace_assert(hashset);
-    trace_assert(iter);
-    return NULL;
+    dynarray_clear(hashset->view);
+
+    for (size_t i = 0; i < hashset->n; ++i) {
+        size_t n = dynarray_count(hashset->buckets[i]);
+        char *bucket = dynarray_data(hashset->buckets[i]);
+
+        for (size_t j = 0; j < n; ++j) {
+            dynarray_push(hashset->view, bucket + j * hashset->element_size);
+        }
+    }
+
+    return dynarray_data(hashset->view);
 }