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 "linked_list.h"
   9 #include "hashset.h"
  10
  11 struct HashSet
  12 {
  13     Lt *lt;
  14     size_t n;
  15     size_t element_size;
  16     LinkedList **buckets;
  17 };
  18
  19 static uint64_t fnv1(char *data, size_t size)
  20 {
  21     uint64_t hash = 0xcbf29ce484222325;
  22
  23     for (size_t i = 0; i < size; ++i) {
  24         hash = hash * 0x100000001b3;
  25         hash = hash ^ (uint64_t) data[i];
  26     }
  27
  28     return hash;
  29 }
  30
  31 HashSet *create_hashset(size_t element_size, size_t n)
  32 {
  33     Lt *lt = create_lt();
  34     if (lt == NULL) {
  35         return NULL;
  36     }
  37
  38     HashSet *hash_set = PUSH_LT(lt, nth_alloc(sizeof(HashSet)), free);
  39     if (hash_set == NULL) {
  40         RETURN_LT(lt, NULL);
  41     }
  42     hash_set->lt = lt;
  43
  44     hash_set->n = n;
  45     hash_set->element_size = element_size;
  46
  47     hash_set->buckets = PUSH_LT(lt, nth_calloc(n, sizeof(LinkedList*)), 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_linked_list(element_size),
  56             destroy_linked_list);
  57         if (hash_set->buckets[i] == NULL) {
  58             RETURN_LT(lt, NULL);
  59         }
  60     }
  61
  62     return hash_set;
  63 }
  64
  65 void destroy_hashset(HashSet *hashset)
  66 {
  67     trace_assert(hashset);
  68     RETURN_LT0(hashset->lt);
  69 }
  70
  71 int hashset_insert(HashSet *hashset, void *element)
  72 {
  73     trace_assert(hashset);
  74     trace_assert(element);
  75
  76     const uint64_t hash = fnv1(element, hashset->element_size);
  77     const size_t i = hash % hashset->n;
  78
  79     if (linked_list_find(hashset->buckets[i], element) == NULL) {
  80         linked_list_push_back(hashset->buckets[i], element);
  81     }
  82
  83     return 0;
  84 }
  85
  86 int hashset_remove(HashSet *hashset, void *element)
  87 {
  88     trace_assert(hashset);
  89     trace_assert(element);
  90
  91     const uint64_t hash = fnv1(element, hashset->element_size);
  92     const size_t i = hash % hashset->n;
  93
  94     NodeLL *node = linked_list_find(hashset->buckets[i], element);
  95
  96     if (node != NULL) {
  97         linked_list_remove(hashset->buckets[i], node);
  98     }
  99
 100     return 0;
 101 }
 102
 103 bool hashset_contains(HashSet *hashset, void *element)
 104 {
 105     trace_assert(hashset);
 106     trace_assert(element);
 107
 108     const uint64_t hash = fnv1(element, hashset->element_size);
 109     const size_t i = hash % hashset->n;
 110
 111     return linked_list_find(hashset->buckets[i], element) != NULL;
 112 }
 113
 114 void hashset_clear(HashSet *hashset)
 115 {
 116     trace_assert(hashset);
 117
 118     for (size_t i = 0; i < hashset->n; ++i) {
 119         linked_list_clear(hashset->buckets[i]);
 120     }
 121 }
 122
 123 size_t hashset_count(HashSet *hashset)
 124 {
 125     trace_assert(hashset);
 126     return 0;
 127 }
 128
 129 HashSetIterator *hashset_begin(HashSet *hashset)
 130 {
 131     trace_assert(hashset);
 132     return NULL;
 133 }
 134
 135 HashSetIterator *hashset_next(HashSet *hashset, HashSetIterator *iter)
 136 {
 137     trace_assert(hashset);
 138     trace_assert(iter);
 139     return NULL;
 140 }