src/basic/hashmap.c

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