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