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 void* hashmap_remove2(Hashmap *h, const void *key, void **rkey) {
 586         struct hashmap_entry *e;
 587         unsigned hash;
 588         void *data;
 589
 590         if (!h) {
 591                 if (rkey)
 592                         *rkey = NULL;
 593                 return NULL;
 594         }
 595
 596         hash = bucket_hash(h, key);
 597         e = hash_scan(h, hash, key);
 598         if (!e) {
 599                 if (rkey)
 600                         *rkey = NULL;
 601                 return NULL;
 602         }
 603
 604         data = e->value;
 605         if (rkey)
 606                 *rkey = (void*) e->key;
 607
 608         remove_entry(h, e);
 609
 610         return data;
 611 }
 612
 613 int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value) {
 614         struct hashmap_entry *e;
 615         unsigned old_hash, new_hash;
 616
 617         if (!h)
 618                 return -ENOENT;
 619
 620         old_hash = bucket_hash(h, old_key);
 621         e = hash_scan(h, old_hash, old_key);
 622         if (!e)
 623                 return -ENOENT;
 624
 625         new_hash = bucket_hash(h, new_key);
 626         if (hash_scan(h, new_hash, new_key))
 627                 return -EEXIST;
 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 int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value) {
 640         struct hashmap_entry *e, *k;
 641         unsigned old_hash, new_hash;
 642
 643         if (!h)
 644                 return -ENOENT;
 645
 646         old_hash = bucket_hash(h, old_key);
 647         e = hash_scan(h, old_hash, old_key);
 648         if (!e)
 649                 return -ENOENT;
 650
 651         new_hash = bucket_hash(h, new_key);
 652         k = hash_scan(h, new_hash, new_key);
 653         if (k)
 654                 if (e != k)
 655                         remove_entry(h, k);
 656
 657         unlink_entry(h, e, old_hash);
 658
 659         e->key = new_key;
 660         e->value = value;
 661
 662         link_entry(h, e, new_hash);
 663
 664         return 0;
 665 }
 666
 667 void* hashmap_remove_value(Hashmap *h, const void *key, void *value) {
 668         struct hashmap_entry *e;
 669         unsigned hash;
 670
 671         if (!h)
 672                 return NULL;
 673
 674         hash = bucket_hash(h, key);
 675
 676         e = hash_scan(h, hash, key);
 677         if (!e)
 678                 return NULL;
 679
 680         if (e->value != value)
 681                 return NULL;
 682
 683         remove_entry(h, e);
 684
 685         return value;
 686 }
 687
 688 void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key) {
 689         struct hashmap_entry *e;
 690
 691         assert(i);
 692
 693         if (!h)
 694                 goto at_end;
 695
 696         if (*i == ITERATOR_LAST)
 697                 goto at_end;
 698
 699         if (*i == ITERATOR_FIRST && !h->iterate_list_head)
 700                 goto at_end;
 701
 702         e = *i == ITERATOR_FIRST ? h->iterate_list_head : (struct hashmap_entry*) *i;
 703
 704         if (e->iterate_next)
 705                 *i = (Iterator) e->iterate_next;
 706         else
 707                 *i = ITERATOR_LAST;
 708
 709         if (key)
 710                 *key = e->key;
 711
 712         return e->value;
 713
 714 at_end:
 715         *i = ITERATOR_LAST;
 716
 717         if (key)
 718                 *key = NULL;
 719
 720         return NULL;
 721 }
 722
 723 void *hashmap_iterate_backwards(Hashmap *h, Iterator *i, const void **key) {
 724         struct hashmap_entry *e;
 725
 726         assert(i);
 727
 728         if (!h)
 729                 goto at_beginning;
 730
 731         if (*i == ITERATOR_FIRST)
 732                 goto at_beginning;
 733
 734         if (*i == ITERATOR_LAST && !h->iterate_list_tail)
 735                 goto at_beginning;
 736
 737         e = *i == ITERATOR_LAST ? h->iterate_list_tail : (struct hashmap_entry*) *i;
 738
 739         if (e->iterate_previous)
 740                 *i = (Iterator) e->iterate_previous;
 741         else
 742                 *i = ITERATOR_FIRST;
 743
 744         if (key)
 745                 *key = e->key;
 746
 747         return e->value;
 748
 749 at_beginning:
 750         *i = ITERATOR_FIRST;
 751
 752         if (key)
 753                 *key = NULL;
 754
 755         return NULL;
 756 }
 757
 758 void *hashmap_iterate_skip(Hashmap *h, const void *key, Iterator *i) {
 759         unsigned hash;
 760         struct hashmap_entry *e;
 761
 762         if (!h)
 763                 return NULL;
 764
 765         hash = bucket_hash(h, key);
 766
 767         e = hash_scan(h, hash, key);
 768         if (!e)
 769                 return NULL;
 770
 771         *i = (Iterator) e;
 772
 773         return e->value;
 774 }
 775
 776 void* hashmap_first(Hashmap *h) {
 777
 778         if (!h)
 779                 return NULL;
 780
 781         if (!h->iterate_list_head)
 782                 return NULL;
 783
 784         return h->iterate_list_head->value;
 785 }
 786
 787 void* hashmap_first_key(Hashmap *h) {
 788
 789         if (!h)
 790                 return NULL;
 791
 792         if (!h->iterate_list_head)
 793                 return NULL;
 794
 795         return (void*) h->iterate_list_head->key;
 796 }
 797
 798 void* hashmap_last(Hashmap *h) {
 799
 800         if (!h)
 801                 return NULL;
 802
 803         if (!h->iterate_list_tail)
 804                 return NULL;
 805
 806         return h->iterate_list_tail->value;
 807 }
 808
 809 void* hashmap_steal_first(Hashmap *h) {
 810         void *data;
 811
 812         if (!h)
 813                 return NULL;
 814
 815         if (!h->iterate_list_head)
 816                 return NULL;
 817
 818         data = h->iterate_list_head->value;
 819         remove_entry(h, h->iterate_list_head);
 820
 821         return data;
 822 }
 823
 824 void* hashmap_steal_first_key(Hashmap *h) {
 825         void *key;
 826
 827         if (!h)
 828                 return NULL;
 829
 830         if (!h->iterate_list_head)
 831                 return NULL;
 832
 833         key = (void*) h->iterate_list_head->key;
 834         remove_entry(h, h->iterate_list_head);
 835
 836         return key;
 837 }
 838
 839 unsigned hashmap_size(Hashmap *h) {
 840
 841         if (!h)
 842                 return 0;
 843
 844         return h->n_entries;
 845 }
 846
 847 unsigned hashmap_buckets(Hashmap *h) {
 848
 849         if (!h)
 850                 return 0;
 851
 852         return h->n_buckets;
 853 }
 854
 855 bool hashmap_isempty(Hashmap *h) {
 856
 857         if (!h)
 858                 return true;
 859
 860         return h->n_entries == 0;
 861 }
 862
 863 int hashmap_merge(Hashmap *h, Hashmap *other) {
 864         struct hashmap_entry *e;
 865
 866         assert(h);
 867
 868         if (!other)
 869                 return 0;
 870
 871         for (e = other->iterate_list_head; e; e = e->iterate_next) {
 872                 int r;
 873
 874                 r = hashmap_put(h, e->key, e->value);
 875                 if (r < 0 && r != -EEXIST)
 876                         return r;
 877         }
 878
 879         return 0;
 880 }
 881
 882 void hashmap_move(Hashmap *h, Hashmap *other) {
 883         struct hashmap_entry *e, *n;
 884
 885         assert(h);
 886
 887         /* The same as hashmap_merge(), but every new item from other
 888          * is moved to h. This function is guaranteed to succeed. */
 889
 890         if (!other)
 891                 return;
 892
 893         for (e = other->iterate_list_head; e; e = n) {
 894                 unsigned h_hash, other_hash;
 895
 896                 n = e->iterate_next;
 897
 898                 h_hash = bucket_hash(h, e->key);
 899                 if (hash_scan(h, h_hash, e->key))
 900                         continue;
 901
 902                 other_hash = bucket_hash(other, e->key);
 903                 unlink_entry(other, e, other_hash);
 904                 link_entry(h, e, h_hash);
 905         }
 906 }
 907
 908 int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) {
 909         unsigned h_hash, other_hash;
 910         struct hashmap_entry *e;
 911
 912         if (!other)
 913                 return 0;
 914
 915         assert(h);
 916
 917         h_hash = bucket_hash(h, key);
 918         if (hash_scan(h, h_hash, key))
 919                 return -EEXIST;
 920
 921         other_hash = bucket_hash(other, key);
 922         e = hash_scan(other, other_hash, key);
 923         if (!e)
 924                 return -ENOENT;
 925
 926         unlink_entry(other, e, other_hash);
 927         link_entry(h, e, h_hash);
 928
 929         return 0;
 930 }
 931
 932 Hashmap *hashmap_copy(Hashmap *h) {
 933         Hashmap *copy;
 934
 935         assert(h);
 936
 937         copy = hashmap_new(h->hash_func, h->compare_func);
 938         if (!copy)
 939                 return NULL;
 940
 941         if (hashmap_merge(copy, h) < 0) {
 942                 hashmap_free(copy);
 943                 return NULL;
 944         }
 945
 946         return copy;
 947 }
 948
 949 char **hashmap_get_strv(Hashmap *h) {
 950         char **sv;
 951         Iterator it;
 952         char *item;
 953         int n;
 954
 955         sv = new(char*, h->n_entries+1);
 956         if (!sv)
 957                 return NULL;
 958
 959         n = 0;
 960         HASHMAP_FOREACH(item, h, it)
 961                 sv[n++] = item;
 962         sv[n] = NULL;
 963
 964         return sv;
 965 }
 966
 967 void *hashmap_next(Hashmap *h, const void *key) {
 968         unsigned hash;
 969         struct hashmap_entry *e;
 970
 971         assert(h);
 972         assert(key);
 973
 974         if (!h)
 975                 return NULL;
 976
 977         hash = bucket_hash(h, key);
 978         e = hash_scan(h, hash, key);
 979         if (!e)
 980                 return NULL;
 981
 982         e = e->iterate_next;
 983         if (!e)
 984                 return NULL;
 985
 986         return e->value;
 987 }