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