git.ozlabs.org Git - ccan/blob - 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 <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 */