src/basic/hashmap.h

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