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