src/basic/hashmap.c

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