src/basic/hashmap.h

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