src/hashset.c

   1 #include <stdlib.h>
   2 #include <stdint.h>
   3 #include <stdbool.h>
   4
   5 #include "system/lt.h"
   6 #include "system/stacktrace.h"
   7 #include "system/nth_alloc.h"
   8 #include "hashset.h"
   9 #include "dynarray.h"
  10
  11 struct HashSet
  12 {
  13     Lt *lt;
  14     size_t n;
  15     size_t element_size;
  16     size_t count;
  17     Dynarray **buckets;
  18     Dynarray *view;
  19 };
  20
  21 static uint64_t fnv1(const char *data, size_t size)
  22 {
  23     uint64_t hash = 0xcbf29ce484222325;
  24
  25     for (size_t i = 0; i < size; ++i) {
  26         hash = hash * 0x100000001b3;
  27         hash = hash ^ (uint64_t) data[i];
  28     }
  29
  30     return hash;
  31 }
  32
  33 HashSet *create_hashset(size_t element_size, size_t n)
  34 {
  35     Lt *lt = create_lt();
  36     if (lt == NULL) {
  37         return NULL;
  38     }
  39
  40     HashSet *hash_set = PUSH_LT(lt, nth_alloc(sizeof(HashSet)), free);
  41     if (hash_set == NULL) {
  42         RETURN_LT(lt, NULL);
  43     }
  44     hash_set->lt = lt;
  45
  46     hash_set->n = n;
  47     hash_set->count = 0;
  48     hash_set->element_size = element_size;
  49
  50     hash_set->buckets = PUSH_LT(lt, nth_calloc(n, sizeof(Dynarray*)), free);
  51     if (hash_set->buckets == NULL) {
  52         RETURN_LT(lt, NULL);
  53     }
  54
  55     for (size_t i = 0; i < n; ++i) {
  56         hash_set->buckets[i] = PUSH_LT(
  57             lt,
  58             create_dynarray(element_size),
  59             destroy_dynarray);
  60         if (hash_set->buckets[i] == NULL) {
  61             RETURN_LT(lt, NULL);
  62         }
  63     }
  64
  65     hash_set->view = PUSH_LT(lt, create_dynarray(element_size), destroy_dynarray);
  66     if (hash_set->view == NULL) {
  67         RETURN_LT(lt, NULL);
  68     }
  69
  70     return hash_set;
  71 }
  72
  73 void destroy_hashset(HashSet *hashset)
  74 {
  75     trace_assert(hashset);
  76     RETURN_LT0(hashset->lt);
  77 }
  78
  79 int hashset_insert(HashSet *hashset, const void *element)
  80 {
  81     trace_assert(hashset);
  82     trace_assert(element);
  83
  84     const uint64_t hash = fnv1(element, hashset->element_size);
  85     const size_t i = hash % hashset->n;
  86
  87     if (!dynarray_contains(hashset->buckets[i], element)) {
  88         dynarray_push(hashset->buckets[i], element);
  89         hashset->count++;
  90     }
  91
  92     return 0;
  93 }
  94
  95 bool hashset_contains(HashSet *hashset, const void *element)
  96 {
  97     trace_assert(hashset);
  98     trace_assert(element);
  99
 100     const uint64_t hash = fnv1(element, hashset->element_size);
 101     const size_t i = hash % hashset->n;
 102
 103     return dynarray_contains(hashset->buckets[i], element);
 104 }
 105
 106 void hashset_clear(HashSet *hashset)
 107 {
 108     trace_assert(hashset);
 109
 110     for (size_t i = 0; i < hashset->n; ++i) {
 111         dynarray_clear(hashset->buckets[i]);
 112     }
 113
 114     hashset->count = 0;
 115 }
 116 size_t hashset_count(HashSet *hashset)
 117
 118 {
 119     trace_assert(hashset);
 120     return hashset->count;
 121 }
 122
 123 void *hashset_values(HashSet *hashset)
 124 {
 125     dynarray_clear(hashset->view);
 126
 127     for (size_t i = 0; i < hashset->n; ++i) {
 128         size_t n = dynarray_count(hashset->buckets[i]);
 129         char *bucket = dynarray_data(hashset->buckets[i]);
 130
 131         for (size_t j = 0; j < n; ++j) {
 132             dynarray_push(hashset->view, bucket + j * hashset->element_size);
 133         }
 134     }
 135
 136     return dynarray_data(hashset->view);
 137 }