htable: restore perfect bit when resizing.

If the lower bit differs between pointers, we can lose our "perfect"
bit.  Since we're rehashing the entire thing anyway, we can pick
another bit when we double the hash table.

diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c
index dec53127470a9f6b06a53555286a9fcbb153dbef..bbd4fa96e587c64a04446756787bd163ad4dc3c8 100644 (file)
--- a/ccan/htable/htable.c
+++ b/ccan/htable/htable.c
@@ -2,6 +2,7 @@
 #include <ccan/compiler/compiler.h>
 #include <stdint.h>
 #include <stdlib.h>
 #include <ccan/compiler/compiler.h>
 #include <stdint.h>
 #include <stdlib.h>

+#include <limits.h>

 #include <stdbool.h>
 #include <assert.h>
 
 #include <stdbool.h>
 #include <assert.h>
 


@@ -170,7 +171,16 @@ static COLD_ATTRIBUTE bool double_table(struct htable *ht)
        ht->max *= 2;
        ht->max_with_deleted *= 2;
 
        ht->max *= 2;
        ht->max_with_deleted *= 2;
 

-       /* FIXME: If we lost our perfect bit, we could reclaim it here! */
+       /* If we lost our "perfect bit", get it back now. */
+       if (!ht->perfect_bit && ht->common_mask) {
+               for (i = 0; i < sizeof(ht->common_mask) * CHAR_BIT; i++) {
+                       if (ht->common_mask & ((size_t)1 << i)) {
+                               ht->perfect_bit = (size_t)1 << i;
+                               break;
+                       }
+               }
+       }
+

        for (i = 0; i < oldnum; i++) {
                if (entry_is_valid(e = oldtable[i])) {
                        void *p = get_raw_ptr(ht, e);
        for (i = 0; i < oldnum; i++) {
                if (entry_is_valid(e = oldtable[i])) {
                        void *p = get_raw_ptr(ht, e);

diff --git a/ccan/htable/test/run.c b/ccan/htable/test/run.c
index 27f744c52cbd05c857e9b5298f2df471f6f8d451..ece46a0fd7cf4025ae2249785a2fd9d4694a5ee8 100644 (file)
--- a/ccan/htable/test/run.c
+++ b/ccan/htable/test/run.c
@@ -96,13 +96,14 @@ static bool check_mask(struct htable *ht, uint64_t val[], unsigned num)
 int main(int argc, char *argv[])
 {
        unsigned int i;
 int main(int argc, char *argv[])
 {
        unsigned int i;

+       uintptr_t perfect_bit;

        struct htable *ht;
        uint64_t val[NUM_VALS];
        uint64_t dne;
        void *p;
        struct htable_iter iter;
 
        struct htable *ht;
        uint64_t val[NUM_VALS];
        uint64_t dne;
        void *p;
        struct htable_iter iter;
 

-       plan_tests(19);
+       plan_tests(23);

        for (i = 0; i < NUM_VALS; i++)
                val[i] = i;
        dne = i;
        for (i = 0; i < NUM_VALS; i++)
                val[i] = i;
        dne = i;


@@ -143,6 +144,8 @@ int main(int argc, char *argv[])
        htable_add(ht, hash(&val[NUM_VALS-1], NULL), &val[NUM_VALS-1]);
        ok1(ht->common_mask == 0);
        ok1(ht->common_bits == 0);
        htable_add(ht, hash(&val[NUM_VALS-1], NULL), &val[NUM_VALS-1]);
        ok1(ht->common_mask == 0);
        ok1(ht->common_bits == 0);

+       /* Get rid of bogus pointer before we trip over it! */
+       htable_del(ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);

 
        /* Add the rest. */
        add_vals(ht, val, NUM_VALS-1);
 
        /* Add the rest. */
        add_vals(ht, val, NUM_VALS-1);


@@ -151,5 +154,23 @@ int main(int argc, char *argv[])
        find_vals(ht, val, NUM_VALS);
        ok1(!htable_get(ht, hash(&dne, NULL), objcmp, &dne));
 
        find_vals(ht, val, NUM_VALS);
        ok1(!htable_get(ht, hash(&dne, NULL), objcmp, &dne));
 

+       htable_free(ht);
+
+       /* Corner cases: wipe out the perfect bit using bogus pointer. */
+       ht = htable_new(hash, NULL);
+       htable_add(ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]));
+       ok1(ht->perfect_bit);
+       perfect_bit = ht->perfect_bit;
+       htable_add(ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]
+                                  | perfect_bit));
+       ok1(ht->perfect_bit == 0);
+       htable_del(ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1] | perfect_bit));
+
+       /* Enlarging should restore it... */
+       add_vals(ht, val, NUM_VALS-1);
+
+       ok1(ht->perfect_bit != 0);
+       htable_free(ht);
+

        return exit_status();
 }
        return exit_status();
 }