X-Git-Url: http://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Fhtable%2Fhtable.h;h=eac57e37a326612226f6cd7907c04bcbc589c360;hp=e150c2ef0958065d3e289482d78dfe8267017a9b;hb=HEAD;hpb=7b56762984ce66f38728b542ca347bcb6fe3e981 diff --git a/ccan/htable/htable.h b/ccan/htable/htable.h index e150c2ef..faaf541b 100644 --- a/ccan/htable/htable.h +++ b/ccan/htable/htable.h @@ -2,10 +2,19 @@ #ifndef CCAN_HTABLE_H #define CCAN_HTABLE_H #include "config.h" +#include #include #include #include +/* Define CCAN_HTABLE_DEBUG for expensive debugging checks on each call. */ +#define HTABLE_LOC __FILE__ ":" stringify(__LINE__) +#ifdef CCAN_HTABLE_DEBUG +#define htable_debug(h, loc) htable_check((h), loc) +#else +#define htable_debug(h, loc) ((void)loc, h) +#endif + /** * struct htable - private definition of a htable. * @@ -15,11 +24,10 @@ struct htable { size_t (*rehash)(const void *elem, void *priv); void *priv; - unsigned int bits; - size_t elems, deleted, max, max_with_deleted; + unsigned int bits, perfect_bitnum; + size_t elems, deleted; /* These are the bits which are the same in all pointers. */ uintptr_t common_mask, common_bits; - uintptr_t perfect_bit; uintptr_t *table; }; @@ -35,12 +43,13 @@ struct htable { * // For simplicity's sake, say hash value is contents of elem. * static size_t rehash(const void *elem, void *unused) * { + * (void)unused; * return *(size_t *)elem; * } * static struct htable ht = HTABLE_INITIALIZER(ht, rehash, NULL); */ #define HTABLE_INITIALIZER(name, rehash, priv) \ - { rehash, priv, 0, 0, 0, 0, 0, -1, 0, 0, &name.perfect_bit } + { rehash, priv, 0, 0, 0, 0, -1, 0, &name.common_bits } /** * htable_init - initialize an empty hash table. @@ -66,6 +75,15 @@ bool htable_init_sized(struct htable *ht, size_t (*rehash)(const void *elem, void *priv), void *priv, size_t size); +/** + * htable_count - count number of entries in a hash table. + * @ht: the hash table + */ +static inline size_t htable_count(const struct htable *ht) +{ + return ht->elems; +} + /** * htable_clear - empty a hash table. * @ht: the hash table to clear @@ -74,23 +92,54 @@ bool htable_init_sized(struct htable *ht, */ void htable_clear(struct htable *ht); + +/** + * htable_check - check hash table for consistency + * @ht: the htable + * @abortstr: the location to print on aborting, or NULL. + * + * Because hash tables have redundant information, consistency checking that + * each element is in the correct location can be done. This is useful as a + * debugging check. If @abortstr is non-NULL, that will be printed in a + * diagnostic if the htable is inconsistent, and the function will abort. + * + * Returns the htable if it is consistent, NULL if not (it can never return + * NULL if @abortstr is set). + */ +struct htable *htable_check(const struct htable *ht, const char *abortstr); + /** - * htable_rehash - use a hashtree's rehash function - * @elem: the argument to rehash() + * htable_copy - duplicate a hash table. + * @dst: the hash table to overwrite + * @src: the hash table to copy + * + * Only fails on out-of-memory. * + * Equivalent to (but faster than): + * if (!htable_init_sized(dst, src->rehash, src->priv, 1U << src->bits)) + * return false; + * v = htable_first(src, &i); + * while (v) { + * htable_add(dst, v); + * v = htable_next(src, i); + * } + * return true; */ -size_t htable_rehash(const void *elem); +#define htable_copy(dst, src) htable_copy_(dst, htable_debug(src, HTABLE_LOC)) +bool htable_copy_(struct htable *dst, const struct htable *src); /** * htable_add - add a pointer into a hash table. * @ht: the htable * @hash: the hash value of the object - * @p: the non-NULL pointer + * @p: the non-NULL pointer (also cannot be (void *)1). * * Also note that this can only fail due to allocation failure. Otherwise, it * returns true. */ -bool htable_add(struct htable *ht, size_t hash, const void *p); +#define htable_add(ht, hash, p) \ + htable_add_(htable_debug(ht, HTABLE_LOC), hash, p) +bool htable_add_(struct htable *ht, size_t hash, const void *p); /** * htable_del - remove a pointer from a hash table @@ -100,7 +149,9 @@ bool htable_add(struct htable *ht, size_t hash, const void *p); * * Returns true if the pointer was found (and deleted). */ -bool htable_del(struct htable *ht, size_t hash, const void *p); +#define htable_del(ht, hash, p) \ + htable_del_(htable_debug(ht, HTABLE_LOC), hash, p) +bool htable_del_(struct htable *ht, size_t hash, const void *p); /** * struct htable_iter - iterator or htable_first or htable_firstval etc. @@ -121,8 +172,11 @@ struct htable_iter { * See Also: * htable_delval() */ -void *htable_firstval(const struct htable *htable, - struct htable_iter *i, size_t hash); +#define htable_firstval(htable, i, hash) \ + htable_firstval_(htable_debug(htable, HTABLE_LOC), i, hash) + +void *htable_firstval_(const struct htable *htable, + struct htable_iter *i, size_t hash); /** * htable_nextval - find another candidate for a given hash value @@ -132,8 +186,10 @@ void *htable_firstval(const struct htable *htable, * * You'll need to check the value is what you want; returns NULL if no more. */ -void *htable_nextval(const struct htable *htable, - struct htable_iter *i, size_t hash); +#define htable_nextval(htable, i, hash) \ + htable_nextval_(htable_debug(htable, HTABLE_LOC), i, hash) +void *htable_nextval_(const struct htable *htable, + struct htable_iter *i, size_t hash); /** * htable_get - find an entry in the hash table @@ -166,7 +222,9 @@ static inline void *htable_get(const struct htable *ht, * * Get an entry in the hashtable; NULL if empty. */ -void *htable_first(const struct htable *htable, struct htable_iter *i); +#define htable_first(htable, i) \ + htable_first_(htable_debug(htable, HTABLE_LOC), i) +void *htable_first_(const struct htable *htable, struct htable_iter *i); /** * htable_next - find another entry in the hash table @@ -176,7 +234,9 @@ void *htable_first(const struct htable *htable, struct htable_iter *i); * Get another entry in the hashtable; NULL if all done. * This is usually used after htable_first or prior non-NULL htable_next. */ -void *htable_next(const struct htable *htable, struct htable_iter *i); +#define htable_next(htable, i) \ + htable_next_(htable_debug(htable, HTABLE_LOC), i) +void *htable_next_(const struct htable *htable, struct htable_iter *i); /** * htable_prev - find the previous entry in the hash table @@ -191,7 +251,9 @@ void *htable_next(const struct htable *htable, struct htable_iter *i); * This is usually used in the middle of (or after) a htable_next iteration and * to "unwind" actions taken. */ -void *htable_prev(const struct htable *htable, struct htable_iter *i); +#define htable_prev(htable, i) \ + htable_prev_(htable_debug(htable, HTABLE_LOC), i) +void *htable_prev_(const struct htable *htable, struct htable_iter *i); /** * htable_delval - remove an iterated pointer from a hash table @@ -201,6 +263,28 @@ void *htable_prev(const struct htable *htable, struct htable_iter *i); * Usually used to delete a hash entry after it has been found with * htable_firstval etc. */ -void htable_delval(struct htable *ht, struct htable_iter *i); +#define htable_delval(htable, i) \ + htable_delval_(htable_debug(htable, HTABLE_LOC), i) +void htable_delval_(struct htable *ht, struct htable_iter *i); + +/** + * htable_pick - set iterator to a random valid entry. + * @ht: the htable + * @seed: a random number to use. + * @i: the htable_iter which is output (or NULL). + * + * Usually used with htable_delval to delete a random entry. Returns + * NULL iff the table is empty, otherwise a random entry. + */ +#define htable_pick(htable, seed, i) \ + htable_pick_(htable_debug(htable, HTABLE_LOC), seed, i) +void *htable_pick_(const struct htable *ht, size_t seed, struct htable_iter *i); +/** + * htable_set_allocator - set calloc/free functions. + * @alloc: allocator to use, must zero memory! + * @free: unallocator to use (@p is NULL or a return from @alloc) + */ +void htable_set_allocator(void *(*alloc)(struct htable *, size_t len), + void (*free)(struct htable *, void *p)); #endif /* CCAN_HTABLE_H */