From cbfcfe53cb6184d76d2343b224409ee67841f458 Mon Sep 17 00:00:00 2001
From: Rusty Russell <rusty@rustcorp.com.au>
Date: Mon, 30 Aug 2010 14:59:34 +0930
Subject: [PATCH] tdb2: fixes and test for hash enlargement.

---
 ccan/tdb2/tdb.c                   | 14 +++++---
 ccan/tdb2/test/run-enlarge_hash.c | 54 ++++++++++++++++++++++++++-----
 2 files changed, 56 insertions(+), 12 deletions(-)

diff --git a/ccan/tdb2/tdb.c b/ccan/tdb2/tdb.c
index 915b4c76..d19ceda2 100644
--- a/ccan/tdb2/tdb.c
+++ b/ccan/tdb2/tdb.c
@@ -599,12 +599,18 @@ static void enlarge_hash(struct tdb_context *tdb)
 				 "find_bucket_and_lock: zero hash bucket!\n");
 			goto unlock;
 		}
-		h = hash_record(tdb, off);
+
+		/* Find next empty hash slot. */
+		for (h = hash_record(tdb, off);
+		     tdb_read_off(tdb, newoff + (h & ((num * 2)-1))
+				  * sizeof(tdb_off_t)) != 0;
+		     h++);
+
 		/* FIXME: Encode extra hash bits! */
-		if (tdb_write_off(tdb, newoff
-				  + (h & ((num * 2) - 1)) * sizeof(uint64_t),
-				  off) == -1)
+		if (tdb_write_off(tdb, newoff + (h & ((num * 2)-1))
+				  * sizeof(tdb_off_t), off) == -1)
 			goto unlock;
+		i++;
 	}
 
 	/* Free up old hash. */
diff --git a/ccan/tdb2/test/run-enlarge_hash.c b/ccan/tdb2/test/run-enlarge_hash.c
index 9a22820f..ca8d3b95 100644
--- a/ccan/tdb2/test/run-enlarge_hash.c
+++ b/ccan/tdb2/test/run-enlarge_hash.c
@@ -6,24 +6,62 @@
 #include <ccan/tap/tap.h>
 #include "logging.h"
 
+/* We rig the hash so adjacent-numbered records always clash. */
+static uint64_t clash(const void *key, size_t len, uint64_t seed, void *priv)
+{
+	return *(unsigned int *)key / 2;
+}
+
 int main(int argc, char *argv[])
 {
 	unsigned int i;
 	struct tdb_context *tdb;
+	unsigned int v;
+	struct tdb_data key = { (unsigned char *)&v, sizeof(v) };
+	struct tdb_data data = { (unsigned char *)&v, sizeof(v) };
+	union tdb_attribute hattr = { .hash = { .base = { TDB_ATTRIBUTE_HASH },
+						.hash_fn = clash } };
 	int flags[] = { TDB_INTERNAL, TDB_DEFAULT,
 			TDB_INTERNAL|TDB_CONVERT, TDB_CONVERT };
 
-	plan_tests(sizeof(flags) / sizeof(flags[0]) * 2 + 1);
+	hattr.base.next = &tap_log_attr;
+
+	plan_tests(sizeof(flags) / sizeof(flags[0]) * 11 + 1);
 	for (i = 0; i < sizeof(flags) / sizeof(flags[0]); i++) {
 		tdb = tdb_open("run-enlarge-hash.tdb", flags[i],
-			       O_RDWR|O_CREAT|O_TRUNC, 0600, &tap_log_attr);
+			       O_RDWR|O_CREAT|O_TRUNC, 0600, &hattr);
 		ok1(tdb);
-		if (tdb) {
-			enlarge_hash(tdb);
-			ok1(tdb_check(tdb, NULL, NULL) == 0);
-			tdb_close(tdb);
-		}
-		/* FIXME: Test enlarging with hash clash. */
+		if (!tdb)
+			continue;
+
+		/* Put a single entry in. */
+		v = 0;
+		ok1(tdb_store(tdb, key, data, TDB_INSERT) == 0);
+		enlarge_hash(tdb);
+		ok1(tdb_check(tdb, NULL, NULL) == 0);
+
+		/* Put a non-clashing entry in. */
+		v = 2;
+		ok1(tdb_store(tdb, key, data, TDB_INSERT) == 0);
+		enlarge_hash(tdb);
+		ok1(tdb_check(tdb, NULL, NULL) == 0);
+
+		/* Now, make a clash. */
+		v = 1;
+		ok1(tdb_store(tdb, key, data, TDB_INSERT) == 0);
+		enlarge_hash(tdb);
+		ok1(tdb_check(tdb, NULL, NULL) == 0);
+
+		/* Clash at end. */
+		v = ((1 << tdb->header.v.hash_bits) - 1) * 2;
+		ok1(tdb_store(tdb, key, data, TDB_INSERT) == 0);
+		v++;
+		ok1(tdb_store(tdb, key, data, TDB_INSERT) == 0);
+		ok1(tdb_check(tdb, NULL, NULL) == 0);
+		enlarge_hash(tdb);
+		ok1(tdb_check(tdb, NULL, NULL) == 0);
+
+		tdb_close(tdb);
 	}
 	ok1(tap_log_messages == 0);
 	return exit_status();
-- 
2.39.2