external/htable.h

   1 /* Licensed under LGPLv2+ - see LICENSE file for details */
   2 #ifndef CCAN_HTABLE_H
   3 #define CCAN_HTABLE_H
   4 #include <stdint.h>
   5 #include <stdbool.h>
   6 #include <stdlib.h>
   7
   8 /**
   9  * struct htable - private definition of a htable.
  10  *
  11  * It's exposed here so you can put it in your structures and so we can
  12  * supply inline functions.
  13  */
  14 struct htable {
  15         size_t (*rehash)(const void *elem, void *priv);
  16         void *priv;
  17         unsigned int bits;
  18         size_t elems, deleted, max, max_with_deleted;
  19         /* These are the bits which are the same in all pointers. */
  20         uintptr_t common_mask, common_bits;
  21         uintptr_t perfect_bit;
  22         uintptr_t *table;
  23 };
  24
  25 /**
  26  * HTABLE_INITIALIZER - static initialization for a hash table.
  27  * @name: name of this htable.
  28  * @rehash: hash function to use for rehashing.
  29  * @priv: private argument to @rehash function.
  30  *
  31  * This is useful for setting up static and global hash tables.
  32  *
  33  * Example:
  34  *      // For simplicity's sake, say hash value is contents of elem.
  35  *      static size_t rehash(const void *elem, void *unused)
  36  *      {
  37  *              return *(size_t *)elem;
  38  *      }
  39  *      static struct htable ht = HTABLE_INITIALIZER(ht, rehash, NULL);
  40  */
  41 #define HTABLE_INITIALIZER(name, rehash, priv)                          \
  42         { rehash, priv, 0, 0, 0, 0, 0, -1, 0, 0, &name.perfect_bit }
  43
  44 /**
  45  * htable_init - initialize an empty hash table.
  46  * @ht: the hash table to initialize
  47  * @rehash: hash function to use for rehashing.
  48  * @priv: private argument to @rehash function.
  49  */
  50 void htable_init(struct htable *ht,
  51                  size_t (*rehash)(const void *elem, void *priv), void *priv);
  52
  53 /**
  54  * htable_clear - empty a hash table.
  55  * @ht: the hash table to clear
  56  *
  57  * This doesn't do anything to any pointers left in it.
  58  */
  59 void htable_clear(struct htable *ht);
  60
  61 /**
  62  * htable_rehash - use a hashtree's rehash function
  63  * @elem: the argument to rehash()
  64  *
  65  */
  66 size_t htable_rehash(const void *elem);
  67
  68 /**
  69  * htable_add - add a pointer into a hash table.
  70  * @ht: the htable
  71  * @hash: the hash value of the object
  72  * @p: the non-NULL pointer
  73  *
  74  * Also note that this can only fail due to allocation failure.  Otherwise, it
  75  * returns true.
  76  */
  77 bool htable_add(struct htable *ht, size_t hash, const void *p);
  78
  79 /**
  80  * htable_del - remove a pointer from a hash table
  81  * @ht: the htable
  82  * @hash: the hash value of the object
  83  * @p: the pointer
  84  *
  85  * Returns true if the pointer was found (and deleted).
  86  */
  87 bool htable_del(struct htable *ht, size_t hash, const void *p);
  88
  89 /**
  90  * struct htable_iter - iterator or htable_first or htable_firstval etc.
  91  *
  92  * This refers to a location inside the hashtable.
  93  */
  94 struct htable_iter {
  95         size_t off;
  96 };
  97
  98 /**
  99  * htable_firstval - find a candidate for a given hash value
 100  * @htable: the hashtable
 101  * @i: the struct htable_iter to initialize
 102  * @hash: the hash value
 103  *
 104  * You'll need to check the value is what you want; returns NULL if none.
 105  * See Also:
 106  *      htable_delval()
 107  */
 108 void *htable_firstval(const struct htable *htable,
 109                       struct htable_iter *i, size_t hash);
 110
 111 /**
 112  * htable_nextval - find another candidate for a given hash value
 113  * @htable: the hashtable
 114  * @i: the struct htable_iter to initialize
 115  * @hash: the hash value
 116  *
 117  * You'll need to check the value is what you want; returns NULL if no more.
 118  */
 119 void *htable_nextval(const struct htable *htable,
 120                      struct htable_iter *i, size_t hash);
 121
 122 /**
 123  * htable_get - find an entry in the hash table
 124  * @ht: the hashtable
 125  * @h: the hash value of the entry
 126  * @cmp: the comparison function
 127  * @ptr: the pointer to hand to the comparison function.
 128  *
 129  * Convenient inline wrapper for htable_firstval/htable_nextval loop.
 130  */
 131 static inline void *htable_get(const struct htable *ht,
 132                                size_t h,
 133                                bool (*cmp)(const void *candidate, void *ptr),
 134                                const void *ptr)
 135 {
 136         struct htable_iter i;
 137         void *c;
 138
 139         for (c = htable_firstval(ht,&i,h); c; c = htable_nextval(ht,&i,h)) {
 140                 if (cmp(c, (void *)ptr))
 141                         return c;
 142         }
 143         return NULL;
 144 }
 145
 146 /**
 147  * htable_first - find an entry in the hash table
 148  * @ht: the hashtable
 149  * @i: the struct htable_iter to initialize
 150  *
 151  * Get an entry in the hashtable; NULL if empty.
 152  */
 153 void *htable_first(const struct htable *htable, struct htable_iter *i);
 154
 155 /**
 156  * htable_next - find another entry in the hash table
 157  * @ht: the hashtable
 158  * @i: the struct htable_iter to use
 159  *
 160  * Get another entry in the hashtable; NULL if all done.
 161  * This is usually used after htable_first or prior non-NULL htable_next.
 162  */
 163 void *htable_next(const struct htable *htable, struct htable_iter *i);
 164
 165 /**
 166  * htable_delval - remove an iterated pointer from a hash table
 167  * @ht: the htable
 168  * @i: the htable_iter
 169  *
 170  * Usually used to delete a hash entry after it has been found with
 171  * htable_firstval etc.
 172  */
 173 void htable_delval(struct htable *ht, struct htable_iter *i);
 174
 175 #endif /* CCAN_HTABLE_H */