1 /* Licensed under LGPLv2+ - see LICENSE file for details */
9 * struct htable - private definition of a htable.
11 * It's exposed here so you can put it in your structures and so we can
12 * supply inline functions.
15 size_t (*rehash)(const void *elem, void *priv);
18 size_t elems, deleted, max, max_with_deleted;
19 /* These are the bits which are the same in all pointers. */
20 uintptr_t common_mask, common_bits;
21 uintptr_t perfect_bit;
26 * HTABLE_INITIALIZER - static initialization for a hash table.
27 * @name: name of this htable.
28 * @rehash: hash function to use for rehashing.
29 * @priv: private argument to @rehash function.
31 * This is useful for setting up static and global hash tables.
34 * // For simplicity's sake, say hash value is contents of elem.
35 * static size_t rehash(const void *elem, void *unused)
37 * return *(size_t *)elem;
39 * static struct htable ht = HTABLE_INITIALIZER(ht, rehash, NULL);
41 #define HTABLE_INITIALIZER(name, rehash, priv) \
42 { rehash, priv, 0, 0, 0, 0, 0, -1, 0, 0, &name.perfect_bit }
45 * htable_init - initialize an empty hash table.
46 * @ht: the hash table to initialize
47 * @rehash: hash function to use for rehashing.
48 * @priv: private argument to @rehash function.
50 void htable_init(struct htable *ht,
51 size_t (*rehash)(const void *elem, void *priv), void *priv);
54 * htable_clear - empty a hash table.
55 * @ht: the hash table to clear
57 * This doesn't do anything to any pointers left in it.
59 void htable_clear(struct htable *ht);
62 * htable_rehash - use a hashtree's rehash function
63 * @elem: the argument to rehash()
66 size_t htable_rehash(const void *elem);
69 * htable_add - add a pointer into a hash table.
71 * @hash: the hash value of the object
72 * @p: the non-NULL pointer
74 * Also note that this can only fail due to allocation failure. Otherwise, it
77 bool htable_add(struct htable *ht, size_t hash, const void *p);
80 * htable_del - remove a pointer from a hash table
82 * @hash: the hash value of the object
85 * Returns true if the pointer was found (and deleted).
87 bool htable_del(struct htable *ht, size_t hash, const void *p);
90 * struct htable_iter - iterator or htable_first or htable_firstval etc.
92 * This refers to a location inside the hashtable.
99 * htable_firstval - find a candidate for a given hash value
100 * @htable: the hashtable
101 * @i: the struct htable_iter to initialize
102 * @hash: the hash value
104 * You'll need to check the value is what you want; returns NULL if none.
108 void *htable_firstval(const struct htable *htable,
109 struct htable_iter *i, size_t hash);
112 * htable_nextval - find another candidate for a given hash value
113 * @htable: the hashtable
114 * @i: the struct htable_iter to initialize
115 * @hash: the hash value
117 * You'll need to check the value is what you want; returns NULL if no more.
119 void *htable_nextval(const struct htable *htable,
120 struct htable_iter *i, size_t hash);
123 * htable_get - find an entry in the hash table
125 * @h: the hash value of the entry
126 * @cmp: the comparison function
127 * @ptr: the pointer to hand to the comparison function.
129 * Convenient inline wrapper for htable_firstval/htable_nextval loop.
131 static inline void *htable_get(const struct htable *ht,
133 bool (*cmp)(const void *candidate, void *ptr),
136 struct htable_iter i;
139 for (c = htable_firstval(ht,&i,h); c; c = htable_nextval(ht,&i,h)) {
140 if (cmp(c, (void *)ptr))
147 * htable_first - find an entry in the hash table
149 * @i: the struct htable_iter to initialize
151 * Get an entry in the hashtable; NULL if empty.
153 void *htable_first(const struct htable *htable, struct htable_iter *i);
156 * htable_next - find another entry in the hash table
158 * @i: the struct htable_iter to use
160 * Get another entry in the hashtable; NULL if all done.
161 * This is usually used after htable_first or prior non-NULL htable_next.
163 void *htable_next(const struct htable *htable, struct htable_iter *i);
166 * htable_delval - remove an iterated pointer from a hash table
168 * @i: the htable_iter
170 * Usually used to delete a hash entry after it has been found with
171 * htable_firstval etc.
173 void htable_delval(struct htable *ht, struct htable_iter *i);
175 #endif /* CCAN_HTABLE_H */