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 0a01ead8978ad4c4e914a37dbe029c2ef1219004..b7e65d11966acc96be83dffbb25a273fec153145 100644 (file)
--- 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) {
        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;
        }
                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 (file)
index 0000000..fdd1856
--- /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 1a9e2de4cb6e7f98fe5e75485e06b37c73de26d5..7fc05e24f6bfac4b38748491911c6741d0b841a8 100644 (file)
--- 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[])
 {
 
 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];
        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);
        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));
 
        /* Mask should be set. */
        ok1(check_mask(&ht, val, 1));