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