tal: add tal_dup_or_null and tal_dup_talarr helpers.
[ccan] / ccan / htable / htable.h
1 /* Licensed under LGPLv2+ - see LICENSE file for details */
2 #ifndef CCAN_HTABLE_H
3 #define CCAN_HTABLE_H
4 #include "config.h"
5 #include <ccan/str/str.h>
6 #include <stdint.h>
7 #include <stdbool.h>
8 #include <stdlib.h>
9
10 /* Define CCAN_HTABLE_DEBUG for expensive debugging checks on each call. */
11 #define HTABLE_LOC __FILE__ ":" stringify(__LINE__)
12 #ifdef CCAN_HTABLE_DEBUG
13 #define htable_debug(h, loc) htable_check((h), loc)
14 #else
15 #define htable_debug(h, loc) ((void)loc, h)
16 #endif
17
18 /**
19  * struct htable - private definition of a htable.
20  *
21  * It's exposed here so you can put it in your structures and so we can
22  * supply inline functions.
23  */
24 struct htable {
25         size_t (*rehash)(const void *elem, void *priv);
26         void *priv;
27         unsigned int bits, perfect_bitnum;
28         size_t elems, deleted;
29         /* These are the bits which are the same in all pointers. */
30         uintptr_t common_mask, common_bits;
31         uintptr_t *table;
32 };
33
34 /**
35  * HTABLE_INITIALIZER - static initialization for a hash table.
36  * @name: name of this htable.
37  * @rehash: hash function to use for rehashing.
38  * @priv: private argument to @rehash function.
39  *
40  * This is useful for setting up static and global hash tables.
41  *
42  * Example:
43  *      // For simplicity's sake, say hash value is contents of elem.
44  *      static size_t rehash(const void *elem, void *unused)
45  *      {
46  *              (void)unused;
47  *              return *(size_t *)elem;
48  *      }
49  *      static struct htable ht = HTABLE_INITIALIZER(ht, rehash, NULL);
50  */
51 #define HTABLE_INITIALIZER(name, rehash, priv)                          \
52         { rehash, priv, 0, 0, 0, 0, -1, 0, &name.common_bits }
53
54 /**
55  * htable_init - initialize an empty hash table.
56  * @ht: the hash table to initialize
57  * @rehash: hash function to use for rehashing.
58  * @priv: private argument to @rehash function.
59  */
60 void htable_init(struct htable *ht,
61                  size_t (*rehash)(const void *elem, void *priv), void *priv);
62
63 /**
64  * htable_init_sized - initialize an empty hash table of given size.
65  * @ht: the hash table to initialize
66  * @rehash: hash function to use for rehashing.
67  * @priv: private argument to @rehash function.
68  * @size: the number of element.
69  *
70  * If this returns false, @ht is still usable, but may need to do reallocation
71  * upon an add.  If this returns true, it will not need to reallocate within
72  * @size htable_adds.
73  */
74 bool htable_init_sized(struct htable *ht,
75                        size_t (*rehash)(const void *elem, void *priv),
76                        void *priv, size_t size);
77
78 /**
79  * htable_count - count number of entries in a hash table.
80  * @ht: the hash table
81  */
82 static inline size_t htable_count(const struct htable *ht)
83 {
84         return ht->elems;
85 }
86
87 /**
88  * htable_clear - empty a hash table.
89  * @ht: the hash table to clear
90  *
91  * This doesn't do anything to any pointers left in it.
92  */
93 void htable_clear(struct htable *ht);
94
95
96 /**
97  * htable_check - check hash table for consistency
98  * @ht: the htable
99  * @abortstr: the location to print on aborting, or NULL.
100  *
101  * Because hash tables have redundant information, consistency checking that
102  * each element is in the correct location can be done.  This is useful as a
103  * debugging check.  If @abortstr is non-NULL, that will be printed in a
104  * diagnostic if the htable is inconsistent, and the function will abort.
105  *
106  * Returns the htable if it is consistent, NULL if not (it can never return
107  * NULL if @abortstr is set).
108  */
109 struct htable *htable_check(const struct htable *ht, const char *abortstr);
110
111 /**
112  * htable_copy - duplicate a hash table.
113  * @dst: the hash table to overwrite
114  * @src: the hash table to copy
115  *
116  * Only fails on out-of-memory.
117  *
118  * Equivalent to (but faster than):
119  *    if (!htable_init_sized(dst, src->rehash, src->priv, 1U << src->bits))
120  *         return false;
121  *    v = htable_first(src, &i);
122  *    while (v) {
123  *              htable_add(dst, v);
124  *              v = htable_next(src, i);
125  *    }
126  *    return true;
127  */
128 #define htable_copy(dst, src) htable_copy_(dst, htable_debug(src, HTABLE_LOC))
129 bool htable_copy_(struct htable *dst, const struct htable *src);
130
131 /**
132  * htable_add - add a pointer into a hash table.
133  * @ht: the htable
134  * @hash: the hash value of the object
135  * @p: the non-NULL pointer
136  *
137  * Also note that this can only fail due to allocation failure.  Otherwise, it
138  * returns true.
139  */
140 #define htable_add(ht, hash, p) \
141         htable_add_(htable_debug(ht, HTABLE_LOC), hash, p)
142 bool htable_add_(struct htable *ht, size_t hash, const void *p);
143
144 /**
145  * htable_del - remove a pointer from a hash table
146  * @ht: the htable
147  * @hash: the hash value of the object
148  * @p: the pointer
149  *
150  * Returns true if the pointer was found (and deleted).
151  */
152 #define htable_del(ht, hash, p) \
153         htable_del_(htable_debug(ht, HTABLE_LOC), hash, p)
154 bool htable_del_(struct htable *ht, size_t hash, const void *p);
155
156 /**
157  * struct htable_iter - iterator or htable_first or htable_firstval etc.
158  *
159  * This refers to a location inside the hashtable.
160  */
161 struct htable_iter {
162         size_t off;
163 };
164
165 /**
166  * htable_firstval - find a candidate for a given hash value
167  * @htable: the hashtable
168  * @i: the struct htable_iter to initialize
169  * @hash: the hash value
170  *
171  * You'll need to check the value is what you want; returns NULL if none.
172  * See Also:
173  *      htable_delval()
174  */
175 #define htable_firstval(htable, i, hash) \
176         htable_firstval_(htable_debug(htable, HTABLE_LOC), i, hash)
177
178 void *htable_firstval_(const struct htable *htable,
179                        struct htable_iter *i, size_t hash);
180
181 /**
182  * htable_nextval - find another candidate for a given hash value
183  * @htable: the hashtable
184  * @i: the struct htable_iter to initialize
185  * @hash: the hash value
186  *
187  * You'll need to check the value is what you want; returns NULL if no more.
188  */
189 #define htable_nextval(htable, i, hash) \
190         htable_nextval_(htable_debug(htable, HTABLE_LOC), i, hash)
191 void *htable_nextval_(const struct htable *htable,
192                       struct htable_iter *i, size_t hash);
193
194 /**
195  * htable_get - find an entry in the hash table
196  * @ht: the hashtable
197  * @h: the hash value of the entry
198  * @cmp: the comparison function
199  * @ptr: the pointer to hand to the comparison function.
200  *
201  * Convenient inline wrapper for htable_firstval/htable_nextval loop.
202  */
203 static inline void *htable_get(const struct htable *ht,
204                                size_t h,
205                                bool (*cmp)(const void *candidate, void *ptr),
206                                const void *ptr)
207 {
208         struct htable_iter i;
209         void *c;
210
211         for (c = htable_firstval(ht,&i,h); c; c = htable_nextval(ht,&i,h)) {
212                 if (cmp(c, (void *)ptr))
213                         return c;
214         }
215         return NULL;
216 }
217
218 /**
219  * htable_first - find an entry in the hash table
220  * @ht: the hashtable
221  * @i: the struct htable_iter to initialize
222  *
223  * Get an entry in the hashtable; NULL if empty.
224  */
225 #define htable_first(htable, i) \
226         htable_first_(htable_debug(htable, HTABLE_LOC), i)
227 void *htable_first_(const struct htable *htable, struct htable_iter *i);
228
229 /**
230  * htable_next - find another entry in the hash table
231  * @ht: the hashtable
232  * @i: the struct htable_iter to use
233  *
234  * Get another entry in the hashtable; NULL if all done.
235  * This is usually used after htable_first or prior non-NULL htable_next.
236  */
237 #define htable_next(htable, i) \
238         htable_next_(htable_debug(htable, HTABLE_LOC), i)
239 void *htable_next_(const struct htable *htable, struct htable_iter *i);
240
241 /**
242  * htable_prev - find the previous entry in the hash table
243  * @ht: the hashtable
244  * @i: the struct htable_iter to use
245  *
246  * Get previous entry in the hashtable; NULL if all done.
247  *
248  * "previous" here only means the item that would have been returned by
249  * htable_next() before the item it returned most recently.
250  *
251  * This is usually used in the middle of (or after) a htable_next iteration and
252  * to "unwind" actions taken.
253  */
254 #define htable_prev(htable, i) \
255         htable_prev_(htable_debug(htable, HTABLE_LOC), i)
256 void *htable_prev_(const struct htable *htable, struct htable_iter *i);
257
258 /**
259  * htable_delval - remove an iterated pointer from a hash table
260  * @ht: the htable
261  * @i: the htable_iter
262  *
263  * Usually used to delete a hash entry after it has been found with
264  * htable_firstval etc.
265  */
266 #define htable_delval(htable, i) \
267         htable_delval_(htable_debug(htable, HTABLE_LOC), i)
268 void htable_delval_(struct htable *ht, struct htable_iter *i);
269
270 /**
271  * htable_pick - set iterator to a random valid entry.
272  * @ht: the htable
273  * @seed: a random number to use.
274  * @i: the htable_iter which is output (or NULL).
275  *
276  * Usually used with htable_delval to delete a random entry.  Returns
277  * NULL iff the table is empty, otherwise a random entry.
278  */
279 #define htable_pick(htable, seed, i)                                    \
280         htable_pick_(htable_debug(htable, HTABLE_LOC), seed, i)
281 void *htable_pick_(const struct htable *ht, size_t seed, struct htable_iter *i);
282
283 /**
284  * htable_set_allocator - set calloc/free functions.
285  * @alloc: allocator to use, must zero memory!
286  * @free: unallocator to use (@p is NULL or a return from @alloc)
287  */
288 void htable_set_allocator(void *(*alloc)(struct htable *, size_t len),
289                           void (*free)(struct htable *, void *p));
290 #endif /* CCAN_HTABLE_H */