6 #include "system/stacktrace.h"
7 #include "system/nth_alloc.h"
21 static uint64_t fnv1(const char *data, size_t size)
23 uint64_t hash = 0xcbf29ce484222325;
25 for (size_t i = 0; i < size; ++i) {
26 hash = hash * 0x100000001b3;
27 hash = hash ^ (uint64_t) data[i];
33 HashSet *create_hashset(size_t element_size, size_t n)
37 HashSet *hash_set = PUSH_LT(lt, nth_calloc(1, sizeof(HashSet)), free);
38 if (hash_set == NULL) {
45 hash_set->element_size = element_size;
47 hash_set->buckets = PUSH_LT(lt, nth_calloc(n, sizeof(Dynarray*)), free);
48 if (hash_set->buckets == NULL) {
52 for (size_t i = 0; i < n; ++i) {
53 hash_set->buckets[i] = PUSH_LT(
55 create_dynarray(element_size),
57 if (hash_set->buckets[i] == NULL) {
62 hash_set->view = PUSH_LT(lt, create_dynarray(element_size), destroy_dynarray);
63 if (hash_set->view == NULL) {
70 void destroy_hashset(HashSet *hashset)
72 trace_assert(hashset);
73 RETURN_LT0(hashset->lt);
76 int hashset_insert(HashSet *hashset, const void *element)
78 trace_assert(hashset);
79 trace_assert(element);
81 const uint64_t hash = fnv1(element, hashset->element_size);
82 const size_t i = (size_t)(hash % hashset->n);
84 if (!dynarray_contains(hashset->buckets[i], element)) {
85 dynarray_push(hashset->buckets[i], element);
92 bool hashset_contains(HashSet *hashset, const void *element)
94 trace_assert(hashset);
95 trace_assert(element);
97 const uint64_t hash = fnv1(element, hashset->element_size);
98 const size_t i = (size_t)(hash % hashset->n);
100 return dynarray_contains(hashset->buckets[i], element);
103 void hashset_clear(HashSet *hashset)
105 trace_assert(hashset);
107 for (size_t i = 0; i < hashset->n; ++i) {
108 dynarray_clear(hashset->buckets[i]);
113 size_t hashset_count(HashSet *hashset)
116 trace_assert(hashset);
117 return hashset->count;
120 void *hashset_values(HashSet *hashset)
122 dynarray_clear(hashset->view);
124 for (size_t i = 0; i < hashset->n; ++i) {
125 size_t n = dynarray_count(hashset->buckets[i]);
126 char *bucket = dynarray_data(hashset->buckets[i]);
128 for (size_t j = 0; j < n; ++j) {
129 dynarray_push(hashset->view, bucket + j * hashset->element_size);
133 return dynarray_data(hashset->view);