htable.h (8888B)
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 <ccan/str/str.h> 6 #include <stdint.h> 7 #include <stdbool.h> 8 #include <stdlib.h> 9 10 /* Define CCAN_HTABLE_DEBUG for expensive debugging checks on each call. */ 11 #define HTABLE_LOC __FILE__ ":" stringify(__LINE__) 12 #ifdef CCAN_HTABLE_DEBUG 13 #define htable_debug(h, loc) htable_check((h), loc) 14 #else 15 #define htable_debug(h, loc) ((void)loc, h) 16 #endif 17 18 /** 19 * struct htable - private definition of a htable. 20 * 21 * It's exposed here so you can put it in your structures and so we can 22 * supply inline functions. 23 */ 24 struct htable { 25 size_t (*rehash)(const void *elem, void *priv); 26 void *priv; 27 unsigned int bits, perfect_bitnum; 28 size_t elems, deleted; 29 /* These are the bits which are the same in all pointers. */ 30 uintptr_t common_mask, common_bits; 31 uintptr_t *table; 32 }; 33 34 /** 35 * HTABLE_INITIALIZER - static initialization for a hash table. 36 * @name: name of this htable. 37 * @rehash: hash function to use for rehashing. 38 * @priv: private argument to @rehash function. 39 * 40 * This is useful for setting up static and global hash tables. 41 * 42 * Example: 43 * // For simplicity's sake, say hash value is contents of elem. 44 * static size_t rehash(const void *elem, void *unused) 45 * { 46 * (void)unused; 47 * return *(size_t *)elem; 48 * } 49 * static struct htable ht = HTABLE_INITIALIZER(ht, rehash, NULL); 50 */ 51 #define HTABLE_INITIALIZER(name, rehash, priv) \ 52 { rehash, priv, 0, 0, 0, 0, -1, 0, &name.common_bits } 53 54 /** 55 * htable_init - initialize an empty hash table. 56 * @ht: the hash table to initialize 57 * @rehash: hash function to use for rehashing. 58 * @priv: private argument to @rehash function. 59 */ 60 void htable_init(struct htable *ht, 61 size_t (*rehash)(const void *elem, void *priv), void *priv); 62 63 /** 64 * htable_init_sized - initialize an empty hash table of given size. 65 * @ht: the hash table to initialize 66 * @rehash: hash function to use for rehashing. 67 * @priv: private argument to @rehash function. 68 * @size: the number of element. 69 * 70 * If this returns false, @ht is still usable, but may need to do reallocation 71 * upon an add. If this returns true, it will not need to reallocate within 72 * @size htable_adds. 73 */ 74 bool htable_init_sized(struct htable *ht, 75 size_t (*rehash)(const void *elem, void *priv), 76 void *priv, size_t size); 77 78 /** 79 * htable_count - count number of entries in a hash table. 80 * @ht: the hash table 81 */ 82 static inline size_t htable_count(const struct htable *ht) 83 { 84 return ht->elems; 85 } 86 87 /** 88 * htable_clear - empty a hash table. 89 * @ht: the hash table to clear 90 * 91 * This doesn't do anything to any pointers left in it. 92 */ 93 void htable_clear(struct htable *ht); 94 95 96 /** 97 * htable_check - check hash table for consistency 98 * @ht: the htable 99 * @abortstr: the location to print on aborting, or NULL. 100 * 101 * Because hash tables have redundant information, consistency checking that 102 * each element is in the correct location can be done. This is useful as a 103 * debugging check. If @abortstr is non-NULL, that will be printed in a 104 * diagnostic if the htable is inconsistent, and the function will abort. 105 * 106 * Returns the htable if it is consistent, NULL if not (it can never return 107 * NULL if @abortstr is set). 108 */ 109 struct htable *htable_check(const struct htable *ht, const char *abortstr); 110 111 /** 112 * htable_copy - duplicate a hash table. 113 * @dst: the hash table to overwrite 114 * @src: the hash table to copy 115 * 116 * Only fails on out-of-memory. 117 * 118 * Equivalent to (but faster than): 119 * if (!htable_init_sized(dst, src->rehash, src->priv, 1U << src->bits)) 120 * return false; 121 * v = htable_first(src, &i); 122 * while (v) { 123 * htable_add(dst, v); 124 * v = htable_next(src, i); 125 * } 126 * return true; 127 */ 128 #define htable_copy(dst, src) htable_copy_(dst, htable_debug(src, HTABLE_LOC)) 129 bool htable_copy_(struct htable *dst, const struct htable *src); 130 131 /** 132 * htable_add - add a pointer into a hash table. 133 * @ht: the htable 134 * @hash: the hash value of the object 135 * @p: the non-NULL pointer (also cannot be (void *)1). 136 * 137 * Also note that this can only fail due to allocation failure. Otherwise, it 138 * returns true. 139 */ 140 #define htable_add(ht, hash, p) \ 141 htable_add_(htable_debug(ht, HTABLE_LOC), hash, p) 142 bool htable_add_(struct htable *ht, size_t hash, const void *p); 143 144 /** 145 * htable_del - remove a pointer from a hash table 146 * @ht: the htable 147 * @hash: the hash value of the object 148 * @p: the pointer 149 * 150 * Returns true if the pointer was found (and deleted). 151 */ 152 #define htable_del(ht, hash, p) \ 153 htable_del_(htable_debug(ht, HTABLE_LOC), hash, p) 154 bool htable_del_(struct htable *ht, size_t hash, const void *p); 155 156 /** 157 * struct htable_iter - iterator or htable_first or htable_firstval etc. 158 * 159 * This refers to a location inside the hashtable. 160 */ 161 struct htable_iter { 162 size_t off; 163 }; 164 165 /** 166 * htable_firstval - find a candidate for a given hash value 167 * @htable: the hashtable 168 * @i: the struct htable_iter to initialize 169 * @hash: the hash value 170 * 171 * You'll need to check the value is what you want; returns NULL if none. 172 * See Also: 173 * htable_delval() 174 */ 175 #define htable_firstval(htable, i, hash) \ 176 htable_firstval_(htable_debug(htable, HTABLE_LOC), i, hash) 177 178 void *htable_firstval_(const struct htable *htable, 179 struct htable_iter *i, size_t hash); 180 181 /** 182 * htable_nextval - find another candidate for a given hash value 183 * @htable: the hashtable 184 * @i: the struct htable_iter to initialize 185 * @hash: the hash value 186 * 187 * You'll need to check the value is what you want; returns NULL if no more. 188 */ 189 #define htable_nextval(htable, i, hash) \ 190 htable_nextval_(htable_debug(htable, HTABLE_LOC), i, hash) 191 void *htable_nextval_(const struct htable *htable, 192 struct htable_iter *i, size_t hash); 193 194 /** 195 * htable_get - find an entry in the hash table 196 * @ht: the hashtable 197 * @h: the hash value of the entry 198 * @cmp: the comparison function 199 * @ptr: the pointer to hand to the comparison function. 200 * 201 * Convenient inline wrapper for htable_firstval/htable_nextval loop. 202 */ 203 static inline void *htable_get(const struct htable *ht, 204 size_t h, 205 bool (*cmp)(const void *candidate, void *ptr), 206 const void *ptr) 207 { 208 struct htable_iter i; 209 void *c; 210 211 for (c = htable_firstval(ht,&i,h); c; c = htable_nextval(ht,&i,h)) { 212 if (cmp(c, (void *)ptr)) 213 return c; 214 } 215 return NULL; 216 } 217 218 /** 219 * htable_first - find an entry in the hash table 220 * @ht: the hashtable 221 * @i: the struct htable_iter to initialize 222 * 223 * Get an entry in the hashtable; NULL if empty. 224 */ 225 #define htable_first(htable, i) \ 226 htable_first_(htable_debug(htable, HTABLE_LOC), i) 227 void *htable_first_(const struct htable *htable, struct htable_iter *i); 228 229 /** 230 * htable_next - find another entry in the hash table 231 * @ht: the hashtable 232 * @i: the struct htable_iter to use 233 * 234 * Get another entry in the hashtable; NULL if all done. 235 * This is usually used after htable_first or prior non-NULL htable_next. 236 */ 237 #define htable_next(htable, i) \ 238 htable_next_(htable_debug(htable, HTABLE_LOC), i) 239 void *htable_next_(const struct htable *htable, struct htable_iter *i); 240 241 /** 242 * htable_prev - find the previous entry in the hash table 243 * @ht: the hashtable 244 * @i: the struct htable_iter to use 245 * 246 * Get previous entry in the hashtable; NULL if all done. 247 * 248 * "previous" here only means the item that would have been returned by 249 * htable_next() before the item it returned most recently. 250 * 251 * This is usually used in the middle of (or after) a htable_next iteration and 252 * to "unwind" actions taken. 253 */ 254 #define htable_prev(htable, i) \ 255 htable_prev_(htable_debug(htable, HTABLE_LOC), i) 256 void *htable_prev_(const struct htable *htable, struct htable_iter *i); 257 258 /** 259 * htable_delval - remove an iterated pointer from a hash table 260 * @ht: the htable 261 * @i: the htable_iter 262 * 263 * Usually used to delete a hash entry after it has been found with 264 * htable_firstval etc. 265 */ 266 #define htable_delval(htable, i) \ 267 htable_delval_(htable_debug(htable, HTABLE_LOC), i) 268 void htable_delval_(struct htable *ht, struct htable_iter *i); 269 270 /** 271 * htable_pick - set iterator to a random valid entry. 272 * @ht: the htable 273 * @seed: a random number to use. 274 * @i: the htable_iter which is output (or NULL). 275 * 276 * Usually used with htable_delval to delete a random entry. Returns 277 * NULL iff the table is empty, otherwise a random entry. 278 */ 279 #define htable_pick(htable, seed, i) \ 280 htable_pick_(htable_debug(htable, HTABLE_LOC), seed, i) 281 void *htable_pick_(const struct htable *ht, size_t seed, struct htable_iter *i); 282 283 /** 284 * htable_set_allocator - set calloc/free functions. 285 * @alloc: allocator to use, must zero memory! 286 * @free: unallocator to use (@p is NULL or a return from @alloc) 287 */ 288 void htable_set_allocator(void *(*alloc)(struct htable *, size_t len), 289 void (*free)(struct htable *, void *p)); 290 #endif /* CCAN_HTABLE_H */