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
  10   systemd is free software; you can redistribute it and/or modify it
  11   under the terms of the GNU Lesser General Public License as published by
  12   the Free Software Foundation; either version 2.1 of the License, or
  13   (at your option) any later version.
  14
  15   systemd is distributed in the hope that it will be useful, but
  16   WITHOUT ANY WARRANTY; without even the implied warranty of
  17   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  18   Lesser General Public License for more details.
  19
  20   You should have received a copy of the GNU Lesser General Public License
  21   along with systemd; If not, see <http://www.gnu.org/licenses/>.
  22 ***/
  23
  24 #include <stdbool.h>
  25
  26 #include "macro.h"
  27 #include "util.h"
  28
  29 /* Pretty straightforward hash table implementation. As a minor
  30  * optimization a NULL hashmap object will be treated as empty hashmap
  31  * for all read operations. That way it is not necessary to
  32  * instantiate an object for each Hashmap use. */
  33
  34 #define HASH_KEY_SIZE 16
  35
  36 typedef struct Hashmap Hashmap;
  37 typedef struct OrderedHashmap OrderedHashmap;
  38 typedef struct _IteratorStruct _IteratorStruct;
  39 typedef _IteratorStruct* Iterator;
  40
  41 #define ITERATOR_FIRST ((Iterator) 0)
  42 #define ITERATOR_LAST ((Iterator) -1)
  43
  44 typedef unsigned long (*hash_func_t)(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]);
  45 typedef int (*compare_func_t)(const void *a, const void *b);
  46
  47 struct hash_ops {
  48         hash_func_t hash;
  49         compare_func_t compare;
  50 };
  51
  52 unsigned long string_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_;
  53 int string_compare_func(const void *a, const void *b) _pure_;
  54 extern const struct hash_ops string_hash_ops;
  55
  56 /* This will compare the passed pointers directly, and will not
  57  * dereference them. This is hence not useful for strings or
  58  * suchlike. */
  59 unsigned long trivial_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_;
  60 int trivial_compare_func(const void *a, const void *b) _const_;
  61 extern const struct hash_ops trivial_hash_ops;
  62
  63 /* 32bit values we can always just embedd in the pointer itself, but
  64  * in order to support 32bit archs we need store 64bit values
  65  * indirectly, since they don't fit in a pointer. */
  66 unsigned long uint64_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_;
  67 int uint64_compare_func(const void *a, const void *b) _pure_;
  68 extern const struct hash_ops uint64_hash_ops;
  69
  70 /* On some archs dev_t is 32bit, and on others 64bit. And sometimes
  71  * it's 64bit on 32bit archs, and sometimes 32bit on 64bit archs. Yuck! */
  72 #if SIZEOF_DEV_T != 8
  73 unsigned long devt_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_;
  74 int devt_compare_func(const void *a, const void *b) _pure_;
  75 extern const struct hash_ops devt_hash_ops = {
  76         .hash = devt_hash_func,
  77         .compare = devt_compare_func
  78 };
  79 #else
  80 #define devt_hash_func uint64_hash_func
  81 #define devt_compare_func uint64_compare_func
  82 #define devt_hash_ops uint64_hash_ops
  83 #endif
  84
  85 Hashmap *hashmap_new(const struct hash_ops *hash_ops);
  86 static inline OrderedHashmap *ordered_hashmap_new(const struct hash_ops *hash_ops) {
  87         return (OrderedHashmap*) hashmap_new(hash_ops);
  88 }
  89 void hashmap_free(Hashmap *h);
  90 static inline void ordered_hashmap_free(OrderedHashmap *h) {
  91         hashmap_free((Hashmap*) h);
  92 }
  93 void hashmap_free_free(Hashmap *h);
  94 static inline void ordered_hashmap_free_free(OrderedHashmap *h) {
  95         hashmap_free_free((Hashmap*) h);
  96 }
  97 void hashmap_free_free_free(Hashmap *h);
  98 static inline void ordered_hashmap_free_free_free(OrderedHashmap *h) {
  99         hashmap_free_free_free((Hashmap*) h);
 100 }
 101 Hashmap *hashmap_copy(Hashmap *h);
 102 static inline OrderedHashmap *ordered_hashmap_copy(OrderedHashmap *h) {
 103         return (OrderedHashmap*) hashmap_copy((Hashmap*) h);
 104 }
 105 int hashmap_ensure_allocated(Hashmap **h, const struct hash_ops *hash_ops);
 106 static inline int ordered_hashmap_ensure_allocated(OrderedHashmap **h, const struct hash_ops *hash_ops) {
 107         return hashmap_ensure_allocated((Hashmap**) h, hash_ops);
 108 }
 109
 110 int hashmap_put(Hashmap *h, const void *key, void *value);
 111 static inline int ordered_hashmap_put(OrderedHashmap *h, const void *key, void *value) {
 112         return hashmap_put((Hashmap*) h, key, value);
 113 }
 114 int hashmap_update(Hashmap *h, const void *key, void *value);
 115 static inline int ordered_hashmap_update(OrderedHashmap *h, const void *key, void *value) {
 116         return hashmap_update((Hashmap*) h, key, value);
 117 }
 118 int hashmap_replace(Hashmap *h, const void *key, void *value);
 119 static inline int ordered_hashmap_replace(OrderedHashmap *h, const void *key, void *value) {
 120         return hashmap_replace((Hashmap*) h, key, value);
 121 }
 122 void *hashmap_get(Hashmap *h, const void *key);
 123 static inline void *ordered_hashmap_get(OrderedHashmap *h, const void *key) {
 124         return hashmap_get((Hashmap*) h, key);
 125 }
 126 void *hashmap_get2(Hashmap *h, const void *key, void **rkey);
 127 static inline void *ordered_hashmap_get2(OrderedHashmap *h, const void *key, void **rkey) {
 128         return hashmap_get2((Hashmap*) h, key, rkey);
 129 }
 130 bool hashmap_contains(Hashmap *h, const void *key);
 131 static inline bool ordered_hashmap_contains(OrderedHashmap *h, const void *key) {
 132         return hashmap_contains((Hashmap*) h, key);
 133 }
 134 void *hashmap_remove(Hashmap *h, const void *key);
 135 static inline void *ordered_hashmap_remove(OrderedHashmap *h, const void *key) {
 136         return hashmap_remove((Hashmap*) h, key);
 137 }
 138 void *hashmap_remove2(Hashmap *h, const void *key, void **rkey);
 139 static inline void *ordered_hashmap_remove2(OrderedHashmap *h, const void *key, void **rkey) {
 140         return hashmap_remove2((Hashmap*) h, key, rkey);
 141 }
 142 void *hashmap_remove_value(Hashmap *h, const void *key, void *value);
 143 static inline void *ordered_hashmap_remove_value(OrderedHashmap *h, const void *key, void *value) {
 144         return hashmap_remove_value((Hashmap*) h, key, value);
 145 }
 146 int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value);
 147 static inline int ordered_hashmap_remove_and_put(OrderedHashmap *h, const void *old_key, const void *new_key, void *value) {
 148         return hashmap_remove_and_put((Hashmap*) h, old_key, new_key, value);
 149 }
 150 int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value);
 151 static inline int ordered_hashmap_remove_and_replace(OrderedHashmap *h, const void *old_key, const void *new_key, void *value) {
 152         return hashmap_remove_and_replace((Hashmap*) h, old_key, new_key, value);
 153 }
 154
 155 int hashmap_merge(Hashmap *h, Hashmap *other);
 156 static inline int ordered_hashmap_merge(OrderedHashmap *h, OrderedHashmap *other) {
 157         return hashmap_merge((Hashmap*) h, (Hashmap*) other);
 158 }
 159 void hashmap_move(Hashmap *h, Hashmap *other);
 160 static inline void ordered_hashmap_move(OrderedHashmap *h, OrderedHashmap *other) {
 161         hashmap_move((Hashmap*) h, (Hashmap*) other);
 162 }
 163 int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key);
 164 static inline int ordered_hashmap_move_one(OrderedHashmap *h, OrderedHashmap *other, const void *key) {
 165         return hashmap_move_one((Hashmap*) h, (Hashmap*) other, key);
 166 }
 167
 168 unsigned hashmap_size(Hashmap *h) _pure_;
 169 static inline unsigned ordered_hashmap_size(OrderedHashmap *h) {
 170         return hashmap_size((Hashmap*) h);
 171 }
 172 bool hashmap_isempty(Hashmap *h) _pure_;
 173 static inline bool ordered_hashmap_isempty(OrderedHashmap *h) {
 174         return hashmap_isempty((Hashmap*) h);
 175 }
 176 unsigned hashmap_buckets(Hashmap *h) _pure_;
 177 static inline unsigned ordered_hashmap_buckets(OrderedHashmap *h) {
 178         return hashmap_buckets((Hashmap*) h);
 179 }
 180
 181 void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key);
 182 static inline void *ordered_hashmap_iterate(OrderedHashmap *h, Iterator *i, const void **key) {
 183         return hashmap_iterate((Hashmap*) h, i, key);
 184 }
 185
 186 void hashmap_clear(Hashmap *h);
 187 static inline void ordered_hashmap_clear(OrderedHashmap *h) {
 188         hashmap_clear((Hashmap*) h);
 189 }
 190 void hashmap_clear_free(Hashmap *h);
 191 static inline void ordered_hashmap_clear_free(OrderedHashmap *h) {
 192         hashmap_clear_free((Hashmap*) h);
 193 }
 194 void hashmap_clear_free_free(Hashmap *h);
 195 static inline void ordered_hashmap_clear_free_free(OrderedHashmap *h) {
 196         hashmap_clear_free_free((Hashmap*) h);
 197 }
 198
 199 void *hashmap_steal_first(Hashmap *h);
 200 static inline void *ordered_hashmap_steal_first(OrderedHashmap *h) {
 201         return hashmap_steal_first((Hashmap*) h);
 202 }
 203 void *hashmap_steal_first_key(Hashmap *h);
 204 static inline void *ordered_hashmap_steal_first_key(OrderedHashmap *h) {
 205         return hashmap_steal_first_key((Hashmap*) h);
 206 }
 207 void *hashmap_first(Hashmap *h) _pure_;
 208 static inline void *ordered_hashmap_first(OrderedHashmap *h) {
 209         return hashmap_first((Hashmap*) h);
 210 }
 211 void *hashmap_first_key(Hashmap *h) _pure_;
 212 static inline void *ordered_hashmap_first_key(OrderedHashmap *h) {
 213         return hashmap_first_key((Hashmap*) h);
 214 }
 215
 216 void *hashmap_next(Hashmap *h, const void *key);
 217 static inline void *ordered_hashmap_next(OrderedHashmap *h, const void *key) {
 218         return hashmap_next((Hashmap*) h, key);
 219 }
 220
 221 char **hashmap_get_strv(Hashmap *h);
 222 static inline char **ordered_hashmap_get_strv(OrderedHashmap *h) {
 223         return hashmap_get_strv((Hashmap*) h);
 224 }
 225
 226 #define HASHMAP_FOREACH(e, h, i) \
 227         for ((i) = ITERATOR_FIRST, (e) = hashmap_iterate((h), &(i), NULL); (e); (e) = hashmap_iterate((h), &(i), NULL))
 228
 229 #define ORDERED_HASHMAP_FOREACH(e, h, i) \
 230         for ((i) = ITERATOR_FIRST, (e) = ordered_hashmap_iterate((h), &(i), NULL); \
 231              (e); \
 232              (e) = ordered_hashmap_iterate((h), &(i), NULL))
 233
 234 #define HASHMAP_FOREACH_KEY(e, k, h, i) \
 235         for ((i) = ITERATOR_FIRST, (e) = hashmap_iterate((h), &(i), (const void**) &(k)); (e); (e) = hashmap_iterate((h), &(i), (const void**) &(k)))
 236
 237 #define ORDERED_HASHMAP_FOREACH_KEY(e, k, h, i) \
 238         for ((i) = ITERATOR_FIRST, (e) = ordered_hashmap_iterate((h), &(i), (const void**) &(k)); \
 239              (e); \
 240              (e) = ordered_hashmap_iterate((h), &(i), (const void**) &(k)))
 241
 242 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free);
 243 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free_free);
 244 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free_free_free);
 245 DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap*, ordered_hashmap_free);
 246 DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap*, ordered_hashmap_free_free);
 247 DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap*, ordered_hashmap_free_free_free);
 248 #define _cleanup_hashmap_free_ _cleanup_(hashmap_freep)
 249 #define _cleanup_hashmap_free_free_ _cleanup_(hashmap_free_freep)
 250 #define _cleanup_hashmap_free_free_free_ _cleanup_(hashmap_free_free_freep)
 251 #define _cleanup_ordered_hashmap_free_ _cleanup_(ordered_hashmap_freep)
 252 #define _cleanup_ordered_hashmap_free_free_ _cleanup_(ordered_hashmap_free_freep)
 253 #define _cleanup_ordered_hashmap_free_free_free_ _cleanup_(ordered_hashmap_free_free_freep)