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