From d3104024f71cf4f89195787add6c7ac381d62f40 Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Mon, 8 Nov 2010 16:24:31 +1030 Subject: [PATCH] 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. --- ccan/htable/htable.c | 12 +++++++++++- ccan/htable/test/run.c | 23 ++++++++++++++++++++++- 2 files changed, 33 insertions(+), 2 deletions(-) diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c index dec53127..bbd4fa96 100644 --- a/ccan/htable/htable.c +++ b/ccan/htable/htable.c @@ -2,6 +2,7 @@ #include #include #include +#include #include #include @@ -170,7 +171,16 @@ static COLD_ATTRIBUTE bool double_table(struct htable *ht) 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); diff --git a/ccan/htable/test/run.c b/ccan/htable/test/run.c index 27f744c5..ece46a0f 100644 --- 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; + uintptr_t perfect_bit; 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; @@ -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); + /* 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); @@ -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)); + 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(); } -- 2.39.2