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