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