#ifndef CCAN_HTABLE_H
#define CCAN_HTABLE_H
#include "config.h"
+#include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>
-struct htable;
+/**
+ * struct htable - private definition of a htable.
+ *
+ * It's exposed here so you can put it in your structures and so we can
+ * supply inline functions.
+ */
+struct htable {
+ size_t (*rehash)(const void *elem, void *priv);
+ void *priv;
+ unsigned int bits;
+ size_t elems, deleted, max, max_with_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_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, 0, -1, 0, 0, &name.perfect_bit }
+
+/**
+ * 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.
+ */
+void htable_init(struct htable *ht,
+ size_t (*rehash)(const void *elem, void *priv), void *priv);
/**
- * htable_new - allocate 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.
*/
-struct htable *htable_new(size_t (*hash)(const void *elem, void *priv),
- void *priv);
+bool htable_init_sized(struct htable *ht,
+ size_t (*rehash)(const void *elem, void *priv),
+ void *priv, size_t size);
/**
- * htable_free - dellocate a hash tree.
+ * 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_free(const struct htable *);
+void htable_clear(struct htable *ht);
+
+/**
+ * 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;
+ */
+bool htable_copy(struct htable *dst, const struct htable *src);
/**
* htable_rehash - use a hashtree's rehash function
size_t htable_rehash(const void *elem);
/**
- * 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
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
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.
+ */
+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
*