From: Rusty Russell <rusty@rustcorp.com.au>
Date: Fri, 9 Mar 2012 02:50:35 +0000 (+1030)
Subject: htable: fix bug where first entry has hash of 0 or 1.
X-Git-Url: http://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=0b93bd102aad6b61f1e569fb12aabc6352a1d7cd

htable: fix bug where first entry has hash of 0 or 1.

Thanks to Zoltán Lajos Kis for the bug report and test case!
---

diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c
index 0a01ead8..b7e65d11 100644
--- a/ccan/htable/htable.c
+++ b/ccan/htable/htable.c
@@ -197,8 +197,17 @@ static COLD void update_common(struct htable *ht, const void *p)
 	uintptr_t maskdiff, bitsdiff;
 
 	if (ht->elems == 0) {
-		ht->common_mask = -1;
-		ht->common_bits = (uintptr_t)p;
+		/* 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;
 	}
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 00000000..fdd18569
--- /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)
+{
+	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
index 1a9e2de4..7fc05e24 100644
--- a/ccan/htable/test/run.c
+++ b/ccan/htable/test/run.c
@@ -97,7 +97,7 @@ static bool check_mask(struct htable *ht, uint64_t val[], unsigned num)
 
 int main(int argc, char *argv[])
 {
-	unsigned int i;
+	unsigned int i, weight;
 	uintptr_t perfect_bit;
 	struct htable ht;
 	uint64_t val[NUM_VALS];
@@ -121,7 +121,14 @@ int main(int argc, char *argv[])
 	add_vals(&ht, val, 0, 1);
 	ok1(ht.bits == 1);
 	ok1(ht.max == 1);
-	ok1(ht.common_mask == -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));