src/shared/hashmap.h

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