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