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
  37     HashSet *hash_set = PUSH_LT(lt, nth_calloc(1, sizeof(HashSet)), free);
  38     if (hash_set == NULL) {
  39         RETURN_LT(lt, NULL);
  40     }
  41     hash_set->lt = lt;
  42
  43     hash_set->n = n;
  44     hash_set->count = 0;
  45     hash_set->element_size = element_size;
  46
  47     hash_set->buckets = PUSH_LT(lt, nth_calloc(n, sizeof(Dynarray*)), free);
  48     if (hash_set->buckets == NULL) {
  49         RETURN_LT(lt, NULL);
  50     }
  51
  52     for (size_t i = 0; i < n; ++i) {
  53         hash_set->buckets[i] = PUSH_LT(
  54             lt,
  55             create_dynarray(element_size),
  56             destroy_dynarray);
  57         if (hash_set->buckets[i] == NULL) {
  58             RETURN_LT(lt, NULL);
  59         }
  60     }
  61
  62     hash_set->view = PUSH_LT(lt, create_dynarray(element_size), destroy_dynarray);
  63     if (hash_set->view == NULL) {
  64         RETURN_LT(lt, NULL);
  65     }
  66
  67     return hash_set;
  68 }
  69
  70 void destroy_hashset(HashSet *hashset)
  71 {
  72     trace_assert(hashset);
  73     RETURN_LT0(hashset->lt);
  74 }
  75
  76 int hashset_insert(HashSet *hashset, const void *element)
  77 {
  78     trace_assert(hashset);
  79     trace_assert(element);
  80
  81     const uint64_t hash = fnv1(element, hashset->element_size);
  82     const size_t i = (size_t)(hash % hashset->n);
  83
  84     if (!dynarray_contains(hashset->buckets[i], element)) {
  85         dynarray_push(hashset->buckets[i], element);
  86         hashset->count++;
  87     }
  88
  89     return 0;
  90 }
  91
  92 bool hashset_contains(HashSet *hashset, const void *element)
  93 {
  94     trace_assert(hashset);
  95     trace_assert(element);
  96
  97     const uint64_t hash = fnv1(element, hashset->element_size);
  98     const size_t i = (size_t)(hash % hashset->n);
  99
 100     return dynarray_contains(hashset->buckets[i], element);
 101 }
 102
 103 void hashset_clear(HashSet *hashset)
 104 {
 105     trace_assert(hashset);
 106
 107     for (size_t i = 0; i < hashset->n; ++i) {
 108         dynarray_clear(hashset->buckets[i]);
 109     }
 110
 111     hashset->count = 0;
 112 }
 113 size_t hashset_count(HashSet *hashset)
 114
 115 {
 116     trace_assert(hashset);
 117     return hashset->count;
 118 }
 119
 120 void *hashset_values(HashSet *hashset)
 121 {
 122     dynarray_clear(hashset->view);
 123
 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]);
 127
 128         for (size_t j = 0; j < n; ++j) {
 129             dynarray_push(hashset->view, bucket + j * hashset->element_size);
 130         }
 131     }
 132
 133     return dynarray_data(hashset->view);
 134 }