1 /* Licensed under LGPLv2+ - see LICENSE file for details */
10 * struct htable - private definition of a htable.
12 * It's exposed here so you can put it in your structures and so we can
13 * supply inline functions.
16 size_t (*rehash)(const void *elem, void *priv);
19 size_t elems, deleted, max, max_with_deleted;
20 /* These are the bits which are the same in all pointers. */
21 uintptr_t common_mask, common_bits;
22 uintptr_t perfect_bit;
27 * HTABLE_INITIALIZER - static initialization for a hash table.
28 * @name: name of this htable.
29 * @rehash: hash function to use for rehashing.
30 * @priv: private argument to @rehash function.
32 * This is useful for setting up static and global hash tables.
35 * // For simplicity's sake, say hash value is contents of elem.
36 * static size_t rehash(const void *elem, void *unused)
39 * return *(size_t *)elem;
41 * static struct htable ht = HTABLE_INITIALIZER(ht, rehash, NULL);
43 #define HTABLE_INITIALIZER(name, rehash, priv) \
44 { rehash, priv, 0, 0, 0, 0, 0, -1, 0, 0, &name.perfect_bit }
47 * htable_init - initialize an empty hash table.
48 * @ht: the hash table to initialize
49 * @rehash: hash function to use for rehashing.
50 * @priv: private argument to @rehash function.
52 void htable_init(struct htable *ht,
53 size_t (*rehash)(const void *elem, void *priv), void *priv);
56 * htable_init_sized - initialize an empty hash table of given size.
57 * @ht: the hash table to initialize
58 * @rehash: hash function to use for rehashing.
59 * @priv: private argument to @rehash function.
60 * @size: the number of element.
62 * If this returns false, @ht is still usable, but may need to do reallocation
63 * upon an add. If this returns true, it will not need to reallocate within
66 bool htable_init_sized(struct htable *ht,
67 size_t (*rehash)(const void *elem, void *priv),
68 void *priv, size_t size);
71 * htable_clear - empty a hash table.
72 * @ht: the hash table to clear
74 * This doesn't do anything to any pointers left in it.
76 void htable_clear(struct htable *ht);
79 * htable_copy - duplicate a hash table.
80 * @dst: the hash table to overwrite
81 * @src: the hash table to copy
83 * Only fails on out-of-memory.
85 * Equivalent to (but faster than):
86 * if (!htable_init_sized(dst, src->rehash, src->priv, 1U << src->bits))
88 * v = htable_first(src, &i);
91 * v = htable_next(src, i);
95 bool htable_copy(struct htable *dst, const struct htable *src);
98 * htable_rehash - use a hashtree's rehash function
99 * @elem: the argument to rehash()
102 size_t htable_rehash(const void *elem);
105 * htable_add - add a pointer into a hash table.
107 * @hash: the hash value of the object
108 * @p: the non-NULL pointer
110 * Also note that this can only fail due to allocation failure. Otherwise, it
113 bool htable_add(struct htable *ht, size_t hash, const void *p);
116 * htable_del - remove a pointer from a hash table
118 * @hash: the hash value of the object
121 * Returns true if the pointer was found (and deleted).
123 bool htable_del(struct htable *ht, size_t hash, const void *p);
126 * struct htable_iter - iterator or htable_first or htable_firstval etc.
128 * This refers to a location inside the hashtable.
135 * htable_firstval - find a candidate for a given hash value
136 * @htable: the hashtable
137 * @i: the struct htable_iter to initialize
138 * @hash: the hash value
140 * You'll need to check the value is what you want; returns NULL if none.
144 void *htable_firstval(const struct htable *htable,
145 struct htable_iter *i, size_t hash);
148 * htable_nextval - find another candidate for a given hash value
149 * @htable: the hashtable
150 * @i: the struct htable_iter to initialize
151 * @hash: the hash value
153 * You'll need to check the value is what you want; returns NULL if no more.
155 void *htable_nextval(const struct htable *htable,
156 struct htable_iter *i, size_t hash);
159 * htable_get - find an entry in the hash table
161 * @h: the hash value of the entry
162 * @cmp: the comparison function
163 * @ptr: the pointer to hand to the comparison function.
165 * Convenient inline wrapper for htable_firstval/htable_nextval loop.
167 static inline void *htable_get(const struct htable *ht,
169 bool (*cmp)(const void *candidate, void *ptr),
172 struct htable_iter i;
175 for (c = htable_firstval(ht,&i,h); c; c = htable_nextval(ht,&i,h)) {
176 if (cmp(c, (void *)ptr))
183 * htable_first - find an entry in the hash table
185 * @i: the struct htable_iter to initialize
187 * Get an entry in the hashtable; NULL if empty.
189 void *htable_first(const struct htable *htable, struct htable_iter *i);
192 * htable_next - find another entry in the hash table
194 * @i: the struct htable_iter to use
196 * Get another entry in the hashtable; NULL if all done.
197 * This is usually used after htable_first or prior non-NULL htable_next.
199 void *htable_next(const struct htable *htable, struct htable_iter *i);
202 * htable_prev - find the previous entry in the hash table
204 * @i: the struct htable_iter to use
206 * Get previous entry in the hashtable; NULL if all done.
208 * "previous" here only means the item that would have been returned by
209 * htable_next() before the item it returned most recently.
211 * This is usually used in the middle of (or after) a htable_next iteration and
212 * to "unwind" actions taken.
214 void *htable_prev(const struct htable *htable, struct htable_iter *i);
217 * htable_delval - remove an iterated pointer from a hash table
219 * @i: the htable_iter
221 * Usually used to delete a hash entry after it has been found with
222 * htable_firstval etc.
224 void htable_delval(struct htable *ht, struct htable_iter *i);
226 #endif /* CCAN_HTABLE_H */