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