src/basic/hashmap.c

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