begriffs open source - libderp/blob - src/hashmap.c

   1 #include <assert.h>
   2
   3 #include "internal/alloc.h"
   4 #include "derp/hashmap.h"
   5 #include "derp/list.h"
   6
   7 #define DEFAULT_CAPACITY 64
   8
   9 struct hashmap
  10 {
  11         size_t capacity;
  12         list **buckets;
  13
  14         dtor *key_dtor;
  15         dtor *val_dtor;
  16         hashfn *hash;
  17         comparator *cmp;
  18         void *cmp_aux;
  19         void *dtor_aux;
  20 };
  21
  22 struct hm_iter
  23 {
  24         hashmap *h;
  25         size_t bucket;
  26         list_item *offset;
  27 };
  28
  29 static void
  30 internal_hm_free_pair(void *x, void *aux)
  31 {
  32         hashmap *h = aux;
  33         struct map_pair *p = x;
  34         if (h->key_dtor)
  35                 h->key_dtor(p->k, h->dtor_aux);
  36         if (h->val_dtor)
  37                 h->val_dtor(p->v, h->dtor_aux);
  38         internal_free(x);
  39 }
  40
  41 hashmap *
  42 hm_new(size_t capacity, hashfn *hash,
  43        comparator *cmp, void *cmp_aux)
  44 {
  45         if (!hash || !cmp)
  46                 return NULL;
  47         if (capacity == 0)
  48                 capacity = DEFAULT_CAPACITY;
  49         hashmap *h = internal_malloc(sizeof *h);
  50         if (!h)
  51                 goto fail;
  52         *h = (hashmap){
  53                 .capacity = capacity,
  54                 .buckets = internal_malloc(capacity * sizeof *h->buckets),
  55                 .hash = hash,
  56                 .cmp = cmp,
  57                 .cmp_aux = cmp_aux
  58         };
  59         if (!h->buckets)
  60                 goto fail;
  61
  62         size_t i;
  63         for (i = 0; i < capacity; i++)
  64                 h->buckets[i] = NULL; /* in case allocation fails part-way */
  65         for (i = 0; i < capacity; i++)
  66         {
  67                 if (!(h->buckets[i] = l_new()))
  68                         goto fail;
  69                 l_dtor(h->buckets[i], internal_hm_free_pair, h);
  70         }
  71         return h;
  72
  73 fail:
  74         hm_free(h);
  75         return NULL;
  76 }
  77
  78
  79 void
  80 hm_dtor(hashmap *h, dtor *key_dtor, dtor *val_dtor, void *dtor_aux)
  81 {
  82         if (!h)
  83                 return;
  84         h->key_dtor = key_dtor;
  85         h->val_dtor = val_dtor;
  86         h->dtor_aux = dtor_aux;
  87 }
  88
  89 void
  90 hm_free(hashmap *h)
  91 {
  92         if (!h)
  93                 return;
  94         if (h->buckets)
  95         {
  96                 for (size_t i = 0; i < h->capacity; i++)
  97                         l_free(h->buckets[i]);
  98                 internal_free(h->buckets);
  99         }
 100         internal_free(h);
 101 }
 102
 103 size_t
 104 hm_length(const hashmap *h)
 105 {
 106         if (!h)
 107                 return 0;
 108         size_t i, n;
 109         for (n = i = 0; i < h->capacity; i++)
 110                 n += l_length(h->buckets[i]);
 111         return n;
 112 }
 113
 114 bool
 115 hm_is_empty(const hashmap *h)
 116 {
 117         return hm_length(h) == 0;
 118 }
 119
 120 /* kinda weird assumption: p is struct pair*, k is type of p->k */
 121 static int
 122 internal_hm_cmp(const void *p, const void *k, void *aux)
 123 {
 124         assert(p); assert(k); assert(aux);
 125         hashmap *h = aux;
 126         return h->cmp(((const struct map_pair *)p)->k, k, h->cmp_aux);
 127 }
 128
 129 void *
 130 hm_at(const hashmap *h, const void *key)
 131 {
 132         if (!h)
 133                 return NULL;
 134         list *bucket = h->buckets[h->hash(key) % h->capacity];
 135         list_item *li = l_find(bucket, key, internal_hm_cmp, (void*)h);
 136         if (!li)
 137                 return NULL;
 138         return ((struct map_pair*)li->data)->v;
 139 }
 140
 141 bool
 142 hm_insert(hashmap *h, void *key, void *val)
 143 {
 144         if (!h)
 145                 return false;
 146         list *bucket = h->buckets[h->hash(key) % h->capacity];
 147         list_item *li = l_find(bucket, key, internal_hm_cmp, h);
 148         if (li)
 149         {
 150                 struct map_pair *p = (struct map_pair*)li->data;
 151                 if (p->v != val && h->val_dtor)
 152                         h->val_dtor(p->v, h->dtor_aux);
 153                 p->v = val;
 154         }
 155         else
 156         {
 157                 struct map_pair *p = internal_malloc(sizeof *p);
 158                 if (!p)
 159                         return false;
 160                 *p = (struct map_pair){.k = key, .v = val};
 161                 l_append(bucket, p);
 162         }
 163         return true;
 164 }
 165
 166 bool
 167 hm_remove(hashmap *h, void *key)
 168 {
 169         if (!h)
 170                 return false;
 171         list *bucket = h->buckets[h->hash(key) % h->capacity];
 172         list_item *li = l_find(bucket, key, internal_hm_cmp, h);
 173         if (!li)
 174                 return false;
 175         internal_hm_free_pair(li->data, h);
 176         l_remove(bucket, li);
 177         return true;
 178 }
 179
 180 void
 181 hm_clear(hashmap *h)
 182 {
 183         if (!h)
 184                 return;
 185         for (size_t i = 0; i < h->capacity; i++)
 186                 l_clear(h->buckets[i]);
 187 }
 188
 189 hm_iter *
 190 hm_iter_begin(hashmap *h)
 191 {
 192         if (!h)
 193                 return NULL;
 194         hm_iter *i = internal_malloc(sizeof *i);
 195         if (!i)
 196                 return NULL;
 197         *i = (hm_iter){.h = h};
 198         return i;
 199 }
 200
 201 struct map_pair *
 202 hm_iter_next(hm_iter *i)
 203 {
 204         if (!i)
 205                 return NULL;
 206         while (!i->offset && i->bucket < i->h->capacity)
 207                 i->offset = l_first(i->h->buckets[i->bucket++]);
 208         if (!i->offset)
 209                 return NULL;
 210         struct map_pair *p = i->offset->data;
 211         i->offset = i->offset->next;
 212         return p;
 213 }
 214
 215 void
 216 hm_iter_free(hm_iter *i)
 217 {
 218         internal_free(i);
 219 }