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