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