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