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