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, unsigned entries_add) {
 373         struct hashmap_entry **n, *i;
 374         unsigned m, new_n_entries, new_n_buckets;
 375         uint8_t nkey[HASH_KEY_SIZE];
 376
 377         assert(h);
 378
 379         new_n_entries = h->n_entries + entries_add;
 380
 381         /* overflow? */
 382         if (_unlikely_(new_n_entries < entries_add || new_n_entries > UINT_MAX / 4))
 383                 return -ENOMEM;
 384
 385         new_n_buckets = new_n_entries * 4 / 3;
 386
 387         if (_likely_(new_n_buckets <= h->n_buckets))
 388                 return 0;
 389
 390         /* Increase by four at least */
 391         m = MAX((h->n_entries+1)*4-1, new_n_buckets);
 392
 393         /* If we hit OOM we simply risk packed hashmaps... */
 394         n = new0(struct hashmap_entry*, m);
 395         if (!n)
 396                 return -ENOMEM;
 397
 398         /* Let's use a different randomized hash key for the
 399          * extension, so that people cannot guess what we are using
 400          * here forever */
 401         get_hash_key(nkey, false);
 402
 403         for (i = h->iterate_list_head; i; i = i->iterate_next) {
 404                 unsigned long old_bucket, new_bucket;
 405
 406                 old_bucket = h->hash_ops->hash(i->key, h->hash_key) % h->n_buckets;
 407
 408                 /* First, drop from old bucket table */
 409                 if (i->bucket_next)
 410                         i->bucket_next->bucket_previous = i->bucket_previous;
 411
 412                 if (i->bucket_previous)
 413                         i->bucket_previous->bucket_next = i->bucket_next;
 414                 else
 415                         h->buckets[old_bucket] = i->bucket_next;
 416
 417                 /* Then, add to new backet table */
 418                 new_bucket = h->hash_ops->hash(i->key, nkey) % m;
 419
 420                 i->bucket_next = n[new_bucket];
 421                 i->bucket_previous = NULL;
 422                 if (n[new_bucket])
 423                         n[new_bucket]->bucket_previous = i;
 424                 n[new_bucket] = i;
 425         }
 426
 427         if (h->buckets != (struct hashmap_entry**) ((uint8_t*) h + ALIGN(sizeof(Hashmap))))
 428                 free(h->buckets);
 429
 430         h->buckets = n;
 431         h->n_buckets = m;
 432
 433         memcpy(h->hash_key, nkey, HASH_KEY_SIZE);
 434
 435         return 1;
 436 }
 437
 438 static int __hashmap_put(Hashmap *h, const void *key, void *value, unsigned hash) {
 439         /* For when we know no such entry exists yet */
 440
 441         struct hashmap_entry *e;
 442
 443         if (resize_buckets(h, 1) > 0)
 444                 hash = bucket_hash(h, key);
 445
 446         if (h->from_pool)
 447                 e = mempool_alloc_tile(&hashmap_entry_pool);
 448         else
 449                 e = new(struct hashmap_entry, 1);
 450
 451         if (!e)
 452                 return -ENOMEM;
 453
 454         e->key = key;
 455         e->value = value;
 456
 457         link_entry(h, e, hash);
 458
 459         return 1;
 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         return __hashmap_put(h, key, value, hash);
 477 }
 478
 479 int hashmap_replace(Hashmap *h, const void *key, void *value) {
 480         struct hashmap_entry *e;
 481         unsigned hash;
 482
 483         assert(h);
 484
 485         hash = bucket_hash(h, key);
 486         e = hash_scan(h, hash, key);
 487         if (e) {
 488                 e->key = key;
 489                 e->value = value;
 490                 return 0;
 491         }
 492
 493         return __hashmap_put(h, key, value, hash);
 494 }
 495
 496 int hashmap_update(Hashmap *h, const void *key, void *value) {
 497         struct hashmap_entry *e;
 498         unsigned hash;
 499
 500         assert(h);
 501
 502         hash = bucket_hash(h, key);
 503         e = hash_scan(h, hash, key);
 504         if (!e)
 505                 return -ENOENT;
 506
 507         e->value = value;
 508         return 0;
 509 }
 510
 511 void* hashmap_get(Hashmap *h, const void *key) {
 512         unsigned hash;
 513         struct hashmap_entry *e;
 514
 515         if (!h)
 516                 return NULL;
 517
 518         hash = bucket_hash(h, key);
 519         e = hash_scan(h, hash, key);
 520         if (!e)
 521                 return NULL;
 522
 523         return e->value;
 524 }
 525
 526 void* hashmap_get2(Hashmap *h, const void *key, void **key2) {
 527         unsigned hash;
 528         struct hashmap_entry *e;
 529
 530         if (!h)
 531                 return NULL;
 532
 533         hash = bucket_hash(h, key);
 534         e = hash_scan(h, hash, key);
 535         if (!e)
 536                 return NULL;
 537
 538         if (key2)
 539                 *key2 = (void*) e->key;
 540
 541         return e->value;
 542 }
 543
 544 bool hashmap_contains(Hashmap *h, const void *key) {
 545         unsigned hash;
 546
 547         if (!h)
 548                 return false;
 549
 550         hash = bucket_hash(h, key);
 551         return !!hash_scan(h, hash, key);
 552 }
 553
 554 void* hashmap_remove(Hashmap *h, const void *key) {
 555         struct hashmap_entry *e;
 556         unsigned hash;
 557         void *data;
 558
 559         if (!h)
 560                 return NULL;
 561
 562         hash = bucket_hash(h, key);
 563         e = hash_scan(h, hash, key);
 564         if (!e)
 565                 return NULL;
 566
 567         data = e->value;
 568         remove_entry(h, e);
 569
 570         return data;
 571 }
 572
 573 void* hashmap_remove2(Hashmap *h, const void *key, void **rkey) {
 574         struct hashmap_entry *e;
 575         unsigned hash;
 576         void *data;
 577
 578         if (!h) {
 579                 if (rkey)
 580                         *rkey = NULL;
 581                 return NULL;
 582         }
 583
 584         hash = bucket_hash(h, key);
 585         e = hash_scan(h, hash, key);
 586         if (!e) {
 587                 if (rkey)
 588                         *rkey = NULL;
 589                 return NULL;
 590         }
 591
 592         data = e->value;
 593         if (rkey)
 594                 *rkey = (void*) e->key;
 595
 596         remove_entry(h, e);
 597
 598         return data;
 599 }
 600
 601 int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value) {
 602         struct hashmap_entry *e;
 603         unsigned old_hash, new_hash;
 604
 605         if (!h)
 606                 return -ENOENT;
 607
 608         old_hash = bucket_hash(h, old_key);
 609         e = hash_scan(h, old_hash, old_key);
 610         if (!e)
 611                 return -ENOENT;
 612
 613         new_hash = bucket_hash(h, new_key);
 614         if (hash_scan(h, new_hash, new_key))
 615                 return -EEXIST;
 616
 617         unlink_entry(h, e, old_hash);
 618
 619         e->key = new_key;
 620         e->value = value;
 621
 622         link_entry(h, e, new_hash);
 623
 624         return 0;
 625 }
 626
 627 int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value) {
 628         struct hashmap_entry *e, *k;
 629         unsigned old_hash, new_hash;
 630
 631         if (!h)
 632                 return -ENOENT;
 633
 634         old_hash = bucket_hash(h, old_key);
 635         e = hash_scan(h, old_hash, old_key);
 636         if (!e)
 637                 return -ENOENT;
 638
 639         new_hash = bucket_hash(h, new_key);
 640         k = hash_scan(h, new_hash, new_key);
 641         if (k)
 642                 if (e != k)
 643                         remove_entry(h, k);
 644
 645         unlink_entry(h, e, old_hash);
 646
 647         e->key = new_key;
 648         e->value = value;
 649
 650         link_entry(h, e, new_hash);
 651
 652         return 0;
 653 }
 654
 655 void* hashmap_remove_value(Hashmap *h, const void *key, void *value) {
 656         struct hashmap_entry *e;
 657         unsigned hash;
 658
 659         if (!h)
 660                 return NULL;
 661
 662         hash = bucket_hash(h, key);
 663
 664         e = hash_scan(h, hash, key);
 665         if (!e)
 666                 return NULL;
 667
 668         if (e->value != value)
 669                 return NULL;
 670
 671         remove_entry(h, e);
 672
 673         return value;
 674 }
 675
 676 void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key) {
 677         struct hashmap_entry *e;
 678
 679         assert(i);
 680
 681         if (!h)
 682                 goto at_end;
 683
 684         if (*i == ITERATOR_LAST)
 685                 goto at_end;
 686
 687         if (*i == ITERATOR_FIRST && !h->iterate_list_head)
 688                 goto at_end;
 689
 690         e = *i == ITERATOR_FIRST ? h->iterate_list_head : (struct hashmap_entry*) *i;
 691
 692         if (e->iterate_next)
 693                 *i = (Iterator) e->iterate_next;
 694         else
 695                 *i = ITERATOR_LAST;
 696
 697         if (key)
 698                 *key = e->key;
 699
 700         return e->value;
 701
 702 at_end:
 703         *i = ITERATOR_LAST;
 704
 705         if (key)
 706                 *key = NULL;
 707
 708         return NULL;
 709 }
 710
 711 void* hashmap_first(Hashmap *h) {
 712
 713         if (!h)
 714                 return NULL;
 715
 716         if (!h->iterate_list_head)
 717                 return NULL;
 718
 719         return h->iterate_list_head->value;
 720 }
 721
 722 void* hashmap_first_key(Hashmap *h) {
 723
 724         if (!h)
 725                 return NULL;
 726
 727         if (!h->iterate_list_head)
 728                 return NULL;
 729
 730         return (void*) h->iterate_list_head->key;
 731 }
 732
 733 void* hashmap_steal_first(Hashmap *h) {
 734         void *data;
 735
 736         if (!h)
 737                 return NULL;
 738
 739         if (!h->iterate_list_head)
 740                 return NULL;
 741
 742         data = h->iterate_list_head->value;
 743         remove_entry(h, h->iterate_list_head);
 744
 745         return data;
 746 }
 747
 748 void* hashmap_steal_first_key(Hashmap *h) {
 749         void *key;
 750
 751         if (!h)
 752                 return NULL;
 753
 754         if (!h->iterate_list_head)
 755                 return NULL;
 756
 757         key = (void*) h->iterate_list_head->key;
 758         remove_entry(h, h->iterate_list_head);
 759
 760         return key;
 761 }
 762
 763 unsigned hashmap_size(Hashmap *h) {
 764
 765         if (!h)
 766                 return 0;
 767
 768         return h->n_entries;
 769 }
 770
 771 unsigned hashmap_buckets(Hashmap *h) {
 772
 773         if (!h)
 774                 return 0;
 775
 776         return h->n_buckets;
 777 }
 778
 779 bool hashmap_isempty(Hashmap *h) {
 780
 781         if (!h)
 782                 return true;
 783
 784         return h->n_entries == 0;
 785 }
 786
 787 int hashmap_merge(Hashmap *h, Hashmap *other) {
 788         struct hashmap_entry *e;
 789
 790         assert(h);
 791
 792         if (!other)
 793                 return 0;
 794
 795         for (e = other->iterate_list_head; e; e = e->iterate_next) {
 796                 int r;
 797
 798                 r = hashmap_put(h, e->key, e->value);
 799                 if (r < 0 && r != -EEXIST)
 800                         return r;
 801         }
 802
 803         return 0;
 804 }
 805
 806 int hashmap_reserve(Hashmap *h, unsigned entries_add) {
 807         int r;
 808
 809         assert(h);
 810
 811         r = resize_buckets(h, entries_add);
 812         if (r < 0)
 813                 return r;
 814
 815         return 0;
 816 }
 817
 818 void hashmap_move(Hashmap *h, Hashmap *other) {
 819         struct hashmap_entry *e, *n;
 820
 821         assert(h);
 822
 823         /* The same as hashmap_merge(), but every new item from other
 824          * is moved to h. This function is guaranteed to succeed. */
 825
 826         if (!other)
 827                 return;
 828
 829         for (e = other->iterate_list_head; e; e = n) {
 830                 unsigned h_hash, other_hash;
 831
 832                 n = e->iterate_next;
 833
 834                 h_hash = bucket_hash(h, e->key);
 835                 if (hash_scan(h, h_hash, e->key))
 836                         continue;
 837
 838                 other_hash = bucket_hash(other, e->key);
 839                 unlink_entry(other, e, other_hash);
 840                 link_entry(h, e, h_hash);
 841         }
 842 }
 843
 844 int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) {
 845         unsigned h_hash, other_hash;
 846         struct hashmap_entry *e;
 847
 848         assert(h);
 849
 850         h_hash = bucket_hash(h, key);
 851         if (hash_scan(h, h_hash, key))
 852                 return -EEXIST;
 853
 854         if (!other)
 855                 return -ENOENT;
 856
 857         other_hash = bucket_hash(other, key);
 858         e = hash_scan(other, other_hash, key);
 859         if (!e)
 860                 return -ENOENT;
 861
 862         unlink_entry(other, e, other_hash);
 863         link_entry(h, e, h_hash);
 864
 865         return 0;
 866 }
 867
 868 Hashmap *hashmap_copy(Hashmap *h) {
 869         Hashmap *copy;
 870
 871         assert(h);
 872
 873         copy = hashmap_new(h->hash_ops);
 874         if (!copy)
 875                 return NULL;
 876
 877         if (hashmap_merge(copy, h) < 0) {
 878                 hashmap_free(copy);
 879                 return NULL;
 880         }
 881
 882         return copy;
 883 }
 884
 885 char **hashmap_get_strv(Hashmap *h) {
 886         char **sv;
 887         Iterator it;
 888         char *item;
 889         int n;
 890
 891         sv = new(char*, h->n_entries+1);
 892         if (!sv)
 893                 return NULL;
 894
 895         n = 0;
 896         HASHMAP_FOREACH(item, h, it)
 897                 sv[n++] = item;
 898         sv[n] = NULL;
 899
 900         return sv;
 901 }
 902
 903 void *hashmap_next(Hashmap *h, const void *key) {
 904         unsigned hash;
 905         struct hashmap_entry *e;
 906
 907         assert(key);
 908
 909         if (!h)
 910                 return NULL;
 911
 912         hash = bucket_hash(h, key);
 913         e = hash_scan(h, hash, key);
 914         if (!e)
 915                 return NULL;
 916
 917         e = e->iterate_next;
 918         if (!e)
 919                 return NULL;
 920
 921         return e->value;
 922 }