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