git.ozlabs.org Git - ccan/blob - ccan/htable/htable_type.h

   1 /* Licensed under LGPLv2+ - see LICENSE file for details */
   2 #ifndef CCAN_HTABLE_TYPE_H
   3 #define CCAN_HTABLE_TYPE_H
   4 #include <ccan/htable/htable.h>
   5 #include <ccan/compiler/compiler.h>
   6 #include "config.h"
   7
   8 /**
   9  * HTABLE_DEFINE_TYPE - create a set of htable ops for a type
  10  * @type: a type whose pointers will be values in the hash.
  11  * @keyof: a function/macro to extract a key: <keytype> @keyof(const type *elem)
  12  * @hashfn: a hash function for a @key: size_t @hashfn(const <keytype> *)
  13  * @eqfn: an equality function keys: bool @eqfn(const type *, const <keytype> *)
  14  * @prefix: a prefix for all the functions to define (of form <name>_*)
  15  *
  16  * NULL values may not be placed into the hash table.
  17  *
  18  * This defines the type hashtable type and an iterator type:
  19  *      struct <name>;
  20  *      struct <name>_iter;
  21  *
  22  * It also defines initialization and freeing functions:
  23  *      void <name>_init(struct <name> *);
  24  *      bool <name>_init_sized(struct <name> *, size_t);
  25  *      void <name>_clear(struct <name> *);
  26  *      bool <name>_copy(struct <name> *dst, const struct <name> *src);
  27  *
  28  * Count entries:
  29  *      size_t <name>_count(const struct <name> *ht);
  30  *
  31  * Add function only fails if we run out of memory:
  32  *      bool <name>_add(struct <name> *ht, const <type> *e);
  33  *
  34  * Delete and delete-by key return true if it was in the set:
  35  *      bool <name>_del(struct <name> *ht, const <type> *e);
  36  *      bool <name>_delkey(struct <name> *ht, const <keytype> *k);
  37  *
  38  * Find and return the (first) matching element, or NULL:
  39  *      type *<name>_get(const struct @name *ht, const <keytype> *k);
  40  *
  41  * Find and return all matching elements, or NULL:
  42  *      type *<name>_getfirst(const struct @name *ht, const <keytype> *k,
  43  *                            struct <name>_iter *i);
  44  *      type *<name>_getnext(const struct @name *ht, const <keytype> *k,
  45  *                           struct <name>_iter *i);
  46  *
  47  * Iteration over hashtable is also supported:
  48  *      type *<name>_first(const struct <name> *ht, struct <name>_iter *i);
  49  *      type *<name>_next(const struct <name> *ht, struct <name>_iter *i);
  50  *      type *<name>_prev(const struct <name> *ht, struct <name>_iter *i);
  51  *      type *<name>_pick(const struct <name> *ht, size_t seed,
  52  *                        struct <name>_iter *i);
  53  * It's currently safe to iterate over a changing hashtable, but you might
  54  * miss an element.  Iteration isn't very efficient, either.
  55  *
  56  * You can use HTABLE_INITIALIZER like so:
  57  *      struct <name> ht = { HTABLE_INITIALIZER(ht.raw, <name>_hash, NULL) };
  58  */
  59 #define HTABLE_DEFINE_TYPE(type, keyof, hashfn, eqfn, name)             \
  60         struct name { struct htable raw; };                             \
  61         struct name##_iter { struct htable_iter i; };                   \
  62         static inline size_t name##_hash(const void *elem, void *priv)  \
  63         {                                                               \
  64                 (void)priv;                                             \
  65                 return hashfn(keyof((const type *)elem));               \
  66         }                                                               \
  67         static inline UNNEEDED void name##_init(struct name *ht)        \
  68         {                                                               \
  69                 htable_init(&ht->raw, name##_hash, NULL);               \
  70         }                                                               \
  71         static inline UNNEEDED bool name##_init_sized(struct name *ht,  \
  72                                                       size_t s)         \
  73         {                                                               \
  74                 return htable_init_sized(&ht->raw, name##_hash, NULL, s); \
  75         }                                                               \
  76         static inline UNNEEDED size_t name##_count(const struct name *ht) \
  77         {                                                               \
  78                 return htable_count(&ht->raw);                          \
  79         }                                                               \
  80         static inline UNNEEDED void name##_clear(struct name *ht)       \
  81         {                                                               \
  82                 htable_clear(&ht->raw);                                 \
  83         }                                                               \
  84         static inline UNNEEDED bool name##_copy(struct name *dst,       \
  85                                                 const struct name *src) \
  86         {                                                               \
  87                 return htable_copy(&dst->raw, &src->raw);               \
  88         }                                                               \
  89         static inline bool name##_add(struct name *ht, const type *elem) \
  90         {                                                               \
  91                 return htable_add(&ht->raw, hashfn(keyof(elem)), elem); \
  92         }                                                               \
  93         static inline UNNEEDED bool name##_del(struct name *ht,         \
  94                                                const type *elem)        \
  95         {                                                               \
  96                 return htable_del(&ht->raw, hashfn(keyof(elem)), elem); \
  97         }                                                               \
  98         static inline UNNEEDED type *name##_get(const struct name *ht,  \
  99                                        const HTABLE_KTYPE(keyof, type) k) \
 100         {                                                               \
 101                 struct htable_iter i;                                   \
 102                 size_t h = hashfn(k);                                   \
 103                 void *c;                                                \
 104                                                                         \
 105                 for (c = htable_firstval(&ht->raw,&i,h);                \
 106                      c;                                                 \
 107                      c = htable_nextval(&ht->raw,&i,h)) {               \
 108                         if (eqfn(c, k))                                 \
 109                                 return c;                               \
 110                 }                                                       \
 111                 return NULL;                                            \
 112         }                                                               \
 113         static inline UNNEEDED type *name##_getmatch_(const struct name *ht, \
 114                                          const HTABLE_KTYPE(keyof, type) k, \
 115                                          size_t h,                      \
 116                                          type *v,                       \
 117                                          struct name##_iter *iter)      \
 118         {                                                               \
 119                 while (v) {                                             \
 120                         if (eqfn(v, k))                                 \
 121                                 break;                                  \
 122                         v = htable_nextval(&ht->raw, &iter->i, h);      \
 123                 }                                                       \
 124                 return v;                                               \
 125         }                                                               \
 126         static inline UNNEEDED type *name##_getfirst(const struct name *ht, \
 127                                          const HTABLE_KTYPE(keyof, type) k, \
 128                                          struct name##_iter *iter)      \
 129         {                                                               \
 130                 size_t h = hashfn(k);                                   \
 131                 type *v = htable_firstval(&ht->raw, &iter->i, h);       \
 132                 return name##_getmatch_(ht, k, h, v, iter);                     \
 133         }                                                               \
 134         static inline UNNEEDED type *name##_getnext(const struct name *ht, \
 135                                          const HTABLE_KTYPE(keyof, type) k, \
 136                                          struct name##_iter *iter)      \
 137         {                                                               \
 138                 size_t h = hashfn(k);                                   \
 139                 type *v = htable_nextval(&ht->raw, &iter->i, h);        \
 140                 return name##_getmatch_(ht, k, h, v, iter);             \
 141         }                                                               \
 142         static inline UNNEEDED bool name##_delkey(struct name *ht,      \
 143                                          const HTABLE_KTYPE(keyof, type) k) \
 144         {                                                               \
 145                 type *elem = name##_get(ht, k);                         \
 146                 if (elem)                                               \
 147                         return name##_del(ht, elem);                    \
 148                 return false;                                           \
 149         }                                                               \
 150         static inline UNNEEDED type *name##_pick(const struct name *ht, \
 151                                                 size_t seed,            \
 152                                                 struct name##_iter *iter) \
 153         {                                                               \
 154                 /* Note &iter->i == NULL iff iter is NULL */            \
 155                 return htable_pick(&ht->raw, seed, &iter->i);                   \
 156         }                                                               \
 157         static inline UNNEEDED type *name##_first(const struct name *ht, \
 158                                          struct name##_iter *iter)      \
 159         {                                                               \
 160                 return htable_first(&ht->raw, &iter->i);                \
 161         }                                                               \
 162         static inline UNNEEDED type *name##_next(const struct name *ht, \
 163                                         struct name##_iter *iter)       \
 164         {                                                               \
 165                 return htable_next(&ht->raw, &iter->i);                 \
 166         }                                                               \
 167         static inline UNNEEDED type *name##_prev(const struct name *ht, \
 168                                         struct name##_iter *iter)       \
 169         {                                                               \
 170                 return htable_prev(&ht->raw, &iter->i);                 \
 171         }
 172
 173 #if HAVE_TYPEOF
 174 #define HTABLE_KTYPE(keyof, type) typeof(keyof((const type *)NULL))
 175 #else
 176 /* Assumes keys are a pointer: if not, override. */
 177 #ifndef HTABLE_KTYPE
 178 #define HTABLE_KTYPE(keyof, type) void *
 179 #endif
 180 #endif
 181 #endif /* CCAN_HTABLE_TYPE_H */