src/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 General Public License as published by
  10   the Free Software Foundation; either version 2 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   General Public License for more details.
  17
  18   You should have received a copy of the GNU 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 }