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         hashmap_clear(h);
 110
 111         free(h);
 112 }
 113
 114 void hashmap_clear(Hashmap *h) {
 115         if (!h)
 116                 return;
 117
 118         while (h->iterate_list_head)
 119                 remove_entry(h, h->iterate_list_head);
 120 }
 121
 122 static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *key) {
 123         struct hashmap_entry *e;
 124         assert(h);
 125         assert(hash < NBUCKETS);
 126
 127         for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
 128                 if (h->compare_func(e->key, key) == 0)
 129                         return e;
 130
 131         return NULL;
 132 }
 133
 134 int hashmap_put(Hashmap *h, const void *key, void *value) {
 135         struct hashmap_entry *e;
 136         unsigned hash;
 137
 138         assert(h);
 139
 140         hash = h->hash_func(key) % NBUCKETS;
 141
 142         if ((e = hash_scan(h, hash, key))) {
 143
 144                 if (e->value == value)
 145                         return 0;
 146
 147                 return -EEXIST;
 148         }
 149
 150         if (!(e = new(struct hashmap_entry, 1)))
 151                 return -ENOMEM;
 152
 153         e->key = key;
 154         e->value = value;
 155
 156         /* Insert into hash table */
 157         e->bucket_next = BY_HASH(h)[hash];
 158         e->bucket_previous = NULL;
 159         if (BY_HASH(h)[hash])
 160                 BY_HASH(h)[hash]->bucket_previous = e;
 161         BY_HASH(h)[hash] = e;
 162
 163         /* Insert into iteration list */
 164         e->iterate_previous = h->iterate_list_tail;
 165         e->iterate_next = NULL;
 166         if (h->iterate_list_tail) {
 167                 assert(h->iterate_list_head);
 168                 h->iterate_list_tail->iterate_next = e;
 169         } else {
 170                 assert(!h->iterate_list_head);
 171                 h->iterate_list_head = e;
 172         }
 173         h->iterate_list_tail = e;
 174
 175         h->n_entries++;
 176         assert(h->n_entries >= 1);
 177
 178         return 0;
 179 }
 180
 181 int hashmap_replace(Hashmap *h, const void *key, void *value) {
 182         struct hashmap_entry *e;
 183         unsigned hash;
 184
 185         assert(h);
 186
 187         hash = h->hash_func(key) % NBUCKETS;
 188
 189         if ((e = hash_scan(h, hash, key))) {
 190                 e->value = value;
 191                 return 0;
 192         }
 193
 194         return hashmap_put(h, key, value);
 195 }
 196
 197 void* hashmap_get(Hashmap *h, const void *key) {
 198         unsigned hash;
 199         struct hashmap_entry *e;
 200
 201         if (!h)
 202                 return NULL;
 203
 204         hash = h->hash_func(key) % NBUCKETS;
 205
 206         if (!(e = hash_scan(h, hash, key)))
 207                 return NULL;
 208
 209         return e->value;
 210 }
 211
 212 void* hashmap_remove(Hashmap *h, const void *key) {
 213         struct hashmap_entry *e;
 214         unsigned hash;
 215         void *data;
 216
 217         if (!h)
 218                 return NULL;
 219
 220         hash = h->hash_func(key) % NBUCKETS;
 221
 222         if (!(e = hash_scan(h, hash, key)))
 223                 return NULL;
 224
 225         data = e->value;
 226         remove_entry(h, e);
 227
 228         return data;
 229 }
 230
 231 void* hashmap_remove_value(Hashmap *h, const void *key, void *value) {
 232         struct hashmap_entry *e;
 233         unsigned hash;
 234
 235         if (!h)
 236                 return NULL;
 237
 238         hash = h->hash_func(key) % NBUCKETS;
 239
 240         if (!(e = hash_scan(h, hash, key)))
 241                 return NULL;
 242
 243         if (e->value != value)
 244                 return NULL;
 245
 246         remove_entry(h, e);
 247
 248         return value;
 249 }
 250
 251 void *hashmap_iterate(Hashmap *h, void **state, const void **key) {
 252         struct hashmap_entry *e;
 253
 254         assert(state);
 255
 256         if (!h)
 257                 goto at_end;
 258
 259         if (*state == (void*) -1)
 260                 goto at_end;
 261
 262         if (!*state && !h->iterate_list_head)
 263                 goto at_end;
 264
 265         e = *state ? *state : h->iterate_list_head;
 266
 267         if (e->iterate_next)
 268                 *state = e->iterate_next;
 269         else
 270                 *state = (void*) -1;
 271
 272         if (key)
 273                 *key = e->key;
 274
 275         return e->value;
 276
 277 at_end:
 278         *state = (void *) -1;
 279
 280         if (key)
 281                 *key = NULL;
 282
 283         return NULL;
 284 }
 285
 286 void *hashmap_iterate_backwards(Hashmap *h, void **state, const void **key) {
 287         struct hashmap_entry *e;
 288
 289         assert(state);
 290
 291         if (!h)
 292                 goto at_beginning;
 293
 294         if (*state == (void*) -1)
 295                 goto at_beginning;
 296
 297         if (!*state && !h->iterate_list_tail)
 298                 goto at_beginning;
 299
 300         e = *state ? *state : h->iterate_list_tail;
 301
 302         if (e->iterate_previous)
 303                 *state = e->iterate_previous;
 304         else
 305                 *state = (void*) -1;
 306
 307         if (key)
 308                 *key = e->key;
 309
 310         return e->value;
 311
 312 at_beginning:
 313         *state = (void *) -1;
 314
 315         if (key)
 316                 *key = NULL;
 317
 318         return NULL;
 319 }
 320
 321 void* hashmap_first(Hashmap *h) {
 322
 323         if (!h)
 324                 return NULL;
 325
 326         if (!h->iterate_list_head)
 327                 return NULL;
 328
 329         return h->iterate_list_head->value;
 330 }
 331
 332 void* hashmap_last(Hashmap *h) {
 333
 334         if (!h)
 335                 return NULL;
 336
 337         if (!h->iterate_list_tail)
 338                 return NULL;
 339
 340         return h->iterate_list_tail->value;
 341 }
 342
 343 void* hashmap_steal_first(Hashmap *h) {
 344         void *data;
 345
 346         if (!h)
 347                 return NULL;
 348
 349         if (!h->iterate_list_head)
 350                 return NULL;
 351
 352         data = h->iterate_list_head->value;
 353         remove_entry(h, h->iterate_list_head);
 354
 355         return data;
 356 }
 357
 358 unsigned hashmap_size(Hashmap *h) {
 359
 360         if (!h)
 361                 return 0;
 362
 363         return h->n_entries;
 364 }
 365
 366 bool hashmap_isempty(Hashmap *h) {
 367
 368         if (!h)
 369                 return true;
 370
 371         return h->n_entries == 0;
 372 }
 373
 374 int hashmap_merge(Hashmap *h, Hashmap *other) {
 375         struct hashmap_entry *e;
 376
 377         assert(h);
 378
 379         if (!other)
 380                 return 0;
 381
 382         for (e = other->iterate_list_head; e; e = e->iterate_next) {
 383                 int r;
 384
 385                 if ((r = hashmap_put(h, e->key, e->value)) < 0)
 386                         if (r != -EEXIST)
 387                                 return r;
 388         }
 389
 390         return 0;
 391 }
 392
 393 Hashmap *hashmap_copy(Hashmap *h) {
 394         Hashmap *copy;
 395
 396         assert(h);
 397
 398         if (!(copy = hashmap_new(h->hash_func, h->compare_func)))
 399                 return NULL;
 400
 401         if (hashmap_merge(copy, h) < 0) {
 402                 hashmap_free(copy);
 403                 return NULL;
 404         }
 405
 406         return copy;
 407 }