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