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