src/basic/hashmap.c

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