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 /* kinda weird assumption: p is struct pair*, k is type of p->k */
  97 static int
  98 _hm_cmp(const void *p, const void *k, void *aux)
  99 {
 100         assert(p); assert(k); assert(aux);
 101         hashmap *h = aux;
 102         return h->cmp(((const struct pair *)p)->k, k, h->cmp_aux);
 103 }
 104
 105 void *
 106 hm_at(const hashmap *h, const void *key)
 107 {
 108         if (!h)
 109                 return NULL;
 110         list *bucket = h->buckets[h->hash(key) % h->capacity];
 111         list_item *li = l_find(bucket, key, _hm_cmp, (void*)h);
 112         if (!li)
 113                 return NULL;
 114         return ((struct pair*)li->data)->v;
 115 }
 116
 117 bool
 118 hm_insert(hashmap *h, void *key, void *val)
 119 {
 120         if (!h)
 121                 return false;
 122         list *bucket = h->buckets[h->hash(key) % h->capacity];
 123         list_item *li = l_find(bucket, key, _hm_cmp, h);
 124         if (li)
 125         {
 126                 struct pair *p = (struct pair*)li->data;
 127                 if (p->v != val && h->val_dtor)
 128                         h->val_dtor(p->v);
 129                 p->v = val;
 130                 return true;
 131         }
 132         else
 133         {
 134                 struct pair *p = malloc(sizeof *p);
 135                 if (!p)
 136                         return false;
 137                 *p = (struct pair){.k = key, .v = val};
 138                 l_append(bucket, p);
 139                 return true;
 140         }
 141 }
 142
 143 bool
 144 hm_remove(hashmap *h, void *key)
 145 {
 146         if (!h)
 147                 return false;
 148         list *bucket = h->buckets[h->hash(key) % h->capacity];
 149         list_item *li = l_find(bucket, key, _hm_cmp, h);
 150         if (!li)
 151                 return false;
 152         l_remove(bucket, li);
 153         /* XXX: free li and pair */
 154         return true;
 155 }
 156
 157 void
 158 hm_clear(hashmap *h)
 159 {
 160         if (!h)
 161                 return;
 162         for (size_t i = 0; i < h->capacity; i++)
 163                 l_clear(h->buckets[i]);
 164 }