#ifndef CCAN_HTABLE_H
#define CCAN_HTABLE_H
#include "config.h"
+#include <ccan/str/str.h>
#include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>
+/* 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.
*
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;
};
/**
- * htable_init - initialize an empty hash tree.
+ * HTABLE_INITIALIZER - static initialization for a hash table.
+ * @name: name of this htable.
+ * @rehash: hash function to use for rehashing.
+ * @priv: private argument to @rehash function.
+ *
+ * This is useful for setting up static and global hash tables.
+ *
+ * Example:
+ * // 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, -1, 0, &name.common_bits }
+
+/**
+ * htable_init - initialize an empty hash table.
* @ht: the hash table to initialize
* @rehash: hash function to use for rehashing.
* @priv: private argument to @rehash function.
size_t (*rehash)(const void *elem, void *priv), void *priv);
/**
- * htable_clear - empty a hash tree.
+ * htable_init_sized - initialize an empty hash table of given size.
+ * @ht: the hash table to initialize
+ * @rehash: hash function to use for rehashing.
+ * @priv: private argument to @rehash function.
+ * @size: the number of element.
+ *
+ * If this returns false, @ht is still usable, but may need to do reallocation
+ * upon an add. If this returns true, it will not need to reallocate within
+ * @size htable_adds.
+ */
+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
*
* This doesn't do anything to any pointers left in it.
*/
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 tree.
+ * 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 tree
+ * htable_del - remove a pointer from a hash table
* @ht: the htable
* @hash: the hash value of the object
* @p: the pointer
*
* 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.
* 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
*
* 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
*
* 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
* 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_delval - remove an iterated pointer from a hash tree
+ * htable_prev - find the previous entry in the hash table
+ * @ht: the hashtable
+ * @i: the struct htable_iter to use
+ *
+ * Get previous entry in the hashtable; NULL if all done.
+ *
+ * "previous" here only means the item that would have been returned by
+ * htable_next() before the item it returned most recently.
+ *
+ * This is usually used in the middle of (or after) a htable_next iteration and
+ * to "unwind" actions taken.
+ */
+#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
* @ht: the htable
* @i: the htable_iter
*
* 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 */
projects / ccan / blobdiff