X-Git-Url: http://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Fhtable%2Fhtable_type.h;h=6764c3f24ae103c8bccbcc8949c283ff56dcca1e;hp=15a70fc28d039e31f9285f83a496e14faa09c71f;hb=HEAD;hpb=f3538fc7cbe97e7e0daa216b187596d77f189bf2 diff --git a/ccan/htable/htable_type.h b/ccan/htable/htable_type.h index 15a70fc2..103d2ff1 100644 --- a/ccan/htable/htable_type.h +++ b/ccan/htable/htable_type.h @@ -1,19 +1,23 @@ /* Licensed under LGPLv2+ - see LICENSE file for details */ #ifndef CCAN_HTABLE_TYPE_H #define CCAN_HTABLE_TYPE_H +#include "config.h" +#include #include #include -#include "config.h" /** - * HTABLE_DEFINE_TYPE - create a set of htable ops for a type + * HTABLE_DEFINE_NODUPS_TYPE/HTABLE_DEFINE_DUPS_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: @keyof(const type *elem) * @hashfn: a hash function for a @key: size_t @hashfn(const *) * @eqfn: an equality function keys: bool @eqfn(const type *, const *) * @prefix: a prefix for all the functions to define (of form _*) * - * NULL values may not be placed into the hash table. + * There are two variants, one of which allows duplicate keys, and one which + * does not. The defined functions differ in some cases, as shown below. + * + * NULL values may not be placed into the hash table (nor (void *)1). * * This defines the type hashtable type and an iterator type: * struct ; @@ -21,20 +25,30 @@ * * It also defines initialization and freeing functions: * void _init(struct *); - * void _init_sized(struct *, size_t); + * bool _init_sized(struct *, size_t); * void _clear(struct *); + * bool _copy(struct *dst, const struct *src); + * + * Count entries: + * size_t _count(const struct *ht); * * Add function only fails if we run out of memory: * bool _add(struct *ht, const *e); * * Delete and delete-by key return true if it was in the set: * bool _del(struct *ht, const *e); - * bool _delkey(struct *ht, const *k); + * bool _delkey(struct *ht, const *k) (NODUPS only); + * + * Delete by iterator: + * bool _delval(struct *ht, struct _iter *i); * - * Find and return the (first) matching element, or NULL: - * type *_get(const struct @name *ht, const *k); + * Find and return the matching element, or NULL: + * type *_get(const struct @name *ht, const *k) (NODUPS only); * - * Find and return all matching elements, or NULL: + * Test for an element: + * bool _exists(const struct @name *ht, const *k); + * + * Find and return all matching elements, or NULL (DUPS only): * type *_getfirst(const struct @name *ht, const *k, * struct _iter *i); * type *_getnext(const struct @name *ht, const *k, @@ -43,14 +57,16 @@ * Iteration over hashtable is also supported: * type *_first(const struct *ht, struct _iter *i); * type *_next(const struct *ht, struct _iter *i); - * + * type *_prev(const struct *ht, struct _iter *i); + * type *_pick(const struct *ht, size_t seed, + * struct _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 ht = { HTABLE_INITIALIZER(ht.raw, _hash, NULL) }; */ -#define HTABLE_DEFINE_TYPE(type, keyof, hashfn, eqfn, name) \ +#define HTABLE_DEFINE_TYPE_CORE(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) \ @@ -62,63 +78,102 @@ { \ htable_init(&ht->raw, name##_hash, NULL); \ } \ - static inline UNNEEDED void name##_init_sized(struct name *ht, \ + static inline UNNEEDED bool name##_init_sized(struct name *ht, \ size_t s) \ { \ - htable_init_sized(&ht->raw, name##_hash, NULL, 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 bool name##_add(struct name *ht, const type *elem) \ + static inline UNNEEDED bool name##_copy(struct name *dst, \ + const struct name *src) \ { \ - return htable_add(&ht->raw, hashfn(keyof(elem)), elem); \ + return htable_copy(&dst->raw, &src->raw); \ } \ 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) \ - { \ - /* Typecheck for eqfn */ \ - (void)sizeof(eqfn((const type *)NULL, \ - keyof((const type *)NULL))); \ - return htable_get(&ht->raw, \ - hashfn(k), \ - (bool (*)(const void *, void *))(eqfn), \ - k); \ - } \ 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) \ + struct htable_iter *iter) \ { \ while (v) { \ if (eqfn(v, k)) \ break; \ - v = htable_nextval(&ht->raw, &iter->i, h); \ + v = htable_nextval(&ht->raw, iter, h); \ } \ return v; \ } \ - static inline UNNEEDED type *name##_getfirst(const struct name *ht, \ - const HTABLE_KTYPE(keyof, type) k, \ - struct name##_iter *iter) \ + static inline UNNEEDED bool name##_exists(const struct name *ht, \ + const HTABLE_KTYPE(keyof, type) k) \ { \ + struct htable_iter i; \ size_t h = hashfn(k); \ - type *v = htable_firstval(&ht->raw, &iter->i, h); \ - return name##_getmatch_(ht, k, h, v, iter); \ + void *v; \ + \ + v = htable_firstval(&ht->raw, &i, h); \ + return name##_getmatch_(ht, k, h, v, &i) != NULL; \ } \ - static inline UNNEEDED type *name##_getnext(const struct name *ht, \ - const HTABLE_KTYPE(keyof, type) k, \ + 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); \ + } + +#define HTABLE_DEFINE_NODUPS_TYPE(type, keyof, hashfn, eqfn, name) \ + HTABLE_DEFINE_TYPE_CORE(type, keyof, hashfn, eqfn, name) \ + 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); \ - type *v = htable_nextval(&ht->raw, &iter->i, h); \ - return name##_getmatch_(ht, k, h, v, iter); \ + void *v; \ + \ + v = htable_firstval(&ht->raw, &i, h); \ + return name##_getmatch_(ht, k, h, v, &i); \ + } \ + static inline bool name##_add(struct name *ht, const type *elem) \ + { \ + /* Open-coded for slightly more efficiency */ \ + const HTABLE_KTYPE(keyof, type) k = keyof(elem); \ + struct htable_iter i; \ + size_t h = hashfn(k); \ + void *v; \ + \ + v = htable_firstval(&ht->raw, &i, h); \ + assert(!name##_getmatch_(ht, k, h, v, &i)); \ + return htable_add(&ht->raw, h, elem); \ } \ static inline UNNEEDED bool name##_delkey(struct name *ht, \ const HTABLE_KTYPE(keyof, type) k) \ @@ -127,21 +182,39 @@ if (elem) \ return name##_del(ht, elem); \ return false; \ + } + +#define HTABLE_DEFINE_DUPS_TYPE(type, keyof, hashfn, eqfn, name) \ + HTABLE_DEFINE_TYPE_CORE(type, keyof, hashfn, eqfn, name) \ + static inline bool name##_add(struct name *ht, const type *elem) \ + { \ + const HTABLE_KTYPE(keyof, type) k = keyof(elem); \ + return htable_add(&ht->raw, hashfn(k), elem); \ } \ - static inline UNNEEDED type *name##_first(const struct name *ht, \ + static inline UNNEEDED type *name##_getfirst(const struct name *ht, \ + const HTABLE_KTYPE(keyof, type) k, \ struct name##_iter *iter) \ { \ - return htable_first(&ht->raw, &iter->i); \ + size_t h = hashfn(k); \ + type *v = htable_firstval(&ht->raw, &iter->i, h); \ + return name##_getmatch_(ht, k, h, v, &iter->i); \ } \ - static inline UNNEEDED type *name##_next(const struct name *ht, \ - struct name##_iter *iter) \ + static inline UNNEEDED type *name##_getnext(const struct name *ht, \ + const HTABLE_KTYPE(keyof, type) k, \ + struct name##_iter *iter) \ { \ - return htable_next(&ht->raw, &iter->i); \ + size_t h = hashfn(k); \ + type *v = htable_nextval(&ht->raw, &iter->i, h); \ + return name##_getmatch_(ht, k, h, v, &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 */