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

   1 #include "hashmap.h"
   2 #include "list.h"
   3
   4 #include <assert.h>
   5 #include <stdlib.h>
   6
   7 #define DEFAULT_CAPACITY 64
   8
   9 struct pair
  10 {
  11         void *k;
  12         void *v;
  13 };
  14
  15 struct hashmap
  16 {
  17         size_t capacity;
  18         list **buckets;
  19
  20         dtor *key_dtor;
  21         dtor *val_dtor;
  22         hashfn *hash;
  23         comparator *cmp;
  24         void *cmp_aux;
  25         void *dtor_aux;
  26 };
  27
  28 static void
  29 _hm_free_pair(void *x, void *aux)
  30 {
  31         hashmap *h = aux;
  32         struct pair *p = x;
  33         if (h->key_dtor)
  34                 h->key_dtor(p->k, h->dtor_aux);
  35         if (h->val_dtor)
  36                 h->val_dtor(p->v, h->dtor_aux);
  37         free(x);
  38 }
  39
  40 hashmap *
  41 hm_new(size_t capacity, hashfn *hash,
  42        comparator *cmp, void *cmp_aux)
  43 {
  44         if (!hash || !cmp)
  45                 return NULL;
  46         if (capacity == 0)
  47                 capacity = DEFAULT_CAPACITY;
  48         hashmap *h = malloc(sizeof *h);
  49         if (!h)
  50                 goto fail;
  51         *h = (hashmap){
  52                 .capacity = capacity,
  53                 .buckets = malloc(capacity * sizeof *h->buckets),
  54                 .hash = hash,
  55                 .cmp = cmp,
  56                 .cmp_aux = cmp_aux
  57         };
  58         if (!h->buckets)
  59                 goto fail;
  60
  61         size_t i;
  62         for (i = 0; i < capacity; i++)
  63                 h->buckets[i] = NULL; /* in case allocation fails part-way */
  64         for (i = 0; i < capacity; i++)
  65         {
  66                 if (!(h->buckets[i] = l_new()))
  67                         goto fail;
  68                 l_dtor(h->buckets[i], _hm_free_pair, h);
  69         }
  70         return h;
  71
  72 fail:
  73         hm_free(h);
  74         return NULL;
  75 }
  76
  77
  78 void
  79 hm_dtor(hashmap *h, dtor *key_dtor, dtor *val_dtor, void *dtor_aux)
  80 {
  81         if (!h)
  82                 return;
  83         h->key_dtor = key_dtor;
  84         h->val_dtor = val_dtor;
  85         h->dtor_aux = dtor_aux;
  86 }
  87
  88 void
  89 hm_free(hashmap *h)
  90 {
  91         if (!h)
  92                 return;
  93         if (h->buckets)
  94         {
  95                 for (size_t i = 0; i < h->capacity; i++)
  96                         l_free(h->buckets[i]);
  97                 free(h->buckets);
  98         }
  99         free(h);
 100 }
 101
 102 size_t
 103 hm_length(const hashmap *h)
 104 {
 105         if (!h)
 106                 return 0;
 107         size_t i, n;
 108         for (n = i = 0; i < h->capacity; i++)
 109                 n += l_length(h->buckets[i]);
 110         return n;
 111 }
 112
 113 bool
 114 hm_is_empty(const hashmap *h)
 115 {
 116         return hm_length(h) == 0;
 117 }
 118
 119 /* kinda weird assumption: p is struct pair*, k is type of p->k */
 120 static int
 121 _hm_cmp(const void *p, const void *k, void *aux)
 122 {
 123         assert(p); assert(k); assert(aux);
 124         hashmap *h = aux;
 125         return h->cmp(((const struct pair *)p)->k, k, h->cmp_aux);
 126 }
 127
 128 void *
 129 hm_at(const hashmap *h, const void *key)
 130 {
 131         if (!h)
 132                 return NULL;
 133         list *bucket = h->buckets[h->hash(key) % h->capacity];
 134         list_item *li = l_find(bucket, key, _hm_cmp, (void*)h);
 135         if (!li)
 136                 return NULL;
 137         return ((struct pair*)li->data)->v;
 138 }
 139
 140 bool
 141 hm_insert(hashmap *h, void *key, void *val)
 142 {
 143         if (!h)
 144                 return false;
 145         list *bucket = h->buckets[h->hash(key) % h->capacity];
 146         list_item *li = l_find(bucket, key, _hm_cmp, h);
 147         if (li)
 148         {
 149                 struct pair *p = (struct pair*)li->data;
 150                 if (p->v != val && h->val_dtor)
 151                         h->val_dtor(p->v, h->dtor_aux);
 152                 p->v = val;
 153                 return true;
 154         }
 155         else
 156         {
 157                 struct pair *p = malloc(sizeof *p);
 158                 if (!p)
 159                         return false;
 160                 *p = (struct pair){.k = key, .v = val};
 161                 l_append(bucket, p);
 162                 return true;
 163         }
 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, _hm_cmp, h);
 173         if (!li)
 174                 return false;
 175         _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 }