src/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 link_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) {
 100         assert(h);
 101         assert(e);
 102
 103         /* Insert into hash table */
 104         e->bucket_next = BY_HASH(h)[hash];
 105         e->bucket_previous = NULL;
 106         if (BY_HASH(h)[hash])
 107                 BY_HASH(h)[hash]->bucket_previous = e;
 108         BY_HASH(h)[hash] = e;
 109
 110         /* Insert into iteration list */
 111         e->iterate_previous = h->iterate_list_tail;
 112         e->iterate_next = NULL;
 113         if (h->iterate_list_tail) {
 114                 assert(h->iterate_list_head);
 115                 h->iterate_list_tail->iterate_next = e;
 116         } else {
 117                 assert(!h->iterate_list_head);
 118                 h->iterate_list_head = e;
 119         }
 120         h->iterate_list_tail = e;
 121
 122         h->n_entries++;
 123         assert(h->n_entries >= 1);
 124 }
 125
 126 static void unlink_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) {
 127         assert(h);
 128         assert(e);
 129
 130         /* Remove from iteration list */
 131         if (e->iterate_next)
 132                 e->iterate_next->iterate_previous = e->iterate_previous;
 133         else
 134                 h->iterate_list_tail = e->iterate_previous;
 135
 136         if (e->iterate_previous)
 137                 e->iterate_previous->iterate_next = e->iterate_next;
 138         else
 139                 h->iterate_list_head = e->iterate_next;
 140
 141         /* Remove from hash table bucket list */
 142         if (e->bucket_next)
 143                 e->bucket_next->bucket_previous = e->bucket_previous;
 144
 145         if (e->bucket_previous)
 146                 e->bucket_previous->bucket_next = e->bucket_next;
 147         else
 148                 BY_HASH(h)[hash] = e->bucket_next;
 149
 150         assert(h->n_entries >= 1);
 151         h->n_entries--;
 152 }
 153
 154 static void remove_entry(Hashmap *h, struct hashmap_entry *e) {
 155         unsigned hash;
 156
 157         assert(h);
 158         assert(e);
 159
 160         hash = h->hash_func(e->key) % NBUCKETS;
 161
 162         unlink_entry(h, e, hash);
 163         free(e);
 164 }
 165
 166 void hashmap_free(Hashmap*h) {
 167
 168         if (!h)
 169                 return;
 170
 171         hashmap_clear(h);
 172
 173         free(h);
 174 }
 175
 176 void hashmap_clear(Hashmap *h) {
 177         if (!h)
 178                 return;
 179
 180         while (h->iterate_list_head)
 181                 remove_entry(h, h->iterate_list_head);
 182 }
 183
 184 static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *key) {
 185         struct hashmap_entry *e;
 186         assert(h);
 187         assert(hash < NBUCKETS);
 188
 189         for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
 190                 if (h->compare_func(e->key, key) == 0)
 191                         return e;
 192
 193         return NULL;
 194 }
 195
 196 int hashmap_put(Hashmap *h, const void *key, void *value) {
 197         struct hashmap_entry *e;
 198         unsigned hash;
 199
 200         assert(h);
 201
 202         hash = h->hash_func(key) % NBUCKETS;
 203
 204         if ((e = hash_scan(h, hash, key))) {
 205
 206                 if (e->value == value)
 207                         return 0;
 208
 209                 return -EEXIST;
 210         }
 211
 212         if (!(e = new(struct hashmap_entry, 1)))
 213                 return -ENOMEM;
 214
 215         e->key = key;
 216         e->value = value;
 217
 218         link_entry(h, e, hash);
 219
 220         return 1;
 221 }
 222
 223 int hashmap_replace(Hashmap *h, const void *key, void *value) {
 224         struct hashmap_entry *e;
 225         unsigned hash;
 226
 227         assert(h);
 228
 229         hash = h->hash_func(key) % NBUCKETS;
 230
 231         if ((e = hash_scan(h, hash, key))) {
 232                 e->key = key;
 233                 e->value = value;
 234                 return 0;
 235         }
 236
 237         return hashmap_put(h, key, value);
 238 }
 239
 240 void* hashmap_get(Hashmap *h, const void *key) {
 241         unsigned hash;
 242         struct hashmap_entry *e;
 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         return e->value;
 253 }
 254
 255 void* hashmap_remove(Hashmap *h, const void *key) {
 256         struct hashmap_entry *e;
 257         unsigned hash;
 258         void *data;
 259
 260         if (!h)
 261                 return NULL;
 262
 263         hash = h->hash_func(key) % NBUCKETS;
 264
 265         if (!(e = hash_scan(h, hash, key)))
 266                 return NULL;
 267
 268         data = e->value;
 269         remove_entry(h, e);
 270
 271         return data;
 272 }
 273
 274 int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value) {
 275         struct hashmap_entry *e;
 276         unsigned old_hash, new_hash;
 277
 278         if (!h)
 279                 return -ENOENT;
 280
 281         old_hash = h->hash_func(old_key) % NBUCKETS;
 282         if (!(e = hash_scan(h, old_hash, old_key)))
 283                 return -ENOENT;
 284
 285         new_hash = h->hash_func(new_key) % NBUCKETS;
 286         if (hash_scan(h, new_hash, new_key))
 287                 return -EEXIST;
 288
 289         unlink_entry(h, e, old_hash);
 290
 291         e->key = new_key;
 292         e->value = value;
 293
 294         link_entry(h, e, new_hash);
 295
 296         return 0;
 297 }
 298
 299 int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value) {
 300         struct hashmap_entry *e, *k;
 301         unsigned old_hash, new_hash;
 302
 303         if (!h)
 304                 return -ENOENT;
 305
 306         old_hash = h->hash_func(old_key) % NBUCKETS;
 307         if (!(e = hash_scan(h, old_hash, old_key)))
 308                 return -ENOENT;
 309
 310         new_hash = h->hash_func(new_key) % NBUCKETS;
 311
 312         if ((k = hash_scan(h, new_hash, new_key)))
 313                 if (e != k)
 314                         remove_entry(h, k);
 315
 316         unlink_entry(h, e, old_hash);
 317
 318         e->key = new_key;
 319         e->value = value;
 320
 321         link_entry(h, e, new_hash);
 322
 323         return 0;
 324 }
 325
 326 void* hashmap_remove_value(Hashmap *h, const void *key, void *value) {
 327         struct hashmap_entry *e;
 328         unsigned hash;
 329
 330         if (!h)
 331                 return NULL;
 332
 333         hash = h->hash_func(key) % NBUCKETS;
 334
 335         if (!(e = hash_scan(h, hash, key)))
 336                 return NULL;
 337
 338         if (e->value != value)
 339                 return NULL;
 340
 341         remove_entry(h, e);
 342
 343         return value;
 344 }
 345
 346 void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key) {
 347         struct hashmap_entry *e;
 348
 349         assert(i);
 350
 351         if (!h)
 352                 goto at_end;
 353
 354         if (*i == ITERATOR_LAST)
 355                 goto at_end;
 356
 357         if (*i == ITERATOR_FIRST && !h->iterate_list_head)
 358                 goto at_end;
 359
 360         e = *i == ITERATOR_FIRST ? h->iterate_list_head : (struct hashmap_entry*) *i;
 361
 362         if (e->iterate_next)
 363                 *i = (Iterator) e->iterate_next;
 364         else
 365                 *i = ITERATOR_LAST;
 366
 367         if (key)
 368                 *key = e->key;
 369
 370         return e->value;
 371
 372 at_end:
 373         *i = ITERATOR_LAST;
 374
 375         if (key)
 376                 *key = NULL;
 377
 378         return NULL;
 379 }
 380
 381 void *hashmap_iterate_backwards(Hashmap *h, Iterator *i, const void **key) {
 382         struct hashmap_entry *e;
 383
 384         assert(i);
 385
 386         if (!h)
 387                 goto at_beginning;
 388
 389         if (*i == ITERATOR_FIRST)
 390                 goto at_beginning;
 391
 392         if (*i == ITERATOR_LAST && !h->iterate_list_tail)
 393                 goto at_beginning;
 394
 395         e = *i == ITERATOR_LAST ? h->iterate_list_tail : (struct hashmap_entry*) *i;
 396
 397         if (e->iterate_previous)
 398                 *i = (Iterator) e->iterate_previous;
 399         else
 400                 *i = ITERATOR_FIRST;
 401
 402         if (key)
 403                 *key = e->key;
 404
 405         return e->value;
 406
 407 at_beginning:
 408         *i = ITERATOR_FIRST;
 409
 410         if (key)
 411                 *key = NULL;
 412
 413         return NULL;
 414 }
 415
 416 void *hashmap_iterate_skip(Hashmap *h, const void *key, Iterator *i) {
 417         unsigned hash;
 418         struct hashmap_entry *e;
 419
 420         if (!h)
 421                 return NULL;
 422
 423         hash = h->hash_func(key) % NBUCKETS;
 424
 425         if (!(e = hash_scan(h, hash, key)))
 426                 return NULL;
 427
 428         *i = (Iterator) e;
 429
 430         return e->value;
 431 }
 432
 433 void* hashmap_first(Hashmap *h) {
 434
 435         if (!h)
 436                 return NULL;
 437
 438         if (!h->iterate_list_head)
 439                 return NULL;
 440
 441         return h->iterate_list_head->value;
 442 }
 443
 444 void* hashmap_last(Hashmap *h) {
 445
 446         if (!h)
 447                 return NULL;
 448
 449         if (!h->iterate_list_tail)
 450                 return NULL;
 451
 452         return h->iterate_list_tail->value;
 453 }
 454
 455 void* hashmap_steal_first(Hashmap *h) {
 456         void *data;
 457
 458         if (!h)
 459                 return NULL;
 460
 461         if (!h->iterate_list_head)
 462                 return NULL;
 463
 464         data = h->iterate_list_head->value;
 465         remove_entry(h, h->iterate_list_head);
 466
 467         return data;
 468 }
 469
 470 unsigned hashmap_size(Hashmap *h) {
 471
 472         if (!h)
 473                 return 0;
 474
 475         return h->n_entries;
 476 }
 477
 478 bool hashmap_isempty(Hashmap *h) {
 479
 480         if (!h)
 481                 return true;
 482
 483         return h->n_entries == 0;
 484 }
 485
 486 int hashmap_merge(Hashmap *h, Hashmap *other) {
 487         struct hashmap_entry *e;
 488
 489         assert(h);
 490
 491         if (!other)
 492                 return 0;
 493
 494         for (e = other->iterate_list_head; e; e = e->iterate_next) {
 495                 int r;
 496
 497                 if ((r = hashmap_put(h, e->key, e->value)) < 0)
 498                         if (r != -EEXIST)
 499                                 return r;
 500         }
 501
 502         return 0;
 503 }
 504
 505 void hashmap_move(Hashmap *h, Hashmap *other) {
 506         struct hashmap_entry *e, *n;
 507
 508         assert(h);
 509
 510         /* The same as hashmap_merge(), but every new item from other
 511          * is moved to h. This function is guaranteed to succeed. */
 512
 513         if (!other)
 514                 return;
 515
 516         for (e = other->iterate_list_head; e; e = n) {
 517                 unsigned h_hash, other_hash;
 518
 519                 n = e->iterate_next;
 520
 521                 h_hash = h->hash_func(e->key) % NBUCKETS;
 522
 523                 if (hash_scan(h, h_hash, e->key))
 524                         continue;
 525
 526                 other_hash = other->hash_func(e->key) % NBUCKETS;
 527
 528                 unlink_entry(other, e, other_hash);
 529                 link_entry(h, e, h_hash);
 530         }
 531 }
 532
 533 int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) {
 534         unsigned h_hash, other_hash;
 535         struct hashmap_entry *e;
 536
 537         if (!other)
 538                 return 0;
 539
 540         assert(h);
 541
 542         h_hash = h->hash_func(key) % NBUCKETS;
 543         if (hash_scan(h, h_hash, key))
 544                 return -EEXIST;
 545
 546         other_hash = other->hash_func(key) % NBUCKETS;
 547         if (!(e = hash_scan(other, other_hash, key)))
 548                 return -ENOENT;
 549
 550         unlink_entry(other, e, other_hash);
 551         link_entry(h, e, h_hash);
 552
 553         return 0;
 554 }
 555
 556 Hashmap *hashmap_copy(Hashmap *h) {
 557         Hashmap *copy;
 558
 559         assert(h);
 560
 561         if (!(copy = hashmap_new(h->hash_func, h->compare_func)))
 562                 return NULL;
 563
 564         if (hashmap_merge(copy, h) < 0) {
 565                 hashmap_free(copy);
 566                 return NULL;
 567         }
 568
 569         return copy;
 570 }