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