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 #include "siphash24.h"
  31
  32 #define INITIAL_N_BUCKETS 31
  33
  34 struct hashmap_entry {
  35         const void *key;
  36         void *value;
  37         struct hashmap_entry *bucket_next, *bucket_previous;
  38         struct hashmap_entry *iterate_next, *iterate_previous;
  39 };
  40
  41 struct Hashmap {
  42         hash_func_t hash_func;
  43         compare_func_t compare_func;
  44
  45         struct hashmap_entry *iterate_list_head, *iterate_list_tail;
  46
  47         struct hashmap_entry ** buckets;
  48         unsigned n_buckets, n_entries;
  49
  50         uint8_t hash_key[HASH_KEY_SIZE];
  51         bool from_pool:1;
  52 };
  53
  54 struct pool {
  55         struct pool *next;
  56         unsigned n_tiles;
  57         unsigned n_used;
  58 };
  59
  60 static struct pool *first_hashmap_pool = NULL;
  61 static void *first_hashmap_tile = NULL;
  62
  63 static struct pool *first_entry_pool = NULL;
  64 static void *first_entry_tile = NULL;
  65
  66 static void* allocate_tile(struct pool **first_pool, void **first_tile, size_t tile_size, unsigned at_least) {
  67         unsigned i;
  68
  69         /* When a tile is released we add it to the list and simply
  70          * place the next pointer at its offset 0. */
  71
  72         assert(tile_size >= sizeof(void*));
  73         assert(at_least > 0);
  74
  75         if (*first_tile) {
  76                 void *r;
  77
  78                 r = *first_tile;
  79                 *first_tile = * (void**) (*first_tile);
  80                 return r;
  81         }
  82
  83         if (_unlikely_(!*first_pool) || _unlikely_((*first_pool)->n_used >= (*first_pool)->n_tiles)) {
  84                 unsigned n;
  85                 size_t size;
  86                 struct pool *p;
  87
  88                 n = *first_pool ? (*first_pool)->n_tiles : 0;
  89                 n = MAX(at_least, n * 2);
  90                 size = PAGE_ALIGN(ALIGN(sizeof(struct pool)) + n*tile_size);
  91                 n = (size - ALIGN(sizeof(struct pool))) / tile_size;
  92
  93                 p = malloc(size);
  94                 if (!p)
  95                         return NULL;
  96
  97                 p->next = *first_pool;
  98                 p->n_tiles = n;
  99                 p->n_used = 0;
 100
 101                 *first_pool = p;
 102         }
 103
 104         i = (*first_pool)->n_used++;
 105
 106         return ((uint8_t*) (*first_pool)) + ALIGN(sizeof(struct pool)) + i*tile_size;
 107 }
 108
 109 static void deallocate_tile(void **first_tile, void *p) {
 110         * (void**) p = *first_tile;
 111         *first_tile = p;
 112 }
 113
 114 #ifdef VALGRIND
 115
 116 static void drop_pool(struct pool *p) {
 117         while (p) {
 118                 struct pool *n;
 119                 n = p->next;
 120                 free(p);
 121                 p = n;
 122         }
 123 }
 124
 125 __attribute__((destructor)) static void cleanup_pool(void) {
 126         /* Be nice to valgrind */
 127
 128         drop_pool(first_hashmap_pool);
 129         drop_pool(first_entry_pool);
 130 }
 131
 132 #endif
 133
 134 unsigned long string_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) {
 135         uint64_t u;
 136         siphash24((uint8_t*) &u, p, strlen(p), hash_key);
 137         return (unsigned long) u;
 138 }
 139
 140 int string_compare_func(const void *a, const void *b) {
 141         return strcmp(a, b);
 142 }
 143
 144 unsigned long trivial_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) {
 145         uint64_t u;
 146         siphash24((uint8_t*) &u, &p, sizeof(p), hash_key);
 147         return (unsigned long) u;
 148 }
 149
 150 int trivial_compare_func(const void *a, const void *b) {
 151         return a < b ? -1 : (a > b ? 1 : 0);
 152 }
 153
 154 unsigned long uint64_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) {
 155         uint64_t u;
 156         siphash24((uint8_t*) &u, p, sizeof(uint64_t), hash_key);
 157         return (unsigned long) u;
 158 }
 159
 160 int uint64_compare_func(const void *_a, const void *_b) {
 161         uint64_t a, b;
 162         a = *(const uint64_t*) _a;
 163         b = *(const uint64_t*) _b;
 164         return a < b ? -1 : (a > b ? 1 : 0);
 165 }
 166
 167 static unsigned bucket_hash(Hashmap *h, const void *p) {
 168         return (unsigned) (h->hash_func(p, h->hash_key) % h->n_buckets);
 169 }
 170
 171 static void get_hash_key(uint8_t hash_key[HASH_KEY_SIZE], bool reuse_is_ok) {
 172         static uint8_t current[HASH_KEY_SIZE];
 173         static bool current_initialized = false;
 174
 175         /* Returns a hash function key to use. In order to keep things
 176          * fast we will not generate a new key each time we allocate a
 177          * new hash table. Instead, we'll just reuse the most recently
 178          * generated one, except if we never generated one or when we
 179          * are rehashing an entire hash table because we reached a
 180          * fill level */
 181
 182         if (!current_initialized || !reuse_is_ok) {
 183                 random_bytes(current, sizeof(current));
 184                 current_initialized = true;
 185         }
 186
 187         memcpy(hash_key, current, sizeof(current));
 188 }
 189
 190 Hashmap *hashmap_new(hash_func_t hash_func, compare_func_t compare_func) {
 191         bool b;
 192         Hashmap *h;
 193         size_t size;
 194
 195         b = is_main_thread();
 196
 197         size = ALIGN(sizeof(Hashmap)) + INITIAL_N_BUCKETS * sizeof(struct hashmap_entry*);
 198
 199         if (b) {
 200                 h = allocate_tile(&first_hashmap_pool, &first_hashmap_tile, size, 8);
 201                 if (!h)
 202                         return NULL;
 203
 204                 memzero(h, size);
 205         } else {
 206                 h = malloc0(size);
 207
 208                 if (!h)
 209                         return NULL;
 210         }
 211
 212         h->hash_func = hash_func ? hash_func : trivial_hash_func;
 213         h->compare_func = compare_func ? compare_func : trivial_compare_func;
 214
 215         h->n_buckets = INITIAL_N_BUCKETS;
 216         h->n_entries = 0;
 217         h->iterate_list_head = h->iterate_list_tail = NULL;
 218
 219         h->buckets = (struct hashmap_entry**) ((uint8_t*) h + ALIGN(sizeof(Hashmap)));
 220
 221         h->from_pool = b;
 222
 223         get_hash_key(h->hash_key, true);
 224
 225         return h;
 226 }
 227
 228 int hashmap_ensure_allocated(Hashmap **h, hash_func_t hash_func, compare_func_t compare_func) {
 229         Hashmap *q;
 230
 231         assert(h);
 232
 233         if (*h)
 234                 return 0;
 235
 236         q = hashmap_new(hash_func, compare_func);
 237         if (!q)
 238                 return -ENOMEM;
 239
 240         *h = q;
 241         return 0;
 242 }
 243
 244 static void link_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) {
 245         assert(h);
 246         assert(e);
 247
 248         /* Insert into hash table */
 249         e->bucket_next = h->buckets[hash];
 250         e->bucket_previous = NULL;
 251         if (h->buckets[hash])
 252                 h->buckets[hash]->bucket_previous = e;
 253         h->buckets[hash] = e;
 254
 255         /* Insert into iteration list */
 256         e->iterate_previous = h->iterate_list_tail;
 257         e->iterate_next = NULL;
 258         if (h->iterate_list_tail) {
 259                 assert(h->iterate_list_head);
 260                 h->iterate_list_tail->iterate_next = e;
 261         } else {
 262                 assert(!h->iterate_list_head);
 263                 h->iterate_list_head = e;
 264         }
 265         h->iterate_list_tail = e;
 266
 267         h->n_entries++;
 268         assert(h->n_entries >= 1);
 269 }
 270
 271 static void unlink_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) {
 272         assert(h);
 273         assert(e);
 274
 275         /* Remove from iteration list */
 276         if (e->iterate_next)
 277                 e->iterate_next->iterate_previous = e->iterate_previous;
 278         else
 279                 h->iterate_list_tail = e->iterate_previous;
 280
 281         if (e->iterate_previous)
 282                 e->iterate_previous->iterate_next = e->iterate_next;
 283         else
 284                 h->iterate_list_head = e->iterate_next;
 285
 286         /* Remove from hash table bucket list */
 287         if (e->bucket_next)
 288                 e->bucket_next->bucket_previous = e->bucket_previous;
 289
 290         if (e->bucket_previous)
 291                 e->bucket_previous->bucket_next = e->bucket_next;
 292         else
 293                 h->buckets[hash] = e->bucket_next;
 294
 295         assert(h->n_entries >= 1);
 296         h->n_entries--;
 297 }
 298
 299 static void remove_entry(Hashmap *h, struct hashmap_entry *e) {
 300         unsigned hash;
 301
 302         assert(h);
 303         assert(e);
 304
 305         hash = bucket_hash(h, e->key);
 306         unlink_entry(h, e, hash);
 307
 308         if (h->from_pool)
 309                 deallocate_tile(&first_entry_tile, e);
 310         else
 311                 free(e);
 312 }
 313
 314 void hashmap_free(Hashmap*h) {
 315
 316         /* Free the hashmap, but nothing in it */
 317
 318         if (!h)
 319                 return;
 320
 321         hashmap_clear(h);
 322
 323         if (h->buckets != (struct hashmap_entry**) ((uint8_t*) h + ALIGN(sizeof(Hashmap))))
 324                 free(h->buckets);
 325
 326         if (h->from_pool)
 327                 deallocate_tile(&first_hashmap_tile, h);
 328         else
 329                 free(h);
 330 }
 331
 332 void hashmap_free_free(Hashmap *h) {
 333
 334         /* Free the hashmap and all data objects in it, but not the
 335          * keys */
 336
 337         if (!h)
 338                 return;
 339
 340         hashmap_clear_free(h);
 341         hashmap_free(h);
 342 }
 343
 344 void hashmap_free_free_free(Hashmap *h) {
 345
 346         /* Free the hashmap and all data and key objects in it */
 347
 348         if (!h)
 349                 return;
 350
 351         hashmap_clear_free_free(h);
 352         hashmap_free(h);
 353 }
 354
 355 void hashmap_clear(Hashmap *h) {
 356         if (!h)
 357                 return;
 358
 359         while (h->iterate_list_head)
 360                 remove_entry(h, h->iterate_list_head);
 361 }
 362
 363 void hashmap_clear_free(Hashmap *h) {
 364         void *p;
 365
 366         if (!h)
 367                 return;
 368
 369         while ((p = hashmap_steal_first(h)))
 370                 free(p);
 371 }
 372
 373 void hashmap_clear_free_free(Hashmap *h) {
 374         if (!h)
 375                 return;
 376
 377         while (h->iterate_list_head) {
 378                 void *a, *b;
 379
 380                 a = h->iterate_list_head->value;
 381                 b = (void*) h->iterate_list_head->key;
 382                 remove_entry(h, h->iterate_list_head);
 383                 free(a);
 384                 free(b);
 385         }
 386 }
 387
 388 static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *key) {
 389         struct hashmap_entry *e;
 390         assert(h);
 391         assert(hash < h->n_buckets);
 392
 393         for (e = h->buckets[hash]; e; e = e->bucket_next)
 394                 if (h->compare_func(e->key, key) == 0)
 395                         return e;
 396
 397         return NULL;
 398 }
 399
 400 static bool resize_buckets(Hashmap *h) {
 401         struct hashmap_entry **n, *i;
 402         unsigned m;
 403         uint8_t nkey[HASH_KEY_SIZE];
 404
 405         assert(h);
 406
 407         if (_likely_(h->n_entries*4 < h->n_buckets*3))
 408                 return false;
 409
 410         /* Increase by four */
 411         m = (h->n_entries+1)*4-1;
 412
 413         /* If we hit OOM we simply risk packed hashmaps... */
 414         n = new0(struct hashmap_entry*, m);
 415         if (!n)
 416                 return false;
 417
 418         /* Let's use a different randomized hash key for the
 419          * extension, so that people cannot guess what we are using
 420          * here forever */
 421         get_hash_key(nkey, false);
 422
 423         for (i = h->iterate_list_head; i; i = i->iterate_next) {
 424                 unsigned long old_bucket, new_bucket;
 425
 426                 old_bucket = h->hash_func(i->key, h->hash_key) % h->n_buckets;
 427
 428                 /* First, drop from old bucket table */
 429                 if (i->bucket_next)
 430                         i->bucket_next->bucket_previous = i->bucket_previous;
 431
 432                 if (i->bucket_previous)
 433                         i->bucket_previous->bucket_next = i->bucket_next;
 434                 else
 435                         h->buckets[old_bucket] = i->bucket_next;
 436
 437                 /* Then, add to new backet table */
 438                 new_bucket = h->hash_func(i->key, nkey)  % m;
 439
 440                 i->bucket_next = n[new_bucket];
 441                 i->bucket_previous = NULL;
 442                 if (n[new_bucket])
 443                         n[new_bucket]->bucket_previous = i;
 444                 n[new_bucket] = i;
 445         }
 446
 447         if (h->buckets != (struct hashmap_entry**) ((uint8_t*) h + ALIGN(sizeof(Hashmap))))
 448                 free(h->buckets);
 449
 450         h->buckets = n;
 451         h->n_buckets = m;
 452
 453         memcpy(h->hash_key, nkey, HASH_KEY_SIZE);
 454
 455         return true;
 456 }
 457
 458 int hashmap_put(Hashmap *h, const void *key, void *value) {
 459         struct hashmap_entry *e;
 460         unsigned hash;
 461
 462         assert(h);
 463
 464         hash = bucket_hash(h, key);
 465         e = hash_scan(h, hash, key);
 466         if (e) {
 467                 if (e->value == value)
 468                         return 0;
 469                 return -EEXIST;
 470         }
 471
 472         if (resize_buckets(h))
 473                 hash = bucket_hash(h, key);
 474
 475         if (h->from_pool)
 476                 e = allocate_tile(&first_entry_pool, &first_entry_tile, sizeof(struct hashmap_entry), 64U);
 477         else
 478                 e = new(struct hashmap_entry, 1);
 479
 480         if (!e)
 481                 return -ENOMEM;
 482
 483         e->key = key;
 484         e->value = value;
 485
 486         link_entry(h, e, hash);
 487
 488         return 1;
 489 }
 490
 491 int hashmap_replace(Hashmap *h, const void *key, void *value) {
 492         struct hashmap_entry *e;
 493         unsigned hash;
 494
 495         assert(h);
 496
 497         hash = bucket_hash(h, key);
 498         e = hash_scan(h, hash, key);
 499         if (e) {
 500                 e->key = key;
 501                 e->value = value;
 502                 return 0;
 503         }
 504
 505         return hashmap_put(h, key, value);
 506 }
 507
 508 int hashmap_update(Hashmap *h, const void *key, void *value) {
 509         struct hashmap_entry *e;
 510         unsigned hash;
 511
 512         assert(h);
 513
 514         hash = bucket_hash(h, key);
 515         e = hash_scan(h, hash, key);
 516         if (!e)
 517                 return -ENOENT;
 518
 519         e->value = value;
 520         return 0;
 521 }
 522
 523 void* hashmap_get(Hashmap *h, const void *key) {
 524         unsigned hash;
 525         struct hashmap_entry *e;
 526
 527         if (!h)
 528                 return NULL;
 529
 530         hash = bucket_hash(h, key);
 531         e = hash_scan(h, hash, key);
 532         if (!e)
 533                 return NULL;
 534
 535         return e->value;
 536 }
 537
 538 void* hashmap_get2(Hashmap *h, const void *key, void **key2) {
 539         unsigned hash;
 540         struct hashmap_entry *e;
 541
 542         if (!h)
 543                 return NULL;
 544
 545         hash = bucket_hash(h, key);
 546         e = hash_scan(h, hash, key);
 547         if (!e)
 548                 return NULL;
 549
 550         if (key2)
 551                 *key2 = (void*) e->key;
 552
 553         return e->value;
 554 }
 555
 556 bool hashmap_contains(Hashmap *h, const void *key) {
 557         unsigned hash;
 558
 559         if (!h)
 560                 return false;
 561
 562         hash = bucket_hash(h, key);
 563         return !!hash_scan(h, hash, key);
 564 }
 565
 566 void* hashmap_remove(Hashmap *h, const void *key) {
 567         struct hashmap_entry *e;
 568         unsigned hash;
 569         void *data;
 570
 571         if (!h)
 572                 return NULL;
 573
 574         hash = bucket_hash(h, key);
 575         e = hash_scan(h, hash, key);
 576         if (!e)
 577                 return NULL;
 578
 579         data = e->value;
 580         remove_entry(h, e);
 581
 582         return data;
 583 }
 584
 585 int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value) {
 586         struct hashmap_entry *e;
 587         unsigned old_hash, new_hash;
 588
 589         if (!h)
 590                 return -ENOENT;
 591
 592         old_hash = bucket_hash(h, old_key);
 593         e = hash_scan(h, old_hash, old_key);
 594         if (!e)
 595                 return -ENOENT;
 596
 597         new_hash = bucket_hash(h, new_key);
 598         if (hash_scan(h, new_hash, new_key))
 599                 return -EEXIST;
 600
 601         unlink_entry(h, e, old_hash);
 602
 603         e->key = new_key;
 604         e->value = value;
 605
 606         link_entry(h, e, new_hash);
 607
 608         return 0;
 609 }
 610
 611 int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value) {
 612         struct hashmap_entry *e, *k;
 613         unsigned old_hash, new_hash;
 614
 615         if (!h)
 616                 return -ENOENT;
 617
 618         old_hash = bucket_hash(h, old_key);
 619         e = hash_scan(h, old_hash, old_key);
 620         if (!e)
 621                 return -ENOENT;
 622
 623         new_hash = bucket_hash(h, new_key);
 624         k = hash_scan(h, new_hash, new_key);
 625         if (k)
 626                 if (e != k)
 627                         remove_entry(h, k);
 628
 629         unlink_entry(h, e, old_hash);
 630
 631         e->key = new_key;
 632         e->value = value;
 633
 634         link_entry(h, e, new_hash);
 635
 636         return 0;
 637 }
 638
 639 void* hashmap_remove_value(Hashmap *h, const void *key, void *value) {
 640         struct hashmap_entry *e;
 641         unsigned hash;
 642
 643         if (!h)
 644                 return NULL;
 645
 646         hash = bucket_hash(h, key);
 647
 648         e = hash_scan(h, hash, key);
 649         if (!e)
 650                 return NULL;
 651
 652         if (e->value != value)
 653                 return NULL;
 654
 655         remove_entry(h, e);
 656
 657         return value;
 658 }
 659
 660 void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key) {
 661         struct hashmap_entry *e;
 662
 663         assert(i);
 664
 665         if (!h)
 666                 goto at_end;
 667
 668         if (*i == ITERATOR_LAST)
 669                 goto at_end;
 670
 671         if (*i == ITERATOR_FIRST && !h->iterate_list_head)
 672                 goto at_end;
 673
 674         e = *i == ITERATOR_FIRST ? h->iterate_list_head : (struct hashmap_entry*) *i;
 675
 676         if (e->iterate_next)
 677                 *i = (Iterator) e->iterate_next;
 678         else
 679                 *i = ITERATOR_LAST;
 680
 681         if (key)
 682                 *key = e->key;
 683
 684         return e->value;
 685
 686 at_end:
 687         *i = ITERATOR_LAST;
 688
 689         if (key)
 690                 *key = NULL;
 691
 692         return NULL;
 693 }
 694
 695 void *hashmap_iterate_backwards(Hashmap *h, Iterator *i, const void **key) {
 696         struct hashmap_entry *e;
 697
 698         assert(i);
 699
 700         if (!h)
 701                 goto at_beginning;
 702
 703         if (*i == ITERATOR_FIRST)
 704                 goto at_beginning;
 705
 706         if (*i == ITERATOR_LAST && !h->iterate_list_tail)
 707                 goto at_beginning;
 708
 709         e = *i == ITERATOR_LAST ? h->iterate_list_tail : (struct hashmap_entry*) *i;
 710
 711         if (e->iterate_previous)
 712                 *i = (Iterator) e->iterate_previous;
 713         else
 714                 *i = ITERATOR_FIRST;
 715
 716         if (key)
 717                 *key = e->key;
 718
 719         return e->value;
 720
 721 at_beginning:
 722         *i = ITERATOR_FIRST;
 723
 724         if (key)
 725                 *key = NULL;
 726
 727         return NULL;
 728 }
 729
 730 void *hashmap_iterate_skip(Hashmap *h, const void *key, Iterator *i) {
 731         unsigned hash;
 732         struct hashmap_entry *e;
 733
 734         if (!h)
 735                 return NULL;
 736
 737         hash = bucket_hash(h, key);
 738
 739         e = hash_scan(h, hash, key);
 740         if (!e)
 741                 return NULL;
 742
 743         *i = (Iterator) e;
 744
 745         return e->value;
 746 }
 747
 748 void* hashmap_first(Hashmap *h) {
 749
 750         if (!h)
 751                 return NULL;
 752
 753         if (!h->iterate_list_head)
 754                 return NULL;
 755
 756         return h->iterate_list_head->value;
 757 }
 758
 759 void* hashmap_first_key(Hashmap *h) {
 760
 761         if (!h)
 762                 return NULL;
 763
 764         if (!h->iterate_list_head)
 765                 return NULL;
 766
 767         return (void*) h->iterate_list_head->key;
 768 }
 769
 770 void* hashmap_last(Hashmap *h) {
 771
 772         if (!h)
 773                 return NULL;
 774
 775         if (!h->iterate_list_tail)
 776                 return NULL;
 777
 778         return h->iterate_list_tail->value;
 779 }
 780
 781 void* hashmap_steal_first(Hashmap *h) {
 782         void *data;
 783
 784         if (!h)
 785                 return NULL;
 786
 787         if (!h->iterate_list_head)
 788                 return NULL;
 789
 790         data = h->iterate_list_head->value;
 791         remove_entry(h, h->iterate_list_head);
 792
 793         return data;
 794 }
 795
 796 void* hashmap_steal_first_key(Hashmap *h) {
 797         void *key;
 798
 799         if (!h)
 800                 return NULL;
 801
 802         if (!h->iterate_list_head)
 803                 return NULL;
 804
 805         key = (void*) h->iterate_list_head->key;
 806         remove_entry(h, h->iterate_list_head);
 807
 808         return key;
 809 }
 810
 811 unsigned hashmap_size(Hashmap *h) {
 812
 813         if (!h)
 814                 return 0;
 815
 816         return h->n_entries;
 817 }
 818
 819 unsigned hashmap_buckets(Hashmap *h) {
 820
 821         if (!h)
 822                 return 0;
 823
 824         return h->n_buckets;
 825 }
 826
 827 bool hashmap_isempty(Hashmap *h) {
 828
 829         if (!h)
 830                 return true;
 831
 832         return h->n_entries == 0;
 833 }
 834
 835 int hashmap_merge(Hashmap *h, Hashmap *other) {
 836         struct hashmap_entry *e;
 837
 838         assert(h);
 839
 840         if (!other)
 841                 return 0;
 842
 843         for (e = other->iterate_list_head; e; e = e->iterate_next) {
 844                 int r;
 845
 846                 r = hashmap_put(h, e->key, e->value);
 847                 if (r < 0 && r != -EEXIST)
 848                         return r;
 849         }
 850
 851         return 0;
 852 }
 853
 854 void hashmap_move(Hashmap *h, Hashmap *other) {
 855         struct hashmap_entry *e, *n;
 856
 857         assert(h);
 858
 859         /* The same as hashmap_merge(), but every new item from other
 860          * is moved to h. This function is guaranteed to succeed. */
 861
 862         if (!other)
 863                 return;
 864
 865         for (e = other->iterate_list_head; e; e = n) {
 866                 unsigned h_hash, other_hash;
 867
 868                 n = e->iterate_next;
 869
 870                 h_hash = bucket_hash(h, e->key);
 871                 if (hash_scan(h, h_hash, e->key))
 872                         continue;
 873
 874                 other_hash = bucket_hash(other, e->key);
 875                 unlink_entry(other, e, other_hash);
 876                 link_entry(h, e, h_hash);
 877         }
 878 }
 879
 880 int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) {
 881         unsigned h_hash, other_hash;
 882         struct hashmap_entry *e;
 883
 884         if (!other)
 885                 return 0;
 886
 887         assert(h);
 888
 889         h_hash = bucket_hash(h, key);
 890         if (hash_scan(h, h_hash, key))
 891                 return -EEXIST;
 892
 893         other_hash = bucket_hash(other, key);
 894         e = hash_scan(other, other_hash, key);
 895         if (!e)
 896                 return -ENOENT;
 897
 898         unlink_entry(other, e, other_hash);
 899         link_entry(h, e, h_hash);
 900
 901         return 0;
 902 }
 903
 904 Hashmap *hashmap_copy(Hashmap *h) {
 905         Hashmap *copy;
 906
 907         assert(h);
 908
 909         copy = hashmap_new(h->hash_func, h->compare_func);
 910         if (!copy)
 911                 return NULL;
 912
 913         if (hashmap_merge(copy, h) < 0) {
 914                 hashmap_free(copy);
 915                 return NULL;
 916         }
 917
 918         return copy;
 919 }
 920
 921 char **hashmap_get_strv(Hashmap *h) {
 922         char **sv;
 923         Iterator it;
 924         char *item;
 925         int n;
 926
 927         sv = new(char*, h->n_entries+1);
 928         if (!sv)
 929                 return NULL;
 930
 931         n = 0;
 932         HASHMAP_FOREACH(item, h, it)
 933                 sv[n++] = item;
 934         sv[n] = NULL;
 935
 936         return sv;
 937 }
 938
 939 void *hashmap_next(Hashmap *h, const void *key) {
 940         unsigned hash;
 941         struct hashmap_entry *e;
 942
 943         assert(h);
 944         assert(key);
 945
 946         if (!h)
 947                 return NULL;
 948
 949         hash = bucket_hash(h, key);
 950         e = hash_scan(h, hash, key);
 951         if (!e)
 952                 return NULL;
 953
 954         e = e->iterate_next;
 955         if (!e)
 956                 return NULL;
 957
 958         return e->value;
 959 }