#include <stdlib.h>
#include <stdint.h>
+#include <stdbool.h>
#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;
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);
}
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;
}
RETURN_LT0(hashset->lt);
}
-int hashset_insert(HashSet *hashset, void *element)
+int hashset_insert(HashSet *hashset, const 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);
+ if (!dynarray_contains(hashset->buckets[i], element)) {
+ dynarray_push(hashset->buckets[i], element);
+ hashset->count++;
}
return 0;
}
-int hashset_remove(HashSet *hashset, void *element)
+bool hashset_contains(HashSet *hashset, const void *element)
{
trace_assert(hashset);
trace_assert(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);
- }
-
- return 0;
+ return dynarray_contains(hashset->buckets[i], element);
}
-bool hashset_contains(HashSet *hashset, void *element)
+void hashset_clear(HashSet *hashset)
{
trace_assert(hashset);
- trace_assert(element);
- const uint64_t hash = fnv1(element, hashset->element_size);
- const size_t i = hash % hashset->n;
+ for (size_t i = 0; i < hashset->n; ++i) {
+ dynarray_clear(hashset->buckets[i]);
+ }
- return linked_list_find(hashset->buckets[i], element) != NULL;
+ hashset->count = 0;
}
+size_t hashset_count(HashSet *hashset)
-void hashset_clear(HashSet *hashset)
{
trace_assert(hashset);
+ return hashset->count;
+}
+
+void *hashset_values(HashSet *hashset)
+{
+ 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);
}