progress

15 files changed, 2358 insertions, 0 deletions

diff --git a/ccan/htable/LICENSE b/ccan/htable/LICENSE
new file mode 120000
index 0000000..dc314ec
--- /dev/null
+++ b/ccan/htable/LICENSE
@@ -0,0 +1 @@
+../../licenses/LGPL-2.1
\ No newline at end of file
diff --git a/ccan/htable/_info b/ccan/htable/_info
new file mode 100644
index 0000000..a3bb76d
--- /dev/null
+++ b/ccan/htable/_info
@@ -0,0 +1,117 @@
+#include "config.h"
+#include <string.h>
+#include <stdio.h>
+
+/**
+ * htable - hash table routines
+ *
+ * A hash table is an efficient structure for looking up keys.  This version
+ * grows with usage and allows efficient deletion.
+ *
+ * Example:
+ *	#include <ccan/htable/htable.h>
+ *	#include <ccan/hash/hash.h>
+ *	#include <stdio.h>
+ *	#include <err.h>
+ *	#include <string.h>
+ *
+ *	struct name_to_digit {
+ *		const char *name;
+ *		unsigned int val;
+ *	};
+ *
+ *	static struct name_to_digit map[] = {
+ *		{ "zero", 0},
+ *		{ "one", 1 },
+ *		{ "two", 2 },
+ *		{ "three", 3 },
+ *		{ "four", 4 },
+ *		{ "five", 5 },
+ *		{ "six", 6 },
+ *		{ "seven", 7 },
+ *		{ "eight", 8 },
+ *		{ "nine", 9 }
+ *	};
+ *
+ *	// Wrapper for rehash function pointer.
+ *	static size_t rehash(const void *e, void *unused)
+ *	{
+ *		(void)unused;
+ *		return hash_string(((struct name_to_digit *)e)->name);
+ *	}
+ *
+ *	// Comparison function.
+ *	static bool streq(const void *e, void *string)
+ *	{
+ *		return strcmp(((struct name_to_digit *)e)->name, string) == 0;
+ *	}
+ *
+ *	// We let them add their own aliases, eg. --alias=v=5
+ *	static void add_alias(struct htable *ht, const char *alias)
+ *	{
+ *		char *eq;
+ *		struct name_to_digit *n;
+ *
+ *		n = malloc(sizeof(*n));
+ *		n->name = strdup(alias);
+ *
+ *		eq = strchr(n->name, '=');
+ *		if (!eq || ((n->val = atoi(eq+1)) == 0 && !strcmp(eq+1, "0")))
+ *			errx(1, "Usage: --alias=<name>=<value>");
+ *		*eq = '\0';
+ *		htable_add(ht, hash_string(n->name), n);
+ *	}
+ *
+ *	int main(int argc, char *argv[])
+ *	{
+ *		struct htable ht;
+ *		int i;
+ *		unsigned long val;
+ *
+ *		if (argc < 2)
+ *			errx(1, "Usage: %s [--alias=<name>=<val>]... <str>...",
+ *			     argv[0]);
+ *
+ *		// Create and populate hash table.
+ *		htable_init(&ht, rehash, NULL);
+ *		for (i = 0; i < (int)(sizeof(map)/sizeof(map[0])); i++)
+ *			htable_add(&ht, hash_string(map[i].name), &map[i]);
+ *
+ *		// Add any aliases to the hash table.
+ *		for (i = 1; i < argc; i++) {
+ *			if (!strncmp(argv[i], "--alias=", strlen("--alias=")))
+ *				add_alias(&ht, argv[i] + strlen("--alias="));
+ *			else
+ *				break;
+ *		}
+ *
+ *		// Find the other args in the hash table.
+ *		for (val = 0; i < argc; i++) {
+ *			struct name_to_digit *n;
+ *			n = htable_get(&ht, hash_string(argv[i]),
+ *				       streq, argv[i]);
+ *			if (!n)
+ *				errx(1, "Invalid digit name %s", argv[i]);
+ *			// Append it to the value we are building up.
+ *			val *= 10;
+ *			val += n->val;
+ *		}
+ *		printf("%lu\n", val);
+ *		return 0;
+ *	}
+ *
+ * License: LGPL (v2.1 or any later version)
+ * Author: Rusty Russell <rusty@rustcorp.com.au>
+ */
+int main(int argc, char *argv[])
+{
+	if (argc != 2)
+		return 1;
+
+	if (strcmp(argv[1], "depends") == 0) {
+		printf("ccan/compiler\n");
+		return 0;
+	}
+
+	return 1;
+}
diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c
new file mode 100644
index 0000000..e1d1369
--- /dev/null
+++ b/ccan/htable/htable.c
@@ -0,0 +1,325 @@
+/* Licensed under LGPLv2+ - see LICENSE file for details */
+#include <ccan/htable/htable.h>
+#include <ccan/compiler/compiler.h>
+#include <stdlib.h>
+#include <limits.h>
+#include <stdbool.h>
+#include <assert.h>
+#include <string.h>
+
+/* We use 0x1 as deleted marker. */
+#define HTABLE_DELETED (0x1)
+
+/* We clear out the bits which are always the same, and put metadata there. */
+static inline uintptr_t get_extra_ptr_bits(const struct htable *ht,
+					   uintptr_t e)
+{
+	return e & ht->common_mask;
+}
+
+static inline void *get_raw_ptr(const struct htable *ht, uintptr_t e)
+{
+	return (void *)((e & ~ht->common_mask) | ht->common_bits);
+}
+
+static inline uintptr_t make_hval(const struct htable *ht,
+				  const void *p, uintptr_t bits)
+{
+	return ((uintptr_t)p & ~ht->common_mask) | bits;
+}
+
+static inline bool entry_is_valid(uintptr_t e)
+{
+	return e > HTABLE_DELETED;
+}
+
+static inline uintptr_t get_hash_ptr_bits(const struct htable *ht,
+					  size_t hash)
+{
+	/* Shuffling the extra bits (as specified in mask) down the
+	 * end is quite expensive.  But the lower bits are redundant, so
+	 * we fold the value first. */
+	return (hash ^ (hash >> ht->bits))
+		& ht->common_mask & ~ht->perfect_bit;
+}
+
+void htable_init(struct htable *ht,
+		 size_t (*rehash)(const void *elem, void *priv), void *priv)
+{
+	struct htable empty = HTABLE_INITIALIZER(empty, NULL, NULL);
+	*ht = empty;
+	ht->rehash = rehash;
+	ht->priv = priv;
+	ht->table = &ht->perfect_bit;
+}
+
+/* We've changed ht->bits, update ht->max and ht->max_with_deleted */
+static void htable_adjust_capacity(struct htable *ht)
+{
+	ht->max = ((size_t)3 << ht->bits) / 4;
+	ht->max_with_deleted = ((size_t)9 << ht->bits) / 10;
+}
+
+bool htable_init_sized(struct htable *ht,
+		       size_t (*rehash)(const void *, void *),
+		       void *priv, size_t expect)
+{
+	htable_init(ht, rehash, priv);
+
+	/* Don't go insane with sizing. */
+	for (ht->bits = 1; ((size_t)3 << ht->bits) / 4 < expect; ht->bits++) {
+		if (ht->bits == 30)
+			break;
+	}
+
+	ht->table = calloc(1 << ht->bits, sizeof(size_t));
+	if (!ht->table) {
+		ht->table = &ht->perfect_bit;
+		return false;
+	}
+	htable_adjust_capacity(ht);
+	return true;
+}
+	
+void htable_clear(struct htable *ht)
+{
+	if (ht->table != &ht->perfect_bit)
+		free((void *)ht->table);
+	htable_init(ht, ht->rehash, ht->priv);
+}
+
+bool htable_copy(struct htable *dst, const struct htable *src)
+{
+	uintptr_t *htable = malloc(sizeof(size_t) << src->bits);
+
+	if (!htable)
+		return false;
+
+	*dst = *src;
+	dst->table = htable;
+	memcpy(dst->table, src->table, sizeof(size_t) << src->bits);
+	return true;
+}
+
+static size_t hash_bucket(const struct htable *ht, size_t h)
+{
+	return h & ((1 << ht->bits)-1);
+}
+
+static void *htable_val(const struct htable *ht,
+			struct htable_iter *i, size_t hash, uintptr_t perfect)
+{
+	uintptr_t h2 = get_hash_ptr_bits(ht, hash) | perfect;
+
+	while (ht->table[i->off]) {
+		if (ht->table[i->off] != HTABLE_DELETED) {
+			if (get_extra_ptr_bits(ht, ht->table[i->off]) == h2)
+				return get_raw_ptr(ht, ht->table[i->off]);
+		}
+		i->off = (i->off + 1) & ((1 << ht->bits)-1);
+		h2 &= ~perfect;
+	}
+	return NULL;
+}
+
+void *htable_firstval(const struct htable *ht,
+		      struct htable_iter *i, size_t hash)
+{
+	i->off = hash_bucket(ht, hash);
+	return htable_val(ht, i, hash, ht->perfect_bit);
+}
+
+void *htable_nextval(const struct htable *ht,
+		     struct htable_iter *i, size_t hash)
+{
+	i->off = (i->off + 1) & ((1 << ht->bits)-1);
+	return htable_val(ht, i, hash, 0);
+}
+
+void *htable_first(const struct htable *ht, struct htable_iter *i)
+{
+	for (i->off = 0; i->off < (size_t)1 << ht->bits; i->off++) {
+		if (entry_is_valid(ht->table[i->off]))
+			return get_raw_ptr(ht, ht->table[i->off]);
+	}
+	return NULL;
+}
+
+void *htable_next(const struct htable *ht, struct htable_iter *i)
+{
+	for (i->off++; i->off < (size_t)1 << ht->bits; i->off++) {
+		if (entry_is_valid(ht->table[i->off]))
+			return get_raw_ptr(ht, ht->table[i->off]);
+	}
+	return NULL;
+}
+
+void *htable_prev(const struct htable *ht, struct htable_iter *i)
+{
+	for (;;) {
+		if (!i->off)
+			return NULL;
+		i->off --;
+		if (entry_is_valid(ht->table[i->off]))
+			return get_raw_ptr(ht, ht->table[i->off]);
+	}
+}
+
+/* This does not expand the hash table, that's up to caller. */
+static void ht_add(struct htable *ht, const void *new, size_t h)
+{
+	size_t i;
+	uintptr_t perfect = ht->perfect_bit;
+
+	i = hash_bucket(ht, h);
+
+	while (entry_is_valid(ht->table[i])) {
+		perfect = 0;
+		i = (i + 1) & ((1 << ht->bits)-1);
+	}
+	ht->table[i] = make_hval(ht, new, get_hash_ptr_bits(ht, h)|perfect);
+}
+
+static COLD bool double_table(struct htable *ht)
+{
+	unsigned int i;
+	size_t oldnum = (size_t)1 << ht->bits;
+	uintptr_t *oldtable, e;
+
+	oldtable = ht->table;
+	ht->table = calloc(1 << (ht->bits+1), sizeof(size_t));
+	if (!ht->table) {
+		ht->table = oldtable;
+		return false;
+	}
+	ht->bits++;
+	htable_adjust_capacity(ht);
+
+	/* If we lost our "perfect bit", get it back now. */
+	if (!ht->perfect_bit && ht->common_mask) {
+		for (i = 0; i < sizeof(ht->common_mask) * CHAR_BIT; i++) {
+			if (ht->common_mask & ((size_t)1 << i)) {
+				ht->perfect_bit = (size_t)1 << i;
+				break;
+			}
+		}
+	}
+
+	if (oldtable != &ht->perfect_bit) {
+		for (i = 0; i < oldnum; i++) {
+			if (entry_is_valid(e = oldtable[i])) {
+				void *p = get_raw_ptr(ht, e);
+				ht_add(ht, p, ht->rehash(p, ht->priv));
+			}
+		}
+		free(oldtable);
+	}
+	ht->deleted = 0;
+	return true;
+}
+
+static COLD void rehash_table(struct htable *ht)
+{
+	size_t start, i;
+	uintptr_t e;
+
+	/* Beware wrap cases: we need to start from first empty bucket. */
+	for (start = 0; ht->table[start]; start++);
+
+	for (i = 0; i < (size_t)1 << ht->bits; i++) {
+		size_t h = (i + start) & ((1 << ht->bits)-1);
+		e = ht->table[h];
+		if (!e)
+			continue;
+		if (e == HTABLE_DELETED)
+			ht->table[h] = 0;
+		else if (!(e & ht->perfect_bit)) {
+			void *p = get_raw_ptr(ht, e);
+			ht->table[h] = 0;
+			ht_add(ht, p, ht->rehash(p, ht->priv));
+		}
+	}
+	ht->deleted = 0;
+}
+
+/* We stole some bits, now we need to put them back... */
+static COLD void update_common(struct htable *ht, const void *p)
+{
+	unsigned int i;
+	uintptr_t maskdiff, bitsdiff;
+
+	if (ht->elems == 0) {
+		/* Always reveal one bit of the pointer in the bucket,
+		 * so it's not zero or HTABLE_DELETED (1), even if
+		 * hash happens to be 0.  Assumes (void *)1 is not a
+		 * valid pointer. */
+		for (i = sizeof(uintptr_t)*CHAR_BIT - 1; i > 0; i--) {
+			if ((uintptr_t)p & ((uintptr_t)1 << i))
+				break;
+		}
+
+		ht->common_mask = ~((uintptr_t)1 << i);
+		ht->common_bits = ((uintptr_t)p & ht->common_mask);
+		ht->perfect_bit = 1;
+		return;
+	}
+
+	/* Find bits which are unequal to old common set. */
+	maskdiff = ht->common_bits ^ ((uintptr_t)p & ht->common_mask);
+
+	/* These are the bits which go there in existing entries. */
+	bitsdiff = ht->common_bits & maskdiff;
+
+	for (i = 0; i < (size_t)1 << ht->bits; i++) {
+		if (!entry_is_valid(ht->table[i]))
+			continue;
+		/* Clear the bits no longer in the mask, set them as
+		 * expected. */
+		ht->table[i] &= ~maskdiff;
+		ht->table[i] |= bitsdiff;
+	}
+
+	/* Take away those bits from our mask, bits and perfect bit. */
+	ht->common_mask &= ~maskdiff;
+	ht->common_bits &= ~maskdiff;
+	ht->perfect_bit &= ~maskdiff;
+}
+
+bool htable_add(struct htable *ht, size_t hash, const void *p)
+{
+	if (ht->elems+1 > ht->max && !double_table(ht))
+		return false;
+	if (ht->elems+1 + ht->deleted > ht->max_with_deleted)
+		rehash_table(ht);
+	assert(p);
+	if (((uintptr_t)p & ht->common_mask) != ht->common_bits)
+		update_common(ht, p);
+
+	ht_add(ht, p, hash);
+	ht->elems++;
+	return true;
+}
+
+bool htable_del(struct htable *ht, size_t h, const void *p)
+{
+	struct htable_iter i;
+	void *c;
+
+	for (c = htable_firstval(ht,&i,h); c; c = htable_nextval(ht,&i,h)) {
+		if (c == p) {
+			htable_delval(ht, &i);
+			return true;
+		}
+	}
+	return false;
+}
+
+void htable_delval(struct htable *ht, struct htable_iter *i)
+{
+	assert(i->off < (size_t)1 << ht->bits);
+	assert(entry_is_valid(ht->table[i->off]));
+
+	ht->elems--;
+	ht->table[i->off] = HTABLE_DELETED;
+	ht->deleted++;
+}
diff --git a/ccan/htable/htable.h b/ccan/htable/htable.h
new file mode 100644
index 0000000..9845388
--- /dev/null
+++ b/ccan/htable/htable.h
@@ -0,0 +1,226 @@
+/* Licensed under LGPLv2+ - see LICENSE file for details */
+#ifndef CCAN_HTABLE_H
+#define CCAN_HTABLE_H
+#include "config.h"
+#include <stdint.h>
+#include <stdbool.h>
+#include <stdlib.h>
+
+/**
+ * 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_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_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_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
+ * @elem: the argument to rehash()
+ *
+ */
+size_t htable_rehash(const void *elem);
+
+/**
+ * htable_add - add a pointer into a hash table.
+ * @ht: the htable
+ * @hash: the hash value of the object
+ * @p: the non-NULL pointer
+ *
+ * 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);
+
+/**
+ * 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);
+
+/**
+ * struct htable_iter - iterator or htable_first or htable_firstval etc.
+ *
+ * This refers to a location inside the hashtable.
+ */
+struct htable_iter {
+	size_t off;
+};
+
+/**
+ * htable_firstval - find a candidate for a given hash value
+ * @htable: the hashtable
+ * @i: the struct htable_iter to initialize
+ * @hash: the hash value
+ *
+ * You'll need to check the value is what you want; returns NULL if none.
+ * See Also:
+ *	htable_delval()
+ */
+void *htable_firstval(const struct htable *htable,
+		      struct htable_iter *i, size_t hash);
+
+/**
+ * htable_nextval - find another candidate for a given hash value
+ * @htable: the hashtable
+ * @i: the struct htable_iter to initialize
+ * @hash: the 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);
+
+/**
+ * htable_get - find an entry in the hash table
+ * @ht: the hashtable
+ * @h: the hash value of the entry
+ * @cmp: the comparison function
+ * @ptr: the pointer to hand to the comparison function.
+ *
+ * Convenient inline wrapper for htable_firstval/htable_nextval loop.
+ */
+static inline void *htable_get(const struct htable *ht,
+			       size_t h,
+			       bool (*cmp)(const void *candidate, void *ptr),
+			       const void *ptr)
+{
+	struct htable_iter i;
+	void *c;
+
+	for (c = htable_firstval(ht,&i,h); c; c = htable_nextval(ht,&i,h)) {
+		if (cmp(c, (void *)ptr))
+			return c;
+	}
+	return NULL;
+}
+
+/**
+ * htable_first - find an entry in the hash table
+ * @ht: the hashtable
+ * @i: the struct htable_iter to initialize
+ *
+ * Get an entry in the hashtable; NULL if empty.
+ */
+void *htable_first(const struct htable *htable, struct htable_iter *i);
+
+/**
+ * htable_next - find another entry in the hash table
+ * @ht: the hashtable
+ * @i: the struct htable_iter to use
+ *
+ * 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);
+
+/**
+ * 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
+ *
+ * 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);
+
+#endif /* CCAN_HTABLE_H */
diff --git a/ccan/htable/htable_type.h b/ccan/htable/htable_type.h
new file mode 100644
index 0000000..1401167
--- /dev/null
+++ b/ccan/htable/htable_type.h
@@ -0,0 +1,166 @@
+/* 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);
+ *
+ * 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);
+ *
+ * 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);
+ *
+ * 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 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 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 */
diff --git a/ccan/htable/test/run-copy.c b/ccan/htable/test/run-copy.c
new file mode 100644
index 0000000..d111495
--- /dev/null
+++ b/ccan/htable/test/run-copy.c
@@ -0,0 +1,44 @@
+#include <ccan/htable/htable.h>
+#include <ccan/htable/htable.c>
+#include <ccan/tap/tap.h>
+#include <stdbool.h>
+#include <string.h>
+
+#define NUM_VALS 512
+
+static size_t hash(const void *elem, void *unused UNNEEDED)
+{
+	size_t h = *(uint64_t *)elem / 2;
+	return h;
+}
+
+static bool cmp(const void *candidate, void *ptr)
+{
+	return *(const uint64_t *)candidate == *(const uint64_t *)ptr;
+}
+
+int main(void)
+{
+	struct htable ht, ht2;
+	uint64_t val[NUM_VALS], i;
+
+	plan_tests((NUM_VALS) * 3);
+	for (i = 0; i < NUM_VALS; i++)
+		val[i] = i;
+
+	htable_init(&ht, hash, NULL);
+	for (i = 0; i < NUM_VALS; i++) {
+		ok1(ht.max >= i);
+		ok1(ht.max <= i * 2);
+		htable_add(&ht, hash(&val[i], NULL), &val[i]);
+	}
+
+	htable_copy(&ht2, &ht);
+	htable_clear(&ht);
+
+	for (i = 0; i < NUM_VALS; i++)
+		ok1(htable_get(&ht2, hash(&i, NULL), cmp, &i) == &val[i]);
+	htable_clear(&ht2);
+
+	return exit_status();
+}
diff --git a/ccan/htable/test/run-size.c b/ccan/htable/test/run-size.c
new file mode 100644
index 0000000..1a2f5cd
--- /dev/null
+++ b/ccan/htable/test/run-size.c
@@ -0,0 +1,36 @@
+#include <ccan/htable/htable.h>
+#include <ccan/htable/htable.c>
+#include <ccan/tap/tap.h>
+#include <stdbool.h>
+#include <string.h>
+
+#define NUM_VALS 512
+
+/* We use the number divided by two as the hash (for lots of
+   collisions). */
+static size_t hash(const void *elem, void *unused UNNEEDED)
+{
+	size_t h = *(uint64_t *)elem / 2;
+	return h;
+}
+
+int main(void)
+{
+	struct htable ht;
+	uint64_t val[NUM_VALS];
+	unsigned int i;
+
+	plan_tests((NUM_VALS) * 2);
+	for (i = 0; i < NUM_VALS; i++)
+		val[i] = i;
+
+	htable_init(&ht, hash, NULL);
+	for (i = 0; i < NUM_VALS; i++) {
+		ok1(ht.max >= i);
+		ok1(ht.max <= i * 2);
+		htable_add(&ht, hash(&val[i], NULL), &val[i]);
+	}
+	htable_clear(&ht);
+
+	return exit_status();
+}
diff --git a/ccan/htable/test/run-type-int.c b/ccan/htable/test/run-type-int.c
new file mode 100644
index 0000000..7b71815
--- /dev/null
+++ b/ccan/htable/test/run-type-int.c
@@ -0,0 +1,215 @@
+/* Key is an unsigned int, not a pointer. */
+#include "config.h"
+#if !defined(HAVE_TYPEOF) || !HAVE_TYPEOF
+#define HTABLE_KTYPE(keyof, type) unsigned int
+#endif
+#include <ccan/htable/htable_type.h>
+#include <ccan/htable/htable.c>
+#include <ccan/tap/tap.h>
+#include <stdbool.h>
+#include <string.h>
+
+#define NUM_BITS 7
+#define NUM_VALS (1 << NUM_BITS)
+
+struct obj {
+	/* Makes sure we don't try to treat and obj as a key or vice versa */
+	unsigned char unused;
+	unsigned int key;
+};
+
+static const unsigned int objkey(const struct obj *obj)
+{
+	return obj->key;
+}
+
+/* We use the number divided by two as the hash (for lots of
+   collisions), plus set all the higher bits so we can detect if they
+   don't get masked out. */
+static size_t objhash(const unsigned int key)
+{
+	size_t h = key / 2;
+	h |= -1UL << NUM_BITS;
+	return h;
+}
+
+static bool cmp(const struct obj *obj, const unsigned int key)
+{
+	return obj->key == key;
+}
+
+HTABLE_DEFINE_TYPE(struct obj, objkey, objhash, cmp, htable_obj);
+
+static void add_vals(struct htable_obj *ht,
+		     struct obj val[], unsigned int num)
+{
+	unsigned int i;
+
+	for (i = 0; i < num; i++) {
+		if (htable_obj_get(ht, i)) {
+			fail("%u already in hash", i);
+			return;
+		}
+		htable_obj_add(ht, &val[i]);
+		if (htable_obj_get(ht, i) != &val[i]) {
+			fail("%u not added to hash", i);
+			return;
+		}
+	}
+	pass("Added %u numbers to hash", i);
+}
+
+static void find_vals(const struct htable_obj *ht,
+		      const struct obj val[], unsigned int num)
+{
+	unsigned int i;
+
+	for (i = 0; i < num; i++) {
+		if (htable_obj_get(ht, i) != &val[i]) {
+			fail("%u not found in hash", i);
+			return;
+		}
+	}
+	pass("Found %u numbers in hash", i);
+}
+
+static void del_vals(struct htable_obj *ht,
+		     const struct obj val[], unsigned int num)
+{
+	unsigned int i;
+
+	for (i = 0; i < num; i++) {
+		if (!htable_obj_delkey(ht, val[i].key)) {
+			fail("%u not deleted from hash", i);
+			return;
+		}
+	}
+	pass("Deleted %u numbers in hash", i);
+}
+
+static void del_vals_bykey(struct htable_obj *ht,
+			   const struct obj val[] UNNEEDED, unsigned int num)
+{
+	unsigned int i;
+
+	for (i = 0; i < num; i++) {
+		if (!htable_obj_delkey(ht, i)) {
+			fail("%u not deleted by key from hash", i);
+			return;
+		}
+	}
+	pass("Deleted %u numbers by key from hash", i);
+}
+
+static bool check_mask(struct htable *ht, const struct obj val[], unsigned num)
+{
+	uint64_t i;
+
+	for (i = 0; i < num; i++) {
+		if (((uintptr_t)&val[i] & ht->common_mask) != ht->common_bits)
+			return false;
+	}
+	return true;
+}
+
+int main(void)
+{
+	unsigned int i;
+	struct htable_obj ht, ht2;
+	struct obj val[NUM_VALS], *result;
+	unsigned int dne;
+	void *p;
+	struct htable_obj_iter iter;
+
+	plan_tests(29);
+	for (i = 0; i < NUM_VALS; i++)
+		val[i].key = i;
+	dne = i;
+
+	htable_obj_init(&ht);
+	ok1(ht.raw.max == 0);
+	ok1(ht.raw.bits == 0);
+
+	/* We cannot find an entry which doesn't exist. */
+	ok1(!htable_obj_get(&ht, dne));
+
+	/* Fill it, it should increase in size. */
+	add_vals(&ht, val, NUM_VALS);
+	ok1(ht.raw.bits == NUM_BITS + 1);
+	ok1(ht.raw.max < (1 << ht.raw.bits));
+
+	/* Mask should be set. */
+	ok1(ht.raw.common_mask != 0);
+	ok1(ht.raw.common_mask != -1);
+	ok1(check_mask(&ht.raw, val, NUM_VALS));
+
+	/* Find all. */
+	find_vals(&ht, val, NUM_VALS);
+	ok1(!htable_obj_get(&ht, dne));
+
+	/* Walk once, should get them all. */
+	i = 0;
+	for (p = htable_obj_first(&ht,&iter); p; p = htable_obj_next(&ht, &iter))
+		i++;
+	ok1(i == NUM_VALS);
+	i = 0;
+	for (p = htable_obj_prev(&ht,&iter); p; p = htable_obj_prev(&ht, &iter))
+		i++;
+	ok1(i == NUM_VALS);
+
+	/* Delete all. */
+	del_vals(&ht, val, NUM_VALS);
+	ok1(!htable_obj_get(&ht, val[0].key));
+
+	/* Worst case, a "pointer" which doesn't have any matching bits. */
+	htable_add(&ht.raw, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
+	htable_obj_add(&ht, &val[NUM_VALS-1]);
+	ok1(ht.raw.common_mask == 0);
+	ok1(ht.raw.common_bits == 0);
+	/* Delete the bogus one before we trip over it. */
+	htable_del(&ht.raw, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
+
+	/* Add the rest. */
+	add_vals(&ht, val, NUM_VALS-1);
+
+	/* Check we can find them all. */
+	find_vals(&ht, val, NUM_VALS);
+	ok1(!htable_obj_get(&ht, dne));
+
+	/* Check copy. */
+	ok1(htable_obj_copy(&ht2, &ht));
+
+	/* Delete them all by key. */
+	del_vals_bykey(&ht, val, NUM_VALS);
+	del_vals_bykey(&ht2, val, NUM_VALS);
+
+	/* Write two of the same value. */
+	val[1] = val[0];
+	htable_obj_add(&ht, &val[0]);
+	htable_obj_add(&ht, &val[1]);
+	i = 0;
+
+	result = htable_obj_getfirst(&ht, i, &iter);
+	ok1(result == &val[0] || result == &val[1]);
+	if (result == &val[0]) {
+		ok1(htable_obj_getnext(&ht, i, &iter) == &val[1]);
+		ok1(htable_obj_getnext(&ht, i, &iter) == NULL);
+
+		/* Deleting first should make us iterate over the other. */
+		ok1(htable_obj_del(&ht, &val[0]));
+		ok1(htable_obj_getfirst(&ht, i, &iter) == &val[1]);
+		ok1(htable_obj_getnext(&ht, i, &iter) == NULL);
+	} else {
+		ok1(htable_obj_getnext(&ht, i, &iter) == &val[0]);
+		ok1(htable_obj_getnext(&ht, i, &iter) == NULL);
+
+		/* Deleting first should make us iterate over the other. */
+		ok1(htable_obj_del(&ht, &val[1]));
+		ok1(htable_obj_getfirst(&ht, i, &iter) == &val[0]);
+		ok1(htable_obj_getnext(&ht, i, &iter) == NULL);
+	}
+
+	htable_obj_clear(&ht);
+	htable_obj_clear(&ht2);
+	return exit_status();
+}
diff --git a/ccan/htable/test/run-type.c b/ccan/htable/test/run-type.c
new file mode 100644
index 0000000..a3616a5
--- /dev/null
+++ b/ccan/htable/test/run-type.c
@@ -0,0 +1,210 @@
+#include <ccan/htable/htable_type.h>
+#include <ccan/htable/htable.c>
+#include <ccan/tap/tap.h>
+#include <stdbool.h>
+#include <string.h>
+
+#define NUM_BITS 7
+#define NUM_VALS (1 << NUM_BITS)
+
+struct obj {
+	/* Makes sure we don't try to treat and obj as a key or vice versa */
+	unsigned char unused;
+	unsigned int key;
+};
+
+static const unsigned int *objkey(const struct obj *obj)
+{
+	return &obj->key;
+}
+
+/* We use the number divided by two as the hash (for lots of
+   collisions), plus set all the higher bits so we can detect if they
+   don't get masked out. */
+static size_t objhash(const unsigned int *key)
+{
+	size_t h = *key / 2;
+	h |= -1UL << NUM_BITS;
+	return h;
+}
+
+static bool cmp(const struct obj *obj, const unsigned int *key)
+{
+	return obj->key == *key;
+}
+
+HTABLE_DEFINE_TYPE(struct obj, objkey, objhash, cmp, htable_obj);
+
+static void add_vals(struct htable_obj *ht,
+		     struct obj val[], unsigned int num)
+{
+	unsigned int i;
+
+	for (i = 0; i < num; i++) {
+		if (htable_obj_get(ht, &i)) {
+			fail("%u already in hash", i);
+			return;
+		}
+		htable_obj_add(ht, &val[i]);
+		if (htable_obj_get(ht, &i) != &val[i]) {
+			fail("%u not added to hash", i);
+			return;
+		}
+	}
+	pass("Added %u numbers to hash", i);
+}
+
+static void find_vals(const struct htable_obj *ht,
+		      const struct obj val[], unsigned int num)
+{
+	unsigned int i;
+
+	for (i = 0; i < num; i++) {
+		if (htable_obj_get(ht, &i) != &val[i]) {
+			fail("%u not found in hash", i);
+			return;
+		}
+	}
+	pass("Found %u numbers in hash", i);
+}
+
+static void del_vals(struct htable_obj *ht,
+		     const struct obj val[], unsigned int num)
+{
+	unsigned int i;
+
+	for (i = 0; i < num; i++) {
+		if (!htable_obj_delkey(ht, &val[i].key)) {
+			fail("%u not deleted from hash", i);
+			return;
+		}
+	}
+	pass("Deleted %u numbers in hash", i);
+}
+
+static void del_vals_bykey(struct htable_obj *ht,
+			   const struct obj val[] UNNEEDED, unsigned int num)
+{
+	unsigned int i;
+
+	for (i = 0; i < num; i++) {
+		if (!htable_obj_delkey(ht, &i)) {
+			fail("%u not deleted by key from hash", i);
+			return;
+		}
+	}
+	pass("Deleted %u numbers by key from hash", i);
+}
+
+static bool check_mask(struct htable *ht, const struct obj val[], unsigned num)
+{
+	uint64_t i;
+
+	for (i = 0; i < num; i++) {
+		if (((uintptr_t)&val[i] & ht->common_mask) != ht->common_bits)
+			return false;
+	}
+	return true;
+}
+
+int main(void)
+{
+	unsigned int i;
+	struct htable_obj ht, ht2;
+	struct obj val[NUM_VALS], *result;
+	unsigned int dne;
+	void *p;
+	struct htable_obj_iter iter;
+
+	plan_tests(29);
+	for (i = 0; i < NUM_VALS; i++)
+		val[i].key = i;
+	dne = i;
+
+	htable_obj_init(&ht);
+	ok1(ht.raw.max == 0);
+	ok1(ht.raw.bits == 0);
+
+	/* We cannot find an entry which doesn't exist. */
+	ok1(!htable_obj_get(&ht, &dne));
+
+	/* Fill it, it should increase in size. */
+	add_vals(&ht, val, NUM_VALS);
+	ok1(ht.raw.bits == NUM_BITS + 1);
+	ok1(ht.raw.max < (1 << ht.raw.bits));
+
+	/* Mask should be set. */
+	ok1(ht.raw.common_mask != 0);
+	ok1(ht.raw.common_mask != -1);
+	ok1(check_mask(&ht.raw, val, NUM_VALS));
+
+	/* Find all. */
+	find_vals(&ht, val, NUM_VALS);
+	ok1(!htable_obj_get(&ht, &dne));
+
+	/* Walk once, should get them all. */
+	i = 0;
+	for (p = htable_obj_first(&ht,&iter); p; p = htable_obj_next(&ht, &iter))
+		i++;
+	ok1(i == NUM_VALS);
+	i = 0;
+	for (p = htable_obj_prev(&ht,&iter); p; p = htable_obj_prev(&ht, &iter))
+		i++;
+	ok1(i == NUM_VALS);
+
+	/* Delete all. */
+	del_vals(&ht, val, NUM_VALS);
+	ok1(!htable_obj_get(&ht, &val[0].key));
+
+	/* Worst case, a "pointer" which doesn't have any matching bits. */
+	htable_add(&ht.raw, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
+	htable_obj_add(&ht, &val[NUM_VALS-1]);
+	ok1(ht.raw.common_mask == 0);
+	ok1(ht.raw.common_bits == 0);
+	/* Delete the bogus one before we trip over it. */
+	htable_del(&ht.raw, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
+
+	/* Add the rest. */
+	add_vals(&ht, val, NUM_VALS-1);
+
+	/* Check we can find them all. */
+	find_vals(&ht, val, NUM_VALS);
+	ok1(!htable_obj_get(&ht, &dne));
+
+	/* Check copy. */
+	ok1(htable_obj_copy(&ht2, &ht));
+
+	/* Delete them all by key. */
+	del_vals_bykey(&ht, val, NUM_VALS);
+	del_vals_bykey(&ht2, val, NUM_VALS);
+
+	/* Write two of the same value. */
+	val[1] = val[0];
+	htable_obj_add(&ht, &val[0]);
+	htable_obj_add(&ht, &val[1]);
+	i = 0;
+
+	result = htable_obj_getfirst(&ht, &i, &iter);
+	ok1(result == &val[0] || result == &val[1]);
+	if (result == &val[0]) {
+		ok1(htable_obj_getnext(&ht, &i, &iter) == &val[1]);
+		ok1(htable_obj_getnext(&ht, &i, &iter) == NULL);
+
+		/* Deleting first should make us iterate over the other. */
+		ok1(htable_obj_del(&ht, &val[0]));
+		ok1(htable_obj_getfirst(&ht, &i, &iter) == &val[1]);
+		ok1(htable_obj_getnext(&ht, &i, &iter) == NULL);
+	} else {
+		ok1(htable_obj_getnext(&ht, &i, &iter) == &val[0]);
+		ok1(htable_obj_getnext(&ht, &i, &iter) == NULL);
+
+		/* Deleting first should make us iterate over the other. */
+		ok1(htable_obj_del(&ht, &val[1]));
+		ok1(htable_obj_getfirst(&ht, &i, &iter) == &val[0]);
+		ok1(htable_obj_getnext(&ht, &i, &iter) == NULL);
+	}
+
+	htable_obj_clear(&ht);
+	htable_obj_clear(&ht2);
+	return exit_status();
+}
diff --git a/ccan/htable/test/run-zero-hash-first-entry.c b/ccan/htable/test/run-zero-hash-first-entry.c
new file mode 100644
index 0000000..3a1a939
--- /dev/null
+++ b/ccan/htable/test/run-zero-hash-first-entry.c
@@ -0,0 +1,61 @@
+#include <ccan/htable/htable.h>
+#include <ccan/htable/htable.c>
+#include <ccan/tap/tap.h>
+#include <stdbool.h>
+
+struct data {
+	size_t key;
+};
+
+/* Hash is simply key itself. */
+static size_t hash(const void *e, void *unused UNNEEDED)
+{
+	struct data *d = (struct data *)e;
+
+	return d->key;
+}
+
+static bool eq(const void *e, void *k)
+{
+	struct data *d = (struct data *)e;
+	size_t *key = (size_t *)k;
+
+	return (d->key == *key);
+}
+
+int main(void)
+{
+	struct htable table;
+	struct data *d0, *d1;
+
+	plan_tests(6);
+
+	d1 = malloc(sizeof(struct data));
+	d1->key = 1;
+	d0 = malloc(sizeof(struct data));
+	d0->key = 0;
+
+	htable_init(&table, hash, NULL);
+
+	htable_add(&table, d0->key, d0);
+	htable_add(&table, d1->key, d1);
+
+	ok1(table.elems == 2);
+	ok1(htable_get(&table, 1, eq, &d1->key) == d1);
+	ok1(htable_get(&table, 0, eq, &d0->key) == d0);
+	htable_clear(&table);
+
+	/* Now add in reverse order, should still be OK. */
+	htable_add(&table, d1->key, d1);
+	htable_add(&table, d0->key, d0);
+
+	ok1(table.elems == 2);
+	ok1(htable_get(&table, 1, eq, &d1->key) == d1);
+	ok1(htable_get(&table, 0, eq, &d0->key) == d0);
+	htable_clear(&table);
+
+	free(d0);
+	free(d1);
+	return exit_status();
+}
+  
diff --git a/ccan/htable/test/run.c b/ccan/htable/test/run.c
new file mode 100644
index 0000000..46514c7
--- /dev/null
+++ b/ccan/htable/test/run.c
@@ -0,0 +1,212 @@
+#include <ccan/htable/htable.h>
+#include <ccan/htable/htable.c>
+#include <ccan/tap/tap.h>
+#include <stdbool.h>
+#include <string.h>
+
+#define NUM_BITS 7
+#define NUM_VALS (1 << NUM_BITS)
+
+/* We use the number divided by two as the hash (for lots of
+   collisions), plus set all the higher bits so we can detect if they
+   don't get masked out. */
+static size_t hash(const void *elem, void *unused UNNEEDED)
+{
+	size_t h = *(uint64_t *)elem / 2;
+	h |= -1UL << NUM_BITS;
+	return h;
+}
+
+static bool objcmp(const void *htelem, void *cmpdata)
+{
+	return *(uint64_t *)htelem == *(uint64_t *)cmpdata;
+}
+
+static void add_vals(struct htable *ht,
+		     const uint64_t val[],
+		     unsigned int off, unsigned int num)
+{
+	uint64_t i;
+
+	for (i = off; i < off+num; i++) {
+		if (htable_get(ht, hash(&i, NULL), objcmp, &i)) {
+			fail("%llu already in hash", (long long)i);
+			return;
+		}
+		htable_add(ht, hash(&val[i], NULL), &val[i]);
+		if (htable_get(ht, hash(&i, NULL), objcmp, &i) != &val[i]) {
+			fail("%llu not added to hash", (long long)i);
+			return;
+		}
+	}
+	pass("Added %llu numbers to hash", (long long)i);
+}
+
+#if 0
+static void refill_vals(struct htable *ht,
+			const uint64_t val[], unsigned int num)
+{
+	uint64_t i;
+
+	for (i = 0; i < num; i++) {
+		if (htable_get(ht, hash(&i, NULL), objcmp, &i))
+			continue;
+		htable_add(ht, hash(&val[i], NULL), &val[i]);
+	}
+}
+#endif
+
+static void find_vals(struct htable *ht,
+		      const uint64_t val[], unsigned int num)
+{
+	uint64_t i;
+
+	for (i = 0; i < num; i++) {
+		if (htable_get(ht, hash(&i, NULL), objcmp, &i) != &val[i]) {
+			fail("%llu not found in hash", (long long)i);
+			return;
+		}
+	}
+	pass("Found %llu numbers in hash", (long long)i);
+}
+
+static void del_vals(struct htable *ht,
+		     const uint64_t val[], unsigned int num)
+{
+	uint64_t i;
+
+	for (i = 0; i < num; i++) {
+		if (!htable_del(ht, hash(&val[i], NULL), &val[i])) {
+			fail("%llu not deleted from hash", (long long)i);
+			return;
+		}
+	}
+	pass("Deleted %llu numbers in hash", (long long)i);
+}
+
+static bool check_mask(struct htable *ht, uint64_t val[], unsigned num)
+{
+	uint64_t i;
+
+	for (i = 0; i < num; i++) {
+		if (((uintptr_t)&val[i] & ht->common_mask) != ht->common_bits)
+			return false;
+	}
+	return true;
+}
+
+int main(void)
+{
+	unsigned int i, weight;
+	uintptr_t perfect_bit;
+	struct htable ht;
+	uint64_t val[NUM_VALS];
+	uint64_t dne;
+	void *p;
+	struct htable_iter iter;
+
+	plan_tests(36);
+	for (i = 0; i < NUM_VALS; i++)
+		val[i] = i;
+	dne = i;
+
+	htable_init(&ht, hash, NULL);
+	ok1(ht.max == 0);
+	ok1(ht.bits == 0);
+
+	/* We cannot find an entry which doesn't exist. */
+	ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
+
+	/* This should increase it once. */
+	add_vals(&ht, val, 0, 1);
+	ok1(ht.bits == 1);
+	ok1(ht.max == 1);
+	weight = 0;
+	for (i = 0; i < sizeof(ht.common_mask) * CHAR_BIT; i++) {
+		if (ht.common_mask & ((uintptr_t)1 << i)) {
+			weight++;
+		}
+	}
+	/* Only one bit should be clear. */
+	ok1(weight == i-1);
+
+	/* Mask should be set. */
+	ok1(check_mask(&ht, val, 1));
+
+	/* This should increase it again. */
+	add_vals(&ht, val, 1, 1);
+	ok1(ht.bits == 2);
+	ok1(ht.max == 3);
+
+	/* Mask should be set. */
+	ok1(ht.common_mask != 0);
+	ok1(ht.common_mask != -1);
+	ok1(check_mask(&ht, val, 2));
+
+	/* Now do the rest. */
+	add_vals(&ht, val, 2, NUM_VALS - 2);
+
+	/* Find all. */
+	find_vals(&ht, val, NUM_VALS);
+	ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
+
+	/* Walk once, should get them all. */
+	i = 0;
+	for (p = htable_first(&ht,&iter); p; p = htable_next(&ht, &iter))
+		i++;
+	ok1(i == NUM_VALS);
+
+	i = 0;
+	for (p = htable_prev(&ht, &iter); p; p = htable_prev(&ht, &iter))
+		i++;
+	ok1(i == NUM_VALS);
+
+	/* Delete all. */
+	del_vals(&ht, val, NUM_VALS);
+	ok1(!htable_get(&ht, hash(&val[0], NULL), objcmp, &val[0]));
+
+	/* Worst case, a "pointer" which doesn't have any matching bits. */
+	htable_add(&ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
+	htable_add(&ht, hash(&val[NUM_VALS-1], NULL), &val[NUM_VALS-1]);
+	ok1(ht.common_mask == 0);
+	ok1(ht.common_bits == 0);
+	/* Get rid of bogus pointer before we trip over it! */
+	htable_del(&ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
+
+	/* Add the rest. */
+	add_vals(&ht, val, 0, NUM_VALS-1);
+
+	/* Check we can find them all. */
+	find_vals(&ht, val, NUM_VALS);
+	ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
+
+	/* Corner cases: wipe out the perfect bit using bogus pointer. */
+	htable_clear(&ht);
+	htable_add(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]));
+	ok1(ht.perfect_bit);
+	perfect_bit = ht.perfect_bit;
+	htable_add(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]
+				   | perfect_bit));
+	ok1(ht.perfect_bit == 0);
+	htable_del(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1] | perfect_bit));
+
+	/* Enlarging should restore it... */
+	add_vals(&ht, val, 0, NUM_VALS-1);
+
+	ok1(ht.perfect_bit != 0);
+	htable_clear(&ht);
+
+	ok1(htable_init_sized(&ht, hash, NULL, 1024));
+	ok1(ht.max >= 1024);
+	htable_clear(&ht);
+
+	ok1(htable_init_sized(&ht, hash, NULL, 1023));
+	ok1(ht.max >= 1023);
+	htable_clear(&ht);
+
+	ok1(htable_init_sized(&ht, hash, NULL, 1025));
+	ok1(ht.max >= 1025);
+	htable_clear(&ht);
+	
+	return exit_status();
+}
diff --git a/ccan/htable/tools/Makefile b/ccan/htable/tools/Makefile
new file mode 100644
index 0000000..a2cad59
--- /dev/null
+++ b/ccan/htable/tools/Makefile
@@ -0,0 +1,40 @@
+CCANDIR=../../..
+CFLAGS=-Wall -Werror -O3 -I$(CCANDIR)
+#CFLAGS=-Wall -Werror -g -I$(CCANDIR)
+
+CCAN_OBJS:=ccan-tal.o ccan-tal-str.o ccan-tal-grab_file.o ccan-take.o ccan-time.o ccan-str.o ccan-noerr.o ccan-list.o
+
+all: speed stringspeed hsearchspeed
+
+speed: speed.o hash.o $(CCAN_OBJS)
+
+speed.o: speed.c ../htable.h ../htable.c
+
+hash.o: ../../hash/hash.c
+	$(CC) $(CFLAGS) -c -o $@ $<
+
+stringspeed: stringspeed.o hash.o $(CCAN_OBJS)
+
+stringspeed.o: speed.c ../htable.h ../htable.c
+
+hsearchspeed: hsearchspeed.o $(CCAN_OBJS)
+
+clean:
+	rm -f stringspeed speed hsearchspeed *.o
+
+ccan-tal.o: $(CCANDIR)/ccan/tal/tal.c
+	$(CC) $(CFLAGS) -c -o $@ $<
+ccan-tal-str.o: $(CCANDIR)/ccan/tal/str/str.c
+	$(CC) $(CFLAGS) -c -o $@ $<
+ccan-take.o: $(CCANDIR)/ccan/take/take.c
+	$(CC) $(CFLAGS) -c -o $@ $<
+ccan-tal-grab_file.o: $(CCANDIR)/ccan/tal/grab_file/grab_file.c
+	$(CC) $(CFLAGS) -c -o $@ $<
+ccan-time.o: $(CCANDIR)/ccan/time/time.c
+	$(CC) $(CFLAGS) -c -o $@ $<
+ccan-list.o: $(CCANDIR)/ccan/list/list.c
+	$(CC) $(CFLAGS) -c -o $@ $<
+ccan-str.o: $(CCANDIR)/ccan/str/str.c
+	$(CC) $(CFLAGS) -c -o $@ $<
+ccan-noerr.o: $(CCANDIR)/ccan/noerr/noerr.c
+	$(CC) $(CFLAGS) -c -o $@ $<
diff --git a/ccan/htable/tools/hsearchspeed.c b/ccan/htable/tools/hsearchspeed.c
new file mode 100644
index 0000000..8828011
--- /dev/null
+++ b/ccan/htable/tools/hsearchspeed.c
@@ -0,0 +1,95 @@
+/* Simple speed tests for a hash of strings using hsearch */
+#include <ccan/htable/htable_type.h>
+#include <ccan/htable/htable.c>
+#include <ccan/tal/str/str.h>
+#include <ccan/tal/grab_file/grab_file.h>
+#include <ccan/tal/tal.h>
+#include <ccan/hash/hash.h>
+#include <ccan/time/time.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+#include <unistd.h>
+#include <sys/time.h>
+#include <search.h>
+
+/* Nanoseconds per operation */
+static size_t normalize(const struct timeabs *start,
+			const struct timeabs *stop,
+			unsigned int num)
+{
+	return time_to_nsec(time_divide(time_between(*stop, *start), num));
+}
+
+int main(int argc, char *argv[])
+{
+	size_t i, j, num;
+	struct timeabs start, stop;
+	char **w;
+	ENTRY *words, *misswords;
+
+	w = tal_strsplit(NULL, grab_file(NULL,
+					 argv[1] ? argv[1] : "/usr/share/dict/words"), "\n", STR_NO_EMPTY);
+	num = tal_count(w) - 1;
+	printf("%zu words\n", num);
+
+	hcreate(num+num/3);
+
+	words = tal_arr(w, ENTRY, num);
+	for (i = 0; i < num; i++) {
+		words[i].key = w[i];
+		words[i].data = words[i].key;
+	}
+
+	/* Append and prepend last char for miss testing. */
+	misswords = tal_arr(w, ENTRY, num);
+	for (i = 0; i < num; i++) {
+		char lastc;
+		if (strlen(w[i]))
+			lastc = w[i][strlen(w[i])-1];
+		else
+			lastc = 'z';
+		misswords[i].key = tal_fmt(misswords, "%c%s%c%c",
+					   lastc, w[i], lastc, lastc);
+	}
+
+	printf("#01: Initial insert: ");
+	fflush(stdout);
+	start = time_now();
+	for (i = 0; i < num; i++)
+		hsearch(words[i], ENTER);
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	printf("#02: Initial lookup (match): ");
+	fflush(stdout);
+	start = time_now();
+	for (i = 0; i < num; i++)
+		if (hsearch(words[i], FIND)->data != words[i].data)
+			abort();
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	printf("#03: Initial lookup (miss): ");
+	fflush(stdout);
+	start = time_now();
+	for (i = 0; i < num; i++) {
+		if (hsearch(misswords[i], FIND))
+			abort();
+	}
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	/* Lookups in order are very cache-friendly for judy; try random */
+	printf("#04: Initial lookup (random): ");
+	fflush(stdout);
+	start = time_now();
+	for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
+		if (hsearch(words[i], FIND)->data != words[i].data)
+			abort();
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	return 0;
+}
diff --git a/ccan/htable/tools/speed.c b/ccan/htable/tools/speed.c
new file mode 100644
index 0000000..dce3fdf
--- /dev/null
+++ b/ccan/htable/tools/speed.c
@@ -0,0 +1,370 @@
+/* Simple speed tests for hashtables. */
+#include <ccan/htable/htable_type.h>
+#include <ccan/htable/htable.c>
+#include <ccan/hash/hash.h>
+#include <ccan/time/time.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+static size_t hashcount;
+struct object {
+	/* The key. */
+	unsigned int key;
+
+	/* Some contents. Doubles as consistency check. */
+	struct object *self;
+};
+
+static const unsigned int *objkey(const struct object *obj)
+{
+	return &obj->key;
+}
+
+static size_t hash_obj(const unsigned int *key)
+{
+	hashcount++;
+	return hashl(key, 1, 0);
+}
+
+static bool cmp(const struct object *object, const unsigned int *key)
+{
+	return object->key == *key;
+}
+
+HTABLE_DEFINE_TYPE(struct object, objkey, hash_obj, cmp, htable_obj);
+
+static unsigned int popcount(unsigned long val)
+{
+#if HAVE_BUILTIN_POPCOUNTL
+	return __builtin_popcountl(val);
+#else
+	if (sizeof(long) == sizeof(u64)) {
+		u64 v = val;
+		v = (v & 0x5555555555555555ULL)
+			+ ((v >> 1) & 0x5555555555555555ULL);
+		v = (v & 0x3333333333333333ULL)
+			+ ((v >> 1) & 0x3333333333333333ULL);
+		v = (v & 0x0F0F0F0F0F0F0F0FULL)
+			+ ((v >> 1) & 0x0F0F0F0F0F0F0F0FULL);
+		v = (v & 0x00FF00FF00FF00FFULL)
+			+ ((v >> 1) & 0x00FF00FF00FF00FFULL);
+		v = (v & 0x0000FFFF0000FFFFULL)
+			+ ((v >> 1) & 0x0000FFFF0000FFFFULL);
+		v = (v & 0x00000000FFFFFFFFULL)
+			+ ((v >> 1) & 0x00000000FFFFFFFFULL);
+		return v;
+	}
+	val = (val & 0x55555555ULL) + ((val >> 1) & 0x55555555ULL);
+	val = (val & 0x33333333ULL) + ((val >> 1) & 0x33333333ULL);
+	val = (val & 0x0F0F0F0FULL) + ((val >> 1) & 0x0F0F0F0FULL);
+	val = (val & 0x00FF00FFULL) + ((val >> 1) & 0x00FF00FFULL);
+	val = (val & 0x0000FFFFULL) + ((val >> 1) & 0x0000FFFFULL);
+	return val;
+#endif
+}
+
+static size_t perfect(const struct htable *ht)
+{
+	size_t i, placed_perfect = 0;
+
+	for (i = 0; i < ((size_t)1 << ht->bits); i++) {
+		if (!entry_is_valid(ht->table[i]))
+			continue;
+		if (hash_bucket(ht, ht->rehash(get_raw_ptr(ht, ht->table[i]),
+					       ht->priv)) == i) {
+			assert((ht->table[i] & ht->perfect_bit)
+			       == ht->perfect_bit);
+			placed_perfect++;
+		}
+	}
+	return placed_perfect;
+}
+
+static size_t count_deleted(const struct htable *ht)
+{
+	size_t i, delete_markers = 0;
+
+	for (i = 0; i < ((size_t)1 << ht->bits); i++) {
+		if (ht->table[i] == HTABLE_DELETED)
+			delete_markers++;
+	}
+	return delete_markers;
+}
+
+/* Nanoseconds per operation */
+static size_t normalize(const struct timeabs *start,
+			const struct timeabs *stop,
+			unsigned int num)
+{
+	return time_to_nsec(time_divide(time_between(*stop, *start), num));
+}
+
+static size_t worst_run(struct htable *ht, size_t *deleted)
+{
+	size_t longest = 0, len = 0, this_del = 0, i;
+
+	*deleted = 0;
+	/* This doesn't take into account end-wrap, but gives an idea. */
+	for (i = 0; i < ((size_t)1 << ht->bits); i++) {
+		if (ht->table[i]) {
+			len++;
+			if (ht->table[i] == HTABLE_DELETED)
+				this_del++;
+		} else {
+			if (len > longest) {
+				longest = len;
+				*deleted = this_del;
+			}
+			len = 0;
+			this_del = 0;
+		}
+	}
+	return longest;
+}
+
+int main(int argc, char *argv[])
+{
+	struct object *objs;
+	unsigned int i, j;
+	size_t num, deleted;
+	struct timeabs start, stop;
+	struct htable_obj ht;
+	bool make_dumb = false;
+
+	if (argv[1] && strcmp(argv[1], "--dumb") == 0) {
+		argv++;
+		make_dumb = true;
+	}
+	num = argv[1] ? atoi(argv[1]) : 1000000;
+	objs = calloc(num, sizeof(objs[0]));
+
+	for (i = 0; i < num; i++) {
+		objs[i].key = i;
+		objs[i].self = &objs[i];
+	}
+
+	htable_obj_init(&ht);
+
+	printf("Initial insert: ");
+	fflush(stdout);
+	start = time_now();
+	for (i = 0; i < num; i++)
+		htable_obj_add(&ht, objs[i].self);
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+	printf("Details: hash size %u, mask bits %u, perfect %.0f%%\n",
+	       1U << ht.raw.bits, popcount(ht.raw.common_mask),
+	       perfect(&ht.raw) * 100.0 / ht.raw.elems);
+
+	if (make_dumb) {
+		/* Screw with mask, to hobble us. */
+		update_common(&ht.raw, (void *)~ht.raw.common_bits);
+		printf("Details: DUMB MODE: mask bits %u\n",
+		       popcount(ht.raw.common_mask));
+	}
+
+	printf("Initial lookup (match): ");
+	fflush(stdout);
+	start = time_now();
+	for (i = 0; i < num; i++)
+		if (htable_obj_get(&ht, &i)->self != objs[i].self)
+			abort();
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	printf("Initial lookup (miss): ");
+	fflush(stdout);
+	start = time_now();
+	for (i = 0; i < num; i++) {
+		unsigned int n = i + num;
+		if (htable_obj_get(&ht, &n))
+			abort();
+	}
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	/* Lookups in order are very cache-friendly for judy; try random */
+	printf("Initial lookup (random): ");
+	fflush(stdout);
+	start = time_now();
+	for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
+		if (htable_obj_get(&ht, &j)->self != &objs[j])
+			abort();
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	hashcount = 0;
+	printf("Initial delete all: ");
+	fflush(stdout);
+	start = time_now();
+	for (i = 0; i < num; i++)
+		if (!htable_obj_del(&ht, objs[i].self))
+			abort();
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+	printf("Details: rehashes %zu\n", hashcount);
+
+	printf("Initial re-inserting: ");
+	fflush(stdout);
+	start = time_now();
+	for (i = 0; i < num; i++)
+		htable_obj_add(&ht, objs[i].self);
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	hashcount = 0;
+	printf("Deleting first half: ");
+	fflush(stdout);
+	start = time_now();
+	for (i = 0; i < num; i+=2)
+		if (!htable_obj_del(&ht, objs[i].self))
+			abort();
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	printf("Details: rehashes %zu, delete markers %zu\n",
+	       hashcount, count_deleted(&ht.raw));
+
+	printf("Adding (a different) half: ");
+	fflush(stdout);
+
+	for (i = 0; i < num; i+=2)
+		objs[i].key = num+i;
+
+	start = time_now();
+	for (i = 0; i < num; i+=2)
+		htable_obj_add(&ht, objs[i].self);
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	printf("Details: delete markers %zu, perfect %.0f%%\n",
+	       count_deleted(&ht.raw), perfect(&ht.raw) * 100.0 / ht.raw.elems);
+
+	printf("Lookup after half-change (match): ");
+	fflush(stdout);
+	start = time_now();
+	for (i = 1; i < num; i+=2)
+		if (htable_obj_get(&ht, &i)->self != objs[i].self)
+			abort();
+	for (i = 0; i < num; i+=2) {
+		unsigned int n = i + num;
+		if (htable_obj_get(&ht, &n)->self != objs[i].self)
+			abort();
+	}
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	printf("Lookup after half-change (miss): ");
+	fflush(stdout);
+	start = time_now();
+	for (i = 0; i < num; i++) {
+		unsigned int n = i + num * 2;
+		if (htable_obj_get(&ht, &n))
+			abort();
+	}
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	/* Hashtables with delete markers can fill with markers over time.
+	 * so do some changes to see how it operates in long-term. */
+	for (i = 0; i < 5; i++) {
+		if (i == 0) {
+			/* We don't measure this: jmap is different. */
+			printf("Details: initial churn\n");
+		} else {
+			printf("Churning %s time: ",
+			       i == 1 ? "second"
+			       : i == 2 ? "third"
+			       : i == 3 ? "fourth"
+			       : "fifth");
+			fflush(stdout);
+		}
+		start = time_now();
+		for (j = 0; j < num; j++) {
+			if (!htable_obj_del(&ht, &objs[j]))
+				abort();
+			objs[j].key = num*i+j;
+			if (!htable_obj_add(&ht, &objs[j]))
+				abort();
+		}
+		stop = time_now();
+		if (i != 0)
+			printf(" %zu ns\n", normalize(&start, &stop, num));
+	}
+
+	/* Spread out the keys more to try to make it harder. */
+	printf("Details: reinserting with spread\n");
+	for (i = 0; i < num; i++) {
+		if (!htable_obj_del(&ht, objs[i].self))
+			abort();
+		objs[i].key = num * 5 + i * 9;
+		if (!htable_obj_add(&ht, objs[i].self))
+			abort();
+	}
+	printf("Details: delete markers %zu, perfect %.0f%%\n",
+	       count_deleted(&ht.raw), perfect(&ht.raw) * 100.0 / ht.raw.elems);
+	i = worst_run(&ht.raw, &deleted);
+	printf("Details: worst run %u (%zu deleted)\n", i, deleted);
+
+	printf("Lookup after churn & spread (match): ");
+	fflush(stdout);
+	start = time_now();
+	for (i = 0; i < num; i++) {
+		unsigned int n = num * 5 + i * 9;
+		if (htable_obj_get(&ht, &n)->self != objs[i].self)
+			abort();
+	}
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	printf("Lookup after churn & spread (miss): ");
+	fflush(stdout);
+	start = time_now();
+	for (i = 0; i < num; i++) {
+		unsigned int n = num * (5 + 9) + i * 9;
+		if (htable_obj_get(&ht, &n))
+			abort();
+	}
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	printf("Lookup after churn & spread (random): ");
+	fflush(stdout);
+	start = time_now();
+	for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num) {
+		unsigned int n = num * 5 + j * 9;
+		if (htable_obj_get(&ht, &n)->self != &objs[j])
+			abort();
+	}
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	hashcount = 0;
+	printf("Deleting half after churn & spread: ");
+	fflush(stdout);
+	start = time_now();
+	for (i = 0; i < num; i+=2)
+		if (!htable_obj_del(&ht, objs[i].self))
+			abort();
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	printf("Adding (a different) half after churn & spread: ");
+	fflush(stdout);
+
+	for (i = 0; i < num; i+=2)
+		objs[i].key = num*6+i*9;
+
+	start = time_now();
+	for (i = 0; i < num; i+=2)
+		htable_obj_add(&ht, objs[i].self);
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	printf("Details: delete markers %zu, perfect %.0f%%\n",
+	       count_deleted(&ht.raw), perfect(&ht.raw) * 100.0 / ht.raw.elems);
+
+	return 0;
+}
diff --git a/ccan/htable/tools/stringspeed.c b/ccan/htable/tools/stringspeed.c
new file mode 100644
index 0000000..c6ca10f
--- /dev/null
+++ b/ccan/htable/tools/stringspeed.c
@@ -0,0 +1,240 @@
+/* Simple speed tests for a hash of strings. */
+#include <ccan/htable/htable_type.h>
+#include <ccan/htable/htable.c>
+#include <ccan/tal/str/str.h>
+#include <ccan/tal/grab_file/grab_file.h>
+#include <ccan/tal/tal.h>
+#include <ccan/hash/hash.h>
+#include <ccan/time/time.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+#include <unistd.h>
+#include <sys/time.h>
+
+static size_t hashcount;
+
+static const char *strkey(const char *str)
+{
+	return str;
+}
+
+static size_t hash_str(const char *key)
+{
+	hashcount++;
+	return hash(key, strlen(key), 0);
+}
+
+static bool cmp(const char *obj, const char *key)
+{
+	return strcmp(obj, key) == 0;
+}
+
+HTABLE_DEFINE_TYPE(char, strkey, hash_str, cmp, htable_str);
+
+/* Nanoseconds per operation */
+static size_t normalize(const struct timeabs *start,
+			const struct timeabs *stop,
+			unsigned int num)
+{
+	return time_to_nsec(time_divide(time_between(*stop, *start), num));
+}
+
+int main(int argc, char *argv[])
+{
+	size_t i, j, num;
+	struct timeabs start, stop;
+	struct htable_str ht;
+	char **words, **misswords;
+
+	words = tal_strsplit(NULL, grab_file(NULL,
+					     argv[1] ? argv[1] : "/usr/share/dict/words"), "\n",
+			     STR_NO_EMPTY);
+	htable_str_init(&ht);
+	num = tal_count(words) - 1;
+	/* Note that on my system, num is just > 98304, where we double! */
+	printf("%zu words\n", num);
+
+	/* Append and prepend last char for miss testing. */
+	misswords = tal_arr(words, char *, num);
+	for (i = 0; i < num; i++) {
+		char lastc;
+		if (strlen(words[i]))
+			lastc = words[i][strlen(words[i])-1];
+		else
+			lastc = 'z';
+		misswords[i] = tal_fmt(misswords, "%c%s%c%c",
+				       lastc, words[i], lastc, lastc);
+	}
+
+	printf("#01: Initial insert: ");
+	fflush(stdout);
+	start = time_now();
+	for (i = 0; i < num; i++)
+		htable_str_add(&ht, words[i]);
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	printf("Bytes allocated: %zu\n",
+	       sizeof(ht.raw.table[0]) << ht.raw.bits);
+
+	printf("#02: Initial lookup (match): ");
+	fflush(stdout);
+	start = time_now();
+	for (i = 0; i < num; i++)
+		if (htable_str_get(&ht, words[i]) != words[i])
+			abort();
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	printf("#03: Initial lookup (miss): ");
+	fflush(stdout);
+	start = time_now();
+	for (i = 0; i < num; i++) {
+		if (htable_str_get(&ht, misswords[i]))
+			abort();
+	}
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	/* Lookups in order are very cache-friendly for judy; try random */
+	printf("#04: Initial lookup (random): ");
+	fflush(stdout);
+	start = time_now();
+	for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
+		if (htable_str_get(&ht, words[j]) != words[j])
+			abort();
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	hashcount = 0;
+	printf("#05: Initial delete all: ");
+	fflush(stdout);
+	start = time_now();
+	for (i = 0; i < num; i++)
+		if (!htable_str_del(&ht, words[i]))
+			abort();
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	printf("#06: Initial re-inserting: ");
+	fflush(stdout);
+	start = time_now();
+	for (i = 0; i < num; i++)
+		htable_str_add(&ht, words[i]);
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	hashcount = 0;
+	printf("#07: Deleting first half: ");
+	fflush(stdout);
+	start = time_now();
+	for (i = 0; i < num; i+=2)
+		if (!htable_str_del(&ht, words[i]))
+			abort();
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	printf("#08: Adding (a different) half: ");
+	fflush(stdout);
+
+	start = time_now();
+	for (i = 0; i < num; i+=2)
+		htable_str_add(&ht, misswords[i]);
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	printf("#09: Lookup after half-change (match): ");
+	fflush(stdout);
+	start = time_now();
+	for (i = 1; i < num; i+=2)
+		if (htable_str_get(&ht, words[i]) != words[i])
+			abort();
+	for (i = 0; i < num; i+=2) {
+		if (htable_str_get(&ht, misswords[i]) != misswords[i])
+			abort();
+	}
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	printf("#10: Lookup after half-change (miss): ");
+	fflush(stdout);
+	start = time_now();
+	for (i = 0; i < num; i+=2)
+		if (htable_str_get(&ht, words[i]))
+			abort();
+	for (i = 1; i < num; i+=2) {
+		if (htable_str_get(&ht, misswords[i]))
+			abort();
+	}
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	/* Hashtables with delete markers can fill with markers over time.
+	 * so do some changes to see how it operates in long-term. */
+	printf("#11: Churn 1: ");
+	start = time_now();
+	for (j = 0; j < num; j+=2) {
+		if (!htable_str_del(&ht, misswords[j]))
+			abort();
+		if (!htable_str_add(&ht, words[j]))
+			abort();
+	}
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	printf("#12: Churn 2: ");
+	start = time_now();
+	for (j = 1; j < num; j+=2) {
+		if (!htable_str_del(&ht, words[j]))
+			abort();
+		if (!htable_str_add(&ht, misswords[j]))
+			abort();
+	}
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	printf("#13: Churn 3: ");
+	start = time_now();
+	for (j = 1; j < num; j+=2) {
+		if (!htable_str_del(&ht, misswords[j]))
+			abort();
+		if (!htable_str_add(&ht, words[j]))
+			abort();
+	}
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	/* Now it's back to normal... */
+	printf("#14: Post-Churn lookup (match): ");
+	fflush(stdout);
+	start = time_now();
+	for (i = 0; i < num; i++)
+		if (htable_str_get(&ht, words[i]) != words[i])
+			abort();
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	printf("#15: Post-Churn lookup (miss): ");
+	fflush(stdout);
+	start = time_now();
+	for (i = 0; i < num; i++) {
+		if (htable_str_get(&ht, misswords[i]))
+			abort();
+	}
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	/* Lookups in order are very cache-friendly for judy; try random */
+	printf("#16: Post-Churn lookup (random): ");
+	fflush(stdout);
+	start = time_now();
+	for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
+		if (htable_str_get(&ht, words[j]) != words[j])
+			abort();
+	stop = time_now();
+	printf(" %zu ns\n", normalize(&start, &stop, num));
+
+	return 0;
+}