From 64b0c5cdeea5bc00ce3b9ef89fd3aade9cb0cd2c Mon Sep 17 00:00:00 2001
From: Rusty Russell <rusty@rustcorp.com.au>
Date: Tue, 12 May 2015 15:22:29 -0700
Subject: [PATCH] htable: add pre-sized option.

I thought this was slowing down my program; it turned out they were
all hashing to the same value.  But it might be useful.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
---
 ccan/htable/htable.c      | 23 +++++++++++++++++++++++
 ccan/htable/htable.h      | 15 +++++++++++++++
 ccan/htable/htable_type.h |  5 +++++
 ccan/htable/test/run.c    | 14 +++++++++++++-
 4 files changed, 56 insertions(+), 1 deletion(-)

diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c
index b7e65d11..59048dc0 100644
--- a/ccan/htable/htable.c
+++ b/ccan/htable/htable.c
@@ -52,6 +52,29 @@ void htable_init(struct htable *ht,
 	ht->table = &ht->perfect_bit;
 }
 
+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;
+	}
+	ht->max = ((size_t)3 << ht->bits) / 4;
+	ht->max_with_deleted = ((size_t)9 << ht->bits) / 10;
+
+	return true;
+}
+	
 void htable_clear(struct htable *ht)
 {
 	if (ht->table != &ht->perfect_bit)
diff --git a/ccan/htable/htable.h b/ccan/htable/htable.h
index ed668e74..03193567 100644
--- a/ccan/htable/htable.h
+++ b/ccan/htable/htable.h
@@ -51,6 +51,21 @@ struct htable {
 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
diff --git a/ccan/htable/htable_type.h b/ccan/htable/htable_type.h
index 03cc46fc..ad3974c5 100644
--- a/ccan/htable/htable_type.h
+++ b/ccan/htable/htable_type.h
@@ -20,6 +20,7 @@
  *
  * It also defines initialization and freeing functions:
  *	void <name>_init(struct <name> *);
+ *	void <name>_init_sized(struct <name> *, size_t);
  *	void <name>_clear(struct <name> *);
  *
  * Add function only fails if we run out of memory:
@@ -53,6 +54,10 @@
 	{								\
 		htable_init(&ht->raw, name##_hash, NULL);		\
 	}								\
+	static inline void name##_init_sized(struct name *ht, size_t s)	\
+	{								\
+		htable_init_sized(&ht->raw, name##_hash, NULL, s);	\
+	}								\
 	static inline void name##_clear(struct name *ht)		\
 	{								\
 		htable_clear(&ht->raw);					\
diff --git a/ccan/htable/test/run.c b/ccan/htable/test/run.c
index 7fc05e24..c5272c15 100644
--- a/ccan/htable/test/run.c
+++ b/ccan/htable/test/run.c
@@ -105,7 +105,7 @@ int main(int argc, char *argv[])
 	void *p;
 	struct htable_iter iter;
 
-	plan_tests(29);
+	plan_tests(35);
 	for (i = 0; i < NUM_VALS; i++)
 		val[i] = i;
 	dne = i;
@@ -191,5 +191,17 @@ int main(int argc, char *argv[])
 	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();
 }
-- 
2.39.2