src/basic/hashmap.h

   1 /* SPDX-License-Identifier: LGPL-2.1+ */
   2 #pragma once
   3
   4 #include <limits.h>
   5 #include <stdbool.h>
   6 #include <stddef.h>
   7
   8 #include "hash-funcs.h"
   9 #include "macro.h"
  10 #include "util.h"
  11
  12 /*
  13  * A hash table implementation. As a minor optimization a NULL hashmap object
  14  * will be treated as empty hashmap for all read operations. That way it is not
  15  * necessary to instantiate an object for each Hashmap use.
  16  *
  17  * If ENABLE_DEBUG_HASHMAP is defined (by configuring with --enable-debug=hashmap),
  18  * the implementation will:
  19  * - store extra data for debugging and statistics (see tools/gdb-sd_dump_hashmaps.py)
  20  * - perform extra checks for invalid use of iterators
  21  */
  22
  23 #define HASH_KEY_SIZE 16
  24
  25 typedef void* (*hashmap_destroy_t)(void *p);
  26
  27 /* The base type for all hashmap and set types. Many functions in the
  28  * implementation take (HashmapBase*) parameters and are run-time polymorphic,
  29  * though the API is not meant to be polymorphic (do not call functions
  30  * internal_*() directly). */
  31 typedef struct HashmapBase HashmapBase;
  32
  33 /* Specific hashmap/set types */
  34 typedef struct Hashmap Hashmap;               /* Maps keys to values */
  35 typedef struct OrderedHashmap OrderedHashmap; /* Like Hashmap, but also remembers entry insertion order */
  36 typedef struct Set Set;                       /* Stores just keys */
  37
  38 typedef struct IteratedCache IteratedCache;   /* Caches the iterated order of one of the above */
  39
  40 /* Ideally the Iterator would be an opaque struct, but it is instantiated
  41  * by hashmap users, so the definition has to be here. Do not use its fields
  42  * directly. */
  43 typedef struct {
  44         unsigned idx;         /* index of an entry to be iterated next */
  45         const void *next_key; /* expected value of that entry's key pointer */
  46 #if ENABLE_DEBUG_HASHMAP
  47         unsigned put_count;   /* hashmap's put_count recorded at start of iteration */
  48         unsigned rem_count;   /* hashmap's rem_count in previous iteration */
  49         unsigned prev_idx;    /* idx in previous iteration */
  50 #endif
  51 } Iterator;
  52
  53 #define _IDX_ITERATOR_FIRST (UINT_MAX - 1)
  54 #define ITERATOR_FIRST ((Iterator) { .idx = _IDX_ITERATOR_FIRST, .next_key = NULL })
  55
  56 /* Macros for type checking */
  57 #define PTR_COMPATIBLE_WITH_HASHMAP_BASE(h) \
  58         (__builtin_types_compatible_p(typeof(h), HashmapBase*) || \
  59          __builtin_types_compatible_p(typeof(h), Hashmap*) || \
  60          __builtin_types_compatible_p(typeof(h), OrderedHashmap*) || \
  61          __builtin_types_compatible_p(typeof(h), Set*))
  62
  63 #define PTR_COMPATIBLE_WITH_PLAIN_HASHMAP(h) \
  64         (__builtin_types_compatible_p(typeof(h), Hashmap*) || \
  65          __builtin_types_compatible_p(typeof(h), OrderedHashmap*)) \
  66
  67 #define HASHMAP_BASE(h) \
  68         __builtin_choose_expr(PTR_COMPATIBLE_WITH_HASHMAP_BASE(h), \
  69                 (HashmapBase*)(h), \
  70                 (void)0)
  71
  72 #define PLAIN_HASHMAP(h) \
  73         __builtin_choose_expr(PTR_COMPATIBLE_WITH_PLAIN_HASHMAP(h), \
  74                 (Hashmap*)(h), \
  75                 (void)0)
  76
  77 #if ENABLE_DEBUG_HASHMAP
  78 # define HASHMAP_DEBUG_PARAMS , const char *func, const char *file, int line
  79 # define HASHMAP_DEBUG_SRC_ARGS   , __func__, __FILE__, __LINE__
  80 # define HASHMAP_DEBUG_PASS_ARGS   , func, file, line
  81 #else
  82 # define HASHMAP_DEBUG_PARAMS
  83 # define HASHMAP_DEBUG_SRC_ARGS
  84 # define HASHMAP_DEBUG_PASS_ARGS
  85 #endif
  86
  87 Hashmap *internal_hashmap_new(const struct hash_ops *hash_ops  HASHMAP_DEBUG_PARAMS);
  88 OrderedHashmap *internal_ordered_hashmap_new(const struct hash_ops *hash_ops  HASHMAP_DEBUG_PARAMS);
  89 #define hashmap_new(ops) internal_hashmap_new(ops  HASHMAP_DEBUG_SRC_ARGS)
  90 #define ordered_hashmap_new(ops) internal_ordered_hashmap_new(ops  HASHMAP_DEBUG_SRC_ARGS)
  91
  92 HashmapBase *internal_hashmap_free(HashmapBase *h, free_func_t default_free_key, free_func_t default_free_value);
  93 static inline Hashmap *hashmap_free(Hashmap *h) {
  94         return (void*) internal_hashmap_free(HASHMAP_BASE(h), NULL, NULL);
  95 }
  96 static inline OrderedHashmap *ordered_hashmap_free(OrderedHashmap *h) {
  97         return (void*) internal_hashmap_free(HASHMAP_BASE(h), NULL, NULL);
  98 }
  99
 100 static inline Hashmap *hashmap_free_free(Hashmap *h) {
 101         return (void*) internal_hashmap_free(HASHMAP_BASE(h), NULL, free);
 102 }
 103 static inline OrderedHashmap *ordered_hashmap_free_free(OrderedHashmap *h) {
 104         return (void*) internal_hashmap_free(HASHMAP_BASE(h), NULL, free);
 105 }
 106
 107 static inline Hashmap *hashmap_free_free_key(Hashmap *h) {
 108         return (void*) internal_hashmap_free(HASHMAP_BASE(h), free, NULL);
 109 }
 110 static inline OrderedHashmap *ordered_hashmap_free_free_key(OrderedHashmap *h) {
 111         return (void*) internal_hashmap_free(HASHMAP_BASE(h), free, NULL);
 112 }
 113
 114 static inline Hashmap *hashmap_free_free_free(Hashmap *h) {
 115         return (void*) internal_hashmap_free(HASHMAP_BASE(h), free, free);
 116 }
 117 static inline OrderedHashmap *ordered_hashmap_free_free_free(OrderedHashmap *h) {
 118         return (void*) internal_hashmap_free(HASHMAP_BASE(h), free, free);
 119 }
 120
 121 IteratedCache *iterated_cache_free(IteratedCache *cache);
 122 int iterated_cache_get(IteratedCache *cache, const void ***res_keys, const void ***res_values, unsigned *res_n_entries);
 123
 124 HashmapBase *internal_hashmap_copy(HashmapBase *h);
 125 static inline Hashmap *hashmap_copy(Hashmap *h) {
 126         return (Hashmap*) internal_hashmap_copy(HASHMAP_BASE(h));
 127 }
 128 static inline OrderedHashmap *ordered_hashmap_copy(OrderedHashmap *h) {
 129         return (OrderedHashmap*) internal_hashmap_copy(HASHMAP_BASE(h));
 130 }
 131
 132 int internal_hashmap_ensure_allocated(Hashmap **h, const struct hash_ops *hash_ops  HASHMAP_DEBUG_PARAMS);
 133 int internal_ordered_hashmap_ensure_allocated(OrderedHashmap **h, const struct hash_ops *hash_ops  HASHMAP_DEBUG_PARAMS);
 134 #define hashmap_ensure_allocated(h, ops) internal_hashmap_ensure_allocated(h, ops  HASHMAP_DEBUG_SRC_ARGS)
 135 #define ordered_hashmap_ensure_allocated(h, ops) internal_ordered_hashmap_ensure_allocated(h, ops  HASHMAP_DEBUG_SRC_ARGS)
 136
 137 IteratedCache *internal_hashmap_iterated_cache_new(HashmapBase *h);
 138 static inline IteratedCache *hashmap_iterated_cache_new(Hashmap *h) {
 139         return (IteratedCache*) internal_hashmap_iterated_cache_new(HASHMAP_BASE(h));
 140 }
 141 static inline IteratedCache *ordered_hashmap_iterated_cache_new(OrderedHashmap *h) {
 142         return (IteratedCache*) internal_hashmap_iterated_cache_new(HASHMAP_BASE(h));
 143 }
 144
 145 int hashmap_put(Hashmap *h, const void *key, void *value);
 146 static inline int ordered_hashmap_put(OrderedHashmap *h, const void *key, void *value) {
 147         return hashmap_put(PLAIN_HASHMAP(h), key, value);
 148 }
 149
 150 int hashmap_update(Hashmap *h, const void *key, void *value);
 151 static inline int ordered_hashmap_update(OrderedHashmap *h, const void *key, void *value) {
 152         return hashmap_update(PLAIN_HASHMAP(h), key, value);
 153 }
 154
 155 int hashmap_replace(Hashmap *h, const void *key, void *value);
 156 static inline int ordered_hashmap_replace(OrderedHashmap *h, const void *key, void *value) {
 157         return hashmap_replace(PLAIN_HASHMAP(h), key, value);
 158 }
 159
 160 void *internal_hashmap_get(HashmapBase *h, const void *key);
 161 static inline void *hashmap_get(Hashmap *h, const void *key) {
 162         return internal_hashmap_get(HASHMAP_BASE(h), key);
 163 }
 164 static inline void *ordered_hashmap_get(OrderedHashmap *h, const void *key) {
 165         return internal_hashmap_get(HASHMAP_BASE(h), key);
 166 }
 167
 168 void *hashmap_get2(Hashmap *h, const void *key, void **rkey);
 169 static inline void *ordered_hashmap_get2(OrderedHashmap *h, const void *key, void **rkey) {
 170         return hashmap_get2(PLAIN_HASHMAP(h), key, rkey);
 171 }
 172
 173 bool internal_hashmap_contains(HashmapBase *h, const void *key);
 174 static inline bool hashmap_contains(Hashmap *h, const void *key) {
 175         return internal_hashmap_contains(HASHMAP_BASE(h), key);
 176 }
 177 static inline bool ordered_hashmap_contains(OrderedHashmap *h, const void *key) {
 178         return internal_hashmap_contains(HASHMAP_BASE(h), key);
 179 }
 180
 181 void *internal_hashmap_remove(HashmapBase *h, const void *key);
 182 static inline void *hashmap_remove(Hashmap *h, const void *key) {
 183         return internal_hashmap_remove(HASHMAP_BASE(h), key);
 184 }
 185 static inline void *ordered_hashmap_remove(OrderedHashmap *h, const void *key) {
 186         return internal_hashmap_remove(HASHMAP_BASE(h), key);
 187 }
 188
 189 void *hashmap_remove2(Hashmap *h, const void *key, void **rkey);
 190 static inline void *ordered_hashmap_remove2(OrderedHashmap *h, const void *key, void **rkey) {
 191         return hashmap_remove2(PLAIN_HASHMAP(h), key, rkey);
 192 }
 193
 194 void *internal_hashmap_remove_value(HashmapBase *h, const void *key, void *value);
 195 static inline void *hashmap_remove_value(Hashmap *h, const void *key, void *value) {
 196         return internal_hashmap_remove_value(HASHMAP_BASE(h), key, value);
 197 }
 198
 199 static inline void *ordered_hashmap_remove_value(OrderedHashmap *h, const void *key, void *value) {
 200         return hashmap_remove_value(PLAIN_HASHMAP(h), key, value);
 201 }
 202
 203 int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value);
 204 static inline int ordered_hashmap_remove_and_put(OrderedHashmap *h, const void *old_key, const void *new_key, void *value) {
 205         return hashmap_remove_and_put(PLAIN_HASHMAP(h), old_key, new_key, value);
 206 }
 207
 208 int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value);
 209 static inline int ordered_hashmap_remove_and_replace(OrderedHashmap *h, const void *old_key, const void *new_key, void *value) {
 210         return hashmap_remove_and_replace(PLAIN_HASHMAP(h), old_key, new_key, value);
 211 }
 212
 213 /* Since merging data from a OrderedHashmap into a Hashmap or vice-versa
 214  * should just work, allow this by having looser type-checking here. */
 215 int internal_hashmap_merge(Hashmap *h, Hashmap *other);
 216 #define hashmap_merge(h, other) internal_hashmap_merge(PLAIN_HASHMAP(h), PLAIN_HASHMAP(other))
 217 #define ordered_hashmap_merge(h, other) hashmap_merge(h, other)
 218
 219 int internal_hashmap_reserve(HashmapBase *h, unsigned entries_add);
 220 static inline int hashmap_reserve(Hashmap *h, unsigned entries_add) {
 221         return internal_hashmap_reserve(HASHMAP_BASE(h), entries_add);
 222 }
 223 static inline int ordered_hashmap_reserve(OrderedHashmap *h, unsigned entries_add) {
 224         return internal_hashmap_reserve(HASHMAP_BASE(h), entries_add);
 225 }
 226
 227 int internal_hashmap_move(HashmapBase *h, HashmapBase *other);
 228 /* Unlike hashmap_merge, hashmap_move does not allow mixing the types. */
 229 static inline int hashmap_move(Hashmap *h, Hashmap *other) {
 230         return internal_hashmap_move(HASHMAP_BASE(h), HASHMAP_BASE(other));
 231 }
 232 static inline int ordered_hashmap_move(OrderedHashmap *h, OrderedHashmap *other) {
 233         return internal_hashmap_move(HASHMAP_BASE(h), HASHMAP_BASE(other));
 234 }
 235
 236 int internal_hashmap_move_one(HashmapBase *h, HashmapBase *other, const void *key);
 237 static inline int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) {
 238         return internal_hashmap_move_one(HASHMAP_BASE(h), HASHMAP_BASE(other), key);
 239 }
 240 static inline int ordered_hashmap_move_one(OrderedHashmap *h, OrderedHashmap *other, const void *key) {
 241         return internal_hashmap_move_one(HASHMAP_BASE(h), HASHMAP_BASE(other), key);
 242 }
 243
 244 unsigned internal_hashmap_size(HashmapBase *h) _pure_;
 245 static inline unsigned hashmap_size(Hashmap *h) {
 246         return internal_hashmap_size(HASHMAP_BASE(h));
 247 }
 248 static inline unsigned ordered_hashmap_size(OrderedHashmap *h) {
 249         return internal_hashmap_size(HASHMAP_BASE(h));
 250 }
 251
 252 static inline bool hashmap_isempty(Hashmap *h) {
 253         return hashmap_size(h) == 0;
 254 }
 255 static inline bool ordered_hashmap_isempty(OrderedHashmap *h) {
 256         return ordered_hashmap_size(h) == 0;
 257 }
 258
 259 unsigned internal_hashmap_buckets(HashmapBase *h) _pure_;
 260 static inline unsigned hashmap_buckets(Hashmap *h) {
 261         return internal_hashmap_buckets(HASHMAP_BASE(h));
 262 }
 263 static inline unsigned ordered_hashmap_buckets(OrderedHashmap *h) {
 264         return internal_hashmap_buckets(HASHMAP_BASE(h));
 265 }
 266
 267 bool internal_hashmap_iterate(HashmapBase *h, Iterator *i, void **value, const void **key);
 268 static inline bool hashmap_iterate(Hashmap *h, Iterator *i, void **value, const void **key) {
 269         return internal_hashmap_iterate(HASHMAP_BASE(h), i, value, key);
 270 }
 271 static inline bool ordered_hashmap_iterate(OrderedHashmap *h, Iterator *i, void **value, const void **key) {
 272         return internal_hashmap_iterate(HASHMAP_BASE(h), i, value, key);
 273 }
 274
 275 void internal_hashmap_clear(HashmapBase *h, free_func_t default_free_key, free_func_t default_free_value);
 276 static inline void hashmap_clear(Hashmap *h) {
 277         internal_hashmap_clear(HASHMAP_BASE(h), NULL, NULL);
 278 }
 279 static inline void ordered_hashmap_clear(OrderedHashmap *h) {
 280         internal_hashmap_clear(HASHMAP_BASE(h), NULL, NULL);
 281 }
 282
 283 static inline void hashmap_clear_free(Hashmap *h) {
 284         internal_hashmap_clear(HASHMAP_BASE(h), NULL, free);
 285 }
 286 static inline void ordered_hashmap_clear_free(OrderedHashmap *h) {
 287         internal_hashmap_clear(HASHMAP_BASE(h), NULL, free);
 288 }
 289
 290 static inline void hashmap_clear_free_key(Hashmap *h) {
 291         internal_hashmap_clear(HASHMAP_BASE(h), free, NULL);
 292 }
 293 static inline void ordered_hashmap_clear_free_key(OrderedHashmap *h) {
 294         internal_hashmap_clear(HASHMAP_BASE(h), free, NULL);
 295 }
 296
 297 static inline void hashmap_clear_free_free(Hashmap *h) {
 298         internal_hashmap_clear(HASHMAP_BASE(h), free, free);
 299 }
 300 static inline void ordered_hashmap_clear_free_free(OrderedHashmap *h) {
 301         internal_hashmap_clear(HASHMAP_BASE(h), free, free);
 302 }
 303
 304 /*
 305  * Note about all *_first*() functions
 306  *
 307  * For plain Hashmaps and Sets the order of entries is undefined.
 308  * The functions find whatever entry is first in the implementation
 309  * internal order.
 310  *
 311  * Only for OrderedHashmaps the order is well defined and finding
 312  * the first entry is O(1).
 313  */
 314
 315 void *internal_hashmap_first_key_and_value(HashmapBase *h, bool remove, void **ret_key);
 316 static inline void *hashmap_steal_first_key_and_value(Hashmap *h, void **ret) {
 317         return internal_hashmap_first_key_and_value(HASHMAP_BASE(h), true, ret);
 318 }
 319 static inline void *ordered_hashmap_steal_first_key_and_value(OrderedHashmap *h, void **ret) {
 320         return internal_hashmap_first_key_and_value(HASHMAP_BASE(h), true, ret);
 321 }
 322 static inline void *hashmap_first_key_and_value(Hashmap *h, void **ret) {
 323         return internal_hashmap_first_key_and_value(HASHMAP_BASE(h), false, ret);
 324 }
 325 static inline void *ordered_hashmap_first_key_and_value(OrderedHashmap *h, void **ret) {
 326         return internal_hashmap_first_key_and_value(HASHMAP_BASE(h), false, ret);
 327 }
 328
 329 static inline void *hashmap_steal_first(Hashmap *h) {
 330         return internal_hashmap_first_key_and_value(HASHMAP_BASE(h), true, NULL);
 331 }
 332 static inline void *ordered_hashmap_steal_first(OrderedHashmap *h) {
 333         return internal_hashmap_first_key_and_value(HASHMAP_BASE(h), true, NULL);
 334 }
 335 static inline void *hashmap_first(Hashmap *h) {
 336         return internal_hashmap_first_key_and_value(HASHMAP_BASE(h), false, NULL);
 337 }
 338 static inline void *ordered_hashmap_first(OrderedHashmap *h) {
 339         return internal_hashmap_first_key_and_value(HASHMAP_BASE(h), false, NULL);
 340 }
 341
 342 static inline void *internal_hashmap_first_key(HashmapBase *h, bool remove) {
 343         void *key = NULL;
 344
 345         (void) internal_hashmap_first_key_and_value(HASHMAP_BASE(h), remove, &key);
 346         return key;
 347 }
 348 static inline void *hashmap_steal_first_key(Hashmap *h) {
 349         return internal_hashmap_first_key(HASHMAP_BASE(h), true);
 350 }
 351 static inline void *ordered_hashmap_steal_first_key(OrderedHashmap *h) {
 352         return internal_hashmap_first_key(HASHMAP_BASE(h), true);
 353 }
 354 static inline void *hashmap_first_key(Hashmap *h) {
 355         return internal_hashmap_first_key(HASHMAP_BASE(h), false);
 356 }
 357 static inline void *ordered_hashmap_first_key(OrderedHashmap *h) {
 358         return internal_hashmap_first_key(HASHMAP_BASE(h), false);
 359 }
 360
 361 #define hashmap_clear_with_destructor(_s, _f)                   \
 362         ({                                                      \
 363                 void *_item;                                    \
 364                 while ((_item = hashmap_steal_first(_s)))       \
 365                         _f(_item);                              \
 366         })
 367 #define hashmap_free_with_destructor(_s, _f)                    \
 368         ({                                                      \
 369                 hashmap_clear_with_destructor(_s, _f);          \
 370                 hashmap_free(_s);                               \
 371         })
 372 #define ordered_hashmap_clear_with_destructor(_s, _f)                   \
 373         ({                                                              \
 374                 void *_item;                                            \
 375                 while ((_item = ordered_hashmap_steal_first(_s)))       \
 376                         _f(_item);                                      \
 377         })
 378 #define ordered_hashmap_free_with_destructor(_s, _f)                    \
 379         ({                                                              \
 380                 ordered_hashmap_clear_with_destructor(_s, _f);          \
 381                 ordered_hashmap_free(_s);                               \
 382         })
 383
 384 /* no hashmap_next */
 385 void *ordered_hashmap_next(OrderedHashmap *h, const void *key);
 386
 387 char **internal_hashmap_get_strv(HashmapBase *h);
 388 static inline char **hashmap_get_strv(Hashmap *h) {
 389         return internal_hashmap_get_strv(HASHMAP_BASE(h));
 390 }
 391 static inline char **ordered_hashmap_get_strv(OrderedHashmap *h) {
 392         return internal_hashmap_get_strv(HASHMAP_BASE(h));
 393 }
 394
 395 /*
 396  * Hashmaps are iterated in unpredictable order.
 397  * OrderedHashmaps are an exception to this. They are iterated in the order
 398  * the entries were inserted.
 399  * It is safe to remove the current entry.
 400  */
 401 #define HASHMAP_FOREACH(e, h, i) \
 402         for ((i) = ITERATOR_FIRST; hashmap_iterate((h), &(i), (void**)&(e), NULL); )
 403
 404 #define ORDERED_HASHMAP_FOREACH(e, h, i) \
 405         for ((i) = ITERATOR_FIRST; ordered_hashmap_iterate((h), &(i), (void**)&(e), NULL); )
 406
 407 #define HASHMAP_FOREACH_KEY(e, k, h, i) \
 408         for ((i) = ITERATOR_FIRST; hashmap_iterate((h), &(i), (void**)&(e), (const void**) &(k)); )
 409
 410 #define ORDERED_HASHMAP_FOREACH_KEY(e, k, h, i) \
 411         for ((i) = ITERATOR_FIRST; ordered_hashmap_iterate((h), &(i), (void**)&(e), (const void**) &(k)); )
 412
 413 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free);
 414 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free_free);
 415 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free_free_free);
 416 DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap*, ordered_hashmap_free);
 417 DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap*, ordered_hashmap_free_free);
 418 DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap*, ordered_hashmap_free_free_free);
 419
 420 #define _cleanup_hashmap_free_ _cleanup_(hashmap_freep)
 421 #define _cleanup_hashmap_free_free_ _cleanup_(hashmap_free_freep)
 422 #define _cleanup_hashmap_free_free_free_ _cleanup_(hashmap_free_free_freep)
 423 #define _cleanup_ordered_hashmap_free_ _cleanup_(ordered_hashmap_freep)
 424 #define _cleanup_ordered_hashmap_free_free_ _cleanup_(ordered_hashmap_free_freep)
 425 #define _cleanup_ordered_hashmap_free_free_free_ _cleanup_(ordered_hashmap_free_free_freep)
 426
 427 DEFINE_TRIVIAL_CLEANUP_FUNC(IteratedCache*, iterated_cache_free);
 428
 429 #define _cleanup_iterated_cache_free_ _cleanup_(iterated_cache_freep)