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