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