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