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