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 (hash_scan(h, hash, key))
 143                 return -EEXIST;
 144
 145         if (!(e = new(struct hashmap_entry, 1)))
 146                 return -ENOMEM;
 147
 148         e->key = key;
 149         e->value = value;
 150
 151         /* Insert into hash table */
 152         e->bucket_next = BY_HASH(h)[hash];
 153         e->bucket_previous = NULL;
 154         if (BY_HASH(h)[hash])
 155                 BY_HASH(h)[hash]->bucket_previous = e;
 156         BY_HASH(h)[hash] = e;
 157
 158         /* Insert into iteration list */
 159         e->iterate_previous = h->iterate_list_tail;
 160         e->iterate_next = NULL;
 161         if (h->iterate_list_tail) {
 162                 assert(h->iterate_list_head);
 163                 h->iterate_list_tail->iterate_next = e;
 164         } else {
 165                 assert(!h->iterate_list_head);
 166                 h->iterate_list_head = e;
 167         }
 168         h->iterate_list_tail = e;
 169
 170         h->n_entries++;
 171         assert(h->n_entries >= 1);
 172
 173         return 0;
 174 }
 175
 176 void* hashmap_get(Hashmap *h, const void *key) {
 177         unsigned hash;
 178         struct hashmap_entry *e;
 179
 180         if (!h)
 181                 return NULL;
 182
 183         hash = h->hash_func(key) % NBUCKETS;
 184
 185         if (!(e = hash_scan(h, hash, key)))
 186                 return NULL;
 187
 188         return e->value;
 189 }
 190
 191 void* hashmap_remove(Hashmap *h, const void *key) {
 192         struct hashmap_entry *e;
 193         unsigned hash;
 194         void *data;
 195
 196         if (!h)
 197                 return NULL;
 198
 199         hash = h->hash_func(key) % NBUCKETS;
 200
 201         if (!(e = hash_scan(h, hash, key)))
 202                 return NULL;
 203
 204         data = e->value;
 205         remove_entry(h, e);
 206
 207         return data;
 208 }
 209
 210 void *hashmap_iterate(Hashmap *h, void **state, const void **key) {
 211         struct hashmap_entry *e;
 212
 213         assert(state);
 214
 215         if (!h)
 216                 goto at_end;
 217
 218         if (*state == (void*) -1)
 219                 goto at_end;
 220
 221         if (!*state && !h->iterate_list_head)
 222                 goto at_end;
 223
 224         e = *state ? *state : h->iterate_list_head;
 225
 226         if (e->iterate_next)
 227                 *state = e->iterate_next;
 228         else
 229                 *state = (void*) -1;
 230
 231         if (key)
 232                 *key = e->key;
 233
 234         return e->value;
 235
 236 at_end:
 237         *state = (void *) -1;
 238
 239         if (key)
 240                 *key = NULL;
 241
 242         return NULL;
 243 }
 244
 245 void *hashmap_iterate_backwards(Hashmap *h, void **state, const void **key) {
 246         struct hashmap_entry *e;
 247
 248         assert(state);
 249
 250         if (!h)
 251                 goto at_beginning;
 252
 253         if (*state == (void*) -1)
 254                 goto at_beginning;
 255
 256         if (!*state && !h->iterate_list_tail)
 257                 goto at_beginning;
 258
 259         e = *state ? *state : h->iterate_list_tail;
 260
 261         if (e->iterate_previous)
 262                 *state = e->iterate_previous;
 263         else
 264                 *state = (void*) -1;
 265
 266         if (key)
 267                 *key = e->key;
 268
 269         return e->value;
 270
 271 at_beginning:
 272         *state = (void *) -1;
 273
 274         if (key)
 275                 *key = NULL;
 276
 277         return NULL;
 278 }
 279
 280 void* hashmap_first(Hashmap *h) {
 281
 282         if (!h)
 283                 return NULL;
 284
 285         if (!h->iterate_list_head)
 286                 return NULL;
 287
 288         return h->iterate_list_head->value;
 289 }
 290
 291 void* hashmap_last(Hashmap *h) {
 292
 293         if (!h)
 294                 return NULL;
 295
 296         if (!h->iterate_list_tail)
 297                 return NULL;
 298
 299         return h->iterate_list_tail->value;
 300 }
 301
 302 void* hashmap_steal_first(Hashmap *h) {
 303         void *data;
 304
 305         if (!h)
 306                 return NULL;
 307
 308         if (!h->iterate_list_head)
 309                 return NULL;
 310
 311         data = h->iterate_list_head->value;
 312         remove_entry(h, h->iterate_list_head);
 313
 314         return data;
 315 }
 316
 317 unsigned hashmap_size(Hashmap *h) {
 318
 319         if (!h)
 320                 return 0;
 321
 322         return h->n_entries;
 323 }
 324
 325 bool hashmap_isempty(Hashmap *h) {
 326
 327         if (!h)
 328                 return true;
 329
 330         return h->n_entries == 0;
 331 }
 332
 333 int hashmap_merge(Hashmap *h, Hashmap *other) {
 334         struct hashmap_entry *e;
 335
 336         assert(h);
 337
 338         if (!other)
 339                 return 0;
 340
 341         for (e = other->iterate_list_head; e; e = e->iterate_next) {
 342                 int r;
 343
 344                 if ((r = hashmap_put(h, e->key, e->value)) < 0)
 345                         if (r != -EEXIST)
 346                                 return r;
 347         }
 348
 349         return 0;
 350 }
 351
 352 Hashmap *hashmap_copy(Hashmap *h) {
 353         Hashmap *copy;
 354
 355         assert(h);
 356
 357         if (!(copy = hashmap_new(h->hash_func, h->compare_func)))
 358                 return NULL;
 359
 360         if (hashmap_merge(copy, h) < 0) {
 361                 hashmap_free(copy);
 362                 return NULL;
 363         }
 364
 365         return copy;
 366 }