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         if (!h)
 269                 return;
 270
 271         hashmap_clear(h);
 272
 273         if (h->from_pool)
 274                 deallocate_tile(&first_hashmap_tile, h);
 275         else
 276                 free(h);
 277 }
 278
 279 void hashmap_free_free(Hashmap *h) {
 280         if (!h)
 281                 return;
 282
 283         hashmap_clear_free(h);
 284         hashmap_free(h);
 285 }
 286
 287 void hashmap_clear(Hashmap *h) {
 288         if (!h)
 289                 return;
 290
 291         while (h->iterate_list_head)
 292                 remove_entry(h, h->iterate_list_head);
 293 }
 294
 295 void hashmap_clear_free(Hashmap *h) {
 296         void *p;
 297
 298         if (!h)
 299                 return;
 300
 301         while ((p = hashmap_steal_first(h)))
 302                 free(p);
 303 }
 304
 305 static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *key) {
 306         struct hashmap_entry *e;
 307         assert(h);
 308         assert(hash < NBUCKETS);
 309
 310         for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
 311                 if (h->compare_func(e->key, key) == 0)
 312                         return e;
 313
 314         return NULL;
 315 }
 316
 317 int hashmap_put(Hashmap *h, const void *key, void *value) {
 318         struct hashmap_entry *e;
 319         unsigned hash;
 320
 321         assert(h);
 322
 323         hash = h->hash_func(key) % NBUCKETS;
 324
 325         if ((e = hash_scan(h, hash, key))) {
 326
 327                 if (e->value == value)
 328                         return 0;
 329
 330                 return -EEXIST;
 331         }
 332
 333         if (h->from_pool)
 334                 e = allocate_tile(&first_entry_pool, &first_entry_tile, sizeof(struct hashmap_entry));
 335         else
 336                 e = new(struct hashmap_entry, 1);
 337
 338         if (!e)
 339                 return -ENOMEM;
 340
 341         e->key = key;
 342         e->value = value;
 343
 344         link_entry(h, e, hash);
 345
 346         return 1;
 347 }
 348
 349 int hashmap_replace(Hashmap *h, const void *key, void *value) {
 350         struct hashmap_entry *e;
 351         unsigned hash;
 352
 353         assert(h);
 354
 355         hash = h->hash_func(key) % NBUCKETS;
 356
 357         if ((e = hash_scan(h, hash, key))) {
 358                 e->key = key;
 359                 e->value = value;
 360                 return 0;
 361         }
 362
 363         return hashmap_put(h, key, value);
 364 }
 365
 366 void* hashmap_get(Hashmap *h, const void *key) {
 367         unsigned hash;
 368         struct hashmap_entry *e;
 369
 370         if (!h)
 371                 return NULL;
 372
 373         hash = h->hash_func(key) % NBUCKETS;
 374
 375         if (!(e = hash_scan(h, hash, key)))
 376                 return NULL;
 377
 378         return e->value;
 379 }
 380
 381 bool hashmap_contains(Hashmap *h, const void *key) {
 382         unsigned hash;
 383
 384         if (!h)
 385                 return false;
 386
 387         hash = h->hash_func(key) % NBUCKETS;
 388
 389         if (!hash_scan(h, hash, key))
 390                 return false;
 391
 392         return true;
 393 }
 394
 395 void* hashmap_remove(Hashmap *h, const void *key) {
 396         struct hashmap_entry *e;
 397         unsigned hash;
 398         void *data;
 399
 400         if (!h)
 401                 return NULL;
 402
 403         hash = h->hash_func(key) % NBUCKETS;
 404
 405         if (!(e = hash_scan(h, hash, key)))
 406                 return NULL;
 407
 408         data = e->value;
 409         remove_entry(h, e);
 410
 411         return data;
 412 }
 413
 414 int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value) {
 415         struct hashmap_entry *e;
 416         unsigned old_hash, new_hash;
 417
 418         if (!h)
 419                 return -ENOENT;
 420
 421         old_hash = h->hash_func(old_key) % NBUCKETS;
 422         if (!(e = hash_scan(h, old_hash, old_key)))
 423                 return -ENOENT;
 424
 425         new_hash = h->hash_func(new_key) % NBUCKETS;
 426         if (hash_scan(h, new_hash, new_key))
 427                 return -EEXIST;
 428
 429         unlink_entry(h, e, old_hash);
 430
 431         e->key = new_key;
 432         e->value = value;
 433
 434         link_entry(h, e, new_hash);
 435
 436         return 0;
 437 }
 438
 439 int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value) {
 440         struct hashmap_entry *e, *k;
 441         unsigned old_hash, new_hash;
 442
 443         if (!h)
 444                 return -ENOENT;
 445
 446         old_hash = h->hash_func(old_key) % NBUCKETS;
 447         if (!(e = hash_scan(h, old_hash, old_key)))
 448                 return -ENOENT;
 449
 450         new_hash = h->hash_func(new_key) % NBUCKETS;
 451
 452         if ((k = hash_scan(h, new_hash, new_key)))
 453                 if (e != k)
 454                         remove_entry(h, k);
 455
 456         unlink_entry(h, e, old_hash);
 457
 458         e->key = new_key;
 459         e->value = value;
 460
 461         link_entry(h, e, new_hash);
 462
 463         return 0;
 464 }
 465
 466 void* hashmap_remove_value(Hashmap *h, const void *key, void *value) {
 467         struct hashmap_entry *e;
 468         unsigned hash;
 469
 470         if (!h)
 471                 return NULL;
 472
 473         hash = h->hash_func(key) % NBUCKETS;
 474
 475         if (!(e = hash_scan(h, hash, key)))
 476                 return NULL;
 477
 478         if (e->value != value)
 479                 return NULL;
 480
 481         remove_entry(h, e);
 482
 483         return value;
 484 }
 485
 486 void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key) {
 487         struct hashmap_entry *e;
 488
 489         assert(i);
 490
 491         if (!h)
 492                 goto at_end;
 493
 494         if (*i == ITERATOR_LAST)
 495                 goto at_end;
 496
 497         if (*i == ITERATOR_FIRST && !h->iterate_list_head)
 498                 goto at_end;
 499
 500         e = *i == ITERATOR_FIRST ? h->iterate_list_head : (struct hashmap_entry*) *i;
 501
 502         if (e->iterate_next)
 503                 *i = (Iterator) e->iterate_next;
 504         else
 505                 *i = ITERATOR_LAST;
 506
 507         if (key)
 508                 *key = e->key;
 509
 510         return e->value;
 511
 512 at_end:
 513         *i = ITERATOR_LAST;
 514
 515         if (key)
 516                 *key = NULL;
 517
 518         return NULL;
 519 }
 520
 521 void *hashmap_iterate_backwards(Hashmap *h, Iterator *i, const void **key) {
 522         struct hashmap_entry *e;
 523
 524         assert(i);
 525
 526         if (!h)
 527                 goto at_beginning;
 528
 529         if (*i == ITERATOR_FIRST)
 530                 goto at_beginning;
 531
 532         if (*i == ITERATOR_LAST && !h->iterate_list_tail)
 533                 goto at_beginning;
 534
 535         e = *i == ITERATOR_LAST ? h->iterate_list_tail : (struct hashmap_entry*) *i;
 536
 537         if (e->iterate_previous)
 538                 *i = (Iterator) e->iterate_previous;
 539         else
 540                 *i = ITERATOR_FIRST;
 541
 542         if (key)
 543                 *key = e->key;
 544
 545         return e->value;
 546
 547 at_beginning:
 548         *i = ITERATOR_FIRST;
 549
 550         if (key)
 551                 *key = NULL;
 552
 553         return NULL;
 554 }
 555
 556 void *hashmap_iterate_skip(Hashmap *h, const void *key, Iterator *i) {
 557         unsigned hash;
 558         struct hashmap_entry *e;
 559
 560         if (!h)
 561                 return NULL;
 562
 563         hash = h->hash_func(key) % NBUCKETS;
 564
 565         if (!(e = hash_scan(h, hash, key)))
 566                 return NULL;
 567
 568         *i = (Iterator) e;
 569
 570         return e->value;
 571 }
 572
 573 void* hashmap_first(Hashmap *h) {
 574
 575         if (!h)
 576                 return NULL;
 577
 578         if (!h->iterate_list_head)
 579                 return NULL;
 580
 581         return h->iterate_list_head->value;
 582 }
 583
 584 void* hashmap_first_key(Hashmap *h) {
 585
 586         if (!h)
 587                 return NULL;
 588
 589         if (!h->iterate_list_head)
 590                 return NULL;
 591
 592         return (void*) h->iterate_list_head->key;
 593 }
 594
 595 void* hashmap_last(Hashmap *h) {
 596
 597         if (!h)
 598                 return NULL;
 599
 600         if (!h->iterate_list_tail)
 601                 return NULL;
 602
 603         return h->iterate_list_tail->value;
 604 }
 605
 606 void* hashmap_steal_first(Hashmap *h) {
 607         void *data;
 608
 609         if (!h)
 610                 return NULL;
 611
 612         if (!h->iterate_list_head)
 613                 return NULL;
 614
 615         data = h->iterate_list_head->value;
 616         remove_entry(h, h->iterate_list_head);
 617
 618         return data;
 619 }
 620
 621 void* hashmap_steal_first_key(Hashmap *h) {
 622         void *key;
 623
 624         if (!h)
 625                 return NULL;
 626
 627         if (!h->iterate_list_head)
 628                 return NULL;
 629
 630         key = (void*) h->iterate_list_head->key;
 631         remove_entry(h, h->iterate_list_head);
 632
 633         return key;
 634 }
 635
 636 unsigned hashmap_size(Hashmap *h) {
 637
 638         if (!h)
 639                 return 0;
 640
 641         return h->n_entries;
 642 }
 643
 644 bool hashmap_isempty(Hashmap *h) {
 645
 646         if (!h)
 647                 return true;
 648
 649         return h->n_entries == 0;
 650 }
 651
 652 int hashmap_merge(Hashmap *h, Hashmap *other) {
 653         struct hashmap_entry *e;
 654
 655         assert(h);
 656
 657         if (!other)
 658                 return 0;
 659
 660         for (e = other->iterate_list_head; e; e = e->iterate_next) {
 661                 int r;
 662
 663                 if ((r = hashmap_put(h, e->key, e->value)) < 0)
 664                         if (r != -EEXIST)
 665                                 return r;
 666         }
 667
 668         return 0;
 669 }
 670
 671 void hashmap_move(Hashmap *h, Hashmap *other) {
 672         struct hashmap_entry *e, *n;
 673
 674         assert(h);
 675
 676         /* The same as hashmap_merge(), but every new item from other
 677          * is moved to h. This function is guaranteed to succeed. */
 678
 679         if (!other)
 680                 return;
 681
 682         for (e = other->iterate_list_head; e; e = n) {
 683                 unsigned h_hash, other_hash;
 684
 685                 n = e->iterate_next;
 686
 687                 h_hash = h->hash_func(e->key) % NBUCKETS;
 688
 689                 if (hash_scan(h, h_hash, e->key))
 690                         continue;
 691
 692                 other_hash = other->hash_func(e->key) % NBUCKETS;
 693
 694                 unlink_entry(other, e, other_hash);
 695                 link_entry(h, e, h_hash);
 696         }
 697 }
 698
 699 int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) {
 700         unsigned h_hash, other_hash;
 701         struct hashmap_entry *e;
 702
 703         if (!other)
 704                 return 0;
 705
 706         assert(h);
 707
 708         h_hash = h->hash_func(key) % NBUCKETS;
 709         if (hash_scan(h, h_hash, key))
 710                 return -EEXIST;
 711
 712         other_hash = other->hash_func(key) % NBUCKETS;
 713         if (!(e = hash_scan(other, other_hash, key)))
 714                 return -ENOENT;
 715
 716         unlink_entry(other, e, other_hash);
 717         link_entry(h, e, h_hash);
 718
 719         return 0;
 720 }
 721
 722 Hashmap *hashmap_copy(Hashmap *h) {
 723         Hashmap *copy;
 724
 725         assert(h);
 726
 727         if (!(copy = hashmap_new(h->hash_func, h->compare_func)))
 728                 return NULL;
 729
 730         if (hashmap_merge(copy, h) < 0) {
 731                 hashmap_free(copy);
 732                 return NULL;
 733         }
 734
 735         return copy;
 736 }
 737
 738 char **hashmap_get_strv(Hashmap *h) {
 739         char **sv;
 740         Iterator it;
 741         char *item;
 742         int n;
 743
 744         sv = new(char*, h->n_entries+1);
 745         if (!sv)
 746                 return NULL;
 747
 748         n = 0;
 749         HASHMAP_FOREACH(item, h, it)
 750                 sv[n++] = item;
 751         sv[n] = NULL;
 752
 753         return sv;
 754 }