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 #ifdef VALGRIND
 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 unsigned uint64_hash_func(const void *p) {
 151         uint64_t u;
 152
 153         assert_cc(sizeof(uint64_t) == 2*sizeof(unsigned));
 154
 155         u = *(const uint64_t*) p;
 156
 157         return (unsigned) ((u >> 32) ^ u);
 158 }
 159
 160 int uint64_compare_func(const void *_a, const void *_b) {
 161         uint64_t a, b;
 162
 163         a = *(const uint64_t*) _a;
 164         b = *(const uint64_t*) _b;
 165
 166         return a < b ? -1 : (a > b ? 1 : 0);
 167 }
 168
 169 Hashmap *hashmap_new(hash_func_t hash_func, compare_func_t compare_func) {
 170         bool b;
 171         Hashmap *h;
 172         size_t size;
 173
 174         b = is_main_thread();
 175
 176         size = ALIGN(sizeof(Hashmap)) + NBUCKETS * sizeof(struct hashmap_entry*);
 177
 178         if (b) {
 179                 h = allocate_tile(&first_hashmap_pool, &first_hashmap_tile, size);
 180                 if (!h)
 181                         return NULL;
 182
 183                 memset(h, 0, size);
 184         } else {
 185                 h = malloc0(size);
 186
 187                 if (!h)
 188                         return NULL;
 189         }
 190
 191         h->hash_func = hash_func ? hash_func : trivial_hash_func;
 192         h->compare_func = compare_func ? compare_func : trivial_compare_func;
 193
 194         h->n_entries = 0;
 195         h->iterate_list_head = h->iterate_list_tail = NULL;
 196
 197         h->from_pool = b;
 198
 199         return h;
 200 }
 201
 202 int hashmap_ensure_allocated(Hashmap **h, hash_func_t hash_func, compare_func_t compare_func) {
 203         assert(h);
 204
 205         if (*h)
 206                 return 0;
 207
 208         if (!(*h = hashmap_new(hash_func, compare_func)))
 209                 return -ENOMEM;
 210
 211         return 0;
 212 }
 213
 214 static void link_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) {
 215         assert(h);
 216         assert(e);
 217
 218         /* Insert into hash table */
 219         e->bucket_next = BY_HASH(h)[hash];
 220         e->bucket_previous = NULL;
 221         if (BY_HASH(h)[hash])
 222                 BY_HASH(h)[hash]->bucket_previous = e;
 223         BY_HASH(h)[hash] = e;
 224
 225         /* Insert into iteration list */
 226         e->iterate_previous = h->iterate_list_tail;
 227         e->iterate_next = NULL;
 228         if (h->iterate_list_tail) {
 229                 assert(h->iterate_list_head);
 230                 h->iterate_list_tail->iterate_next = e;
 231         } else {
 232                 assert(!h->iterate_list_head);
 233                 h->iterate_list_head = e;
 234         }
 235         h->iterate_list_tail = e;
 236
 237         h->n_entries++;
 238         assert(h->n_entries >= 1);
 239 }
 240
 241 static void unlink_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) {
 242         assert(h);
 243         assert(e);
 244
 245         /* Remove from iteration list */
 246         if (e->iterate_next)
 247                 e->iterate_next->iterate_previous = e->iterate_previous;
 248         else
 249                 h->iterate_list_tail = e->iterate_previous;
 250
 251         if (e->iterate_previous)
 252                 e->iterate_previous->iterate_next = e->iterate_next;
 253         else
 254                 h->iterate_list_head = e->iterate_next;
 255
 256         /* Remove from hash table bucket list */
 257         if (e->bucket_next)
 258                 e->bucket_next->bucket_previous = e->bucket_previous;
 259
 260         if (e->bucket_previous)
 261                 e->bucket_previous->bucket_next = e->bucket_next;
 262         else
 263                 BY_HASH(h)[hash] = e->bucket_next;
 264
 265         assert(h->n_entries >= 1);
 266         h->n_entries--;
 267 }
 268
 269 static void remove_entry(Hashmap *h, struct hashmap_entry *e) {
 270         unsigned hash;
 271
 272         assert(h);
 273         assert(e);
 274
 275         hash = h->hash_func(e->key) % NBUCKETS;
 276
 277         unlink_entry(h, e, hash);
 278
 279         if (h->from_pool)
 280                 deallocate_tile(&first_entry_tile, e);
 281         else
 282                 free(e);
 283 }
 284
 285 void hashmap_free(Hashmap*h) {
 286
 287         /* Free the hashmap, but nothing in it */
 288
 289         if (!h)
 290                 return;
 291
 292         hashmap_clear(h);
 293
 294         if (h->from_pool)
 295                 deallocate_tile(&first_hashmap_tile, h);
 296         else
 297                 free(h);
 298 }
 299
 300 void hashmap_free_free(Hashmap *h) {
 301
 302         /* Free the hashmap and all data objects in it, but not the
 303          * keys */
 304
 305         if (!h)
 306                 return;
 307
 308         hashmap_clear_free(h);
 309         hashmap_free(h);
 310 }
 311
 312 void hashmap_free_free_free(Hashmap *h) {
 313
 314         /* Free the hashmap and all data and key objects in it */
 315
 316         if (!h)
 317                 return;
 318
 319         hashmap_clear_free_free(h);
 320         hashmap_free(h);
 321 }
 322
 323 void hashmap_clear(Hashmap *h) {
 324         if (!h)
 325                 return;
 326
 327         while (h->iterate_list_head)
 328                 remove_entry(h, h->iterate_list_head);
 329 }
 330
 331 void hashmap_clear_free(Hashmap *h) {
 332         void *p;
 333
 334         if (!h)
 335                 return;
 336
 337         while ((p = hashmap_steal_first(h)))
 338                 free(p);
 339 }
 340
 341 void hashmap_clear_free_free(Hashmap *h) {
 342         if (!h)
 343                 return;
 344
 345         while (h->iterate_list_head) {
 346                 void *a, *b;
 347
 348                 a = h->iterate_list_head->value;
 349                 b = (void*) h->iterate_list_head->key;
 350                 remove_entry(h, h->iterate_list_head);
 351                 free(a);
 352                 free(b);
 353         }
 354 }
 355
 356
 357 static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *key) {
 358         struct hashmap_entry *e;
 359         assert(h);
 360         assert(hash < NBUCKETS);
 361
 362         for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
 363                 if (h->compare_func(e->key, key) == 0)
 364                         return e;
 365
 366         return NULL;
 367 }
 368
 369 int hashmap_put(Hashmap *h, const void *key, void *value) {
 370         struct hashmap_entry *e;
 371         unsigned hash;
 372
 373         assert(h);
 374
 375         hash = h->hash_func(key) % NBUCKETS;
 376
 377         e = hash_scan(h, hash, key);
 378         if (e) {
 379
 380                 if (e->value == value)
 381                         return 0;
 382
 383                 return -EEXIST;
 384         }
 385
 386         if (h->from_pool)
 387                 e = allocate_tile(&first_entry_pool, &first_entry_tile, sizeof(struct hashmap_entry));
 388         else
 389                 e = new(struct hashmap_entry, 1);
 390
 391         if (!e)
 392                 return -ENOMEM;
 393
 394         e->key = key;
 395         e->value = value;
 396
 397         link_entry(h, e, hash);
 398
 399         return 1;
 400 }
 401
 402 int hashmap_replace(Hashmap *h, const void *key, void *value) {
 403         struct hashmap_entry *e;
 404         unsigned hash;
 405
 406         assert(h);
 407
 408         hash = h->hash_func(key) % NBUCKETS;
 409         e = hash_scan(h, hash, key);
 410         if (e) {
 411                 e->key = key;
 412                 e->value = value;
 413                 return 0;
 414         }
 415
 416         return hashmap_put(h, key, value);
 417 }
 418
 419 int hashmap_update(Hashmap *h, const void *key, void *value) {
 420         struct hashmap_entry *e;
 421         unsigned hash;
 422
 423         assert(h);
 424
 425         hash = h->hash_func(key) % NBUCKETS;
 426         e = hash_scan(h, hash, key);
 427         if (!e)
 428                 return -ENOENT;
 429
 430         e->value = value;
 431         return 0;
 432 }
 433
 434 void* hashmap_get(Hashmap *h, const void *key) {
 435         unsigned hash;
 436         struct hashmap_entry *e;
 437
 438         if (!h)
 439                 return NULL;
 440
 441         hash = h->hash_func(key) % NBUCKETS;
 442         e = hash_scan(h, hash, key);
 443         if (!e)
 444                 return NULL;
 445
 446         return e->value;
 447 }
 448
 449 void* hashmap_get2(Hashmap *h, const void *key, void **key2) {
 450         unsigned hash;
 451         struct hashmap_entry *e;
 452
 453         if (!h)
 454                 return NULL;
 455
 456         hash = h->hash_func(key) % NBUCKETS;
 457         e = hash_scan(h, hash, key);
 458         if (!e)
 459                 return NULL;
 460
 461         if (key2)
 462                 *key2 = (void*) e->key;
 463
 464         return e->value;
 465 }
 466
 467 bool hashmap_contains(Hashmap *h, const void *key) {
 468         unsigned hash;
 469
 470         if (!h)
 471                 return false;
 472
 473         hash = h->hash_func(key) % NBUCKETS;
 474
 475         if (!hash_scan(h, hash, key))
 476                 return false;
 477
 478         return true;
 479 }
 480
 481 void* hashmap_remove(Hashmap *h, const void *key) {
 482         struct hashmap_entry *e;
 483         unsigned hash;
 484         void *data;
 485
 486         if (!h)
 487                 return NULL;
 488
 489         hash = h->hash_func(key) % NBUCKETS;
 490
 491         if (!(e = hash_scan(h, hash, key)))
 492                 return NULL;
 493
 494         data = e->value;
 495         remove_entry(h, e);
 496
 497         return data;
 498 }
 499
 500 int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value) {
 501         struct hashmap_entry *e;
 502         unsigned old_hash, new_hash;
 503
 504         if (!h)
 505                 return -ENOENT;
 506
 507         old_hash = h->hash_func(old_key) % NBUCKETS;
 508         if (!(e = hash_scan(h, old_hash, old_key)))
 509                 return -ENOENT;
 510
 511         new_hash = h->hash_func(new_key) % NBUCKETS;
 512         if (hash_scan(h, new_hash, new_key))
 513                 return -EEXIST;
 514
 515         unlink_entry(h, e, old_hash);
 516
 517         e->key = new_key;
 518         e->value = value;
 519
 520         link_entry(h, e, new_hash);
 521
 522         return 0;
 523 }
 524
 525 int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value) {
 526         struct hashmap_entry *e, *k;
 527         unsigned old_hash, new_hash;
 528
 529         if (!h)
 530                 return -ENOENT;
 531
 532         old_hash = h->hash_func(old_key) % NBUCKETS;
 533         if (!(e = hash_scan(h, old_hash, old_key)))
 534                 return -ENOENT;
 535
 536         new_hash = h->hash_func(new_key) % NBUCKETS;
 537
 538         if ((k = hash_scan(h, new_hash, new_key)))
 539                 if (e != k)
 540                         remove_entry(h, k);
 541
 542         unlink_entry(h, e, old_hash);
 543
 544         e->key = new_key;
 545         e->value = value;
 546
 547         link_entry(h, e, new_hash);
 548
 549         return 0;
 550 }
 551
 552 void* hashmap_remove_value(Hashmap *h, const void *key, void *value) {
 553         struct hashmap_entry *e;
 554         unsigned hash;
 555
 556         if (!h)
 557                 return NULL;
 558
 559         hash = h->hash_func(key) % NBUCKETS;
 560
 561         if (!(e = hash_scan(h, hash, key)))
 562                 return NULL;
 563
 564         if (e->value != value)
 565                 return NULL;
 566
 567         remove_entry(h, e);
 568
 569         return value;
 570 }
 571
 572 void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key) {
 573         struct hashmap_entry *e;
 574
 575         assert(i);
 576
 577         if (!h)
 578                 goto at_end;
 579
 580         if (*i == ITERATOR_LAST)
 581                 goto at_end;
 582
 583         if (*i == ITERATOR_FIRST && !h->iterate_list_head)
 584                 goto at_end;
 585
 586         e = *i == ITERATOR_FIRST ? h->iterate_list_head : (struct hashmap_entry*) *i;
 587
 588         if (e->iterate_next)
 589                 *i = (Iterator) e->iterate_next;
 590         else
 591                 *i = ITERATOR_LAST;
 592
 593         if (key)
 594                 *key = e->key;
 595
 596         return e->value;
 597
 598 at_end:
 599         *i = ITERATOR_LAST;
 600
 601         if (key)
 602                 *key = NULL;
 603
 604         return NULL;
 605 }
 606
 607 void *hashmap_iterate_backwards(Hashmap *h, Iterator *i, const void **key) {
 608         struct hashmap_entry *e;
 609
 610         assert(i);
 611
 612         if (!h)
 613                 goto at_beginning;
 614
 615         if (*i == ITERATOR_FIRST)
 616                 goto at_beginning;
 617
 618         if (*i == ITERATOR_LAST && !h->iterate_list_tail)
 619                 goto at_beginning;
 620
 621         e = *i == ITERATOR_LAST ? h->iterate_list_tail : (struct hashmap_entry*) *i;
 622
 623         if (e->iterate_previous)
 624                 *i = (Iterator) e->iterate_previous;
 625         else
 626                 *i = ITERATOR_FIRST;
 627
 628         if (key)
 629                 *key = e->key;
 630
 631         return e->value;
 632
 633 at_beginning:
 634         *i = ITERATOR_FIRST;
 635
 636         if (key)
 637                 *key = NULL;
 638
 639         return NULL;
 640 }
 641
 642 void *hashmap_iterate_skip(Hashmap *h, const void *key, Iterator *i) {
 643         unsigned hash;
 644         struct hashmap_entry *e;
 645
 646         if (!h)
 647                 return NULL;
 648
 649         hash = h->hash_func(key) % NBUCKETS;
 650
 651         if (!(e = hash_scan(h, hash, key)))
 652                 return NULL;
 653
 654         *i = (Iterator) e;
 655
 656         return e->value;
 657 }
 658
 659 void* hashmap_first(Hashmap *h) {
 660
 661         if (!h)
 662                 return NULL;
 663
 664         if (!h->iterate_list_head)
 665                 return NULL;
 666
 667         return h->iterate_list_head->value;
 668 }
 669
 670 void* hashmap_first_key(Hashmap *h) {
 671
 672         if (!h)
 673                 return NULL;
 674
 675         if (!h->iterate_list_head)
 676                 return NULL;
 677
 678         return (void*) h->iterate_list_head->key;
 679 }
 680
 681 void* hashmap_last(Hashmap *h) {
 682
 683         if (!h)
 684                 return NULL;
 685
 686         if (!h->iterate_list_tail)
 687                 return NULL;
 688
 689         return h->iterate_list_tail->value;
 690 }
 691
 692 void* hashmap_steal_first(Hashmap *h) {
 693         void *data;
 694
 695         if (!h)
 696                 return NULL;
 697
 698         if (!h->iterate_list_head)
 699                 return NULL;
 700
 701         data = h->iterate_list_head->value;
 702         remove_entry(h, h->iterate_list_head);
 703
 704         return data;
 705 }
 706
 707 void* hashmap_steal_first_key(Hashmap *h) {
 708         void *key;
 709
 710         if (!h)
 711                 return NULL;
 712
 713         if (!h->iterate_list_head)
 714                 return NULL;
 715
 716         key = (void*) h->iterate_list_head->key;
 717         remove_entry(h, h->iterate_list_head);
 718
 719         return key;
 720 }
 721
 722 unsigned hashmap_size(Hashmap *h) {
 723
 724         if (!h)
 725                 return 0;
 726
 727         return h->n_entries;
 728 }
 729
 730 bool hashmap_isempty(Hashmap *h) {
 731
 732         if (!h)
 733                 return true;
 734
 735         return h->n_entries == 0;
 736 }
 737
 738 int hashmap_merge(Hashmap *h, Hashmap *other) {
 739         struct hashmap_entry *e;
 740
 741         assert(h);
 742
 743         if (!other)
 744                 return 0;
 745
 746         for (e = other->iterate_list_head; e; e = e->iterate_next) {
 747                 int r;
 748
 749                 if ((r = hashmap_put(h, e->key, e->value)) < 0)
 750                         if (r != -EEXIST)
 751                                 return r;
 752         }
 753
 754         return 0;
 755 }
 756
 757 void hashmap_move(Hashmap *h, Hashmap *other) {
 758         struct hashmap_entry *e, *n;
 759
 760         assert(h);
 761
 762         /* The same as hashmap_merge(), but every new item from other
 763          * is moved to h. This function is guaranteed to succeed. */
 764
 765         if (!other)
 766                 return;
 767
 768         for (e = other->iterate_list_head; e; e = n) {
 769                 unsigned h_hash, other_hash;
 770
 771                 n = e->iterate_next;
 772
 773                 h_hash = h->hash_func(e->key) % NBUCKETS;
 774
 775                 if (hash_scan(h, h_hash, e->key))
 776                         continue;
 777
 778                 other_hash = other->hash_func(e->key) % NBUCKETS;
 779
 780                 unlink_entry(other, e, other_hash);
 781                 link_entry(h, e, h_hash);
 782         }
 783 }
 784
 785 int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) {
 786         unsigned h_hash, other_hash;
 787         struct hashmap_entry *e;
 788
 789         if (!other)
 790                 return 0;
 791
 792         assert(h);
 793
 794         h_hash = h->hash_func(key) % NBUCKETS;
 795         if (hash_scan(h, h_hash, key))
 796                 return -EEXIST;
 797
 798         other_hash = other->hash_func(key) % NBUCKETS;
 799         if (!(e = hash_scan(other, other_hash, key)))
 800                 return -ENOENT;
 801
 802         unlink_entry(other, e, other_hash);
 803         link_entry(h, e, h_hash);
 804
 805         return 0;
 806 }
 807
 808 Hashmap *hashmap_copy(Hashmap *h) {
 809         Hashmap *copy;
 810
 811         assert(h);
 812
 813         if (!(copy = hashmap_new(h->hash_func, h->compare_func)))
 814                 return NULL;
 815
 816         if (hashmap_merge(copy, h) < 0) {
 817                 hashmap_free(copy);
 818                 return NULL;
 819         }
 820
 821         return copy;
 822 }
 823
 824 char **hashmap_get_strv(Hashmap *h) {
 825         char **sv;
 826         Iterator it;
 827         char *item;
 828         int n;
 829
 830         sv = new(char*, h->n_entries+1);
 831         if (!sv)
 832                 return NULL;
 833
 834         n = 0;
 835         HASHMAP_FOREACH(item, h, it)
 836                 sv[n++] = item;
 837         sv[n] = NULL;
 838
 839         return sv;
 840 }
 841
 842 void *hashmap_next(Hashmap *h, const void *key) {
 843         unsigned hash;
 844         struct hashmap_entry *e;
 845
 846         assert(h);
 847         assert(key);
 848
 849         if (!h)
 850                 return NULL;
 851
 852         hash = h->hash_func(key) % NBUCKETS;
 853         e = hash_scan(h, hash, key);
 854         if (!e)
 855                 return NULL;
 856
 857         e = e->iterate_next;
 858         if (!e)
 859                 return NULL;
 860
 861         return e->value;
 862 }