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

[ccan] / ccan / htable / htable.c

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) {
-               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;
        }