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   Copyright 2014 Michal Schmidt
   8
   9   systemd is free software; you can redistribute it and/or modify it
  10   under the terms of the GNU Lesser General Public License as published by
  11   the Free Software Foundation; either version 2.1 of the License, or
  12   (at your option) any later version.
  13
  14   systemd is distributed in the hope that it will be useful, but
  15   WITHOUT ANY WARRANTY; without even the implied warranty of
  16   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  17   Lesser General Public License for more details.
  18
  19   You should have received a copy of the GNU Lesser General Public License
  20   along with systemd; If not, see <http://www.gnu.org/licenses/>.
  21 ***/
  22
  23 #include <stdlib.h>
  24 #include <errno.h>
  25
  26 #include "util.h"
  27 #include "hashmap.h"
  28 #include "set.h"
  29 #include "macro.h"
  30 #include "siphash24.h"
  31 #include "strv.h"
  32 #include "mempool.h"
  33 #include "random-util.h"
  34
  35 #ifdef ENABLE_DEBUG_HASHMAP
  36 #include "list.h"
  37 #endif
  38
  39 /*
  40  * Implementation of hashmaps.
  41  * Addressing: open
  42  *   - uses less RAM compared to closed addressing (chaining), because
  43  *     our entries are small (especially in Sets, which tend to contain
  44  *     the majority of entries in systemd).
  45  * Collision resolution: Robin Hood
  46  *   - tends to equalize displacement of entries from their optimal buckets.
  47  * Probe sequence: linear
  48  *   - though theoretically worse than random probing/uniform hashing/double
  49  *     hashing, it is good for cache locality.
  50  *
  51  * References:
  52  * Celis, P. 1986. Robin Hood Hashing.
  53  * Ph.D. Dissertation. University of Waterloo, Waterloo, Ont., Canada, Canada.
  54  * https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf
  55  * - The results are derived for random probing. Suggests deletion with
  56  *   tombstones and two mean-centered search methods. None of that works
  57  *   well for linear probing.
  58  *
  59  * Janson, S. 2005. Individual displacements for linear probing hashing with different insertion policies.
  60  * ACM Trans. Algorithms 1, 2 (October 2005), 177-213.
  61  * DOI=10.1145/1103963.1103964 http://doi.acm.org/10.1145/1103963.1103964
  62  * http://www.math.uu.se/~svante/papers/sj157.pdf
  63  * - Applies to Robin Hood with linear probing. Contains remarks on
  64  *   the unsuitability of mean-centered search with linear probing.
  65  *
  66  * Viola, A. 2005. Exact distribution of individual displacements in linear probing hashing.
  67  * ACM Trans. Algorithms 1, 2 (October 2005), 214-242.
  68  * DOI=10.1145/1103963.1103965 http://doi.acm.org/10.1145/1103963.1103965
  69  * - Similar to Janson. Note that Viola writes about C_{m,n} (number of probes
  70  *   in a successful search), and Janson writes about displacement. C = d + 1.
  71  *
  72  * Goossaert, E. 2013. Robin Hood hashing: backward shift deletion.
  73  * http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/
  74  * - Explanation of backward shift deletion with pictures.
  75  *
  76  * Khuong, P. 2013. The Other Robin Hood Hashing.
  77  * http://www.pvk.ca/Blog/2013/11/26/the-other-robin-hood-hashing/
  78  * - Short summary of random vs. linear probing, and tombstones vs. backward shift.
  79  */
  80
  81 /*
  82  * XXX Ideas for improvement:
  83  * For unordered hashmaps, randomize iteration order, similarly to Perl:
  84  * http://blog.booking.com/hardening-perls-hash-function.html
  85  */
  86
  87 /* INV_KEEP_FREE = 1 / (1 - max_load_factor)
  88  * e.g. 1 / (1 - 0.8) = 5 ... keep one fifth of the buckets free. */
  89 #define INV_KEEP_FREE            5U
  90
  91 /* Fields common to entries of all hashmap/set types */
  92 struct hashmap_base_entry {
  93         const void *key;
  94 };
  95
  96 /* Entry types for specific hashmap/set types
  97  * hashmap_base_entry must be at the beginning of each entry struct. */
  98
  99 struct plain_hashmap_entry {
 100         struct hashmap_base_entry b;
 101         void *value;
 102 };
 103
 104 struct ordered_hashmap_entry {
 105         struct plain_hashmap_entry p;
 106         unsigned iterate_next, iterate_previous;
 107 };
 108
 109 struct set_entry {
 110         struct hashmap_base_entry b;
 111 };
 112
 113 /* In several functions it is advantageous to have the hash table extended
 114  * virtually by a couple of additional buckets. We reserve special index values
 115  * for these "swap" buckets. */
 116 #define _IDX_SWAP_BEGIN     (UINT_MAX - 3)
 117 #define IDX_PUT             (_IDX_SWAP_BEGIN + 0)
 118 #define IDX_TMP             (_IDX_SWAP_BEGIN + 1)
 119 #define _IDX_SWAP_END       (_IDX_SWAP_BEGIN + 2)
 120
 121 #define IDX_FIRST           (UINT_MAX - 1) /* special index for freshly initialized iterators */
 122 #define IDX_NIL             UINT_MAX       /* special index value meaning "none" or "end" */
 123
 124 assert_cc(IDX_FIRST == _IDX_SWAP_END);
 125 assert_cc(IDX_FIRST == _IDX_ITERATOR_FIRST);
 126
 127 /* Storage space for the "swap" buckets.
 128  * All entry types can fit into a ordered_hashmap_entry. */
 129 struct swap_entries {
 130         struct ordered_hashmap_entry e[_IDX_SWAP_END - _IDX_SWAP_BEGIN];
 131 };
 132
 133 /* Distance from Initial Bucket */
 134 typedef uint8_t dib_raw_t;
 135 #define DIB_RAW_OVERFLOW ((dib_raw_t)0xfdU)   /* indicates DIB value is greater than representable */
 136 #define DIB_RAW_REHASH   ((dib_raw_t)0xfeU)   /* entry yet to be rehashed during in-place resize */
 137 #define DIB_RAW_FREE     ((dib_raw_t)0xffU)   /* a free bucket */
 138 #define DIB_RAW_INIT     ((char)DIB_RAW_FREE) /* a byte to memset a DIB store with when initializing */
 139
 140 #define DIB_FREE UINT_MAX
 141
 142 #ifdef ENABLE_DEBUG_HASHMAP
 143 struct hashmap_debug_info {
 144         LIST_FIELDS(struct hashmap_debug_info, debug_list);
 145         unsigned max_entries;  /* high watermark of n_entries */
 146
 147         /* who allocated this hashmap */
 148         int line;
 149         const char *file;
 150         const char *func;
 151
 152         /* fields to detect modification while iterating */
 153         unsigned put_count;    /* counts puts into the hashmap */
 154         unsigned rem_count;    /* counts removals from hashmap */
 155         unsigned last_rem_idx; /* remembers last removal index */
 156 };
 157
 158 /* Tracks all existing hashmaps. Get at it from gdb. See sd_dump_hashmaps.py */
 159 static LIST_HEAD(struct hashmap_debug_info, hashmap_debug_list);
 160
 161 #define HASHMAP_DEBUG_FIELDS struct hashmap_debug_info debug;
 162
 163 #else /* !ENABLE_DEBUG_HASHMAP */
 164 #define HASHMAP_DEBUG_FIELDS
 165 #endif /* ENABLE_DEBUG_HASHMAP */
 166
 167 enum HashmapType {
 168         HASHMAP_TYPE_PLAIN,
 169         HASHMAP_TYPE_ORDERED,
 170         HASHMAP_TYPE_SET,
 171         _HASHMAP_TYPE_MAX
 172 };
 173
 174 struct _packed_ indirect_storage {
 175         char    *storage;                  /* where buckets and DIBs are stored */
 176         uint8_t  hash_key[HASH_KEY_SIZE];  /* hash key; changes during resize */
 177
 178         unsigned n_entries;                /* number of stored entries */
 179         unsigned n_buckets;                /* number of buckets */
 180
 181         unsigned idx_lowest_entry;         /* Index below which all buckets are free.
 182                                               Makes "while(hashmap_steal_first())" loops
 183                                               O(n) instead of O(n^2) for unordered hashmaps. */
 184         uint8_t  _pad[3];                  /* padding for the whole HashmapBase */
 185         /* The bitfields in HashmapBase complete the alignment of the whole thing. */
 186 };
 187
 188 struct direct_storage {
 189         /* This gives us 39 bytes on 64bit, or 35 bytes on 32bit.
 190          * That's room for 4 set_entries + 4 DIB bytes + 3 unused bytes on 64bit,
 191          *              or 7 set_entries + 7 DIB bytes + 0 unused bytes on 32bit. */
 192         char storage[sizeof(struct indirect_storage)];
 193 };
 194
 195 #define DIRECT_BUCKETS(entry_t) \
 196         (sizeof(struct direct_storage) / (sizeof(entry_t) + sizeof(dib_raw_t)))
 197
 198 /* We should be able to store at least one entry directly. */
 199 assert_cc(DIRECT_BUCKETS(struct ordered_hashmap_entry) >= 1);
 200
 201 /* We have 3 bits for n_direct_entries. */
 202 assert_cc(DIRECT_BUCKETS(struct set_entry) < (1 << 3));
 203
 204 /* Hashmaps with directly stored entries all use this shared hash key.
 205  * It's no big deal if the key is guessed, because there can be only
 206  * a handful of directly stored entries in a hashmap. When a hashmap
 207  * outgrows direct storage, it gets its own key for indirect storage. */
 208 static uint8_t shared_hash_key[HASH_KEY_SIZE];
 209 static bool shared_hash_key_initialized;
 210
 211 /* Fields that all hashmap/set types must have */
 212 struct HashmapBase {
 213         const struct hash_ops *hash_ops;  /* hash and compare ops to use */
 214
 215         union _packed_ {
 216                 struct indirect_storage indirect; /* if  has_indirect */
 217                 struct direct_storage direct;     /* if !has_indirect */
 218         };
 219
 220         enum HashmapType type:2;     /* HASHMAP_TYPE_* */
 221         bool has_indirect:1;         /* whether indirect storage is used */
 222         unsigned n_direct_entries:3; /* Number of entries in direct storage.
 223                                       * Only valid if !has_indirect. */
 224         bool from_pool:1;            /* whether was allocated from mempool */
 225         HASHMAP_DEBUG_FIELDS         /* optional hashmap_debug_info */
 226 };
 227
 228 /* Specific hash types
 229  * HashmapBase must be at the beginning of each hashmap struct. */
 230
 231 struct Hashmap {
 232         struct HashmapBase b;
 233 };
 234
 235 struct OrderedHashmap {
 236         struct HashmapBase b;
 237         unsigned iterate_list_head, iterate_list_tail;
 238 };
 239
 240 struct Set {
 241         struct HashmapBase b;
 242 };
 243
 244 DEFINE_MEMPOOL(hashmap_pool,         Hashmap,        8);
 245 DEFINE_MEMPOOL(ordered_hashmap_pool, OrderedHashmap, 8);
 246 /* No need for a separate Set pool */
 247 assert_cc(sizeof(Hashmap) == sizeof(Set));
 248
 249 struct hashmap_type_info {
 250         size_t head_size;
 251         size_t entry_size;
 252         struct mempool *mempool;
 253         unsigned n_direct_buckets;
 254 };
 255
 256 static const struct hashmap_type_info hashmap_type_info[_HASHMAP_TYPE_MAX] = {
 257         [HASHMAP_TYPE_PLAIN] = {
 258                 .head_size        = sizeof(Hashmap),
 259                 .entry_size       = sizeof(struct plain_hashmap_entry),
 260                 .mempool          = &hashmap_pool,
 261                 .n_direct_buckets = DIRECT_BUCKETS(struct plain_hashmap_entry),
 262         },
 263         [HASHMAP_TYPE_ORDERED] = {
 264                 .head_size        = sizeof(OrderedHashmap),
 265                 .entry_size       = sizeof(struct ordered_hashmap_entry),
 266                 .mempool          = &ordered_hashmap_pool,
 267                 .n_direct_buckets = DIRECT_BUCKETS(struct ordered_hashmap_entry),
 268         },
 269         [HASHMAP_TYPE_SET] = {
 270                 .head_size        = sizeof(Set),
 271                 .entry_size       = sizeof(struct set_entry),
 272                 .mempool          = &hashmap_pool,
 273                 .n_direct_buckets = DIRECT_BUCKETS(struct set_entry),
 274         },
 275 };
 276
 277 unsigned long string_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) {
 278         uint64_t u;
 279         siphash24((uint8_t*) &u, p, strlen(p), hash_key);
 280         return (unsigned long) u;
 281 }
 282
 283 int string_compare_func(const void *a, const void *b) {
 284         return strcmp(a, b);
 285 }
 286
 287 const struct hash_ops string_hash_ops = {
 288         .hash = string_hash_func,
 289         .compare = string_compare_func
 290 };
 291
 292 unsigned long trivial_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) {
 293         uint64_t u;
 294         siphash24((uint8_t*) &u, &p, sizeof(p), hash_key);
 295         return (unsigned long) u;
 296 }
 297
 298 int trivial_compare_func(const void *a, const void *b) {
 299         return a < b ? -1 : (a > b ? 1 : 0);
 300 }
 301
 302 const struct hash_ops trivial_hash_ops = {
 303         .hash = trivial_hash_func,
 304         .compare = trivial_compare_func
 305 };
 306
 307 unsigned long uint64_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) {
 308         uint64_t u;
 309         siphash24((uint8_t*) &u, p, sizeof(uint64_t), hash_key);
 310         return (unsigned long) u;
 311 }
 312
 313 int uint64_compare_func(const void *_a, const void *_b) {
 314         uint64_t a, b;
 315         a = *(const uint64_t*) _a;
 316         b = *(const uint64_t*) _b;
 317         return a < b ? -1 : (a > b ? 1 : 0);
 318 }
 319
 320 const struct hash_ops uint64_hash_ops = {
 321         .hash = uint64_hash_func,
 322         .compare = uint64_compare_func
 323 };
 324
 325 #if SIZEOF_DEV_T != 8
 326 unsigned long devt_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) {
 327         uint64_t u;
 328         siphash24((uint8_t*) &u, p, sizeof(dev_t), hash_key);
 329         return (unsigned long) u;
 330 }
 331
 332 int devt_compare_func(const void *_a, const void *_b) {
 333         dev_t a, b;
 334         a = *(const dev_t*) _a;
 335         b = *(const dev_t*) _b;
 336         return a < b ? -1 : (a > b ? 1 : 0);
 337 }
 338
 339 const struct hash_ops devt_hash_ops = {
 340         .hash = devt_hash_func,
 341         .compare = devt_compare_func
 342 };
 343 #endif
 344
 345 static unsigned n_buckets(HashmapBase *h) {
 346         return h->has_indirect ? h->indirect.n_buckets
 347                                : hashmap_type_info[h->type].n_direct_buckets;
 348 }
 349
 350 static unsigned n_entries(HashmapBase *h) {
 351         return h->has_indirect ? h->indirect.n_entries
 352                                : h->n_direct_entries;
 353 }
 354
 355 static void n_entries_inc(HashmapBase *h) {
 356         if (h->has_indirect)
 357                 h->indirect.n_entries++;
 358         else
 359                 h->n_direct_entries++;
 360 }
 361
 362 static void n_entries_dec(HashmapBase *h) {
 363         if (h->has_indirect)
 364                 h->indirect.n_entries--;
 365         else
 366                 h->n_direct_entries--;
 367 }
 368
 369 static char *storage_ptr(HashmapBase *h) {
 370         return h->has_indirect ? h->indirect.storage
 371                                : h->direct.storage;
 372 }
 373
 374 static uint8_t *hash_key(HashmapBase *h) {
 375         return h->has_indirect ? h->indirect.hash_key
 376                                : shared_hash_key;
 377 }
 378
 379 static unsigned base_bucket_hash(HashmapBase *h, const void *p) {
 380         return (unsigned) (h->hash_ops->hash(p, hash_key(h)) % n_buckets(h));
 381 }
 382 #define bucket_hash(h, p) base_bucket_hash(HASHMAP_BASE(h), p)
 383
 384 static void get_hash_key(uint8_t hash_key[HASH_KEY_SIZE], bool reuse_is_ok) {
 385         static uint8_t current[HASH_KEY_SIZE];
 386         static bool current_initialized = false;
 387
 388         /* Returns a hash function key to use. In order to keep things
 389          * fast we will not generate a new key each time we allocate a
 390          * new hash table. Instead, we'll just reuse the most recently
 391          * generated one, except if we never generated one or when we
 392          * are rehashing an entire hash table because we reached a
 393          * fill level */
 394
 395         if (!current_initialized || !reuse_is_ok) {
 396                 random_bytes(current, sizeof(current));
 397                 current_initialized = true;
 398         }
 399
 400         memcpy(hash_key, current, sizeof(current));
 401 }
 402
 403 static struct hashmap_base_entry *bucket_at(HashmapBase *h, unsigned idx) {
 404         return (struct hashmap_base_entry*)
 405                 (storage_ptr(h) + idx * hashmap_type_info[h->type].entry_size);
 406 }
 407
 408 static struct plain_hashmap_entry *plain_bucket_at(Hashmap *h, unsigned idx) {
 409         return (struct plain_hashmap_entry*) bucket_at(HASHMAP_BASE(h), idx);
 410 }
 411
 412 static struct ordered_hashmap_entry *ordered_bucket_at(OrderedHashmap *h, unsigned idx) {
 413         return (struct ordered_hashmap_entry*) bucket_at(HASHMAP_BASE(h), idx);
 414 }
 415
 416 static struct set_entry *set_bucket_at(Set *h, unsigned idx) {
 417         return (struct set_entry*) bucket_at(HASHMAP_BASE(h), idx);
 418 }
 419
 420 static struct ordered_hashmap_entry *bucket_at_swap(struct swap_entries *swap, unsigned idx) {
 421         return &swap->e[idx - _IDX_SWAP_BEGIN];
 422 }
 423
 424 /* Returns a pointer to the bucket at index idx.
 425  * Understands real indexes and swap indexes, hence "_virtual". */
 426 static struct hashmap_base_entry *bucket_at_virtual(HashmapBase *h, struct swap_entries *swap,
 427                                                     unsigned idx) {
 428         if (idx < _IDX_SWAP_BEGIN)
 429                 return bucket_at(h, idx);
 430
 431         if (idx < _IDX_SWAP_END)
 432                 return &bucket_at_swap(swap, idx)->p.b;
 433
 434         assert_not_reached("Invalid index");
 435 }
 436
 437 static dib_raw_t *dib_raw_ptr(HashmapBase *h) {
 438         return (dib_raw_t*)
 439                 (storage_ptr(h) + hashmap_type_info[h->type].entry_size * n_buckets(h));
 440 }
 441
 442 static unsigned bucket_distance(HashmapBase *h, unsigned idx, unsigned from) {
 443         return idx >= from ? idx - from
 444                            : n_buckets(h) + idx - from;
 445 }
 446
 447 static unsigned bucket_calculate_dib(HashmapBase *h, unsigned idx, dib_raw_t raw_dib) {
 448         unsigned initial_bucket;
 449
 450         if (raw_dib == DIB_RAW_FREE)
 451                 return DIB_FREE;
 452
 453         if (_likely_(raw_dib < DIB_RAW_OVERFLOW))
 454                 return raw_dib;
 455
 456         /*
 457          * Having an overflow DIB value is very unlikely. The hash function
 458          * would have to be bad. For example, in a table of size 2^24 filled
 459          * to load factor 0.9 the maximum observed DIB is only about 60.
 460          * In theory (assuming I used Maxima correctly), for an infinite size
 461          * hash table with load factor 0.8 the probability of a given entry
 462          * having DIB > 40 is 1.9e-8.
 463          * This returns the correct DIB value by recomputing the hash value in
 464          * the unlikely case. XXX Hitting this case could be a hint to rehash.
 465          */
 466         initial_bucket = bucket_hash(h, bucket_at(h, idx)->key);
 467         return bucket_distance(h, idx, initial_bucket);
 468 }
 469
 470 static void bucket_set_dib(HashmapBase *h, unsigned idx, unsigned dib) {
 471         dib_raw_ptr(h)[idx] = dib != DIB_FREE ? MIN(dib, DIB_RAW_OVERFLOW) : DIB_RAW_FREE;
 472 }
 473
 474 static unsigned skip_free_buckets(HashmapBase *h, unsigned idx) {
 475         dib_raw_t *dibs;
 476
 477         dibs = dib_raw_ptr(h);
 478
 479         for ( ; idx < n_buckets(h); idx++)
 480                 if (dibs[idx] != DIB_RAW_FREE)
 481                         return idx;
 482
 483         return IDX_NIL;
 484 }
 485
 486 static void bucket_mark_free(HashmapBase *h, unsigned idx) {
 487         memzero(bucket_at(h, idx), hashmap_type_info[h->type].entry_size);
 488         bucket_set_dib(h, idx, DIB_FREE);
 489 }
 490
 491 static void bucket_move_entry(HashmapBase *h, struct swap_entries *swap,
 492                               unsigned from, unsigned to) {
 493         struct hashmap_base_entry *e_from, *e_to;
 494
 495         assert(from != to);
 496
 497         e_from = bucket_at_virtual(h, swap, from);
 498         e_to   = bucket_at_virtual(h, swap, to);
 499
 500         memcpy(e_to, e_from, hashmap_type_info[h->type].entry_size);
 501
 502         if (h->type == HASHMAP_TYPE_ORDERED) {
 503                 OrderedHashmap *lh = (OrderedHashmap*) h;
 504                 struct ordered_hashmap_entry *le, *le_to;
 505
 506                 le_to = (struct ordered_hashmap_entry*) e_to;
 507
 508                 if (le_to->iterate_next != IDX_NIL) {
 509                         le = (struct ordered_hashmap_entry*)
 510                              bucket_at_virtual(h, swap, le_to->iterate_next);
 511                         le->iterate_previous = to;
 512                 }
 513
 514                 if (le_to->iterate_previous != IDX_NIL) {
 515                         le = (struct ordered_hashmap_entry*)
 516                              bucket_at_virtual(h, swap, le_to->iterate_previous);
 517                         le->iterate_next = to;
 518                 }
 519
 520                 if (lh->iterate_list_head == from)
 521                         lh->iterate_list_head = to;
 522                 if (lh->iterate_list_tail == from)
 523                         lh->iterate_list_tail = to;
 524         }
 525 }
 526
 527 static unsigned next_idx(HashmapBase *h, unsigned idx) {
 528         return (idx + 1U) % n_buckets(h);
 529 }
 530
 531 static unsigned prev_idx(HashmapBase *h, unsigned idx) {
 532         return (n_buckets(h) + idx - 1U) % n_buckets(h);
 533 }
 534
 535 static void *entry_value(HashmapBase *h, struct hashmap_base_entry *e) {
 536         switch (h->type) {
 537
 538         case HASHMAP_TYPE_PLAIN:
 539         case HASHMAP_TYPE_ORDERED:
 540                 return ((struct plain_hashmap_entry*)e)->value;
 541
 542         case HASHMAP_TYPE_SET:
 543                 return (void*) e->key;
 544
 545         default:
 546                 assert_not_reached("Unknown hashmap type");
 547         }
 548 }
 549
 550 static void base_remove_entry(HashmapBase *h, unsigned idx) {
 551         unsigned left, right, prev, dib;
 552         dib_raw_t raw_dib, *dibs;
 553
 554         dibs = dib_raw_ptr(h);
 555         assert(dibs[idx] != DIB_RAW_FREE);
 556
 557 #ifdef ENABLE_DEBUG_HASHMAP
 558         h->debug.rem_count++;
 559         h->debug.last_rem_idx = idx;
 560 #endif
 561
 562         left = idx;
 563         /* Find the stop bucket ("right"). It is either free or has DIB == 0. */
 564         for (right = next_idx(h, left); ; right = next_idx(h, right)) {
 565                 raw_dib = dibs[right];
 566                 if (raw_dib == 0 || raw_dib == DIB_RAW_FREE)
 567                         break;
 568
 569                 /* The buckets are not supposed to be all occupied and with DIB > 0.
 570                  * That would mean we could make everyone better off by shifting them
 571                  * backward. This scenario is impossible. */
 572                 assert(left != right);
 573         }
 574
 575         if (h->type == HASHMAP_TYPE_ORDERED) {
 576                 OrderedHashmap *lh = (OrderedHashmap*) h;
 577                 struct ordered_hashmap_entry *le = ordered_bucket_at(lh, idx);
 578
 579                 if (le->iterate_next != IDX_NIL)
 580                         ordered_bucket_at(lh, le->iterate_next)->iterate_previous = le->iterate_previous;
 581                 else
 582                         lh->iterate_list_tail = le->iterate_previous;
 583
 584                 if (le->iterate_previous != IDX_NIL)
 585                         ordered_bucket_at(lh, le->iterate_previous)->iterate_next = le->iterate_next;
 586                 else
 587                         lh->iterate_list_head = le->iterate_next;
 588         }
 589
 590         /* Now shift all buckets in the interval (left, right) one step backwards */
 591         for (prev = left, left = next_idx(h, left); left != right;
 592              prev = left, left = next_idx(h, left)) {
 593                 dib = bucket_calculate_dib(h, left, dibs[left]);
 594                 assert(dib != 0);
 595                 bucket_move_entry(h, NULL, left, prev);
 596                 bucket_set_dib(h, prev, dib - 1);
 597         }
 598
 599         bucket_mark_free(h, prev);
 600         n_entries_dec(h);
 601 }
 602 #define remove_entry(h, idx) base_remove_entry(HASHMAP_BASE(h), idx)
 603
 604 static unsigned hashmap_iterate_in_insertion_order(OrderedHashmap *h, Iterator *i) {
 605         struct ordered_hashmap_entry *e;
 606         unsigned idx;
 607
 608         assert(h);
 609         assert(i);
 610
 611         if (i->idx == IDX_NIL)
 612                 goto at_end;
 613
 614         if (i->idx == IDX_FIRST && h->iterate_list_head == IDX_NIL)
 615                 goto at_end;
 616
 617         if (i->idx == IDX_FIRST) {
 618                 idx = h->iterate_list_head;
 619                 e = ordered_bucket_at(h, idx);
 620         } else {
 621                 idx = i->idx;
 622                 e = ordered_bucket_at(h, idx);
 623                 /*
 624                  * We allow removing the current entry while iterating, but removal may cause
 625                  * a backward shift. The next entry may thus move one bucket to the left.
 626                  * To detect when it happens, we remember the key pointer of the entry we were
 627                  * going to iterate next. If it does not match, there was a backward shift.
 628                  */
 629                 if (e->p.b.key != i->next_key) {
 630                         idx = prev_idx(HASHMAP_BASE(h), idx);
 631                         e = ordered_bucket_at(h, idx);
 632                 }
 633                 assert(e->p.b.key == i->next_key);
 634         }
 635
 636 #ifdef ENABLE_DEBUG_HASHMAP
 637         i->prev_idx = idx;
 638 #endif
 639
 640         if (e->iterate_next != IDX_NIL) {
 641                 struct ordered_hashmap_entry *n;
 642                 i->idx = e->iterate_next;
 643                 n = ordered_bucket_at(h, i->idx);
 644                 i->next_key = n->p.b.key;
 645         } else
 646                 i->idx = IDX_NIL;
 647
 648         return idx;
 649
 650 at_end:
 651         i->idx = IDX_NIL;
 652         return IDX_NIL;
 653 }
 654
 655 static unsigned hashmap_iterate_in_internal_order(HashmapBase *h, Iterator *i) {
 656         unsigned idx;
 657
 658         assert(h);
 659         assert(i);
 660
 661         if (i->idx == IDX_NIL)
 662                 goto at_end;
 663
 664         if (i->idx == IDX_FIRST) {
 665                 /* fast forward to the first occupied bucket */
 666                 if (h->has_indirect) {
 667                         i->idx = skip_free_buckets(h, h->indirect.idx_lowest_entry);
 668                         h->indirect.idx_lowest_entry = i->idx;
 669                 } else
 670                         i->idx = skip_free_buckets(h, 0);
 671
 672                 if (i->idx == IDX_NIL)
 673                         goto at_end;
 674         } else {
 675                 struct hashmap_base_entry *e;
 676
 677                 assert(i->idx > 0);
 678
 679                 e = bucket_at(h, i->idx);
 680                 /*
 681                  * We allow removing the current entry while iterating, but removal may cause
 682                  * a backward shift. The next entry may thus move one bucket to the left.
 683                  * To detect when it happens, we remember the key pointer of the entry we were
 684                  * going to iterate next. If it does not match, there was a backward shift.
 685                  */
 686                 if (e->key != i->next_key)
 687                         e = bucket_at(h, --i->idx);
 688
 689                 assert(e->key == i->next_key);
 690         }
 691
 692         idx = i->idx;
 693 #ifdef ENABLE_DEBUG_HASHMAP
 694         i->prev_idx = idx;
 695 #endif
 696
 697         i->idx = skip_free_buckets(h, i->idx + 1);
 698         if (i->idx != IDX_NIL)
 699                 i->next_key = bucket_at(h, i->idx)->key;
 700         else
 701                 i->idx = IDX_NIL;
 702
 703         return idx;
 704
 705 at_end:
 706         i->idx = IDX_NIL;
 707         return IDX_NIL;
 708 }
 709
 710 static unsigned hashmap_iterate_entry(HashmapBase *h, Iterator *i) {
 711         if (!h) {
 712                 i->idx = IDX_NIL;
 713                 return IDX_NIL;
 714         }
 715
 716 #ifdef ENABLE_DEBUG_HASHMAP
 717         if (i->idx == IDX_FIRST) {
 718                 i->put_count = h->debug.put_count;
 719                 i->rem_count = h->debug.rem_count;
 720         } else {
 721                 /* While iterating, must not add any new entries */
 722                 assert(i->put_count == h->debug.put_count);
 723                 /* ... or remove entries other than the current one */
 724                 assert(i->rem_count == h->debug.rem_count ||
 725                        (i->rem_count == h->debug.rem_count - 1 &&
 726                         i->prev_idx == h->debug.last_rem_idx));
 727                 /* Reset our removals counter */
 728                 i->rem_count = h->debug.rem_count;
 729         }
 730 #endif
 731
 732         return h->type == HASHMAP_TYPE_ORDERED ? hashmap_iterate_in_insertion_order((OrderedHashmap*) h, i)
 733                                                : hashmap_iterate_in_internal_order(h, i);
 734 }
 735
 736 bool internal_hashmap_iterate(HashmapBase *h, Iterator *i, void **value, const void **key) {
 737         struct hashmap_base_entry *e;
 738         void *data;
 739         unsigned idx;
 740
 741         idx = hashmap_iterate_entry(h, i);
 742         if (idx == IDX_NIL) {
 743                 if (value)
 744                         *value = NULL;
 745                 if (key)
 746                         *key = NULL;
 747
 748                 return false;
 749         }
 750
 751         e = bucket_at(h, idx);
 752         data = entry_value(h, e);
 753         if (value)
 754                 *value = data;
 755         if (key)
 756                 *key = e->key;
 757
 758         return true;
 759 }
 760
 761 bool set_iterate(Set *s, Iterator *i, void **value) {
 762         return internal_hashmap_iterate(HASHMAP_BASE(s), i, value, NULL);
 763 }
 764
 765 #define HASHMAP_FOREACH_IDX(idx, h, i) \
 766         for ((i) = ITERATOR_FIRST, (idx) = hashmap_iterate_entry((h), &(i)); \
 767              (idx != IDX_NIL); \
 768              (idx) = hashmap_iterate_entry((h), &(i)))
 769
 770 static void reset_direct_storage(HashmapBase *h) {
 771         const struct hashmap_type_info *hi = &hashmap_type_info[h->type];
 772         void *p;
 773
 774         assert(!h->has_indirect);
 775
 776         p = mempset(h->direct.storage, 0, hi->entry_size * hi->n_direct_buckets);
 777         memset(p, DIB_RAW_INIT, sizeof(dib_raw_t) * hi->n_direct_buckets);
 778 }
 779
 780 static struct HashmapBase *hashmap_base_new(const struct hash_ops *hash_ops, enum HashmapType type HASHMAP_DEBUG_PARAMS) {
 781         HashmapBase *h;
 782         const struct hashmap_type_info *hi = &hashmap_type_info[type];
 783         bool use_pool;
 784
 785         use_pool = is_main_thread();
 786
 787         h = use_pool ? mempool_alloc0_tile(hi->mempool) : malloc0(hi->head_size);
 788
 789         if (!h)
 790                 return NULL;
 791
 792         h->type = type;
 793         h->from_pool = use_pool;
 794         h->hash_ops = hash_ops ? hash_ops : &trivial_hash_ops;
 795
 796         if (type == HASHMAP_TYPE_ORDERED) {
 797                 OrderedHashmap *lh = (OrderedHashmap*)h;
 798                 lh->iterate_list_head = lh->iterate_list_tail = IDX_NIL;
 799         }
 800
 801         reset_direct_storage(h);
 802
 803         if (!shared_hash_key_initialized) {
 804                 random_bytes(shared_hash_key, sizeof(shared_hash_key));
 805                 shared_hash_key_initialized= true;
 806         }
 807
 808 #ifdef ENABLE_DEBUG_HASHMAP
 809         LIST_PREPEND(debug_list, hashmap_debug_list, &h->debug);
 810         h->debug.func = func;
 811         h->debug.file = file;
 812         h->debug.line = line;
 813 #endif
 814
 815         return h;
 816 }
 817
 818 Hashmap *internal_hashmap_new(const struct hash_ops *hash_ops  HASHMAP_DEBUG_PARAMS) {
 819         return (Hashmap*)        hashmap_base_new(hash_ops, HASHMAP_TYPE_PLAIN HASHMAP_DEBUG_PASS_ARGS);
 820 }
 821
 822 OrderedHashmap *internal_ordered_hashmap_new(const struct hash_ops *hash_ops  HASHMAP_DEBUG_PARAMS) {
 823         return (OrderedHashmap*) hashmap_base_new(hash_ops, HASHMAP_TYPE_ORDERED HASHMAP_DEBUG_PASS_ARGS);
 824 }
 825
 826 Set *internal_set_new(const struct hash_ops *hash_ops  HASHMAP_DEBUG_PARAMS) {
 827         return (Set*)            hashmap_base_new(hash_ops, HASHMAP_TYPE_SET HASHMAP_DEBUG_PASS_ARGS);
 828 }
 829
 830 static int hashmap_base_ensure_allocated(HashmapBase **h, const struct hash_ops *hash_ops,
 831                                          enum HashmapType type HASHMAP_DEBUG_PARAMS) {
 832         HashmapBase *q;
 833
 834         assert(h);
 835
 836         if (*h)
 837                 return 0;
 838
 839         q = hashmap_base_new(hash_ops, type HASHMAP_DEBUG_PASS_ARGS);
 840         if (!q)
 841                 return -ENOMEM;
 842
 843         *h = q;
 844         return 0;
 845 }
 846
 847 int internal_hashmap_ensure_allocated(Hashmap **h, const struct hash_ops *hash_ops  HASHMAP_DEBUG_PARAMS) {
 848         return hashmap_base_ensure_allocated((HashmapBase**)h, hash_ops, HASHMAP_TYPE_PLAIN HASHMAP_DEBUG_PASS_ARGS);
 849 }
 850
 851 int internal_ordered_hashmap_ensure_allocated(OrderedHashmap **h, const struct hash_ops *hash_ops  HASHMAP_DEBUG_PARAMS) {
 852         return hashmap_base_ensure_allocated((HashmapBase**)h, hash_ops, HASHMAP_TYPE_ORDERED HASHMAP_DEBUG_PASS_ARGS);
 853 }
 854
 855 int internal_set_ensure_allocated(Set **s, const struct hash_ops *hash_ops  HASHMAP_DEBUG_PARAMS) {
 856         return hashmap_base_ensure_allocated((HashmapBase**)s, hash_ops, HASHMAP_TYPE_SET HASHMAP_DEBUG_PASS_ARGS);
 857 }
 858
 859 static void hashmap_free_no_clear(HashmapBase *h) {
 860         assert(!h->has_indirect);
 861         assert(!h->n_direct_entries);
 862
 863 #ifdef ENABLE_DEBUG_HASHMAP
 864         LIST_REMOVE(debug_list, hashmap_debug_list, &h->debug);
 865 #endif
 866
 867         if (h->from_pool)
 868                 mempool_free_tile(hashmap_type_info[h->type].mempool, h);
 869         else
 870                 free(h);
 871 }
 872
 873 HashmapBase *internal_hashmap_free(HashmapBase *h) {
 874
 875         /* Free the hashmap, but nothing in it */
 876
 877         if (h) {
 878                 internal_hashmap_clear(h);
 879                 hashmap_free_no_clear(h);
 880         }
 881
 882         return NULL;
 883 }
 884
 885 HashmapBase *internal_hashmap_free_free(HashmapBase *h) {
 886
 887         /* Free the hashmap and all data objects in it, but not the
 888          * keys */
 889
 890         if (h) {
 891                 internal_hashmap_clear_free(h);
 892                 hashmap_free_no_clear(h);
 893         }
 894
 895         return NULL;
 896 }
 897
 898 Hashmap *hashmap_free_free_free(Hashmap *h) {
 899
 900         /* Free the hashmap and all data and key objects in it */
 901
 902         if (h) {
 903                 hashmap_clear_free_free(h);
 904                 hashmap_free_no_clear(HASHMAP_BASE(h));
 905         }
 906
 907         return NULL;
 908 }
 909
 910 void internal_hashmap_clear(HashmapBase *h) {
 911         if (!h)
 912                 return;
 913
 914         if (h->has_indirect) {
 915                 free(h->indirect.storage);
 916                 h->has_indirect = false;
 917         }
 918
 919         h->n_direct_entries = 0;
 920         reset_direct_storage(h);
 921
 922         if (h->type == HASHMAP_TYPE_ORDERED) {
 923                 OrderedHashmap *lh = (OrderedHashmap*) h;
 924                 lh->iterate_list_head = lh->iterate_list_tail = IDX_NIL;
 925         }
 926 }
 927
 928 void internal_hashmap_clear_free(HashmapBase *h) {
 929         unsigned idx;
 930
 931         if (!h)
 932                 return;
 933
 934         for (idx = skip_free_buckets(h, 0); idx != IDX_NIL;
 935              idx = skip_free_buckets(h, idx + 1))
 936                 free(entry_value(h, bucket_at(h, idx)));
 937
 938         internal_hashmap_clear(h);
 939 }
 940
 941 void hashmap_clear_free_free(Hashmap *h) {
 942         unsigned idx;
 943
 944         if (!h)
 945                 return;
 946
 947         for (idx = skip_free_buckets(HASHMAP_BASE(h), 0); idx != IDX_NIL;
 948              idx = skip_free_buckets(HASHMAP_BASE(h), idx + 1)) {
 949                 struct plain_hashmap_entry *e = plain_bucket_at(h, idx);
 950                 free((void*)e->b.key);
 951                 free(e->value);
 952         }
 953
 954         internal_hashmap_clear(HASHMAP_BASE(h));
 955 }
 956
 957 static int resize_buckets(HashmapBase *h, unsigned entries_add);
 958
 959 /*
 960  * Finds an empty bucket to put an entry into, starting the scan at 'idx'.
 961  * Performs Robin Hood swaps as it goes. The entry to put must be placed
 962  * by the caller into swap slot IDX_PUT.
 963  * If used for in-place resizing, may leave a displaced entry in swap slot
 964  * IDX_PUT. Caller must rehash it next.
 965  * Returns: true if it left a displaced entry to rehash next in IDX_PUT,
 966  *          false otherwise.
 967  */
 968 static bool hashmap_put_robin_hood(HashmapBase *h, unsigned idx,
 969                                    struct swap_entries *swap) {
 970         dib_raw_t raw_dib, *dibs;
 971         unsigned dib, distance;
 972
 973 #ifdef ENABLE_DEBUG_HASHMAP
 974         h->debug.put_count++;
 975 #endif
 976
 977         dibs = dib_raw_ptr(h);
 978
 979         for (distance = 0; ; distance++) {
 980                 raw_dib = dibs[idx];
 981                 if (raw_dib == DIB_RAW_FREE || raw_dib == DIB_RAW_REHASH) {
 982                         if (raw_dib == DIB_RAW_REHASH)
 983                                 bucket_move_entry(h, swap, idx, IDX_TMP);
 984
 985                         if (h->has_indirect && h->indirect.idx_lowest_entry > idx)
 986                                 h->indirect.idx_lowest_entry = idx;
 987
 988                         bucket_set_dib(h, idx, distance);
 989                         bucket_move_entry(h, swap, IDX_PUT, idx);
 990                         if (raw_dib == DIB_RAW_REHASH) {
 991                                 bucket_move_entry(h, swap, IDX_TMP, IDX_PUT);
 992                                 return true;
 993                         }
 994
 995                         return false;
 996                 }
 997
 998                 dib = bucket_calculate_dib(h, idx, raw_dib);
 999
1000                 if (dib < distance) {
1001                         /* Found a wealthier entry. Go Robin Hood! */
1002                         bucket_set_dib(h, idx, distance);
1003
1004                         /* swap the entries */
1005                         bucket_move_entry(h, swap, idx, IDX_TMP);
1006                         bucket_move_entry(h, swap, IDX_PUT, idx);
1007                         bucket_move_entry(h, swap, IDX_TMP, IDX_PUT);
1008
1009                         distance = dib;
1010                 }
1011
1012                 idx = next_idx(h, idx);
1013         }
1014 }
1015
1016 /*
1017  * Puts an entry into a hashmap, boldly - no check whether key already exists.
1018  * The caller must place the entry (only its key and value, not link indexes)
1019  * in swap slot IDX_PUT.
1020  * Caller must ensure: the key does not exist yet in the hashmap.
1021  *                     that resize is not needed if !may_resize.
1022  * Returns: 1 if entry was put successfully.
1023  *          -ENOMEM if may_resize==true and resize failed with -ENOMEM.
1024  *          Cannot return -ENOMEM if !may_resize.
1025  */
1026 static int hashmap_base_put_boldly(HashmapBase *h, unsigned idx,
1027                                    struct swap_entries *swap, bool may_resize) {
1028         struct ordered_hashmap_entry *new_entry;
1029         int r;
1030
1031         assert(idx < n_buckets(h));
1032
1033         new_entry = bucket_at_swap(swap, IDX_PUT);
1034
1035         if (may_resize) {
1036                 r = resize_buckets(h, 1);
1037                 if (r < 0)
1038                         return r;
1039                 if (r > 0)
1040                         idx = bucket_hash(h, new_entry->p.b.key);
1041         }
1042         assert(n_entries(h) < n_buckets(h));
1043
1044         if (h->type == HASHMAP_TYPE_ORDERED) {
1045                 OrderedHashmap *lh = (OrderedHashmap*) h;
1046
1047                 new_entry->iterate_next = IDX_NIL;
1048                 new_entry->iterate_previous = lh->iterate_list_tail;
1049
1050                 if (lh->iterate_list_tail != IDX_NIL) {
1051                         struct ordered_hashmap_entry *old_tail;
1052
1053                         old_tail = ordered_bucket_at(lh, lh->iterate_list_tail);
1054                         assert(old_tail->iterate_next == IDX_NIL);
1055                         old_tail->iterate_next = IDX_PUT;
1056                 }
1057
1058                 lh->iterate_list_tail = IDX_PUT;
1059                 if (lh->iterate_list_head == IDX_NIL)
1060                         lh->iterate_list_head = IDX_PUT;
1061         }
1062
1063         assert_se(hashmap_put_robin_hood(h, idx, swap) == false);
1064
1065         n_entries_inc(h);
1066 #ifdef ENABLE_DEBUG_HASHMAP
1067         h->debug.max_entries = MAX(h->debug.max_entries, n_entries(h));
1068 #endif
1069
1070         return 1;
1071 }
1072 #define hashmap_put_boldly(h, idx, swap, may_resize) \
1073         hashmap_base_put_boldly(HASHMAP_BASE(h), idx, swap, may_resize)
1074
1075 /*
1076  * Returns 0 if resize is not needed.
1077  *         1 if successfully resized.
1078  *         -ENOMEM on allocation failure.
1079  */
1080 static int resize_buckets(HashmapBase *h, unsigned entries_add) {
1081         struct swap_entries swap;
1082         char *new_storage;
1083         dib_raw_t *old_dibs, *new_dibs;
1084         const struct hashmap_type_info *hi;
1085         unsigned idx, optimal_idx;
1086         unsigned old_n_buckets, new_n_buckets, n_rehashed, new_n_entries;
1087         uint8_t new_shift;
1088         bool rehash_next;
1089
1090         assert(h);
1091
1092         hi = &hashmap_type_info[h->type];
1093         new_n_entries = n_entries(h) + entries_add;
1094
1095         /* overflow? */
1096         if (_unlikely_(new_n_entries < entries_add))
1097                 return -ENOMEM;
1098
1099         /* For direct storage we allow 100% load, because it's tiny. */
1100         if (!h->has_indirect && new_n_entries <= hi->n_direct_buckets)
1101                 return 0;
1102
1103         /*
1104          * Load factor = n/m = 1 - (1/INV_KEEP_FREE).
1105          * From it follows: m = n + n/(INV_KEEP_FREE - 1)
1106          */
1107         new_n_buckets = new_n_entries + new_n_entries / (INV_KEEP_FREE - 1);
1108         /* overflow? */
1109         if (_unlikely_(new_n_buckets < new_n_entries))
1110                 return -ENOMEM;
1111
1112         if (_unlikely_(new_n_buckets > UINT_MAX / (hi->entry_size + sizeof(dib_raw_t))))
1113                 return -ENOMEM;
1114
1115         old_n_buckets = n_buckets(h);
1116
1117         if (_likely_(new_n_buckets <= old_n_buckets))
1118                 return 0;
1119
1120         new_shift = log2u_round_up(MAX(
1121                         new_n_buckets * (hi->entry_size + sizeof(dib_raw_t)),
1122                         2 * sizeof(struct direct_storage)));
1123
1124         /* Realloc storage (buckets and DIB array). */
1125         new_storage = realloc(h->has_indirect ? h->indirect.storage : NULL,
1126                               1U << new_shift);
1127         if (!new_storage)
1128                 return -ENOMEM;
1129
1130         /* Must upgrade direct to indirect storage. */
1131         if (!h->has_indirect) {
1132                 memcpy(new_storage, h->direct.storage,
1133                        old_n_buckets * (hi->entry_size + sizeof(dib_raw_t)));
1134                 h->indirect.n_entries = h->n_direct_entries;
1135                 h->indirect.idx_lowest_entry = 0;
1136                 h->n_direct_entries = 0;
1137         }
1138
1139         /* Get a new hash key. If we've just upgraded to indirect storage,
1140          * allow reusing a previously generated key. It's still a different key
1141          * from the shared one that we used for direct storage. */
1142         get_hash_key(h->indirect.hash_key, !h->has_indirect);
1143
1144         h->has_indirect = true;
1145         h->indirect.storage = new_storage;
1146         h->indirect.n_buckets = (1U << new_shift) /
1147                                 (hi->entry_size + sizeof(dib_raw_t));
1148
1149         old_dibs = (dib_raw_t*)(new_storage + hi->entry_size * old_n_buckets);
1150         new_dibs = dib_raw_ptr(h);
1151
1152         /*
1153          * Move the DIB array to the new place, replacing valid DIB values with
1154          * DIB_RAW_REHASH to indicate all of the used buckets need rehashing.
1155          * Note: Overlap is not possible, because we have at least doubled the
1156          * number of buckets and dib_raw_t is smaller than any entry type.
1157          */
1158         for (idx = 0; idx < old_n_buckets; idx++) {
1159                 assert(old_dibs[idx] != DIB_RAW_REHASH);
1160                 new_dibs[idx] = old_dibs[idx] == DIB_RAW_FREE ? DIB_RAW_FREE
1161                                                               : DIB_RAW_REHASH;
1162         }
1163
1164         /* Zero the area of newly added entries (including the old DIB area) */
1165         memzero(bucket_at(h, old_n_buckets),
1166                (n_buckets(h) - old_n_buckets) * hi->entry_size);
1167
1168         /* The upper half of the new DIB array needs initialization */
1169         memset(&new_dibs[old_n_buckets], DIB_RAW_INIT,
1170                (n_buckets(h) - old_n_buckets) * sizeof(dib_raw_t));
1171
1172         /* Rehash entries that need it */
1173         n_rehashed = 0;
1174         for (idx = 0; idx < old_n_buckets; idx++) {
1175                 if (new_dibs[idx] != DIB_RAW_REHASH)
1176                         continue;
1177
1178                 optimal_idx = bucket_hash(h, bucket_at(h, idx)->key);
1179
1180                 /*
1181                  * Not much to do if by luck the entry hashes to its current
1182                  * location. Just set its DIB.
1183                  */
1184                 if (optimal_idx == idx) {
1185                         new_dibs[idx] = 0;
1186                         n_rehashed++;
1187                         continue;
1188                 }
1189
1190                 new_dibs[idx] = DIB_RAW_FREE;
1191                 bucket_move_entry(h, &swap, idx, IDX_PUT);
1192                 /* bucket_move_entry does not clear the source */
1193                 memzero(bucket_at(h, idx), hi->entry_size);
1194
1195                 do {
1196                         /*
1197                          * Find the new bucket for the current entry. This may make
1198                          * another entry homeless and load it into IDX_PUT.
1199                          */
1200                         rehash_next = hashmap_put_robin_hood(h, optimal_idx, &swap);
1201                         n_rehashed++;
1202
1203                         /* Did the current entry displace another one? */
1204                         if (rehash_next)
1205                                 optimal_idx = bucket_hash(h, bucket_at_swap(&swap, IDX_PUT)->p.b.key);
1206                 } while (rehash_next);
1207         }
1208
1209         assert(n_rehashed == n_entries(h));
1210
1211         return 1;
1212 }
1213
1214 /*
1215  * Finds an entry with a matching key
1216  * Returns: index of the found entry, or IDX_NIL if not found.
1217  */
1218 static unsigned base_bucket_scan(HashmapBase *h, unsigned idx, const void *key) {
1219         struct hashmap_base_entry *e;
1220         unsigned dib, distance;
1221         dib_raw_t *dibs = dib_raw_ptr(h);
1222
1223         assert(idx < n_buckets(h));
1224
1225         for (distance = 0; ; distance++) {
1226                 if (dibs[idx] == DIB_RAW_FREE)
1227                         return IDX_NIL;
1228
1229                 dib = bucket_calculate_dib(h, idx, dibs[idx]);
1230
1231                 if (dib < distance)
1232                         return IDX_NIL;
1233                 if (dib == distance) {
1234                         e = bucket_at(h, idx);
1235                         if (h->hash_ops->compare(e->key, key) == 0)
1236                                 return idx;
1237                 }
1238
1239                 idx = next_idx(h, idx);
1240         }
1241 }
1242 #define bucket_scan(h, idx, key) base_bucket_scan(HASHMAP_BASE(h), idx, key)
1243
1244 int hashmap_put(Hashmap *h, const void *key, void *value) {
1245         struct swap_entries swap;
1246         struct plain_hashmap_entry *e;
1247         unsigned hash, idx;
1248
1249         assert(h);
1250
1251         hash = bucket_hash(h, key);
1252         idx = bucket_scan(h, hash, key);
1253         if (idx != IDX_NIL) {
1254                 e = plain_bucket_at(h, idx);
1255                 if (e->value == value)
1256                         return 0;
1257                 return -EEXIST;
1258         }
1259
1260         e = &bucket_at_swap(&swap, IDX_PUT)->p;
1261         e->b.key = key;
1262         e->value = value;
1263         return hashmap_put_boldly(h, hash, &swap, true);
1264 }
1265
1266 int set_put(Set *s, const void *key) {
1267         struct swap_entries swap;
1268         struct hashmap_base_entry *e;
1269         unsigned hash, idx;
1270
1271         assert(s);
1272
1273         hash = bucket_hash(s, key);
1274         idx = bucket_scan(s, hash, key);
1275         if (idx != IDX_NIL)
1276                 return 0;
1277
1278         e = &bucket_at_swap(&swap, IDX_PUT)->p.b;
1279         e->key = key;
1280         return hashmap_put_boldly(s, hash, &swap, true);
1281 }
1282
1283 int hashmap_replace(Hashmap *h, const void *key, void *value) {
1284         struct swap_entries swap;
1285         struct plain_hashmap_entry *e;
1286         unsigned hash, idx;
1287
1288         assert(h);
1289
1290         hash = bucket_hash(h, key);
1291         idx = bucket_scan(h, hash, key);
1292         if (idx != IDX_NIL) {
1293                 e = plain_bucket_at(h, idx);
1294 #ifdef ENABLE_DEBUG_HASHMAP
1295                 /* Although the key is equal, the key pointer may have changed,
1296                  * and this would break our assumption for iterating. So count
1297                  * this operation as incompatible with iteration. */
1298                 if (e->b.key != key) {
1299                         h->b.debug.put_count++;
1300                         h->b.debug.rem_count++;
1301                         h->b.debug.last_rem_idx = idx;
1302                 }
1303 #endif
1304                 e->b.key = key;
1305                 e->value = value;
1306                 return 0;
1307         }
1308
1309         e = &bucket_at_swap(&swap, IDX_PUT)->p;
1310         e->b.key = key;
1311         e->value = value;
1312         return hashmap_put_boldly(h, hash, &swap, true);
1313 }
1314
1315 int hashmap_update(Hashmap *h, const void *key, void *value) {
1316         struct plain_hashmap_entry *e;
1317         unsigned hash, idx;
1318
1319         assert(h);
1320
1321         hash = bucket_hash(h, key);
1322         idx = bucket_scan(h, hash, key);
1323         if (idx == IDX_NIL)
1324                 return -ENOENT;
1325
1326         e = plain_bucket_at(h, idx);
1327         e->value = value;
1328         return 0;
1329 }
1330
1331 void *internal_hashmap_get(HashmapBase *h, const void *key) {
1332         struct hashmap_base_entry *e;
1333         unsigned hash, idx;
1334
1335         if (!h)
1336                 return NULL;
1337
1338         hash = bucket_hash(h, key);
1339         idx = bucket_scan(h, hash, key);
1340         if (idx == IDX_NIL)
1341                 return NULL;
1342
1343         e = bucket_at(h, idx);
1344         return entry_value(h, e);
1345 }
1346
1347 void *hashmap_get2(Hashmap *h, const void *key, void **key2) {
1348         struct plain_hashmap_entry *e;
1349         unsigned hash, idx;
1350
1351         if (!h)
1352                 return NULL;
1353
1354         hash = bucket_hash(h, key);
1355         idx = bucket_scan(h, hash, key);
1356         if (idx == IDX_NIL)
1357                 return NULL;
1358
1359         e = plain_bucket_at(h, idx);
1360         if (key2)
1361                 *key2 = (void*) e->b.key;
1362
1363         return e->value;
1364 }
1365
1366 bool internal_hashmap_contains(HashmapBase *h, const void *key) {
1367         unsigned hash;
1368
1369         if (!h)
1370                 return false;
1371
1372         hash = bucket_hash(h, key);
1373         return bucket_scan(h, hash, key) != IDX_NIL;
1374 }
1375
1376 void *internal_hashmap_remove(HashmapBase *h, const void *key) {
1377         struct hashmap_base_entry *e;
1378         unsigned hash, idx;
1379         void *data;
1380
1381         if (!h)
1382                 return NULL;
1383
1384         hash = bucket_hash(h, key);
1385         idx = bucket_scan(h, hash, key);
1386         if (idx == IDX_NIL)
1387                 return NULL;
1388
1389         e = bucket_at(h, idx);
1390         data = entry_value(h, e);
1391         remove_entry(h, idx);
1392
1393         return data;
1394 }
1395
1396 void *hashmap_remove2(Hashmap *h, const void *key, void **rkey) {
1397         struct plain_hashmap_entry *e;
1398         unsigned hash, idx;
1399         void *data;
1400
1401         if (!h) {
1402                 if (rkey)
1403                         *rkey = NULL;
1404                 return NULL;
1405         }
1406
1407         hash = bucket_hash(h, key);
1408         idx = bucket_scan(h, hash, key);
1409         if (idx == IDX_NIL) {
1410                 if (rkey)
1411                         *rkey = NULL;
1412                 return NULL;
1413         }
1414
1415         e = plain_bucket_at(h, idx);
1416         data = e->value;
1417         if (rkey)
1418                 *rkey = (void*) e->b.key;
1419
1420         remove_entry(h, idx);
1421
1422         return data;
1423 }
1424
1425 int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value) {
1426         struct swap_entries swap;
1427         struct plain_hashmap_entry *e;
1428         unsigned old_hash, new_hash, idx;
1429
1430         if (!h)
1431                 return -ENOENT;
1432
1433         old_hash = bucket_hash(h, old_key);
1434         idx = bucket_scan(h, old_hash, old_key);
1435         if (idx == IDX_NIL)
1436                 return -ENOENT;
1437
1438         new_hash = bucket_hash(h, new_key);
1439         if (bucket_scan(h, new_hash, new_key) != IDX_NIL)
1440                 return -EEXIST;
1441
1442         remove_entry(h, idx);
1443
1444         e = &bucket_at_swap(&swap, IDX_PUT)->p;
1445         e->b.key = new_key;
1446         e->value = value;
1447         assert_se(hashmap_put_boldly(h, new_hash, &swap, false) == 1);
1448
1449         return 0;
1450 }
1451
1452 int set_remove_and_put(Set *s, const void *old_key, const void *new_key) {
1453         struct swap_entries swap;
1454         struct hashmap_base_entry *e;
1455         unsigned old_hash, new_hash, idx;
1456
1457         if (!s)
1458                 return -ENOENT;
1459
1460         old_hash = bucket_hash(s, old_key);
1461         idx = bucket_scan(s, old_hash, old_key);
1462         if (idx == IDX_NIL)
1463                 return -ENOENT;
1464
1465         new_hash = bucket_hash(s, new_key);
1466         if (bucket_scan(s, new_hash, new_key) != IDX_NIL)
1467                 return -EEXIST;
1468
1469         remove_entry(s, idx);
1470
1471         e = &bucket_at_swap(&swap, IDX_PUT)->p.b;
1472         e->key = new_key;
1473         assert_se(hashmap_put_boldly(s, new_hash, &swap, false) == 1);
1474
1475         return 0;
1476 }
1477
1478 int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value) {
1479         struct swap_entries swap;
1480         struct plain_hashmap_entry *e;
1481         unsigned old_hash, new_hash, idx_old, idx_new;
1482
1483         if (!h)
1484                 return -ENOENT;
1485
1486         old_hash = bucket_hash(h, old_key);
1487         idx_old = bucket_scan(h, old_hash, old_key);
1488         if (idx_old == IDX_NIL)
1489                 return -ENOENT;
1490
1491         old_key = bucket_at(HASHMAP_BASE(h), idx_old)->key;
1492
1493         new_hash = bucket_hash(h, new_key);
1494         idx_new = bucket_scan(h, new_hash, new_key);
1495         if (idx_new != IDX_NIL)
1496                 if (idx_old != idx_new) {
1497                         remove_entry(h, idx_new);
1498                         /* Compensate for a possible backward shift. */
1499                         if (old_key != bucket_at(HASHMAP_BASE(h), idx_old)->key)
1500                                 idx_old = prev_idx(HASHMAP_BASE(h), idx_old);
1501                         assert(old_key == bucket_at(HASHMAP_BASE(h), idx_old)->key);
1502                 }
1503
1504         remove_entry(h, idx_old);
1505
1506         e = &bucket_at_swap(&swap, IDX_PUT)->p;
1507         e->b.key = new_key;
1508         e->value = value;
1509         assert_se(hashmap_put_boldly(h, new_hash, &swap, false) == 1);
1510
1511         return 0;
1512 }
1513
1514 void *hashmap_remove_value(Hashmap *h, const void *key, void *value) {
1515         struct plain_hashmap_entry *e;
1516         unsigned hash, idx;
1517
1518         if (!h)
1519                 return NULL;
1520
1521         hash = bucket_hash(h, key);
1522         idx = bucket_scan(h, hash, key);
1523         if (idx == IDX_NIL)
1524                 return NULL;
1525
1526         e = plain_bucket_at(h, idx);
1527         if (e->value != value)
1528                 return NULL;
1529
1530         remove_entry(h, idx);
1531
1532         return value;
1533 }
1534
1535 static unsigned find_first_entry(HashmapBase *h) {
1536         Iterator i = ITERATOR_FIRST;
1537
1538         if (!h || !n_entries(h))
1539                 return IDX_NIL;
1540
1541         return hashmap_iterate_entry(h, &i);
1542 }
1543
1544 void *internal_hashmap_first(HashmapBase *h) {
1545         unsigned idx;
1546
1547         idx = find_first_entry(h);
1548         if (idx == IDX_NIL)
1549                 return NULL;
1550
1551         return entry_value(h, bucket_at(h, idx));
1552 }
1553
1554 void *internal_hashmap_first_key(HashmapBase *h) {
1555         struct hashmap_base_entry *e;
1556         unsigned idx;
1557
1558         idx = find_first_entry(h);
1559         if (idx == IDX_NIL)
1560                 return NULL;
1561
1562         e = bucket_at(h, idx);
1563         return (void*) e->key;
1564 }
1565
1566 void *internal_hashmap_steal_first(HashmapBase *h) {
1567         struct hashmap_base_entry *e;
1568         void *data;
1569         unsigned idx;
1570
1571         idx = find_first_entry(h);
1572         if (idx == IDX_NIL)
1573                 return NULL;
1574
1575         e = bucket_at(h, idx);
1576         data = entry_value(h, e);
1577         remove_entry(h, idx);
1578
1579         return data;
1580 }
1581
1582 void *internal_hashmap_steal_first_key(HashmapBase *h) {
1583         struct hashmap_base_entry *e;
1584         void *key;
1585         unsigned idx;
1586
1587         idx = find_first_entry(h);
1588         if (idx == IDX_NIL)
1589                 return NULL;
1590
1591         e = bucket_at(h, idx);
1592         key = (void*) e->key;
1593         remove_entry(h, idx);
1594
1595         return key;
1596 }
1597
1598 unsigned internal_hashmap_size(HashmapBase *h) {
1599
1600         if (!h)
1601                 return 0;
1602
1603         return n_entries(h);
1604 }
1605
1606 unsigned internal_hashmap_buckets(HashmapBase *h) {
1607
1608         if (!h)
1609                 return 0;
1610
1611         return n_buckets(h);
1612 }
1613
1614 int internal_hashmap_merge(Hashmap *h, Hashmap *other) {
1615         Iterator i;
1616         unsigned idx;
1617
1618         assert(h);
1619
1620         HASHMAP_FOREACH_IDX(idx, HASHMAP_BASE(other), i) {
1621                 struct plain_hashmap_entry *pe = plain_bucket_at(other, idx);
1622                 int r;
1623
1624                 r = hashmap_put(h, pe->b.key, pe->value);
1625                 if (r < 0 && r != -EEXIST)
1626                         return r;
1627         }
1628
1629         return 0;
1630 }
1631
1632 int set_merge(Set *s, Set *other) {
1633         Iterator i;
1634         unsigned idx;
1635
1636         assert(s);
1637
1638         HASHMAP_FOREACH_IDX(idx, HASHMAP_BASE(other), i) {
1639                 struct set_entry *se = set_bucket_at(other, idx);
1640                 int r;
1641
1642                 r = set_put(s, se->b.key);
1643                 if (r < 0)
1644                         return r;
1645         }
1646
1647         return 0;
1648 }
1649
1650 int internal_hashmap_reserve(HashmapBase *h, unsigned entries_add) {
1651         int r;
1652
1653         assert(h);
1654
1655         r = resize_buckets(h, entries_add);
1656         if (r < 0)
1657                 return r;
1658
1659         return 0;
1660 }
1661
1662 /*
1663  * The same as hashmap_merge(), but every new item from other is moved to h.
1664  * Keys already in h are skipped and stay in other.
1665  * Returns: 0 on success.
1666  *          -ENOMEM on alloc failure, in which case no move has been done.
1667  */
1668 int internal_hashmap_move(HashmapBase *h, HashmapBase *other) {
1669         struct swap_entries swap;
1670         struct hashmap_base_entry *e, *n;
1671         Iterator i;
1672         unsigned idx;
1673         int r;
1674
1675         assert(h);
1676
1677         if (!other)
1678                 return 0;
1679
1680         assert(other->type == h->type);
1681
1682         /*
1683          * This reserves buckets for the worst case, where none of other's
1684          * entries are yet present in h. This is preferable to risking
1685          * an allocation failure in the middle of the moving and having to
1686          * rollback or return a partial result.
1687          */
1688         r = resize_buckets(h, n_entries(other));
1689         if (r < 0)
1690                 return r;
1691
1692         HASHMAP_FOREACH_IDX(idx, other, i) {
1693                 unsigned h_hash;
1694
1695                 e = bucket_at(other, idx);
1696                 h_hash = bucket_hash(h, e->key);
1697                 if (bucket_scan(h, h_hash, e->key) != IDX_NIL)
1698                         continue;
1699
1700                 n = &bucket_at_swap(&swap, IDX_PUT)->p.b;
1701                 n->key = e->key;
1702                 if (h->type != HASHMAP_TYPE_SET)
1703                         ((struct plain_hashmap_entry*) n)->value =
1704                                 ((struct plain_hashmap_entry*) e)->value;
1705                 assert_se(hashmap_put_boldly(h, h_hash, &swap, false) == 1);
1706
1707                 remove_entry(other, idx);
1708         }
1709
1710         return 0;
1711 }
1712
1713 int internal_hashmap_move_one(HashmapBase *h, HashmapBase *other, const void *key) {
1714         struct swap_entries swap;
1715         unsigned h_hash, other_hash, idx;
1716         struct hashmap_base_entry *e, *n;
1717         int r;
1718
1719         assert(h);
1720
1721         h_hash = bucket_hash(h, key);
1722         if (bucket_scan(h, h_hash, key) != IDX_NIL)
1723                 return -EEXIST;
1724
1725         if (!other)
1726                 return -ENOENT;
1727
1728         assert(other->type == h->type);
1729
1730         other_hash = bucket_hash(other, key);
1731         idx = bucket_scan(other, other_hash, key);
1732         if (idx == IDX_NIL)
1733                 return -ENOENT;
1734
1735         e = bucket_at(other, idx);
1736
1737         n = &bucket_at_swap(&swap, IDX_PUT)->p.b;
1738         n->key = e->key;
1739         if (h->type != HASHMAP_TYPE_SET)
1740                 ((struct plain_hashmap_entry*) n)->value =
1741                         ((struct plain_hashmap_entry*) e)->value;
1742         r = hashmap_put_boldly(h, h_hash, &swap, true);
1743         if (r < 0)
1744                 return r;
1745
1746         remove_entry(other, idx);
1747         return 0;
1748 }
1749
1750 HashmapBase *internal_hashmap_copy(HashmapBase *h) {
1751         HashmapBase *copy;
1752         int r;
1753
1754         assert(h);
1755
1756         copy = hashmap_base_new(h->hash_ops, h->type  HASHMAP_DEBUG_SRC_ARGS);
1757         if (!copy)
1758                 return NULL;
1759
1760         switch (h->type) {
1761         case HASHMAP_TYPE_PLAIN:
1762         case HASHMAP_TYPE_ORDERED:
1763                 r = hashmap_merge((Hashmap*)copy, (Hashmap*)h);
1764                 break;
1765         case HASHMAP_TYPE_SET:
1766                 r = set_merge((Set*)copy, (Set*)h);
1767                 break;
1768         default:
1769                 assert_not_reached("Unknown hashmap type");
1770         }
1771
1772         if (r < 0) {
1773                 internal_hashmap_free(copy);
1774                 return NULL;
1775         }
1776
1777         return copy;
1778 }
1779
1780 char **internal_hashmap_get_strv(HashmapBase *h) {
1781         char **sv;
1782         Iterator i;
1783         unsigned idx, n;
1784
1785         sv = new(char*, n_entries(h)+1);
1786         if (!sv)
1787                 return NULL;
1788
1789         n = 0;
1790         HASHMAP_FOREACH_IDX(idx, h, i)
1791                 sv[n++] = entry_value(h, bucket_at(h, idx));
1792         sv[n] = NULL;
1793
1794         return sv;
1795 }
1796
1797 void *ordered_hashmap_next(OrderedHashmap *h, const void *key) {
1798         struct ordered_hashmap_entry *e;
1799         unsigned hash, idx;
1800
1801         if (!h)
1802                 return NULL;
1803
1804         hash = bucket_hash(h, key);
1805         idx = bucket_scan(h, hash, key);
1806         if (idx == IDX_NIL)
1807                 return NULL;
1808
1809         e = ordered_bucket_at(h, idx);
1810         if (e->iterate_next == IDX_NIL)
1811                 return NULL;
1812         return ordered_bucket_at(h, e->iterate_next)->p.value;
1813 }
1814
1815 int set_consume(Set *s, void *value) {
1816         int r;
1817
1818         r = set_put(s, value);
1819         if (r <= 0)
1820                 free(value);
1821
1822         return r;
1823 }
1824
1825 int set_put_strdup(Set *s, const char *p) {
1826         char *c;
1827         int r;
1828
1829         assert(s);
1830         assert(p);
1831
1832         c = strdup(p);
1833         if (!c)
1834                 return -ENOMEM;
1835
1836         r = set_consume(s, c);
1837         if (r == -EEXIST)
1838                 return 0;
1839
1840         return r;
1841 }
1842
1843 int set_put_strdupv(Set *s, char **l) {
1844         int n = 0, r;
1845         char **i;
1846
1847         STRV_FOREACH(i, l) {
1848                 r = set_put_strdup(s, *i);
1849                 if (r < 0)
1850                         return r;
1851
1852                 n += r;
1853         }
1854
1855         return n;
1856 }