chiark / gitweb /
core: introduce parse_ip_port (#4825)
[elogind.git] / 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)