src/basic/hashmap.h

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