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         e = hash_scan(h, hash, key);
 332         if (e) {
 333
 334                 if (e->value == value)
 335                         return 0;
 336
 337                 return -EEXIST;
 338         }
 339
 340         if (h->from_pool)
 341                 e = allocate_tile(&first_entry_pool, &first_entry_tile, sizeof(struct hashmap_entry));
 342         else
 343                 e = new(struct hashmap_entry, 1);
 344
 345         if (!e)
 346                 return -ENOMEM;
 347
 348         e->key = key;
 349         e->value = value;
 350
 351         link_entry(h, e, hash);
 352
 353         return 1;
 354 }
 355
 356 int hashmap_replace(Hashmap *h, const void *key, void *value) {
 357         struct hashmap_entry *e;
 358         unsigned hash;
 359
 360         assert(h);
 361
 362         hash = h->hash_func(key) % NBUCKETS;
 363         e = hash_scan(h, hash, key);
 364         if (e) {
 365                 e->key = key;
 366                 e->value = value;
 367                 return 0;
 368         }
 369
 370         return hashmap_put(h, key, value);
 371 }
 372
 373 int hashmap_update(Hashmap *h, const void *key, void *value) {
 374         struct hashmap_entry *e;
 375         unsigned hash;
 376
 377         assert(h);
 378
 379         hash = h->hash_func(key) % NBUCKETS;
 380         e = hash_scan(h, hash, key);
 381         if (!e)
 382                 return -ENOENT;
 383
 384         e->value = value;
 385         return 0;
 386 }
 387
 388 void* hashmap_get(Hashmap *h, const void *key) {
 389         unsigned hash;
 390         struct hashmap_entry *e;
 391
 392         if (!h)
 393                 return NULL;
 394
 395         hash = h->hash_func(key) % NBUCKETS;
 396         e = hash_scan(h, hash, key);
 397         if (!e)
 398                 return NULL;
 399
 400         return e->value;
 401 }
 402
 403 void* hashmap_get2(Hashmap *h, const void *key, void **key2) {
 404         unsigned hash;
 405         struct hashmap_entry *e;
 406
 407         if (!h)
 408                 return NULL;
 409
 410         hash = h->hash_func(key) % NBUCKETS;
 411         e = hash_scan(h, hash, key);
 412         if (!e)
 413                 return NULL;
 414
 415         if (key2)
 416                 *key2 = (void*) e->key;
 417
 418         return e->value;
 419 }
 420
 421 bool hashmap_contains(Hashmap *h, const void *key) {
 422         unsigned hash;
 423
 424         if (!h)
 425                 return false;
 426
 427         hash = h->hash_func(key) % NBUCKETS;
 428
 429         if (!hash_scan(h, hash, key))
 430                 return false;
 431
 432         return true;
 433 }
 434
 435 void* hashmap_remove(Hashmap *h, const void *key) {
 436         struct hashmap_entry *e;
 437         unsigned hash;
 438         void *data;
 439
 440         if (!h)
 441                 return NULL;
 442
 443         hash = h->hash_func(key) % NBUCKETS;
 444
 445         if (!(e = hash_scan(h, hash, key)))
 446                 return NULL;
 447
 448         data = e->value;
 449         remove_entry(h, e);
 450
 451         return data;
 452 }
 453
 454 int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value) {
 455         struct hashmap_entry *e;
 456         unsigned old_hash, new_hash;
 457
 458         if (!h)
 459                 return -ENOENT;
 460
 461         old_hash = h->hash_func(old_key) % NBUCKETS;
 462         if (!(e = hash_scan(h, old_hash, old_key)))
 463                 return -ENOENT;
 464
 465         new_hash = h->hash_func(new_key) % NBUCKETS;
 466         if (hash_scan(h, new_hash, new_key))
 467                 return -EEXIST;
 468
 469         unlink_entry(h, e, old_hash);
 470
 471         e->key = new_key;
 472         e->value = value;
 473
 474         link_entry(h, e, new_hash);
 475
 476         return 0;
 477 }
 478
 479 int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value) {
 480         struct hashmap_entry *e, *k;
 481         unsigned old_hash, new_hash;
 482
 483         if (!h)
 484                 return -ENOENT;
 485
 486         old_hash = h->hash_func(old_key) % NBUCKETS;
 487         if (!(e = hash_scan(h, old_hash, old_key)))
 488                 return -ENOENT;
 489
 490         new_hash = h->hash_func(new_key) % NBUCKETS;
 491
 492         if ((k = hash_scan(h, new_hash, new_key)))
 493                 if (e != k)
 494                         remove_entry(h, k);
 495
 496         unlink_entry(h, e, old_hash);
 497
 498         e->key = new_key;
 499         e->value = value;
 500
 501         link_entry(h, e, new_hash);
 502
 503         return 0;
 504 }
 505
 506 void* hashmap_remove_value(Hashmap *h, const void *key, void *value) {
 507         struct hashmap_entry *e;
 508         unsigned hash;
 509
 510         if (!h)
 511                 return NULL;
 512
 513         hash = h->hash_func(key) % NBUCKETS;
 514
 515         if (!(e = hash_scan(h, hash, key)))
 516                 return NULL;
 517
 518         if (e->value != value)
 519                 return NULL;
 520
 521         remove_entry(h, e);
 522
 523         return value;
 524 }
 525
 526 void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key) {
 527         struct hashmap_entry *e;
 528
 529         assert(i);
 530
 531         if (!h)
 532                 goto at_end;
 533
 534         if (*i == ITERATOR_LAST)
 535                 goto at_end;
 536
 537         if (*i == ITERATOR_FIRST && !h->iterate_list_head)
 538                 goto at_end;
 539
 540         e = *i == ITERATOR_FIRST ? h->iterate_list_head : (struct hashmap_entry*) *i;
 541
 542         if (e->iterate_next)
 543                 *i = (Iterator) e->iterate_next;
 544         else
 545                 *i = ITERATOR_LAST;
 546
 547         if (key)
 548                 *key = e->key;
 549
 550         return e->value;
 551
 552 at_end:
 553         *i = ITERATOR_LAST;
 554
 555         if (key)
 556                 *key = NULL;
 557
 558         return NULL;
 559 }
 560
 561 void *hashmap_iterate_backwards(Hashmap *h, Iterator *i, const void **key) {
 562         struct hashmap_entry *e;
 563
 564         assert(i);
 565
 566         if (!h)
 567                 goto at_beginning;
 568
 569         if (*i == ITERATOR_FIRST)
 570                 goto at_beginning;
 571
 572         if (*i == ITERATOR_LAST && !h->iterate_list_tail)
 573                 goto at_beginning;
 574
 575         e = *i == ITERATOR_LAST ? h->iterate_list_tail : (struct hashmap_entry*) *i;
 576
 577         if (e->iterate_previous)
 578                 *i = (Iterator) e->iterate_previous;
 579         else
 580                 *i = ITERATOR_FIRST;
 581
 582         if (key)
 583                 *key = e->key;
 584
 585         return e->value;
 586
 587 at_beginning:
 588         *i = ITERATOR_FIRST;
 589
 590         if (key)
 591                 *key = NULL;
 592
 593         return NULL;
 594 }
 595
 596 void *hashmap_iterate_skip(Hashmap *h, const void *key, Iterator *i) {
 597         unsigned hash;
 598         struct hashmap_entry *e;
 599
 600         if (!h)
 601                 return NULL;
 602
 603         hash = h->hash_func(key) % NBUCKETS;
 604
 605         if (!(e = hash_scan(h, hash, key)))
 606                 return NULL;
 607
 608         *i = (Iterator) e;
 609
 610         return e->value;
 611 }
 612
 613 void* hashmap_first(Hashmap *h) {
 614
 615         if (!h)
 616                 return NULL;
 617
 618         if (!h->iterate_list_head)
 619                 return NULL;
 620
 621         return h->iterate_list_head->value;
 622 }
 623
 624 void* hashmap_first_key(Hashmap *h) {
 625
 626         if (!h)
 627                 return NULL;
 628
 629         if (!h->iterate_list_head)
 630                 return NULL;
 631
 632         return (void*) h->iterate_list_head->key;
 633 }
 634
 635 void* hashmap_last(Hashmap *h) {
 636
 637         if (!h)
 638                 return NULL;
 639
 640         if (!h->iterate_list_tail)
 641                 return NULL;
 642
 643         return h->iterate_list_tail->value;
 644 }
 645
 646 void* hashmap_steal_first(Hashmap *h) {
 647         void *data;
 648
 649         if (!h)
 650                 return NULL;
 651
 652         if (!h->iterate_list_head)
 653                 return NULL;
 654
 655         data = h->iterate_list_head->value;
 656         remove_entry(h, h->iterate_list_head);
 657
 658         return data;
 659 }
 660
 661 void* hashmap_steal_first_key(Hashmap *h) {
 662         void *key;
 663
 664         if (!h)
 665                 return NULL;
 666
 667         if (!h->iterate_list_head)
 668                 return NULL;
 669
 670         key = (void*) h->iterate_list_head->key;
 671         remove_entry(h, h->iterate_list_head);
 672
 673         return key;
 674 }
 675
 676 unsigned hashmap_size(Hashmap *h) {
 677
 678         if (!h)
 679                 return 0;
 680
 681         return h->n_entries;
 682 }
 683
 684 bool hashmap_isempty(Hashmap *h) {
 685
 686         if (!h)
 687                 return true;
 688
 689         return h->n_entries == 0;
 690 }
 691
 692 int hashmap_merge(Hashmap *h, Hashmap *other) {
 693         struct hashmap_entry *e;
 694
 695         assert(h);
 696
 697         if (!other)
 698                 return 0;
 699
 700         for (e = other->iterate_list_head; e; e = e->iterate_next) {
 701                 int r;
 702
 703                 if ((r = hashmap_put(h, e->key, e->value)) < 0)
 704                         if (r != -EEXIST)
 705                                 return r;
 706         }
 707
 708         return 0;
 709 }
 710
 711 void hashmap_move(Hashmap *h, Hashmap *other) {
 712         struct hashmap_entry *e, *n;
 713
 714         assert(h);
 715
 716         /* The same as hashmap_merge(), but every new item from other
 717          * is moved to h. This function is guaranteed to succeed. */
 718
 719         if (!other)
 720                 return;
 721
 722         for (e = other->iterate_list_head; e; e = n) {
 723                 unsigned h_hash, other_hash;
 724
 725                 n = e->iterate_next;
 726
 727                 h_hash = h->hash_func(e->key) % NBUCKETS;
 728
 729                 if (hash_scan(h, h_hash, e->key))
 730                         continue;
 731
 732                 other_hash = other->hash_func(e->key) % NBUCKETS;
 733
 734                 unlink_entry(other, e, other_hash);
 735                 link_entry(h, e, h_hash);
 736         }
 737 }
 738
 739 int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) {
 740         unsigned h_hash, other_hash;
 741         struct hashmap_entry *e;
 742
 743         if (!other)
 744                 return 0;
 745
 746         assert(h);
 747
 748         h_hash = h->hash_func(key) % NBUCKETS;
 749         if (hash_scan(h, h_hash, key))
 750                 return -EEXIST;
 751
 752         other_hash = other->hash_func(key) % NBUCKETS;
 753         if (!(e = hash_scan(other, other_hash, key)))
 754                 return -ENOENT;
 755
 756         unlink_entry(other, e, other_hash);
 757         link_entry(h, e, h_hash);
 758
 759         return 0;
 760 }
 761
 762 Hashmap *hashmap_copy(Hashmap *h) {
 763         Hashmap *copy;
 764
 765         assert(h);
 766
 767         if (!(copy = hashmap_new(h->hash_func, h->compare_func)))
 768                 return NULL;
 769
 770         if (hashmap_merge(copy, h) < 0) {
 771                 hashmap_free(copy);
 772                 return NULL;
 773         }
 774
 775         return copy;
 776 }
 777
 778 char **hashmap_get_strv(Hashmap *h) {
 779         char **sv;
 780         Iterator it;
 781         char *item;
 782         int n;
 783
 784         sv = new(char*, h->n_entries+1);
 785         if (!sv)
 786                 return NULL;
 787
 788         n = 0;
 789         HASHMAP_FOREACH(item, h, it)
 790                 sv[n++] = item;
 791         sv[n] = NULL;
 792
 793         return sv;
 794 }
 795
 796 void *hashmap_next(Hashmap *h, const void *key) {
 797         unsigned hash;
 798         struct hashmap_entry *e;
 799
 800         assert(h);
 801         assert(key);
 802
 803         if (!h)
 804                 return NULL;
 805
 806         hash = h->hash_func(key) % NBUCKETS;
 807         e = hash_scan(h, hash, key);
 808         if (!e)
 809                 return NULL;
 810
 811         e = e->iterate_next;
 812         if (!e)
 813                 return NULL;
 814
 815         return e->value;
 816 }