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