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 ITERATOR_FIRST ((Iterator) { .idx = _IDX_ITERATOR_FIRST, .next_key = NULL })
  69
  70 typedef unsigned long (*hash_func_t)(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]);
  71 typedef int (*compare_func_t)(const void *a, const void *b);
  72
  73 struct hash_ops {
  74         hash_func_t hash;
  75         compare_func_t compare;
  76 };
  77
  78 unsigned long string_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_;
  79 int string_compare_func(const void *a, const void *b) _pure_;
  80 extern const struct hash_ops string_hash_ops;
  81
  82 /* This will compare the passed pointers directly, and will not
  83  * dereference them. This is hence not useful for strings or
  84  * suchlike. */
  85 unsigned long trivial_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_;
  86 int trivial_compare_func(const void *a, const void *b) _const_;
  87 extern const struct hash_ops trivial_hash_ops;
  88
  89 /* 32bit values we can always just embedd in the pointer itself, but
  90  * in order to support 32bit archs we need store 64bit values
  91  * indirectly, since they don't fit in a pointer. */
  92 unsigned long uint64_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_;
  93 int uint64_compare_func(const void *a, const void *b) _pure_;
  94 extern const struct hash_ops uint64_hash_ops;
  95
  96 /* On some archs dev_t is 32bit, and on others 64bit. And sometimes
  97  * it's 64bit on 32bit archs, and sometimes 32bit on 64bit archs. Yuck! */
  98 #if SIZEOF_DEV_T != 8
  99 unsigned long devt_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_;
 100 int devt_compare_func(const void *a, const void *b) _pure_;
 101 extern const struct hash_ops devt_hash_ops = {
 102         .hash = devt_hash_func,
 103         .compare = devt_compare_func
 104 };
 105 #else
 106 #define devt_hash_func uint64_hash_func
 107 #define devt_compare_func uint64_compare_func
 108 #define devt_hash_ops uint64_hash_ops
 109 #endif
 110
 111 /* Macros for type checking */
 112 #define PTR_COMPATIBLE_WITH_HASHMAP_BASE(h) \
 113         (__builtin_types_compatible_p(typeof(h), HashmapBase*) || \
 114          __builtin_types_compatible_p(typeof(h), Hashmap*) || \
 115          __builtin_types_compatible_p(typeof(h), OrderedHashmap*) || \
 116          __builtin_types_compatible_p(typeof(h), Set*))
 117
 118 #define PTR_COMPATIBLE_WITH_PLAIN_HASHMAP(h) \
 119         (__builtin_types_compatible_p(typeof(h), Hashmap*) || \
 120          __builtin_types_compatible_p(typeof(h), OrderedHashmap*)) \
 121
 122 #define HASHMAP_BASE(h) \
 123         __builtin_choose_expr(PTR_COMPATIBLE_WITH_HASHMAP_BASE(h), \
 124                 (HashmapBase*)(h), \
 125                 (void)0)
 126
 127 #define PLAIN_HASHMAP(h) \
 128         __builtin_choose_expr(PTR_COMPATIBLE_WITH_PLAIN_HASHMAP(h), \
 129                 (Hashmap*)(h), \
 130                 (void)0)
 131
 132 #ifdef ENABLE_DEBUG_HASHMAP
 133 # define HASHMAP_DEBUG_PARAMS , const char *func, const char *file, int line
 134 # define HASHMAP_DEBUG_SRC_ARGS   , __func__, __FILE__, __LINE__
 135 # define HASHMAP_DEBUG_PASS_ARGS   , func, file, line
 136 #else
 137 # define HASHMAP_DEBUG_PARAMS
 138 # define HASHMAP_DEBUG_SRC_ARGS
 139 # define HASHMAP_DEBUG_PASS_ARGS
 140 #endif
 141
 142 Hashmap *internal_hashmap_new(const struct hash_ops *hash_ops  HASHMAP_DEBUG_PARAMS);
 143 OrderedHashmap *internal_ordered_hashmap_new(const struct hash_ops *hash_ops  HASHMAP_DEBUG_PARAMS);
 144 #define hashmap_new(ops) internal_hashmap_new(ops  HASHMAP_DEBUG_SRC_ARGS)
 145 #define ordered_hashmap_new(ops) internal_ordered_hashmap_new(ops  HASHMAP_DEBUG_SRC_ARGS)
 146
 147 void internal_hashmap_free(HashmapBase *h);
 148 static inline void hashmap_free(Hashmap *h) {
 149         internal_hashmap_free(HASHMAP_BASE(h));
 150 }
 151 static inline void ordered_hashmap_free(OrderedHashmap *h) {
 152         internal_hashmap_free(HASHMAP_BASE(h));
 153 }
 154
 155 void internal_hashmap_free_free(HashmapBase *h);
 156 static inline void hashmap_free_free(Hashmap *h) {
 157         internal_hashmap_free_free(HASHMAP_BASE(h));
 158 }
 159 static inline void ordered_hashmap_free_free(OrderedHashmap *h) {
 160         internal_hashmap_free_free(HASHMAP_BASE(h));
 161 }
 162
 163 void hashmap_free_free_free(Hashmap *h);
 164 static inline void ordered_hashmap_free_free_free(OrderedHashmap *h) {
 165         hashmap_free_free_free(PLAIN_HASHMAP(h));
 166 }
 167
 168 HashmapBase *internal_hashmap_copy(HashmapBase *h);
 169 static inline Hashmap *hashmap_copy(Hashmap *h) {
 170         return (Hashmap*) internal_hashmap_copy(HASHMAP_BASE(h));
 171 }
 172 static inline OrderedHashmap *ordered_hashmap_copy(OrderedHashmap *h) {
 173         return (OrderedHashmap*) internal_hashmap_copy(HASHMAP_BASE(h));
 174 }
 175
 176 int internal_hashmap_ensure_allocated(Hashmap **h, const struct hash_ops *hash_ops  HASHMAP_DEBUG_PARAMS);
 177 int internal_ordered_hashmap_ensure_allocated(OrderedHashmap **h, const struct hash_ops *hash_ops  HASHMAP_DEBUG_PARAMS);
 178 #define hashmap_ensure_allocated(h, ops) internal_hashmap_ensure_allocated(h, ops  HASHMAP_DEBUG_SRC_ARGS)
 179 #define ordered_hashmap_ensure_allocated(h, ops) internal_ordered_hashmap_ensure_allocated(h, ops  HASHMAP_DEBUG_SRC_ARGS)
 180
 181 int hashmap_put(Hashmap *h, const void *key, void *value);
 182 static inline int ordered_hashmap_put(OrderedHashmap *h, const void *key, void *value) {
 183         return hashmap_put(PLAIN_HASHMAP(h), key, value);
 184 }
 185
 186 int hashmap_update(Hashmap *h, const void *key, void *value);
 187 static inline int ordered_hashmap_update(OrderedHashmap *h, const void *key, void *value) {
 188         return hashmap_update(PLAIN_HASHMAP(h), key, value);
 189 }
 190
 191 int hashmap_replace(Hashmap *h, const void *key, void *value);
 192 static inline int ordered_hashmap_replace(OrderedHashmap *h, const void *key, void *value) {
 193         return hashmap_replace(PLAIN_HASHMAP(h), key, value);
 194 }
 195
 196 void *internal_hashmap_get(HashmapBase *h, const void *key);
 197 static inline void *hashmap_get(Hashmap *h, const void *key) {
 198         return internal_hashmap_get(HASHMAP_BASE(h), key);
 199 }
 200 static inline void *ordered_hashmap_get(OrderedHashmap *h, const void *key) {
 201         return internal_hashmap_get(HASHMAP_BASE(h), key);
 202 }
 203
 204 void *hashmap_get2(Hashmap *h, const void *key, void **rkey);
 205 static inline void *ordered_hashmap_get2(OrderedHashmap *h, const void *key, void **rkey) {
 206         return hashmap_get2(PLAIN_HASHMAP(h), key, rkey);
 207 }
 208
 209 bool internal_hashmap_contains(HashmapBase *h, const void *key);
 210 static inline bool hashmap_contains(Hashmap *h, const void *key) {
 211         return internal_hashmap_contains(HASHMAP_BASE(h), key);
 212 }
 213 static inline bool ordered_hashmap_contains(OrderedHashmap *h, const void *key) {
 214         return internal_hashmap_contains(HASHMAP_BASE(h), key);
 215 }
 216
 217 void *internal_hashmap_remove(HashmapBase *h, const void *key);
 218 static inline void *hashmap_remove(Hashmap *h, const void *key) {
 219         return internal_hashmap_remove(HASHMAP_BASE(h), key);
 220 }
 221 static inline void *ordered_hashmap_remove(OrderedHashmap *h, const void *key) {
 222         return internal_hashmap_remove(HASHMAP_BASE(h), key);
 223 }
 224
 225 void *hashmap_remove2(Hashmap *h, const void *key, void **rkey);
 226 static inline void *ordered_hashmap_remove2(OrderedHashmap *h, const void *key, void **rkey) {
 227         return hashmap_remove2(PLAIN_HASHMAP(h), key, rkey);
 228 }
 229
 230 void *hashmap_remove_value(Hashmap *h, const void *key, void *value);
 231 static inline void *ordered_hashmap_remove_value(OrderedHashmap *h, const void *key, void *value) {
 232         return hashmap_remove_value(PLAIN_HASHMAP(h), key, value);
 233 }
 234
 235 int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value);
 236 static inline int ordered_hashmap_remove_and_put(OrderedHashmap *h, const void *old_key, const void *new_key, void *value) {
 237         return hashmap_remove_and_put(PLAIN_HASHMAP(h), old_key, new_key, value);
 238 }
 239
 240 int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value);
 241 static inline int ordered_hashmap_remove_and_replace(OrderedHashmap *h, const void *old_key, const void *new_key, void *value) {
 242         return hashmap_remove_and_replace(PLAIN_HASHMAP(h), old_key, new_key, value);
 243 }
 244
 245 /* Since merging data from a OrderedHashmap into a Hashmap or vice-versa
 246  * should just work, allow this by having looser type-checking here. */
 247 int internal_hashmap_merge(Hashmap *h, Hashmap *other);
 248 #define hashmap_merge(h, other) internal_hashmap_merge(PLAIN_HASHMAP(h), PLAIN_HASHMAP(other))
 249 #define ordered_hashmap_merge(h, other) hashmap_merge(h, other)
 250
 251 int internal_hashmap_reserve(HashmapBase *h, unsigned entries_add);
 252 static inline int hashmap_reserve(Hashmap *h, unsigned entries_add) {
 253         return internal_hashmap_reserve(HASHMAP_BASE(h), entries_add);
 254 }
 255 static inline int ordered_hashmap_reserve(OrderedHashmap *h, unsigned entries_add) {
 256         return internal_hashmap_reserve(HASHMAP_BASE(h), entries_add);
 257 }
 258
 259 int internal_hashmap_move(HashmapBase *h, HashmapBase *other);
 260 /* Unlike hashmap_merge, hashmap_move does not allow mixing the types. */
 261 static inline int hashmap_move(Hashmap *h, Hashmap *other) {
 262         return internal_hashmap_move(HASHMAP_BASE(h), HASHMAP_BASE(other));
 263 }
 264 static inline int ordered_hashmap_move(OrderedHashmap *h, OrderedHashmap *other) {
 265         return internal_hashmap_move(HASHMAP_BASE(h), HASHMAP_BASE(other));
 266 }
 267
 268 int internal_hashmap_move_one(HashmapBase *h, HashmapBase *other, const void *key);
 269 static inline int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) {
 270         return internal_hashmap_move_one(HASHMAP_BASE(h), HASHMAP_BASE(other), key);
 271 }
 272 static inline int ordered_hashmap_move_one(OrderedHashmap *h, OrderedHashmap *other, const void *key) {
 273         return internal_hashmap_move_one(HASHMAP_BASE(h), HASHMAP_BASE(other), key);
 274 }
 275
 276 unsigned internal_hashmap_size(HashmapBase *h) _pure_;
 277 static inline unsigned hashmap_size(Hashmap *h) {
 278         return internal_hashmap_size(HASHMAP_BASE(h));
 279 }
 280 static inline unsigned ordered_hashmap_size(OrderedHashmap *h) {
 281         return internal_hashmap_size(HASHMAP_BASE(h));
 282 }
 283
 284 static inline bool hashmap_isempty(Hashmap *h) {
 285         return hashmap_size(h) == 0;
 286 }
 287 static inline bool ordered_hashmap_isempty(OrderedHashmap *h) {
 288         return ordered_hashmap_size(h) == 0;
 289 }
 290
 291 unsigned internal_hashmap_buckets(HashmapBase *h) _pure_;
 292 static inline unsigned hashmap_buckets(Hashmap *h) {
 293         return internal_hashmap_buckets(HASHMAP_BASE(h));
 294 }
 295 static inline unsigned ordered_hashmap_buckets(OrderedHashmap *h) {
 296         return internal_hashmap_buckets(HASHMAP_BASE(h));
 297 }
 298
 299 void *internal_hashmap_iterate(HashmapBase *h, Iterator *i, const void **key);
 300 static inline void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key) {
 301         return internal_hashmap_iterate(HASHMAP_BASE(h), i, key);
 302 }
 303 static inline void *ordered_hashmap_iterate(OrderedHashmap *h, Iterator *i, const void **key) {
 304         return internal_hashmap_iterate(HASHMAP_BASE(h), i, key);
 305 }
 306
 307 void internal_hashmap_clear(HashmapBase *h);
 308 static inline void hashmap_clear(Hashmap *h) {
 309         internal_hashmap_clear(HASHMAP_BASE(h));
 310 }
 311 static inline void ordered_hashmap_clear(OrderedHashmap *h) {
 312         internal_hashmap_clear(HASHMAP_BASE(h));
 313 }
 314
 315 void internal_hashmap_clear_free(HashmapBase *h);
 316 static inline void hashmap_clear_free(Hashmap *h) {
 317         internal_hashmap_clear_free(HASHMAP_BASE(h));
 318 }
 319 static inline void ordered_hashmap_clear_free(OrderedHashmap *h) {
 320         internal_hashmap_clear_free(HASHMAP_BASE(h));
 321 }
 322
 323 void hashmap_clear_free_free(Hashmap *h);
 324 static inline void ordered_hashmap_clear_free_free(OrderedHashmap *h) {
 325         hashmap_clear_free_free(PLAIN_HASHMAP(h));
 326 }
 327
 328 /*
 329  * Note about all *_first*() functions
 330  *
 331  * For plain Hashmaps and Sets the order of entries is undefined.
 332  * The functions find whatever entry is first in the implementation
 333  * internal order.
 334  *
 335  * Only for OrderedHashmaps the order is well defined and finding
 336  * the first entry is O(1).
 337  */
 338
 339 void *internal_hashmap_steal_first(HashmapBase *h);
 340 static inline void *hashmap_steal_first(Hashmap *h) {
 341         return internal_hashmap_steal_first(HASHMAP_BASE(h));
 342 }
 343 static inline void *ordered_hashmap_steal_first(OrderedHashmap *h) {
 344         return internal_hashmap_steal_first(HASHMAP_BASE(h));
 345 }
 346
 347 void *internal_hashmap_steal_first_key(HashmapBase *h);
 348 static inline void *hashmap_steal_first_key(Hashmap *h) {
 349         return internal_hashmap_steal_first_key(HASHMAP_BASE(h));
 350 }
 351 static inline void *ordered_hashmap_steal_first_key(OrderedHashmap *h) {
 352         return internal_hashmap_steal_first_key(HASHMAP_BASE(h));
 353 }
 354
 355 void *internal_hashmap_first_key(HashmapBase *h) _pure_;
 356 static inline void *hashmap_first_key(Hashmap *h) {
 357         return internal_hashmap_first_key(HASHMAP_BASE(h));
 358 }
 359 static inline void *ordered_hashmap_first_key(OrderedHashmap *h) {
 360         return internal_hashmap_first_key(HASHMAP_BASE(h));
 361 }
 362
 363 void *internal_hashmap_first(HashmapBase *h) _pure_;
 364 static inline void *hashmap_first(Hashmap *h) {
 365         return internal_hashmap_first(HASHMAP_BASE(h));
 366 }
 367 static inline void *ordered_hashmap_first(OrderedHashmap *h) {
 368         return internal_hashmap_first(HASHMAP_BASE(h));
 369 }
 370
 371 /* no hashmap_next */
 372 void *ordered_hashmap_next(OrderedHashmap *h, const void *key);
 373
 374 char **internal_hashmap_get_strv(HashmapBase *h);
 375 static inline char **hashmap_get_strv(Hashmap *h) {
 376         return internal_hashmap_get_strv(HASHMAP_BASE(h));
 377 }
 378 static inline char **ordered_hashmap_get_strv(OrderedHashmap *h) {
 379         return internal_hashmap_get_strv(HASHMAP_BASE(h));
 380 }
 381
 382 /*
 383  * Hashmaps are iterated in unpredictable order.
 384  * OrderedHashmaps are an exception to this. They are iterated in the order
 385  * the entries were inserted.
 386  * It is safe to remove the current entry.
 387  */
 388 #define HASHMAP_FOREACH(e, h, i) \
 389         for ((i) = ITERATOR_FIRST, (e) = hashmap_iterate((h), &(i), NULL); \
 390              (e); \
 391              (e) = hashmap_iterate((h), &(i), NULL))
 392
 393 #define ORDERED_HASHMAP_FOREACH(e, h, i) \
 394         for ((i) = ITERATOR_FIRST, (e) = ordered_hashmap_iterate((h), &(i), NULL); \
 395              (e); \
 396              (e) = ordered_hashmap_iterate((h), &(i), NULL))
 397
 398 #define HASHMAP_FOREACH_KEY(e, k, h, i) \
 399         for ((i) = ITERATOR_FIRST, (e) = hashmap_iterate((h), &(i), (const void**) &(k)); \
 400              (e); \
 401              (e) = hashmap_iterate((h), &(i), (const void**) &(k)))
 402
 403 #define ORDERED_HASHMAP_FOREACH_KEY(e, k, h, i) \
 404         for ((i) = ITERATOR_FIRST, (e) = ordered_hashmap_iterate((h), &(i), (const void**) &(k)); \
 405              (e); \
 406              (e) = ordered_hashmap_iterate((h), &(i), (const void**) &(k)))
 407
 408 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free);
 409 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free_free);
 410 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free_free_free);
 411 DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap*, ordered_hashmap_free);
 412 DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap*, ordered_hashmap_free_free);
 413 DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap*, ordered_hashmap_free_free_free);
 414
 415 #define _cleanup_hashmap_free_ _cleanup_(hashmap_freep)
 416 #define _cleanup_hashmap_free_free_ _cleanup_(hashmap_free_freep)
 417 #define _cleanup_hashmap_free_free_free_ _cleanup_(hashmap_free_free_freep)
 418 #define _cleanup_ordered_hashmap_free_ _cleanup_(ordered_hashmap_freep)
 419 #define _cleanup_ordered_hashmap_free_free_ _cleanup_(ordered_hashmap_free_freep)
 420 #define _cleanup_ordered_hashmap_free_free_free_ _cleanup_(ordered_hashmap_free_free_freep)