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