hashmap.c

   1 /*-*- Mode: C; c-basic-offset: 8 -*-*/
   2
   3 /***
   4   This file is part of systemd.
   5
   6   Copyright 2010 Lennart Poettering
   7
   8   systemd is free software; you can redistribute it and/or modify it
   9   under the terms of the GNU General Public License as published by
  10   the Free Software Foundation; either version 2 of the License, or
  11   (at your option) any later version.
  12
  13   systemd is distributed in the hope that it will be useful, but
  14   WITHOUT ANY WARRANTY; without even the implied warranty of
  15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16   General Public License for more details.
  17
  18   You should have received a copy of the GNU General Public License
  19   along with systemd; If not, see <http://www.gnu.org/licenses/>.
  20 ***/
  21
  22 #include <assert.h>
  23 #include <stdlib.h>
  24 #include <string.h>
  25 #include <errno.h>
  26
  27 #include "util.h"
  28 #include "hashmap.h"
  29 #include "macro.h"
  30
  31 #define NBUCKETS 127
  32
  33 struct hashmap_entry {
  34         const void *key;
  35         void *value;
  36         struct hashmap_entry *bucket_next, *bucket_previous;
  37         struct hashmap_entry *iterate_next, *iterate_previous;
  38 };
  39
  40 struct Hashmap {
  41         hash_func_t hash_func;
  42         compare_func_t compare_func;
  43
  44         struct hashmap_entry *iterate_list_head, *iterate_list_tail;
  45         unsigned n_entries;
  46 };
  47
  48 #define BY_HASH(h) ((struct hashmap_entry**) ((uint8_t*) (h) + ALIGN(sizeof(Hashmap))))
  49
  50 unsigned string_hash_func(const void *p) {
  51         unsigned hash = 0;
  52         const char *c;
  53
  54         for (c = p; *c; c++)
  55                 hash = 31 * hash + (unsigned) *c;
  56
  57         return hash;
  58 }
  59
  60 int string_compare_func(const void *a, const void *b) {
  61         return strcmp(a, b);
  62 }
  63
  64 unsigned trivial_hash_func(const void *p) {
  65         return PTR_TO_UINT(p);
  66 }
  67
  68 int trivial_compare_func(const void *a, const void *b) {
  69         return a < b ? -1 : (a > b ? 1 : 0);
  70 }
  71
  72 Hashmap *hashmap_new(hash_func_t hash_func, compare_func_t compare_func) {
  73         Hashmap *h;
  74
  75         if (!(h = malloc0(ALIGN(sizeof(Hashmap)) + NBUCKETS * ALIGN(sizeof(struct hashmap_entry*)))))
  76                 return NULL;
  77
  78         h->hash_func = hash_func ? hash_func : trivial_hash_func;
  79         h->compare_func = compare_func ? compare_func : trivial_compare_func;
  80
  81         h->n_entries = 0;
  82         h->iterate_list_head = h->iterate_list_tail = NULL;
  83
  84         return h;
  85 }
  86
  87 int hashmap_ensure_allocated(Hashmap **h, hash_func_t hash_func, compare_func_t compare_func) {
  88         assert(h);
  89
  90         if (*h)
  91                 return 0;
  92
  93         if (!(*h = hashmap_new(hash_func, compare_func)))
  94                 return -ENOMEM;
  95
  96         return 0;
  97 }
  98
  99 static void remove_entry(Hashmap *h, struct hashmap_entry *e) {
 100         assert(h);
 101         assert(e);
 102
 103         /* Remove from iteration list */
 104         if (e->iterate_next)
 105                 e->iterate_next->iterate_previous = e->iterate_previous;
 106         else
 107                 h->iterate_list_tail = e->iterate_previous;
 108
 109         if (e->iterate_previous)
 110                 e->iterate_previous->iterate_next = e->iterate_next;
 111         else
 112                 h->iterate_list_head = e->iterate_next;
 113
 114         /* Remove from hash table bucket list */
 115         if (e->bucket_next)
 116                 e->bucket_next->bucket_previous = e->bucket_previous;
 117
 118         if (e->bucket_previous)
 119                 e->bucket_previous->bucket_next = e->bucket_next;
 120         else {
 121                 unsigned hash = h->hash_func(e->key) % NBUCKETS;
 122                 BY_HASH(h)[hash] = e->bucket_next;
 123         }
 124
 125         free(e);
 126
 127         assert(h->n_entries >= 1);
 128         h->n_entries--;
 129 }
 130
 131 void hashmap_free(Hashmap*h) {
 132
 133         if (!h)
 134                 return;
 135
 136         hashmap_clear(h);
 137
 138         free(h);
 139 }
 140
 141 void hashmap_clear(Hashmap *h) {
 142         if (!h)
 143                 return;
 144
 145         while (h->iterate_list_head)
 146                 remove_entry(h, h->iterate_list_head);
 147 }
 148
 149 static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *key) {
 150         struct hashmap_entry *e;
 151         assert(h);
 152         assert(hash < NBUCKETS);
 153
 154         for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
 155                 if (h->compare_func(e->key, key) == 0)
 156                         return e;
 157
 158         return NULL;
 159 }
 160
 161 int hashmap_put(Hashmap *h, const void *key, void *value) {
 162         struct hashmap_entry *e;
 163         unsigned hash;
 164
 165         assert(h);
 166
 167         hash = h->hash_func(key) % NBUCKETS;
 168
 169         if ((e = hash_scan(h, hash, key))) {
 170
 171                 if (e->value == value)
 172                         return 0;
 173
 174                 return -EEXIST;
 175         }
 176
 177         if (!(e = new(struct hashmap_entry, 1)))
 178                 return -ENOMEM;
 179
 180         e->key = key;
 181         e->value = value;
 182
 183         /* Insert into hash table */
 184         e->bucket_next = BY_HASH(h)[hash];
 185         e->bucket_previous = NULL;
 186         if (BY_HASH(h)[hash])
 187                 BY_HASH(h)[hash]->bucket_previous = e;
 188         BY_HASH(h)[hash] = e;
 189
 190         /* Insert into iteration list */
 191         e->iterate_previous = h->iterate_list_tail;
 192         e->iterate_next = NULL;
 193         if (h->iterate_list_tail) {
 194                 assert(h->iterate_list_head);
 195                 h->iterate_list_tail->iterate_next = e;
 196         } else {
 197                 assert(!h->iterate_list_head);
 198                 h->iterate_list_head = e;
 199         }
 200         h->iterate_list_tail = e;
 201
 202         h->n_entries++;
 203         assert(h->n_entries >= 1);
 204
 205         return 0;
 206 }
 207
 208 int hashmap_replace(Hashmap *h, const void *key, void *value) {
 209         struct hashmap_entry *e;
 210         unsigned hash;
 211
 212         assert(h);
 213
 214         hash = h->hash_func(key) % NBUCKETS;
 215
 216         if ((e = hash_scan(h, hash, key))) {
 217                 e->value = value;
 218                 return 0;
 219         }
 220
 221         return hashmap_put(h, key, value);
 222 }
 223
 224 void* hashmap_get(Hashmap *h, const void *key) {
 225         unsigned hash;
 226         struct hashmap_entry *e;
 227
 228         if (!h)
 229                 return NULL;
 230
 231         hash = h->hash_func(key) % NBUCKETS;
 232
 233         if (!(e = hash_scan(h, hash, key)))
 234                 return NULL;
 235
 236         return e->value;
 237 }
 238
 239 void* hashmap_remove(Hashmap *h, const void *key) {
 240         struct hashmap_entry *e;
 241         unsigned hash;
 242         void *data;
 243
 244         if (!h)
 245                 return NULL;
 246
 247         hash = h->hash_func(key) % NBUCKETS;
 248
 249         if (!(e = hash_scan(h, hash, key)))
 250                 return NULL;
 251
 252         data = e->value;
 253         remove_entry(h, e);
 254
 255         return data;
 256 }
 257
 258 void* hashmap_remove_value(Hashmap *h, const void *key, void *value) {
 259         struct hashmap_entry *e;
 260         unsigned hash;
 261
 262         if (!h)
 263                 return NULL;
 264
 265         hash = h->hash_func(key) % NBUCKETS;
 266
 267         if (!(e = hash_scan(h, hash, key)))
 268                 return NULL;
 269
 270         if (e->value != value)
 271                 return NULL;
 272
 273         remove_entry(h, e);
 274
 275         return value;
 276 }
 277
 278 void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key) {
 279         struct hashmap_entry *e;
 280
 281         assert(i);
 282
 283         if (!h)
 284                 goto at_end;
 285
 286         if (*i == ITERATOR_LAST)
 287                 goto at_end;
 288
 289         if (*i == ITERATOR_FIRST && !h->iterate_list_head)
 290                 goto at_end;
 291
 292         e = *i == ITERATOR_FIRST ? h->iterate_list_head : (struct hashmap_entry*) *i;
 293
 294         if (e->iterate_next)
 295                 *i = (Iterator) e->iterate_next;
 296         else
 297                 *i = ITERATOR_LAST;
 298
 299         if (key)
 300                 *key = e->key;
 301
 302         return e->value;
 303
 304 at_end:
 305         *i = ITERATOR_LAST;
 306
 307         if (key)
 308                 *key = NULL;
 309
 310         return NULL;
 311 }
 312
 313 void *hashmap_iterate_backwards(Hashmap *h, Iterator *i, const void **key) {
 314         struct hashmap_entry *e;
 315
 316         assert(i);
 317
 318         if (!h)
 319                 goto at_beginning;
 320
 321         if (*i == ITERATOR_FIRST)
 322                 goto at_beginning;
 323
 324         if (*i == ITERATOR_LAST && !h->iterate_list_tail)
 325                 goto at_beginning;
 326
 327         e = *i == ITERATOR_LAST ? h->iterate_list_tail : (struct hashmap_entry*) *i;
 328
 329         if (e->iterate_previous)
 330                 *i = (Iterator) e->iterate_previous;
 331         else
 332                 *i = ITERATOR_FIRST;
 333
 334         if (key)
 335                 *key = e->key;
 336
 337         return e->value;
 338
 339 at_beginning:
 340         *i = ITERATOR_FIRST;
 341
 342         if (key)
 343                 *key = NULL;
 344
 345         return NULL;
 346 }
 347
 348 void *hashmap_iterate_skip(Hashmap *h, const void *key, Iterator *i) {
 349         unsigned hash;
 350         struct hashmap_entry *e;
 351
 352         if (!h)
 353                 return NULL;
 354
 355         hash = h->hash_func(key) % NBUCKETS;
 356
 357         if (!(e = hash_scan(h, hash, key)))
 358                 return NULL;
 359
 360         *i = (Iterator) e;
 361
 362         return e->value;
 363 }
 364
 365 void* hashmap_first(Hashmap *h) {
 366
 367         if (!h)
 368                 return NULL;
 369
 370         if (!h->iterate_list_head)
 371                 return NULL;
 372
 373         return h->iterate_list_head->value;
 374 }
 375
 376 void* hashmap_last(Hashmap *h) {
 377
 378         if (!h)
 379                 return NULL;
 380
 381         if (!h->iterate_list_tail)
 382                 return NULL;
 383
 384         return h->iterate_list_tail->value;
 385 }
 386
 387 void* hashmap_steal_first(Hashmap *h) {
 388         void *data;
 389
 390         if (!h)
 391                 return NULL;
 392
 393         if (!h->iterate_list_head)
 394                 return NULL;
 395
 396         data = h->iterate_list_head->value;
 397         remove_entry(h, h->iterate_list_head);
 398
 399         return data;
 400 }
 401
 402 unsigned hashmap_size(Hashmap *h) {
 403
 404         if (!h)
 405                 return 0;
 406
 407         return h->n_entries;
 408 }
 409
 410 bool hashmap_isempty(Hashmap *h) {
 411
 412         if (!h)
 413                 return true;
 414
 415         return h->n_entries == 0;
 416 }
 417
 418 int hashmap_merge(Hashmap *h, Hashmap *other) {
 419         struct hashmap_entry *e;
 420
 421         assert(h);
 422
 423         if (!other)
 424                 return 0;
 425
 426         for (e = other->iterate_list_head; e; e = e->iterate_next) {
 427                 int r;
 428
 429                 if ((r = hashmap_put(h, e->key, e->value)) < 0)
 430                         if (r != -EEXIST)
 431                                 return r;
 432         }
 433
 434         return 0;
 435 }
 436
 437 Hashmap *hashmap_copy(Hashmap *h) {
 438         Hashmap *copy;
 439
 440         assert(h);
 441
 442         if (!(copy = hashmap_new(h->hash_func, h->compare_func)))
 443                 return NULL;
 444
 445         if (hashmap_merge(copy, h) < 0) {
 446                 hashmap_free(copy);
 447                 return NULL;
 448         }
 449
 450         return copy;
 451 }