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 <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 */