diff options
Diffstat (limited to 'ccan/ccan/htable/htable_type.h')
| -rw-r--r-- | ccan/ccan/htable/htable_type.h | 188 |
1 files changed, 188 insertions, 0 deletions
diff --git a/ccan/ccan/htable/htable_type.h b/ccan/ccan/htable/htable_type.h new file mode 100644 index 0000000..0aacb7f --- /dev/null +++ b/ccan/ccan/htable/htable_type.h @@ -0,0 +1,188 @@ +/* Licensed under LGPLv2+ - see LICENSE file for details */ +#ifndef CCAN_HTABLE_TYPE_H +#define CCAN_HTABLE_TYPE_H +#include <ccan/htable/htable.h> +#include <ccan/compiler/compiler.h> +#include "config.h" + +/** + * HTABLE_DEFINE_TYPE - create a set of htable ops for a type + * @type: a type whose pointers will be values in the hash. + * @keyof: a function/macro to extract a key: <keytype> @keyof(const type *elem) + * @hashfn: a hash function for a @key: size_t @hashfn(const <keytype> *) + * @eqfn: an equality function keys: bool @eqfn(const type *, const <keytype> *) + * @prefix: a prefix for all the functions to define (of form <name>_*) + * + * NULL values may not be placed into the hash table. + * + * This defines the type hashtable type and an iterator type: + * struct <name>; + * struct <name>_iter; + * + * It also defines initialization and freeing functions: + * void <name>_init(struct <name> *); + * bool <name>_init_sized(struct <name> *, size_t); + * void <name>_clear(struct <name> *); + * bool <name>_copy(struct <name> *dst, const struct <name> *src); + * + * Count entries: + * size_t <name>_count(const struct <name> *ht); + * + * Add function only fails if we run out of memory: + * bool <name>_add(struct <name> *ht, const <type> *e); + * + * Delete and delete-by key return true if it was in the set: + * bool <name>_del(struct <name> *ht, const <type> *e); + * bool <name>_delkey(struct <name> *ht, const <keytype> *k); + * + * Delete by iterator: + * bool <name>_delval(struct <name> *ht, struct <name>_iter *i); + * + * Find and return the (first) matching element, or NULL: + * type *<name>_get(const struct @name *ht, const <keytype> *k); + * + * Find and return all matching elements, or NULL: + * type *<name>_getfirst(const struct @name *ht, const <keytype> *k, + * struct <name>_iter *i); + * type *<name>_getnext(const struct @name *ht, const <keytype> *k, + * struct <name>_iter *i); + * + * Iteration over hashtable is also supported: + * type *<name>_first(const struct <name> *ht, struct <name>_iter *i); + * type *<name>_next(const struct <name> *ht, struct <name>_iter *i); + * type *<name>_prev(const struct <name> *ht, struct <name>_iter *i); + * type *<name>_pick(const struct <name> *ht, size_t seed, + * struct <name>_iter *i); + * It's currently safe to iterate over a changing hashtable, but you might + * miss an element. Iteration isn't very efficient, either. + * + * You can use HTABLE_INITIALIZER like so: + * struct <name> ht = { HTABLE_INITIALIZER(ht.raw, <name>_hash, NULL) }; + */ +#define HTABLE_DEFINE_TYPE(type, keyof, hashfn, eqfn, name) \ + struct name { struct htable raw; }; \ + struct name##_iter { struct htable_iter i; }; \ + static inline size_t name##_hash(const void *elem, void *priv) \ + { \ + (void)priv; \ + return hashfn(keyof((const type *)elem)); \ + } \ + static inline UNNEEDED void name##_init(struct name *ht) \ + { \ + htable_init(&ht->raw, name##_hash, NULL); \ + } \ + static inline UNNEEDED bool name##_init_sized(struct name *ht, \ + size_t s) \ + { \ + return htable_init_sized(&ht->raw, name##_hash, NULL, s); \ + } \ + static inline UNNEEDED size_t name##_count(const struct name *ht) \ + { \ + return htable_count(&ht->raw); \ + } \ + static inline UNNEEDED void name##_clear(struct name *ht) \ + { \ + htable_clear(&ht->raw); \ + } \ + static inline UNNEEDED bool name##_copy(struct name *dst, \ + const struct name *src) \ + { \ + return htable_copy(&dst->raw, &src->raw); \ + } \ + static inline bool name##_add(struct name *ht, const type *elem) \ + { \ + return htable_add(&ht->raw, hashfn(keyof(elem)), elem); \ + } \ + static inline UNNEEDED bool name##_del(struct name *ht, \ + const type *elem) \ + { \ + return htable_del(&ht->raw, hashfn(keyof(elem)), elem); \ + } \ + static inline UNNEEDED type *name##_get(const struct name *ht, \ + const HTABLE_KTYPE(keyof, type) k) \ + { \ + struct htable_iter i; \ + size_t h = hashfn(k); \ + void *c; \ + \ + for (c = htable_firstval(&ht->raw,&i,h); \ + c; \ + c = htable_nextval(&ht->raw,&i,h)) { \ + if (eqfn(c, k)) \ + return c; \ + } \ + return NULL; \ + } \ + static inline UNNEEDED type *name##_getmatch_(const struct name *ht, \ + const HTABLE_KTYPE(keyof, type) k, \ + size_t h, \ + type *v, \ + struct name##_iter *iter) \ + { \ + while (v) { \ + if (eqfn(v, k)) \ + break; \ + v = htable_nextval(&ht->raw, &iter->i, h); \ + } \ + return v; \ + } \ + static inline UNNEEDED type *name##_getfirst(const struct name *ht, \ + const HTABLE_KTYPE(keyof, type) k, \ + struct name##_iter *iter) \ + { \ + size_t h = hashfn(k); \ + type *v = htable_firstval(&ht->raw, &iter->i, h); \ + return name##_getmatch_(ht, k, h, v, iter); \ + } \ + static inline UNNEEDED type *name##_getnext(const struct name *ht, \ + const HTABLE_KTYPE(keyof, type) k, \ + struct name##_iter *iter) \ + { \ + size_t h = hashfn(k); \ + type *v = htable_nextval(&ht->raw, &iter->i, h); \ + return name##_getmatch_(ht, k, h, v, iter); \ + } \ + static inline UNNEEDED bool name##_delkey(struct name *ht, \ + const HTABLE_KTYPE(keyof, type) k) \ + { \ + type *elem = name##_get(ht, k); \ + if (elem) \ + return name##_del(ht, elem); \ + return false; \ + } \ + static inline UNNEEDED void name##_delval(struct name *ht, \ + struct name##_iter *iter) \ + { \ + htable_delval(&ht->raw, &iter->i); \ + } \ + static inline UNNEEDED type *name##_pick(const struct name *ht, \ + size_t seed, \ + struct name##_iter *iter) \ + { \ + return htable_pick(&ht->raw, seed, iter ? &iter->i : NULL); \ + } \ + static inline UNNEEDED type *name##_first(const struct name *ht, \ + struct name##_iter *iter) \ + { \ + return htable_first(&ht->raw, &iter->i); \ + } \ + static inline UNNEEDED type *name##_next(const struct name *ht, \ + struct name##_iter *iter) \ + { \ + return htable_next(&ht->raw, &iter->i); \ + } \ + static inline UNNEEDED type *name##_prev(const struct name *ht, \ + struct name##_iter *iter) \ + { \ + return htable_prev(&ht->raw, &iter->i); \ + } + +#if HAVE_TYPEOF +#define HTABLE_KTYPE(keyof, type) typeof(keyof((const type *)NULL)) +#else +/* Assumes keys are a pointer: if not, override. */ +#ifndef HTABLE_KTYPE +#define HTABLE_KTYPE(keyof, type) void * +#endif +#endif +#endif /* CCAN_HTABLE_TYPE_H */ |