53c447c09b952b198913efa25a48b82d34777242
[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;
28         size_t elems, deleted, max, max_with_deleted;
29         /* These are the bits which are the same in all pointers. */
30         uintptr_t common_mask, common_bits;
31         uintptr_t perfect_bit;
32         uintptr_t *table;
33 };
34
35 /**
36  * HTABLE_INITIALIZER - static initialization for a hash table.
37  * @name: name of this htable.
38  * @rehash: hash function to use for rehashing.
39  * @priv: private argument to @rehash function.
40  *
41  * This is useful for setting up static and global hash tables.
42  *
43  * Example:
44  *      // For simplicity's sake, say hash value is contents of elem.
45  *      static size_t rehash(const void *elem, void *unused)
46  *      {
47  *              (void)unused;
48  *              return *(size_t *)elem;
49  *      }
50  *      static struct htable ht = HTABLE_INITIALIZER(ht, rehash, NULL);
51  */
52 #define HTABLE_INITIALIZER(name, rehash, priv)                          \
53         { rehash, priv, 0, 0, 0, 0, 0, -1, 0, 0, &name.perfect_bit }
54
55 /**
56  * htable_init - initialize an empty hash table.
57  * @ht: the hash table to initialize
58  * @rehash: hash function to use for rehashing.
59  * @priv: private argument to @rehash function.
60  */
61 void htable_init(struct htable *ht,
62                  size_t (*rehash)(const void *elem, void *priv), void *priv);
63
64 /**
65  * htable_init_sized - initialize an empty hash table of given size.
66  * @ht: the hash table to initialize
67  * @rehash: hash function to use for rehashing.
68  * @priv: private argument to @rehash function.
69  * @size: the number of element.
70  *
71  * If this returns false, @ht is still usable, but may need to do reallocation
72  * upon an add.  If this returns true, it will not need to reallocate within
73  * @size htable_adds.
74  */
75 bool htable_init_sized(struct htable *ht,
76                        size_t (*rehash)(const void *elem, void *priv),
77                        void *priv, size_t size);
78
79 /**
80  * htable_clear - empty a hash table.
81  * @ht: the hash table to clear
82  *
83  * This doesn't do anything to any pointers left in it.
84  */
85 void htable_clear(struct htable *ht);
86
87
88 /**
89  * htable_check - check hash table for consistency
90  * @ht: the htable
91  * @abortstr: the location to print on aborting, or NULL.
92  *
93  * Because hash tables have redundant information, consistency checking that
94  * each element is in the correct location can be done.  This is useful as a
95  * debugging check.  If @abortstr is non-NULL, that will be printed in a
96  * diagnostic if the htable is inconsistent, and the function will abort.
97  *
98  * Returns the htable if it is consistent, NULL if not (it can never return
99  * NULL if @abortstr is set).
100  */
101 struct htable *htable_check(const struct htable *ht, const char *abortstr);
102
103 /**
104  * htable_copy - duplicate a hash table.
105  * @dst: the hash table to overwrite
106  * @src: the hash table to copy
107  *
108  * Only fails on out-of-memory.
109  *
110  * Equivalent to (but faster than):
111  *    if (!htable_init_sized(dst, src->rehash, src->priv, 1U << src->bits))
112  *         return false;
113  *    v = htable_first(src, &i);
114  *    while (v) {
115  *              htable_add(dst, v);
116  *              v = htable_next(src, i);
117  *    }
118  *    return true;
119  */
120 #define htable_copy(dst, src) htable_copy_(dst, htable_debug(src, HTABLE_LOC))
121 bool htable_copy_(struct htable *dst, const struct htable *src);
122
123 /**
124  * htable_add - add a pointer into a hash table.
125  * @ht: the htable
126  * @hash: the hash value of the object
127  * @p: the non-NULL pointer
128  *
129  * Also note that this can only fail due to allocation failure.  Otherwise, it
130  * returns true.
131  */
132 #define htable_add(ht, hash, p) \
133         htable_add_(htable_debug(ht, HTABLE_LOC), hash, p)
134 bool htable_add_(struct htable *ht, size_t hash, const void *p);
135
136 /**
137  * htable_del - remove a pointer from a hash table
138  * @ht: the htable
139  * @hash: the hash value of the object
140  * @p: the pointer
141  *
142  * Returns true if the pointer was found (and deleted).
143  */
144 #define htable_del(ht, hash, p) \
145         htable_del_(htable_debug(ht, HTABLE_LOC), hash, p)
146 bool htable_del_(struct htable *ht, size_t hash, const void *p);
147
148 /**
149  * struct htable_iter - iterator or htable_first or htable_firstval etc.
150  *
151  * This refers to a location inside the hashtable.
152  */
153 struct htable_iter {
154         size_t off;
155 };
156
157 /**
158  * htable_firstval - find a candidate for a given hash value
159  * @htable: the hashtable
160  * @i: the struct htable_iter to initialize
161  * @hash: the hash value
162  *
163  * You'll need to check the value is what you want; returns NULL if none.
164  * See Also:
165  *      htable_delval()
166  */
167 #define htable_firstval(htable, i, hash) \
168         htable_firstval_(htable_debug(htable, HTABLE_LOC), i, hash)
169
170 void *htable_firstval_(const struct htable *htable,
171                        struct htable_iter *i, size_t hash);
172
173 /**
174  * htable_nextval - find another candidate for a given hash value
175  * @htable: the hashtable
176  * @i: the struct htable_iter to initialize
177  * @hash: the hash value
178  *
179  * You'll need to check the value is what you want; returns NULL if no more.
180  */
181 #define htable_nextval(htable, i, hash) \
182         htable_nextval_(htable_debug(htable, HTABLE_LOC), i, hash)
183 void *htable_nextval_(const struct htable *htable,
184                       struct htable_iter *i, size_t hash);
185
186 /**
187  * htable_get - find an entry in the hash table
188  * @ht: the hashtable
189  * @h: the hash value of the entry
190  * @cmp: the comparison function
191  * @ptr: the pointer to hand to the comparison function.
192  *
193  * Convenient inline wrapper for htable_firstval/htable_nextval loop.
194  */
195 static inline void *htable_get(const struct htable *ht,
196                                size_t h,
197                                bool (*cmp)(const void *candidate, void *ptr),
198                                const void *ptr)
199 {
200         struct htable_iter i;
201         void *c;
202
203         for (c = htable_firstval(ht,&i,h); c; c = htable_nextval(ht,&i,h)) {
204                 if (cmp(c, (void *)ptr))
205                         return c;
206         }
207         return NULL;
208 }
209
210 /**
211  * htable_first - find an entry in the hash table
212  * @ht: the hashtable
213  * @i: the struct htable_iter to initialize
214  *
215  * Get an entry in the hashtable; NULL if empty.
216  */
217 #define htable_first(htable, i) \
218         htable_first_(htable_debug(htable, HTABLE_LOC), i)
219 void *htable_first_(const struct htable *htable, struct htable_iter *i);
220
221 /**
222  * htable_next - find another entry in the hash table
223  * @ht: the hashtable
224  * @i: the struct htable_iter to use
225  *
226  * Get another entry in the hashtable; NULL if all done.
227  * This is usually used after htable_first or prior non-NULL htable_next.
228  */
229 #define htable_next(htable, i) \
230         htable_next_(htable_debug(htable, HTABLE_LOC), i)
231 void *htable_next_(const struct htable *htable, struct htable_iter *i);
232
233 /**
234  * htable_prev - find the previous entry in the hash table
235  * @ht: the hashtable
236  * @i: the struct htable_iter to use
237  *
238  * Get previous entry in the hashtable; NULL if all done.
239  *
240  * "previous" here only means the item that would have been returned by
241  * htable_next() before the item it returned most recently.
242  *
243  * This is usually used in the middle of (or after) a htable_next iteration and
244  * to "unwind" actions taken.
245  */
246 #define htable_prev(htable, i) \
247         htable_prev_(htable_debug(htable, HTABLE_LOC), i)
248 void *htable_prev_(const struct htable *htable, struct htable_iter *i);
249
250 /**
251  * htable_delval - remove an iterated pointer from a hash table
252  * @ht: the htable
253  * @i: the htable_iter
254  *
255  * Usually used to delete a hash entry after it has been found with
256  * htable_firstval etc.
257  */
258 #define htable_delval(htable, i) \
259         htable_delval_(htable_debug(htable, HTABLE_LOC), i)
260 void htable_delval_(struct htable *ht, struct htable_iter *i);
261
262 #endif /* CCAN_HTABLE_H */