src/shared/hashmap.c

   1 /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
   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 Lesser General Public License as published by
  10   the Free Software Foundation; either version 2.1 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   Lesser General Public License for more details.
  17
  18   You should have received a copy of the GNU Lesser 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         bool from_pool;
  48 };
  49
  50 #define BY_HASH(h) ((struct hashmap_entry**) ((uint8_t*) (h) + ALIGN(sizeof(Hashmap))))
  51
  52 struct pool {
  53         struct pool *next;
  54         unsigned n_tiles;
  55         unsigned n_used;
  56 };
  57
  58 static struct pool *first_hashmap_pool = NULL;
  59 static void *first_hashmap_tile = NULL;
  60
  61 static struct pool *first_entry_pool = NULL;
  62 static void *first_entry_tile = NULL;
  63
  64 static void* allocate_tile(struct pool **first_pool, void **first_tile, size_t tile_size) {
  65         unsigned i;
  66
  67         if (*first_tile) {
  68                 void *r;
  69
  70                 r = *first_tile;
  71                 *first_tile = * (void**) (*first_tile);
  72                 return r;
  73         }
  74
  75         if (_unlikely_(!*first_pool) || _unlikely_((*first_pool)->n_used >= (*first_pool)->n_tiles)) {
  76                 unsigned n;
  77                 size_t size;
  78                 struct pool *p;
  79
  80                 n = *first_pool ? (*first_pool)->n_tiles : 0;
  81                 n = MAX(512U, n * 2);
  82                 size = PAGE_ALIGN(ALIGN(sizeof(struct pool)) + n*tile_size);
  83                 n = (size - ALIGN(sizeof(struct pool))) / tile_size;
  84
  85                 p = malloc(size);
  86                 if (!p)
  87                         return NULL;
  88
  89                 p->next = *first_pool;
  90                 p->n_tiles = n;
  91                 p->n_used = 0;
  92
  93                 *first_pool = p;
  94         }
  95
  96         i = (*first_pool)->n_used++;
  97
  98         return ((uint8_t*) (*first_pool)) + ALIGN(sizeof(struct pool)) + i*tile_size;
  99 }
 100
 101 static void deallocate_tile(void **first_tile, void *p) {
 102         * (void**) p = *first_tile;
 103         *first_tile = p;
 104 }
 105
 106 #ifndef __OPTIMIZE__
 107
 108 static void drop_pool(struct pool *p) {
 109         while (p) {
 110                 struct pool *n;
 111                 n = p->next;
 112                 free(p);
 113                 p = n;
 114         }
 115 }
 116
 117 __attribute__((destructor)) static void cleanup_pool(void) {
 118         /* Be nice to valgrind */
 119
 120         drop_pool(first_hashmap_pool);
 121         drop_pool(first_entry_pool);
 122 }
 123
 124 #endif
 125
 126 unsigned string_hash_func(const void *p) {
 127         unsigned hash = 5381;
 128         const signed char *c;
 129
 130         /* DJB's hash function */
 131
 132         for (c = p; *c; c++)
 133                 hash = (hash << 5) + hash + (unsigned) *c;
 134
 135         return hash;
 136 }
 137
 138 int string_compare_func(const void *a, const void *b) {
 139         return strcmp(a, b);
 140 }
 141
 142 unsigned trivial_hash_func(const void *p) {
 143         return PTR_TO_UINT(p);
 144 }
 145
 146 int trivial_compare_func(const void *a, const void *b) {
 147         return a < b ? -1 : (a > b ? 1 : 0);
 148 }
 149
 150 Hashmap *hashmap_new(hash_func_t hash_func, compare_func_t compare_func) {
 151         bool b;
 152         Hashmap *h;
 153         size_t size;
 154
 155         b = is_main_thread();
 156
 157         size = ALIGN(sizeof(Hashmap)) + NBUCKETS * sizeof(struct hashmap_entry*);
 158
 159         if (b) {
 160                 h = allocate_tile(&first_hashmap_pool, &first_hashmap_tile, size);
 161                 if (!h)
 162                         return NULL;
 163
 164                 memset(h, 0, size);
 165         } else {
 166                 h = malloc0(size);
 167
 168                 if (!h)
 169                         return NULL;
 170         }
 171
 172         h->hash_func = hash_func ? hash_func : trivial_hash_func;
 173         h->compare_func = compare_func ? compare_func : trivial_compare_func;
 174
 175         h->n_entries = 0;
 176         h->iterate_list_head = h->iterate_list_tail = NULL;
 177
 178         h->from_pool = b;
 179
 180         return h;
 181 }
 182
 183 int hashmap_ensure_allocated(Hashmap **h, hash_func_t hash_func, compare_func_t compare_func) {
 184         assert(h);
 185
 186         if (*h)
 187                 return 0;
 188
 189         if (!(*h = hashmap_new(hash_func, compare_func)))
 190                 return -ENOMEM;
 191
 192         return 0;
 193 }
 194
 195 static void link_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) {
 196         assert(h);
 197         assert(e);
 198
 199         /* Insert into hash table */
 200         e->bucket_next = BY_HASH(h)[hash];
 201         e->bucket_previous = NULL;
 202         if (BY_HASH(h)[hash])
 203                 BY_HASH(h)[hash]->bucket_previous = e;
 204         BY_HASH(h)[hash] = e;
 205
 206         /* Insert into iteration list */
 207         e->iterate_previous = h->iterate_list_tail;
 208         e->iterate_next = NULL;
 209         if (h->iterate_list_tail) {
 210                 assert(h->iterate_list_head);
 211                 h->iterate_list_tail->iterate_next = e;
 212         } else {
 213                 assert(!h->iterate_list_head);
 214                 h->iterate_list_head = e;
 215         }
 216         h->iterate_list_tail = e;
 217
 218         h->n_entries++;
 219         assert(h->n_entries >= 1);
 220 }
 221
 222 static void unlink_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) {
 223         assert(h);
 224         assert(e);
 225
 226         /* Remove from iteration list */
 227         if (e->iterate_next)
 228                 e->iterate_next->iterate_previous = e->iterate_previous;
 229         else
 230                 h->iterate_list_tail = e->iterate_previous;
 231
 232         if (e->iterate_previous)
 233                 e->iterate_previous->iterate_next = e->iterate_next;
 234         else
 235                 h->iterate_list_head = e->iterate_next;
 236
 237         /* Remove from hash table bucket list */
 238         if (e->bucket_next)
 239                 e->bucket_next->bucket_previous = e->bucket_previous;
 240
 241         if (e->bucket_previous)
 242                 e->bucket_previous->bucket_next = e->bucket_next;
 243         else
 244                 BY_HASH(h)[hash] = e->bucket_next;
 245
 246         assert(h->n_entries >= 1);
 247         h->n_entries--;
 248 }
 249
 250 static void remove_entry(Hashmap *h, struct hashmap_entry *e) {
 251         unsigned hash;
 252
 253         assert(h);
 254         assert(e);
 255
 256         hash = h->hash_func(e->key) % NBUCKETS;
 257
 258         unlink_entry(h, e, hash);
 259
 260         if (h->from_pool)
 261                 deallocate_tile(&first_entry_tile, e);
 262         else
 263                 free(e);
 264 }
 265
 266 void hashmap_free(Hashmap*h) {
 267
 268         /* Free the hashmap, but nothing in it */
 269
 270         if (!h)
 271                 return;
 272
 273         hashmap_clear(h);
 274
 275         if (h->from_pool)
 276                 deallocate_tile(&first_hashmap_tile, h);
 277         else
 278                 free(h);
 279 }
 280
 281 void hashmap_free_free(Hashmap *h) {
 282
 283         /* Free the hashmap and all data objects in it, but not the
 284          * keys */
 285
 286         if (!h)
 287                 return;
 288
 289         hashmap_clear_free(h);
 290         hashmap_free(h);
 291 }
 292
 293 void hashmap_clear(Hashmap *h) {
 294         if (!h)
 295                 return;
 296
 297         while (h->iterate_list_head)
 298                 remove_entry(h, h->iterate_list_head);
 299 }
 300
 301 void hashmap_clear_free(Hashmap *h) {
 302         void *p;
 303
 304         if (!h)
 305                 return;
 306
 307         while ((p = hashmap_steal_first(h)))
 308                 free(p);
 309 }
 310
 311 static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *key) {
 312         struct hashmap_entry *e;
 313         assert(h);
 314         assert(hash < NBUCKETS);
 315
 316         for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
 317                 if (h->compare_func(e->key, key) == 0)
 318                         return e;
 319
 320         return NULL;
 321 }
 322
 323 int hashmap_put(Hashmap *h, const void *key, void *value) {
 324         struct hashmap_entry *e;
 325         unsigned hash;
 326
 327         assert(h);
 328
 329         hash = h->hash_func(key) % NBUCKETS;
 330
 331         if ((e = hash_scan(h, hash, key))) {
 332
 333                 if (e->value == value)
 334                         return 0;
 335
 336                 return -EEXIST;
 337         }
 338
 339         if (h->from_pool)
 340                 e = allocate_tile(&first_entry_pool, &first_entry_tile, sizeof(struct hashmap_entry));
 341         else
 342                 e = new(struct hashmap_entry, 1);
 343
 344         if (!e)
 345                 return -ENOMEM;
 346
 347         e->key = key;
 348         e->value = value;
 349
 350         link_entry(h, e, hash);
 351
 352         return 1;
 353 }
 354
 355 int hashmap_replace(Hashmap *h, const void *key, void *value) {
 356         struct hashmap_entry *e;
 357         unsigned hash;
 358
 359         assert(h);
 360
 361         hash = h->hash_func(key) % NBUCKETS;
 362
 363         if ((e = hash_scan(h, hash, key))) {
 364                 e->key = key;
 365                 e->value = value;
 366                 return 0;
 367         }
 368
 369         return hashmap_put(h, key, value);
 370 }
 371
 372 void* hashmap_get(Hashmap *h, const void *key) {
 373         unsigned hash;
 374         struct hashmap_entry *e;
 375
 376         if (!h)
 377                 return NULL;
 378
 379         hash = h->hash_func(key) % NBUCKETS;
 380         e = hash_scan(h, hash, key);
 381         if (!e)
 382                 return NULL;
 383
 384         return e->value;
 385 }
 386
 387 bool hashmap_contains(Hashmap *h, const void *key) {
 388         unsigned hash;
 389
 390         if (!h)
 391                 return false;
 392
 393         hash = h->hash_func(key) % NBUCKETS;
 394
 395         if (!hash_scan(h, hash, key))
 396                 return false;
 397
 398         return true;
 399 }
 400
 401 void* hashmap_remove(Hashmap *h, const void *key) {
 402         struct hashmap_entry *e;
 403         unsigned hash;
 404         void *data;
 405
 406         if (!h)
 407                 return NULL;
 408
 409         hash = h->hash_func(key) % NBUCKETS;
 410
 411         if (!(e = hash_scan(h, hash, key)))
 412                 return NULL;
 413
 414         data = e->value;
 415         remove_entry(h, e);
 416
 417         return data;
 418 }
 419
 420 int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value) {
 421         struct hashmap_entry *e;
 422         unsigned old_hash, new_hash;
 423
 424         if (!h)
 425                 return -ENOENT;
 426
 427         old_hash = h->hash_func(old_key) % NBUCKETS;
 428         if (!(e = hash_scan(h, old_hash, old_key)))
 429                 return -ENOENT;
 430
 431         new_hash = h->hash_func(new_key) % NBUCKETS;
 432         if (hash_scan(h, new_hash, new_key))
 433                 return -EEXIST;
 434
 435         unlink_entry(h, e, old_hash);
 436
 437         e->key = new_key;
 438         e->value = value;
 439
 440         link_entry(h, e, new_hash);
 441
 442         return 0;
 443 }
 444
 445 int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value) {
 446         struct hashmap_entry *e, *k;
 447         unsigned old_hash, new_hash;
 448
 449         if (!h)
 450                 return -ENOENT;
 451
 452         old_hash = h->hash_func(old_key) % NBUCKETS;
 453         if (!(e = hash_scan(h, old_hash, old_key)))
 454                 return -ENOENT;
 455
 456         new_hash = h->hash_func(new_key) % NBUCKETS;
 457
 458         if ((k = hash_scan(h, new_hash, new_key)))
 459                 if (e != k)
 460                         remove_entry(h, k);
 461
 462         unlink_entry(h, e, old_hash);
 463
 464         e->key = new_key;
 465         e->value = value;
 466
 467         link_entry(h, e, new_hash);
 468
 469         return 0;
 470 }
 471
 472 void* hashmap_remove_value(Hashmap *h, const void *key, void *value) {
 473         struct hashmap_entry *e;
 474         unsigned hash;
 475
 476         if (!h)
 477                 return NULL;
 478
 479         hash = h->hash_func(key) % NBUCKETS;
 480
 481         if (!(e = hash_scan(h, hash, key)))
 482                 return NULL;
 483
 484         if (e->value != value)
 485                 return NULL;
 486
 487         remove_entry(h, e);
 488
 489         return value;
 490 }
 491
 492 void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key) {
 493         struct hashmap_entry *e;
 494
 495         assert(i);
 496
 497         if (!h)
 498                 goto at_end;
 499
 500         if (*i == ITERATOR_LAST)
 501                 goto at_end;
 502
 503         if (*i == ITERATOR_FIRST && !h->iterate_list_head)
 504                 goto at_end;
 505
 506         e = *i == ITERATOR_FIRST ? h->iterate_list_head : (struct hashmap_entry*) *i;
 507
 508         if (e->iterate_next)
 509                 *i = (Iterator) e->iterate_next;
 510         else
 511                 *i = ITERATOR_LAST;
 512
 513         if (key)
 514                 *key = e->key;
 515
 516         return e->value;
 517
 518 at_end:
 519         *i = ITERATOR_LAST;
 520
 521         if (key)
 522                 *key = NULL;
 523
 524         return NULL;
 525 }
 526
 527 void *hashmap_iterate_backwards(Hashmap *h, Iterator *i, const void **key) {
 528         struct hashmap_entry *e;
 529
 530         assert(i);
 531
 532         if (!h)
 533                 goto at_beginning;
 534
 535         if (*i == ITERATOR_FIRST)
 536                 goto at_beginning;
 537
 538         if (*i == ITERATOR_LAST && !h->iterate_list_tail)
 539                 goto at_beginning;
 540
 541         e = *i == ITERATOR_LAST ? h->iterate_list_tail : (struct hashmap_entry*) *i;
 542
 543         if (e->iterate_previous)
 544                 *i = (Iterator) e->iterate_previous;
 545         else
 546                 *i = ITERATOR_FIRST;
 547
 548         if (key)
 549                 *key = e->key;
 550
 551         return e->value;
 552
 553 at_beginning:
 554         *i = ITERATOR_FIRST;
 555
 556         if (key)
 557                 *key = NULL;
 558
 559         return NULL;
 560 }
 561
 562 void *hashmap_iterate_skip(Hashmap *h, const void *key, Iterator *i) {
 563         unsigned hash;
 564         struct hashmap_entry *e;
 565
 566         if (!h)
 567                 return NULL;
 568
 569         hash = h->hash_func(key) % NBUCKETS;
 570
 571         if (!(e = hash_scan(h, hash, key)))
 572                 return NULL;
 573
 574         *i = (Iterator) e;
 575
 576         return e->value;
 577 }
 578
 579 void* hashmap_first(Hashmap *h) {
 580
 581         if (!h)
 582                 return NULL;
 583
 584         if (!h->iterate_list_head)
 585                 return NULL;
 586
 587         return h->iterate_list_head->value;
 588 }
 589
 590 void* hashmap_first_key(Hashmap *h) {
 591
 592         if (!h)
 593                 return NULL;
 594
 595         if (!h->iterate_list_head)
 596                 return NULL;
 597
 598         return (void*) h->iterate_list_head->key;
 599 }
 600
 601 void* hashmap_last(Hashmap *h) {
 602
 603         if (!h)
 604                 return NULL;
 605
 606         if (!h->iterate_list_tail)
 607                 return NULL;
 608
 609         return h->iterate_list_tail->value;
 610 }
 611
 612 void* hashmap_steal_first(Hashmap *h) {
 613         void *data;
 614
 615         if (!h)
 616                 return NULL;
 617
 618         if (!h->iterate_list_head)
 619                 return NULL;
 620
 621         data = h->iterate_list_head->value;
 622         remove_entry(h, h->iterate_list_head);
 623
 624         return data;
 625 }
 626
 627 void* hashmap_steal_first_key(Hashmap *h) {
 628         void *key;
 629
 630         if (!h)
 631                 return NULL;
 632
 633         if (!h->iterate_list_head)
 634                 return NULL;
 635
 636         key = (void*) h->iterate_list_head->key;
 637         remove_entry(h, h->iterate_list_head);
 638
 639         return key;
 640 }
 641
 642 unsigned hashmap_size(Hashmap *h) {
 643
 644         if (!h)
 645                 return 0;
 646
 647         return h->n_entries;
 648 }
 649
 650 bool hashmap_isempty(Hashmap *h) {
 651
 652         if (!h)
 653                 return true;
 654
 655         return h->n_entries == 0;
 656 }
 657
 658 int hashmap_merge(Hashmap *h, Hashmap *other) {
 659         struct hashmap_entry *e;
 660
 661         assert(h);
 662
 663         if (!other)
 664                 return 0;
 665
 666         for (e = other->iterate_list_head; e; e = e->iterate_next) {
 667                 int r;
 668
 669                 if ((r = hashmap_put(h, e->key, e->value)) < 0)
 670                         if (r != -EEXIST)
 671                                 return r;
 672         }
 673
 674         return 0;
 675 }
 676
 677 void hashmap_move(Hashmap *h, Hashmap *other) {
 678         struct hashmap_entry *e, *n;
 679
 680         assert(h);
 681
 682         /* The same as hashmap_merge(), but every new item from other
 683          * is moved to h. This function is guaranteed to succeed. */
 684
 685         if (!other)
 686                 return;
 687
 688         for (e = other->iterate_list_head; e; e = n) {
 689                 unsigned h_hash, other_hash;
 690
 691                 n = e->iterate_next;
 692
 693                 h_hash = h->hash_func(e->key) % NBUCKETS;
 694
 695                 if (hash_scan(h, h_hash, e->key))
 696                         continue;
 697
 698                 other_hash = other->hash_func(e->key) % NBUCKETS;
 699
 700                 unlink_entry(other, e, other_hash);
 701                 link_entry(h, e, h_hash);
 702         }
 703 }
 704
 705 int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) {
 706         unsigned h_hash, other_hash;
 707         struct hashmap_entry *e;
 708
 709         if (!other)
 710                 return 0;
 711
 712         assert(h);
 713
 714         h_hash = h->hash_func(key) % NBUCKETS;
 715         if (hash_scan(h, h_hash, key))
 716                 return -EEXIST;
 717
 718         other_hash = other->hash_func(key) % NBUCKETS;
 719         if (!(e = hash_scan(other, other_hash, key)))
 720                 return -ENOENT;
 721
 722         unlink_entry(other, e, other_hash);
 723         link_entry(h, e, h_hash);
 724
 725         return 0;
 726 }
 727
 728 Hashmap *hashmap_copy(Hashmap *h) {
 729         Hashmap *copy;
 730
 731         assert(h);
 732
 733         if (!(copy = hashmap_new(h->hash_func, h->compare_func)))
 734                 return NULL;
 735
 736         if (hashmap_merge(copy, h) < 0) {
 737                 hashmap_free(copy);
 738                 return NULL;
 739         }
 740
 741         return copy;
 742 }
 743
 744 char **hashmap_get_strv(Hashmap *h) {
 745         char **sv;
 746         Iterator it;
 747         char *item;
 748         int n;
 749
 750         sv = new(char*, h->n_entries+1);
 751         if (!sv)
 752                 return NULL;
 753
 754         n = 0;
 755         HASHMAP_FOREACH(item, h, it)
 756                 sv[n++] = item;
 757         sv[n] = NULL;
 758
 759         return sv;
 760 }
 761
 762 void *hashmap_next(Hashmap *h, const void *key) {
 763         unsigned hash;
 764         struct hashmap_entry *e;
 765
 766         assert(h);
 767         assert(key);
 768
 769         if (!h)
 770                 return NULL;
 771
 772         hash = h->hash_func(key) % NBUCKETS;
 773         e = hash_scan(h, hash, key);
 774         if (!e)
 775                 return NULL;
 776
 777         e = e->iterate_next;
 778         if (!e)
 779                 return NULL;
 780
 781         return e->value;
 782 }