From 45f24da35118db441e6153f02f6ddd937da1fa1c Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Tue, 27 Sep 2011 14:26:59 +0930 Subject: [PATCH] htable: start empty. There's no real reason to start with 128 entries. --- ccan/htable/htable.c | 35 ++++++++++++++----------------- ccan/htable/test/run-size.c | 36 +++++++++++++++++++++++++++++++ ccan/htable/test/run-type.c | 13 ++++++------ ccan/htable/test/run.c | 42 ++++++++++++++++++++++++------------- 4 files changed, 87 insertions(+), 39 deletions(-) create mode 100644 ccan/htable/test/run-size.c diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c index 20b6f5ae..ba5f0de5 100644 --- a/ccan/htable/htable.c +++ b/ccan/htable/htable.c @@ -7,9 +7,6 @@ #include #include -/* This means a struct htable takes at least 512 bytes / 1k (32/64 bits). */ -#define HTABLE_BASE_BITS 7 - /* We use 0x1 as deleted marker. */ #define HTABLE_DELETED (0x1) @@ -62,29 +59,27 @@ struct htable *htable_new(size_t (*rehash)(const void *elem, void *priv), { struct htable *ht = malloc(sizeof(struct htable)); if (ht) { - ht->bits = HTABLE_BASE_BITS; + ht->bits = 0; ht->rehash = rehash; ht->priv = priv; ht->elems = 0; ht->deleted = 0; - ht->max = ((size_t)1 << ht->bits) * 3 / 4; - ht->max_with_deleted = ((size_t)1 << ht->bits) * 9 / 10; + ht->max = 0; + ht->max_with_deleted = 0; /* This guarantees we enter update_common first add. */ ht->common_mask = -1; ht->common_bits = 0; ht->perfect_bit = 0; - ht->table = calloc(1 << ht->bits, sizeof(uintptr_t)); - if (!ht->table) { - free(ht); - ht = NULL; - } + /* Dummy table until first insert. */ + ht->table = &ht->perfect_bit; } return ht; } void htable_free(const struct htable *ht) { - free((void *)ht->table); + if (ht->table != &ht->perfect_bit) + free((void *)ht->table); free((void *)ht); } @@ -169,8 +164,8 @@ static COLD bool double_table(struct htable *ht) return false; } ht->bits++; - ht->max *= 2; - ht->max_with_deleted *= 2; + ht->max = ((size_t)3 << ht->bits) / 4; + ht->max_with_deleted = ((size_t)9 << ht->bits) / 10; /* If we lost our "perfect bit", get it back now. */ if (!ht->perfect_bit && ht->common_mask) { @@ -182,14 +177,16 @@ static COLD bool double_table(struct htable *ht) } } - for (i = 0; i < oldnum; i++) { - if (entry_is_valid(e = oldtable[i])) { - void *p = get_raw_ptr(ht, e); - ht_add(ht, p, ht->rehash(p, ht->priv)); + if (oldtable != &ht->perfect_bit) { + for (i = 0; i < oldnum; i++) { + if (entry_is_valid(e = oldtable[i])) { + void *p = get_raw_ptr(ht, e); + ht_add(ht, p, ht->rehash(p, ht->priv)); + } } + free(oldtable); } ht->deleted = 0; - free(oldtable); return true; } diff --git a/ccan/htable/test/run-size.c b/ccan/htable/test/run-size.c new file mode 100644 index 00000000..01e4bb41 --- /dev/null +++ b/ccan/htable/test/run-size.c @@ -0,0 +1,36 @@ +#include +#include +#include +#include +#include + +#define NUM_VALS 512 + +/* We use the number divided by two as the hash (for lots of + collisions). */ +static size_t hash(const void *elem, void *unused) +{ + size_t h = *(uint64_t *)elem / 2; + return h; +} + +int main(int argc, char *argv[]) +{ + struct htable *ht; + uint64_t val[NUM_VALS]; + unsigned int i; + + plan_tests((NUM_VALS) * 2); + for (i = 0; i < NUM_VALS; i++) + val[i] = i; + + ht = htable_new(hash, NULL); + for (i = 0; i < NUM_VALS; i++) { + ok1(ht->max >= i); + ok1(ht->max <= i * 2); + htable_add(ht, hash(&val[i], NULL), &val[i]); + } + htable_free(ht); + + return exit_status(); +} diff --git a/ccan/htable/test/run-type.c b/ccan/htable/test/run-type.c index 02dac29e..aca9c594 100644 --- a/ccan/htable/test/run-type.c +++ b/ccan/htable/test/run-type.c @@ -4,7 +4,8 @@ #include #include -#define NUM_VALS (1 << HTABLE_BASE_BITS) +#define NUM_BITS 7 +#define NUM_VALS (1 << NUM_BITS) struct obj { /* Makes sure we don't try to treat and obj as a key or vice versa */ @@ -23,7 +24,7 @@ static const unsigned int *objkey(const struct obj *obj) static size_t objhash(const unsigned int *key) { size_t h = *key / 2; - h |= -1UL << HTABLE_BASE_BITS; + h |= -1UL << NUM_BITS; return h; } @@ -121,15 +122,15 @@ int main(int argc, char *argv[]) dne = i; ht = htable_obj_new(); - ok1(((struct htable *)ht)->max < (1 << ((struct htable *)ht)->bits)); - ok1(((struct htable *)ht)->bits == HTABLE_BASE_BITS); + ok1(((struct htable *)ht)->max == 0); + ok1(((struct htable *)ht)->bits == 0); /* We cannot find an entry which doesn't exist. */ ok1(!htable_obj_get(ht, &dne)); - /* Fill it, it should increase in size (once). */ + /* Fill it, it should increase in size. */ add_vals(ht, val, NUM_VALS); - ok1(((struct htable *)ht)->bits == HTABLE_BASE_BITS + 1); + ok1(((struct htable *)ht)->bits == NUM_BITS + 1); ok1(((struct htable *)ht)->max < (1 << ((struct htable *)ht)->bits)); /* Mask should be set. */ diff --git a/ccan/htable/test/run.c b/ccan/htable/test/run.c index ece46a0f..5e9d23ee 100644 --- a/ccan/htable/test/run.c +++ b/ccan/htable/test/run.c @@ -4,7 +4,8 @@ #include #include -#define NUM_VALS (1 << HTABLE_BASE_BITS) +#define NUM_BITS 7 +#define NUM_VALS (1 << NUM_BITS) /* We use the number divided by two as the hash (for lots of collisions), plus set all the higher bits so we can detect if they @@ -12,7 +13,7 @@ static size_t hash(const void *elem, void *unused) { size_t h = *(uint64_t *)elem / 2; - h |= -1UL << HTABLE_BASE_BITS; + h |= -1UL << NUM_BITS; return h; } @@ -22,11 +23,12 @@ static bool objcmp(const void *htelem, void *cmpdata) } static void add_vals(struct htable *ht, - const uint64_t val[], unsigned int num) + const uint64_t val[], + unsigned int off, unsigned int num) { uint64_t i; - for (i = 0; i < num; i++) { + for (i = off; i < off+num; i++) { if (htable_get(ht, hash(&i, NULL), objcmp, &i)) { fail("%llu already in hash", (long long)i); return; @@ -103,27 +105,39 @@ int main(int argc, char *argv[]) void *p; struct htable_iter iter; - plan_tests(23); + plan_tests(29); for (i = 0; i < NUM_VALS; i++) val[i] = i; dne = i; ht = htable_new(hash, NULL); - ok1(ht->max < (1 << ht->bits)); - ok1(ht->bits == HTABLE_BASE_BITS); + ok1(ht->max == 0); + ok1(ht->bits == 0); /* We cannot find an entry which doesn't exist. */ ok1(!htable_get(ht, hash(&dne, NULL), objcmp, &dne)); - /* Fill it, it should increase in size (once). */ - add_vals(ht, val, NUM_VALS); - ok1(ht->bits == HTABLE_BASE_BITS + 1); - ok1(ht->max < (1 << ht->bits)); + /* This should increase it once. */ + add_vals(ht, val, 0, 1); + ok1(ht->bits == 1); + ok1(ht->max == 1); + ok1(ht->common_mask == -1); + + /* Mask should be set. */ + ok1(check_mask(ht, val, 1)); + + /* This should increase it again. */ + add_vals(ht, val, 1, 1); + ok1(ht->bits == 2); + ok1(ht->max == 3); /* Mask should be set. */ ok1(ht->common_mask != 0); ok1(ht->common_mask != -1); - ok1(check_mask(ht, val, NUM_VALS)); + ok1(check_mask(ht, val, 2)); + + /* Now do the rest. */ + add_vals(ht, val, 2, NUM_VALS - 2); /* Find all. */ find_vals(ht, val, NUM_VALS); @@ -148,7 +162,7 @@ int main(int argc, char *argv[]) htable_del(ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]); /* Add the rest. */ - add_vals(ht, val, NUM_VALS-1); + add_vals(ht, val, 0, NUM_VALS-1); /* Check we can find them all. */ find_vals(ht, val, NUM_VALS); @@ -167,7 +181,7 @@ int main(int argc, char *argv[]) htable_del(ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1] | perfect_bit)); /* Enlarging should restore it... */ - add_vals(ht, val, NUM_VALS-1); + add_vals(ht, val, 0, NUM_VALS-1); ok1(ht->perfect_bit != 0); htable_free(ht); -- 2.39.2