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         void (*key_dtor)(void *);
  21         void (*val_dtor)(void *);
  22         hashfn *hash;
  23         comparator *cmp;
  24         void *cmp_aux;
  25 };
  26
  27 hashmap *
  28 hm_new(size_t capacity, hashfn *hash,
  29        comparator *cmp, void *aux,
  30        void (*key_dtor)(void *),
  31        void (*val_dtor)(void *))
  32 {
  33         if (!hash || !cmp)
  34                 return NULL;
  35         if (capacity == 0)
  36                 capacity = DEFAULT_CAPACITY;
  37         hashmap *h = malloc(sizeof *h);
  38         if (!h)
  39                 goto fail;
  40         *h = (hashmap){
  41                 .capacity = capacity,
  42                 .buckets = malloc(capacity * sizeof *h->buckets),
  43                 .key_dtor = key_dtor,
  44                 .val_dtor = val_dtor,
  45                 .hash = hash,
  46                 .cmp = cmp,
  47                 .cmp_aux = aux
  48         };
  49         if (!h->buckets)
  50                 goto fail;
  51
  52         size_t i;
  53         for (i = 0; i < capacity; i++)
  54                 h->buckets[i] = NULL; /* in case allocation fails part-way */
  55         for (i = 0; i < capacity; i++)
  56                 if (!(h->buckets[i] = l_new(NULL))) /* XXX: proper dtor */
  57                         goto fail;
  58         return h;
  59
  60 fail:
  61         hm_free(h);
  62         return NULL;
  63 }
  64
  65 void
  66 hm_free(hashmap *h)
  67 {
  68         if (!h)
  69                 return;
  70         if (h->buckets)
  71         {
  72                 for (size_t i = 0; i < h->capacity; i++)
  73                         l_free(h->buckets[i]);
  74                 free(h->buckets);
  75         }
  76         free(h);
  77 }
  78
  79 size_t
  80 hm_length(const hashmap *h)
  81 {
  82         if (!h)
  83                 return 0;
  84         size_t i, n;
  85         for (n = i = 0; i < h->capacity; i++)
  86                 n += l_length(h->buckets[i]);
  87         return n;
  88 }
  89
  90 bool
  91 hm_is_empty(const hashmap *h)
  92 {
  93         return hm_length(h) == 0;
  94 }
  95
  96 void *
  97 hm_at(const hashmap *h, const void *key)
  98 {
  99         if (!h)
 100                 return NULL;
 101         list *bucket = h->buckets[h->hash(key) % h->capacity];
 102         list_item *li = l_find(bucket, key, h->cmp, h->cmp_aux);
 103         if (!li)
 104                 return NULL;
 105         return ((struct pair*)li->data)->v;
 106 }
 107
 108 bool
 109 hm_insert(hashmap *h, void *key, void *val)
 110 {
 111         if (!h)
 112                 return false;
 113         list *bucket = h->buckets[h->hash(key) % h->capacity];
 114         list_item *li = l_find(bucket, key, h->cmp, h->cmp_aux);
 115         if (li)
 116         {
 117                 struct pair *p = (struct pair*)li->data;
 118                 if (p->v != val && h->val_dtor)
 119                         h->val_dtor(p->v);
 120                 p->v = val;
 121                 return true;
 122         }
 123         else
 124         {
 125                 struct pair *p = malloc(sizeof *p);
 126                 if (!p)
 127                         return false;
 128                 *p = (struct pair){.k = key, .v = val};
 129                 l_append(bucket, p);
 130                 return true;
 131         }
 132 }
 133
 134 bool
 135 hm_remove(hashmap *h, void *key)
 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, h->cmp, h->cmp_aux);
 141         if (!li)
 142                 return false;
 143         l_remove(bucket, li);
 144         /* XXX: free li and pair */
 145         return true;
 146 }
 147
 148 void
 149 hm_clear(hashmap *h)
 150 {
 151         if (!h)
 152                 return;
 153         for (size_t i = 0; i < h->capacity; i++)
 154                 l_clear(h->buckets[i]);
 155 }