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