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  *              return *(size_t *)elem;
  39  *      }
  40  *      static struct htable ht = HTABLE_INITIALIZER(ht, rehash, NULL);
  41  */
  42 #define HTABLE_INITIALIZER(name, rehash, priv)                          \
  43         { rehash, priv, 0, 0, 0, 0, 0, -1, 0, 0, &name.perfect_bit }
  44
  45 /**
  46  * htable_init - initialize an empty hash table.
  47  * @ht: the hash table to initialize
  48  * @rehash: hash function to use for rehashing.
  49  * @priv: private argument to @rehash function.
  50  */
  51 void htable_init(struct htable *ht,
  52                  size_t (*rehash)(const void *elem, void *priv), void *priv);
  53
  54 /**
  55  * htable_clear - empty a hash table.
  56  * @ht: the hash table to clear
  57  *
  58  * This doesn't do anything to any pointers left in it.
  59  */
  60 void htable_clear(struct htable *ht);
  61
  62 /**
  63  * htable_rehash - use a hashtree's rehash function
  64  * @elem: the argument to rehash()
  65  *
  66  */
  67 size_t htable_rehash(const void *elem);
  68
  69 /**
  70  * htable_add - add a pointer into a hash table.
  71  * @ht: the htable
  72  * @hash: the hash value of the object
  73  * @p: the non-NULL pointer
  74  *
  75  * Also note that this can only fail due to allocation failure.  Otherwise, it
  76  * returns true.
  77  */
  78 bool htable_add(struct htable *ht, size_t hash, const void *p);
  79
  80 /**
  81  * htable_del - remove a pointer from a hash table
  82  * @ht: the htable
  83  * @hash: the hash value of the object
  84  * @p: the pointer
  85  *
  86  * Returns true if the pointer was found (and deleted).
  87  */
  88 bool htable_del(struct htable *ht, size_t hash, const void *p);
  89
  90 /**
  91  * struct htable_iter - iterator or htable_first or htable_firstval etc.
  92  *
  93  * This refers to a location inside the hashtable.
  94  */
  95 struct htable_iter {
  96         size_t off;
  97 };
  98
  99 /**
 100  * htable_firstval - find a candidate for a given hash value
 101  * @htable: the hashtable
 102  * @i: the struct htable_iter to initialize
 103  * @hash: the hash value
 104  *
 105  * You'll need to check the value is what you want; returns NULL if none.
 106  * See Also:
 107  *      htable_delval()
 108  */
 109 void *htable_firstval(const struct htable *htable,
 110                       struct htable_iter *i, size_t hash);
 111
 112 /**
 113  * htable_nextval - find another candidate for a given hash value
 114  * @htable: the hashtable
 115  * @i: the struct htable_iter to initialize
 116  * @hash: the hash value
 117  *
 118  * You'll need to check the value is what you want; returns NULL if no more.
 119  */
 120 void *htable_nextval(const struct htable *htable,
 121                      struct htable_iter *i, size_t hash);
 122
 123 /**
 124  * htable_get - find an entry in the hash table
 125  * @ht: the hashtable
 126  * @h: the hash value of the entry
 127  * @cmp: the comparison function
 128  * @ptr: the pointer to hand to the comparison function.
 129  *
 130  * Convenient inline wrapper for htable_firstval/htable_nextval loop.
 131  */
 132 static inline void *htable_get(const struct htable *ht,
 133                                size_t h,
 134                                bool (*cmp)(const void *candidate, void *ptr),
 135                                const void *ptr)
 136 {
 137         struct htable_iter i;
 138         void *c;
 139
 140         for (c = htable_firstval(ht,&i,h); c; c = htable_nextval(ht,&i,h)) {
 141                 if (cmp(c, (void *)ptr))
 142                         return c;
 143         }
 144         return NULL;
 145 }
 146
 147 /**
 148  * htable_first - find an entry in the hash table
 149  * @ht: the hashtable
 150  * @i: the struct htable_iter to initialize
 151  *
 152  * Get an entry in the hashtable; NULL if empty.
 153  */
 154 void *htable_first(const struct htable *htable, struct htable_iter *i);
 155
 156 /**
 157  * htable_next - find another entry in the hash table
 158  * @ht: the hashtable
 159  * @i: the struct htable_iter to use
 160  *
 161  * Get another entry in the hashtable; NULL if all done.
 162  * This is usually used after htable_first or prior non-NULL htable_next.
 163  */
 164 void *htable_next(const struct htable *htable, struct htable_iter *i);
 165
 166 /**
 167  * htable_delval - remove an iterated pointer from a hash table
 168  * @ht: the htable
 169  * @i: the htable_iter
 170  *
 171  * Usually used to delete a hash entry after it has been found with
 172  * htable_firstval etc.
 173  */
 174 void htable_delval(struct htable *ht, struct htable_iter *i);
 175
 176 #endif /* CCAN_HTABLE_H */