hashmap.c

   1 /*-*- Mode: C; c-basic-offset: 8 -*-*/
   2
   3 #ifdef HAVE_CONFIG_H
   4 #include <config.h>
   5 #endif
   6
   7 #include <assert.h>
   8 #include <stdlib.h>
   9 #include <string.h>
  10 #include <errno.h>
  11
  12 #include "util.h"
  13 #include "hashmap.h"
  14 #include "macro.h"
  15
  16 #define NBUCKETS 127
  17
  18 struct hashmap_entry {
  19         const void *key;
  20         void *value;
  21
  22         struct hashmap_entry *bucket_next, *bucket_previous;
  23         struct hashmap_entry *iterate_next, *iterate_previous;
  24 };
  25
  26 struct Hashmap {
  27         hash_func_t hash_func;
  28         compare_func_t compare_func;
  29
  30         struct hashmap_entry *iterate_list_head, *iterate_list_tail;
  31         unsigned n_entries;
  32 };
  33
  34 #define BY_HASH(h) ((struct hashmap_entry**) ((uint8_t*) (h) + ALIGN(sizeof(Hashmap))))
  35
  36 unsigned string_hash_func(const void *p) {
  37         unsigned hash = 0;
  38         const char *c;
  39
  40         for (c = p; *c; c++)
  41                 hash = 31 * hash + (unsigned) *c;
  42
  43         return hash;
  44 }
  45
  46 int string_compare_func(const void *a, const void *b) {
  47         return strcmp(a, b);
  48 }
  49
  50 unsigned trivial_hash_func(const void *p) {
  51         return PTR_TO_UINT(p);
  52 }
  53
  54 int trivial_compare_func(const void *a, const void *b) {
  55         return a < b ? -1 : (a > b ? 1 : 0);
  56 }
  57
  58 Hashmap *hashmap_new(hash_func_t hash_func, compare_func_t compare_func) {
  59         Hashmap *h;
  60
  61         if (!(h = malloc0(ALIGN(sizeof(Hashmap)) + NBUCKETS * ALIGN(sizeof(struct hashmap_entry*)))))
  62                 return NULL;
  63
  64         h->hash_func = hash_func ? hash_func : trivial_hash_func;
  65         h->compare_func = compare_func ? compare_func : trivial_compare_func;
  66
  67         h->n_entries = 0;
  68         h->iterate_list_head = h->iterate_list_tail = NULL;
  69
  70         return h;
  71 }
  72
  73 static void remove_entry(Hashmap *h, struct hashmap_entry *e) {
  74         assert(h);
  75         assert(e);
  76
  77         /* Remove from iteration list */
  78         if (e->iterate_next)
  79                 e->iterate_next->iterate_previous = e->iterate_previous;
  80         else
  81                 h->iterate_list_tail = e->iterate_previous;
  82
  83         if (e->iterate_previous)
  84                 e->iterate_previous->iterate_next = e->iterate_next;
  85         else
  86                 h->iterate_list_head = e->iterate_next;
  87
  88         /* Remove from hash table bucket list */
  89         if (e->bucket_next)
  90                 e->bucket_next->bucket_previous = e->bucket_previous;
  91
  92         if (e->bucket_previous)
  93                 e->bucket_previous->bucket_next = e->bucket_next;
  94         else {
  95                 unsigned hash = h->hash_func(e->key) % NBUCKETS;
  96                 BY_HASH(h)[hash] = e->bucket_next;
  97         }
  98
  99         free(e);
 100
 101         assert(h->n_entries >= 1);
 102         h->n_entries--;
 103 }
 104
 105 void hashmap_free(Hashmap*h) {
 106
 107         if (!h)
 108                 return;
 109
 110         while (h->iterate_list_head)
 111                 remove_entry(h, h->iterate_list_head);
 112
 113         free(h);
 114 }
 115
 116 static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *key) {
 117         struct hashmap_entry *e;
 118         assert(h);
 119         assert(hash < NBUCKETS);
 120
 121         for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
 122                 if (h->compare_func(e->key, key) == 0)
 123                         return e;
 124
 125         return NULL;
 126 }
 127
 128 int hashmap_put(Hashmap *h, const void *key, void *value) {
 129         struct hashmap_entry *e;
 130         unsigned hash;
 131
 132         assert(h);
 133
 134         hash = h->hash_func(key) % NBUCKETS;
 135
 136         if (hash_scan(h, hash, key))
 137                 return -EEXIST;
 138
 139         if (!(e = new(struct hashmap_entry, 1)))
 140                 return -ENOMEM;
 141
 142         e->key = key;
 143         e->value = value;
 144
 145         /* Insert into hash table */
 146         e->bucket_next = BY_HASH(h)[hash];
 147         e->bucket_previous = NULL;
 148         if (BY_HASH(h)[hash])
 149                 BY_HASH(h)[hash]->bucket_previous = e;
 150         BY_HASH(h)[hash] = e;
 151
 152         /* Insert into iteration list */
 153         e->iterate_previous = h->iterate_list_tail;
 154         e->iterate_next = NULL;
 155         if (h->iterate_list_tail) {
 156                 assert(h->iterate_list_head);
 157                 h->iterate_list_tail->iterate_next = e;
 158         } else {
 159                 assert(!h->iterate_list_head);
 160                 h->iterate_list_head = e;
 161         }
 162         h->iterate_list_tail = e;
 163
 164         h->n_entries++;
 165         assert(h->n_entries >= 1);
 166
 167         return 0;
 168 }
 169
 170 void* hashmap_get(Hashmap *h, const void *key) {
 171         unsigned hash;
 172         struct hashmap_entry *e;
 173
 174         if (!h)
 175                 return NULL;
 176
 177         hash = h->hash_func(key) % NBUCKETS;
 178
 179         if (!(e = hash_scan(h, hash, key)))
 180                 return NULL;
 181
 182         return e->value;
 183 }
 184
 185 void* hashmap_remove(Hashmap *h, const void *key) {
 186         struct hashmap_entry *e;
 187         unsigned hash;
 188         void *data;
 189
 190         if (!h)
 191                 return NULL;
 192
 193         hash = h->hash_func(key) % NBUCKETS;
 194
 195         if (!(e = hash_scan(h, hash, key)))
 196                 return NULL;
 197
 198         data = e->value;
 199         remove_entry(h, e);
 200
 201         return data;
 202 }
 203
 204 void *hashmap_iterate(Hashmap *h, void **state, const void **key) {
 205         struct hashmap_entry *e;
 206
 207         assert(state);
 208
 209         if (!h)
 210                 goto at_end;
 211
 212         if (*state == (void*) -1)
 213                 goto at_end;
 214
 215         if (!*state && !h->iterate_list_head)
 216                 goto at_end;
 217
 218         e = *state ? *state : h->iterate_list_head;
 219
 220         if (e->iterate_next)
 221                 *state = e->iterate_next;
 222         else
 223                 *state = (void*) -1;
 224
 225         if (key)
 226                 *key = e->key;
 227
 228         return e->value;
 229
 230 at_end:
 231         *state = (void *) -1;
 232
 233         if (key)
 234                 *key = NULL;
 235
 236         return NULL;
 237 }
 238
 239 void *hashmap_iterate_backwards(Hashmap *h, void **state, const void **key) {
 240         struct hashmap_entry *e;
 241
 242         assert(state);
 243
 244         if (!h)
 245                 goto at_beginning;
 246
 247         if (*state == (void*) -1)
 248                 goto at_beginning;
 249
 250         if (!*state && !h->iterate_list_tail)
 251                 goto at_beginning;
 252
 253         e = *state ? *state : h->iterate_list_tail;
 254
 255         if (e->iterate_previous)
 256                 *state = e->iterate_previous;
 257         else
 258                 *state = (void*) -1;
 259
 260         if (key)
 261                 *key = e->key;
 262
 263         return e->value;
 264
 265 at_beginning:
 266         *state = (void *) -1;
 267
 268         if (key)
 269                 *key = NULL;
 270
 271         return NULL;
 272 }
 273
 274 void* hashmap_first(Hashmap *h) {
 275
 276         if (!h)
 277                 return NULL;
 278
 279         if (!h->iterate_list_head)
 280                 return NULL;
 281
 282         return h->iterate_list_head->value;
 283 }
 284
 285 void* hashmap_last(Hashmap *h) {
 286
 287         if (!h)
 288                 return NULL;
 289
 290         if (!h->iterate_list_tail)
 291                 return NULL;
 292
 293         return h->iterate_list_tail->value;
 294 }
 295
 296 void* hashmap_steal_first(Hashmap *h) {
 297         void *data;
 298
 299         if (!h)
 300                 return NULL;
 301
 302         if (!h->iterate_list_head)
 303                 return NULL;
 304
 305         data = h->iterate_list_head->value;
 306         remove_entry(h, h->iterate_list_head);
 307
 308         return data;
 309 }
 310
 311 unsigned hashmap_size(Hashmap *h) {
 312
 313         if (!h)
 314                 return 0;
 315
 316         return h->n_entries;
 317 }
 318
 319 bool hashmap_isempty(Hashmap *h) {
 320
 321         if (!h)
 322                 return true;
 323
 324         return h->n_entries == 0;
 325 }