src/shared/hashmap.c

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