1 /* Licensed under LGPLv2+ - see LICENSE file for details */
5 #include <ccan/str/str.h>
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)
15 #define htable_debug(h, loc) ((void)loc, h)
19 * struct htable - private definition of a htable.
21 * It's exposed here so you can put it in your structures and so we can
22 * supply inline functions.
25 size_t (*rehash)(const void *elem, void *priv);
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;
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.
41 * This is useful for setting up static and global hash tables.
44 * // For simplicity's sake, say hash value is contents of elem.
45 * static size_t rehash(const void *elem, void *unused)
48 * return *(size_t *)elem;
50 * static struct htable ht = HTABLE_INITIALIZER(ht, rehash, NULL);
52 #define HTABLE_INITIALIZER(name, rehash, priv) \
53 { rehash, priv, 0, 0, 0, 0, 0, -1, 0, 0, &name.perfect_bit }
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.
61 void htable_init(struct htable *ht,
62 size_t (*rehash)(const void *elem, void *priv), void *priv);
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.
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
75 bool htable_init_sized(struct htable *ht,
76 size_t (*rehash)(const void *elem, void *priv),
77 void *priv, size_t size);
80 * htable_clear - empty a hash table.
81 * @ht: the hash table to clear
83 * This doesn't do anything to any pointers left in it.
85 void htable_clear(struct htable *ht);
89 * htable_check - check hash table for consistency
91 * @abortstr: the location to print on aborting, or NULL.
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.
98 * Returns the htable if it is consistent, NULL if not (it can never return
99 * NULL if @abortstr is set).
101 struct htable *htable_check(const struct htable *ht, const char *abortstr);
104 * htable_copy - duplicate a hash table.
105 * @dst: the hash table to overwrite
106 * @src: the hash table to copy
108 * Only fails on out-of-memory.
110 * Equivalent to (but faster than):
111 * if (!htable_init_sized(dst, src->rehash, src->priv, 1U << src->bits))
113 * v = htable_first(src, &i);
115 * htable_add(dst, v);
116 * v = htable_next(src, i);
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);
124 * htable_add - add a pointer into a hash table.
126 * @hash: the hash value of the object
127 * @p: the non-NULL pointer
129 * Also note that this can only fail due to allocation failure. Otherwise, it
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);
137 * htable_del - remove a pointer from a hash table
139 * @hash: the hash value of the object
142 * Returns true if the pointer was found (and deleted).
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);
149 * struct htable_iter - iterator or htable_first or htable_firstval etc.
151 * This refers to a location inside the hashtable.
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
163 * You'll need to check the value is what you want; returns NULL if none.
167 #define htable_firstval(htable, i, hash) \
168 htable_firstval_(htable_debug(htable, HTABLE_LOC), i, hash)
170 void *htable_firstval_(const struct htable *htable,
171 struct htable_iter *i, size_t hash);
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
179 * You'll need to check the value is what you want; returns NULL if no more.
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);
187 * htable_get - find an entry in the hash table
189 * @h: the hash value of the entry
190 * @cmp: the comparison function
191 * @ptr: the pointer to hand to the comparison function.
193 * Convenient inline wrapper for htable_firstval/htable_nextval loop.
195 static inline void *htable_get(const struct htable *ht,
197 bool (*cmp)(const void *candidate, void *ptr),
200 struct htable_iter i;
203 for (c = htable_firstval(ht,&i,h); c; c = htable_nextval(ht,&i,h)) {
204 if (cmp(c, (void *)ptr))
211 * htable_first - find an entry in the hash table
213 * @i: the struct htable_iter to initialize
215 * Get an entry in the hashtable; NULL if empty.
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);
222 * htable_next - find another entry in the hash table
224 * @i: the struct htable_iter to use
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.
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);
234 * htable_prev - find the previous entry in the hash table
236 * @i: the struct htable_iter to use
238 * Get previous entry in the hashtable; NULL if all done.
240 * "previous" here only means the item that would have been returned by
241 * htable_next() before the item it returned most recently.
243 * This is usually used in the middle of (or after) a htable_next iteration and
244 * to "unwind" actions taken.
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);
251 * htable_delval - remove an iterated pointer from a hash table
253 * @i: the htable_iter
255 * Usually used to delete a hash entry after it has been found with
256 * htable_firstval etc.
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);
262 #endif /* CCAN_HTABLE_H */