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