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