]> git.ozlabs.org Git - ccan/blob - ccan/htable/htable.h
cpuid: Minor improvements
[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  *              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_clear - empty a hash table.
56  * @ht: the hash table to clear
57  *
58  * This doesn't do anything to any pointers left in it.
59  */
60 void htable_clear(struct htable *ht);
61
62 /**
63  * htable_rehash - use a hashtree's rehash function
64  * @elem: the argument to rehash()
65  *
66  */
67 size_t htable_rehash(const void *elem);
68
69 /**
70  * htable_add - add a pointer into a hash table.
71  * @ht: the htable
72  * @hash: the hash value of the object
73  * @p: the non-NULL pointer
74  *
75  * Also note that this can only fail due to allocation failure.  Otherwise, it
76  * returns true.
77  */
78 bool htable_add(struct htable *ht, size_t hash, const void *p);
79
80 /**
81  * htable_del - remove a pointer from a hash table
82  * @ht: the htable
83  * @hash: the hash value of the object
84  * @p: the pointer
85  *
86  * Returns true if the pointer was found (and deleted).
87  */
88 bool htable_del(struct htable *ht, size_t hash, const void *p);
89
90 /**
91  * struct htable_iter - iterator or htable_first or htable_firstval etc.
92  *
93  * This refers to a location inside the hashtable.
94  */
95 struct htable_iter {
96         size_t off;
97 };
98
99 /**
100  * htable_firstval - find a candidate for a given hash value
101  * @htable: the hashtable
102  * @i: the struct htable_iter to initialize
103  * @hash: the hash value
104  *
105  * You'll need to check the value is what you want; returns NULL if none.
106  * See Also:
107  *      htable_delval()
108  */
109 void *htable_firstval(const struct htable *htable,
110                       struct htable_iter *i, size_t hash);
111
112 /**
113  * htable_nextval - find another candidate for a given hash value
114  * @htable: the hashtable
115  * @i: the struct htable_iter to initialize
116  * @hash: the hash value
117  *
118  * You'll need to check the value is what you want; returns NULL if no more.
119  */
120 void *htable_nextval(const struct htable *htable,
121                      struct htable_iter *i, size_t hash);
122
123 /**
124  * htable_get - find an entry in the hash table
125  * @ht: the hashtable
126  * @h: the hash value of the entry
127  * @cmp: the comparison function
128  * @ptr: the pointer to hand to the comparison function.
129  *
130  * Convenient inline wrapper for htable_firstval/htable_nextval loop.
131  */
132 static inline void *htable_get(const struct htable *ht,
133                                size_t h,
134                                bool (*cmp)(const void *candidate, void *ptr),
135                                const void *ptr)
136 {
137         struct htable_iter i;
138         void *c;
139
140         for (c = htable_firstval(ht,&i,h); c; c = htable_nextval(ht,&i,h)) {
141                 if (cmp(c, (void *)ptr))
142                         return c;
143         }
144         return NULL;
145 }
146
147 /**
148  * htable_first - find an entry in the hash table
149  * @ht: the hashtable
150  * @i: the struct htable_iter to initialize
151  *
152  * Get an entry in the hashtable; NULL if empty.
153  */
154 void *htable_first(const struct htable *htable, struct htable_iter *i);
155
156 /**
157  * htable_next - find another entry in the hash table
158  * @ht: the hashtable
159  * @i: the struct htable_iter to use
160  *
161  * Get another entry in the hashtable; NULL if all done.
162  * This is usually used after htable_first or prior non-NULL htable_next.
163  */
164 void *htable_next(const struct htable *htable, struct htable_iter *i);
165
166 /**
167  * htable_delval - remove an iterated pointer from a hash table
168  * @ht: the htable
169  * @i: the htable_iter
170  *
171  * Usually used to delete a hash entry after it has been found with
172  * htable_firstval etc.
173  */
174 void htable_delval(struct htable *ht, struct htable_iter *i);
175
176 #endif /* CCAN_HTABLE_H */