src/basic/hashmap.h

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