9845388e1b9f47b7938e765a4682c7b4aee689fe
[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 <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  *              (void)unused;
39  *              return *(size_t *)elem;
40  *      }
41  *      static struct htable ht = HTABLE_INITIALIZER(ht, rehash, NULL);
42  */
43 #define HTABLE_INITIALIZER(name, rehash, priv)                          \
44         { rehash, priv, 0, 0, 0, 0, 0, -1, 0, 0, &name.perfect_bit }
45
46 /**
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.
51  */
52 void htable_init(struct htable *ht,
53                  size_t (*rehash)(const void *elem, void *priv), void *priv);
54
55 /**
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.
61  *
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
64  * @size htable_adds.
65  */
66 bool htable_init_sized(struct htable *ht,
67                        size_t (*rehash)(const void *elem, void *priv),
68                        void *priv, size_t size);
69
70 /**
71  * htable_clear - empty a hash table.
72  * @ht: the hash table to clear
73  *
74  * This doesn't do anything to any pointers left in it.
75  */
76 void htable_clear(struct htable *ht);
77
78 /**
79  * htable_copy - duplicate a hash table.
80  * @dst: the hash table to overwrite
81  * @src: the hash table to copy
82  *
83  * Only fails on out-of-memory.
84  *
85  * Equivalent to (but faster than):
86  *    if (!htable_init_sized(dst, src->rehash, src->priv, 1U << src->bits))
87  *         return false;
88  *    v = htable_first(src, &i);
89  *    while (v) {
90  *              htable_add(dst, v);
91  *              v = htable_next(src, i);
92  *    }
93  *    return true;
94  */
95 bool htable_copy(struct htable *dst, const struct htable *src);
96
97 /**
98  * htable_rehash - use a hashtree's rehash function
99  * @elem: the argument to rehash()
100  *
101  */
102 size_t htable_rehash(const void *elem);
103
104 /**
105  * htable_add - add a pointer into a hash table.
106  * @ht: the htable
107  * @hash: the hash value of the object
108  * @p: the non-NULL pointer
109  *
110  * Also note that this can only fail due to allocation failure.  Otherwise, it
111  * returns true.
112  */
113 bool htable_add(struct htable *ht, size_t hash, const void *p);
114
115 /**
116  * htable_del - remove a pointer from a hash table
117  * @ht: the htable
118  * @hash: the hash value of the object
119  * @p: the pointer
120  *
121  * Returns true if the pointer was found (and deleted).
122  */
123 bool htable_del(struct htable *ht, size_t hash, const void *p);
124
125 /**
126  * struct htable_iter - iterator or htable_first or htable_firstval etc.
127  *
128  * This refers to a location inside the hashtable.
129  */
130 struct htable_iter {
131         size_t off;
132 };
133
134 /**
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
139  *
140  * You'll need to check the value is what you want; returns NULL if none.
141  * See Also:
142  *      htable_delval()
143  */
144 void *htable_firstval(const struct htable *htable,
145                       struct htable_iter *i, size_t hash);
146
147 /**
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
152  *
153  * You'll need to check the value is what you want; returns NULL if no more.
154  */
155 void *htable_nextval(const struct htable *htable,
156                      struct htable_iter *i, size_t hash);
157
158 /**
159  * htable_get - find an entry in the hash table
160  * @ht: the hashtable
161  * @h: the hash value of the entry
162  * @cmp: the comparison function
163  * @ptr: the pointer to hand to the comparison function.
164  *
165  * Convenient inline wrapper for htable_firstval/htable_nextval loop.
166  */
167 static inline void *htable_get(const struct htable *ht,
168                                size_t h,
169                                bool (*cmp)(const void *candidate, void *ptr),
170                                const void *ptr)
171 {
172         struct htable_iter i;
173         void *c;
174
175         for (c = htable_firstval(ht,&i,h); c; c = htable_nextval(ht,&i,h)) {
176                 if (cmp(c, (void *)ptr))
177                         return c;
178         }
179         return NULL;
180 }
181
182 /**
183  * htable_first - find an entry in the hash table
184  * @ht: the hashtable
185  * @i: the struct htable_iter to initialize
186  *
187  * Get an entry in the hashtable; NULL if empty.
188  */
189 void *htable_first(const struct htable *htable, struct htable_iter *i);
190
191 /**
192  * htable_next - find another entry in the hash table
193  * @ht: the hashtable
194  * @i: the struct htable_iter to use
195  *
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.
198  */
199 void *htable_next(const struct htable *htable, struct htable_iter *i);
200
201 /**
202  * htable_prev - find the previous entry in the hash table
203  * @ht: the hashtable
204  * @i: the struct htable_iter to use
205  *
206  * Get previous entry in the hashtable; NULL if all done.
207  *
208  * "previous" here only means the item that would have been returned by
209  * htable_next() before the item it returned most recently.
210  *
211  * This is usually used in the middle of (or after) a htable_next iteration and
212  * to "unwind" actions taken.
213  */
214 void *htable_prev(const struct htable *htable, struct htable_iter *i);
215
216 /**
217  * htable_delval - remove an iterated pointer from a hash table
218  * @ht: the htable
219  * @i: the htable_iter
220  *
221  * Usually used to delete a hash entry after it has been found with
222  * htable_firstval etc.
223  */
224 void htable_delval(struct htable *ht, struct htable_iter *i);
225
226 #endif /* CCAN_HTABLE_H */