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