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 <stdint.h>
6 #include <stdbool.h>
7 #include <stdlib.h>
8
9 /**
10 * struct htable - private definition of a htable.
11 *
12 * It's exposed here so you can put it in your structures and so we can
13 * supply inline functions.
14 */
15 struct htable {
16 size_t (*rehash)(const void *elem, void *priv);
17 void *priv;
18 unsigned int bits;
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;
23 uintptr_t *table;
24 };
25
26 /**
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.
31 *
32 * This is useful for setting up static and global hash tables.
33 *
34 * Example:
35 * // For simplicity's sake, say hash value is contents of elem.
36 * static size_t rehash(const void *elem, void *unused)
37 * {
38 * return *(size_t *)elem;
39 * }
40 * static struct htable ht = HTABLE_INITIALIZER(ht, rehash, NULL);
41 */
42 #define HTABLE_INITIALIZER(name, rehash, priv) \
43 { rehash, priv, 0, 0, 0, 0, 0, -1, 0, 0, &name.perfect_bit }
44
45 /**
46 * htable_init - initialize an empty hash table.
47 * @ht: the hash table to initialize
48 * @rehash: hash function to use for rehashing.
49 * @priv: private argument to @rehash function.
50 */
51 void htable_init(struct htable *ht,
52 size_t (*rehash)(const void *elem, void *priv), void *priv);
53
54 /**
55 * htable_init_sized - initialize an empty hash table of given size.
56 * @ht: the hash table to initialize
57 * @rehash: hash function to use for rehashing.
58 * @priv: private argument to @rehash function.
59 * @size: the number of element.
60 *
61 * If this returns false, @ht is still usable, but may need to do reallocation
62 * upon an add. If this returns true, it will not need to reallocate within
63 * @size htable_adds.
64 */
65 bool htable_init_sized(struct htable *ht,
66 size_t (*rehash)(const void *elem, void *priv),
67 void *priv, size_t size);
68
69 /**
70 * htable_clear - empty a hash table.
71 * @ht: the hash table to clear
72 *
73 * This doesn't do anything to any pointers left in it.
74 */
75 void htable_clear(struct htable *ht);
76
77 /**
78 * htable_rehash - use a hashtree's rehash function
79 * @elem: the argument to rehash()
80 *
81 */
82 size_t htable_rehash(const void *elem);
83
84 /**
85 * htable_add - add a pointer into a hash table.
86 * @ht: the htable
87 * @hash: the hash value of the object
88 * @p: the non-NULL pointer
89 *
90 * Also note that this can only fail due to allocation failure. Otherwise, it
91 * returns true.
92 */
93 bool htable_add(struct htable *ht, size_t hash, const void *p);
94
95 /**
96 * htable_del - remove a pointer from a hash table
97 * @ht: the htable
98 * @hash: the hash value of the object
99 * @p: the pointer
100 *
101 * Returns true if the pointer was found (and deleted).
102 */
103 bool htable_del(struct htable *ht, size_t hash, const void *p);
104
105 /**
106 * struct htable_iter - iterator or htable_first or htable_firstval etc.
107 *
108 * This refers to a location inside the hashtable.
109 */
110 struct htable_iter {
111 size_t off;
112 };
113
114 /**
115 * htable_firstval - find a candidate for a given hash value
116 * @htable: the hashtable
117 * @i: the struct htable_iter to initialize
118 * @hash: the hash value
119 *
120 * You'll need to check the value is what you want; returns NULL if none.
121 * See Also:
122 * htable_delval()
123 */
124 void *htable_firstval(const struct htable *htable,
125 struct htable_iter *i, size_t hash);
126
127 /**
128 * htable_nextval - find another candidate for a given hash value
129 * @htable: the hashtable
130 * @i: the struct htable_iter to initialize
131 * @hash: the hash value
132 *
133 * You'll need to check the value is what you want; returns NULL if no more.
134 */
135 void *htable_nextval(const struct htable *htable,
136 struct htable_iter *i, size_t hash);
137
138 /**
139 * htable_get - find an entry in the hash table
140 * @ht: the hashtable
141 * @h: the hash value of the entry
142 * @cmp: the comparison function
143 * @ptr: the pointer to hand to the comparison function.
144 *
145 * Convenient inline wrapper for htable_firstval/htable_nextval loop.
146 */
htable_get(const struct htable * ht,size_t h,bool (* cmp)(const void * candidate,void * ptr),const void * ptr)147 static inline void *htable_get(const struct htable *ht,
148 size_t h,
149 bool (*cmp)(const void *candidate, void *ptr),
150 const void *ptr)
151 {
152 struct htable_iter i;
153 void *c;
154
155 for (c = htable_firstval(ht,&i,h); c; c = htable_nextval(ht,&i,h)) {
156 if (cmp(c, (void *)ptr))
157 return c;
158 }
159 return NULL;
160 }
161
162 /**
163 * htable_first - find an entry in the hash table
164 * @ht: the hashtable
165 * @i: the struct htable_iter to initialize
166 *
167 * Get an entry in the hashtable; NULL if empty.
168 */
169 void *htable_first(const struct htable *htable, struct htable_iter *i);
170
171 /**
172 * htable_next - find another entry in the hash table
173 * @ht: the hashtable
174 * @i: the struct htable_iter to use
175 *
176 * Get another entry in the hashtable; NULL if all done.
177 * This is usually used after htable_first or prior non-NULL htable_next.
178 */
179 void *htable_next(const struct htable *htable, struct htable_iter *i);
180
181 /**
182 * htable_delval - remove an iterated pointer from a hash table
183 * @ht: the htable
184 * @i: the htable_iter
185 *
186 * Usually used to delete a hash entry after it has been found with
187 * htable_firstval etc.
188 */
189 void htable_delval(struct htable *ht, struct htable_iter *i);
190
191 #endif /* CCAN_HTABLE_H */
192