From f359fde1b7c3ca60faebd4df710bf30a68784e27 Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Mon, 6 Jun 2016 13:44:36 +0930 Subject: [PATCH] htable: add htable_copy. Signed-off-by: Rusty Russell --- ccan/htable/htable.c | 28 ++++++++++++++++++----- ccan/htable/htable.h | 19 ++++++++++++++++ ccan/htable/test/run-copy.c | 44 +++++++++++++++++++++++++++++++++++++ 3 files changed, 86 insertions(+), 5 deletions(-) create mode 100644 ccan/htable/test/run-copy.c diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c index 5a773cd8..e1d13699 100644 --- a/ccan/htable/htable.c +++ b/ccan/htable/htable.c @@ -5,6 +5,7 @@ #include #include #include +#include /* We use 0x1 as deleted marker. */ #define HTABLE_DELETED (0x1) @@ -52,6 +53,13 @@ void htable_init(struct htable *ht, ht->table = &ht->perfect_bit; } +/* We've changed ht->bits, update ht->max and ht->max_with_deleted */ +static void htable_adjust_capacity(struct htable *ht) +{ + ht->max = ((size_t)3 << ht->bits) / 4; + ht->max_with_deleted = ((size_t)9 << ht->bits) / 10; +} + bool htable_init_sized(struct htable *ht, size_t (*rehash)(const void *, void *), void *priv, size_t expect) @@ -69,9 +77,7 @@ bool htable_init_sized(struct htable *ht, ht->table = &ht->perfect_bit; return false; } - ht->max = ((size_t)3 << ht->bits) / 4; - ht->max_with_deleted = ((size_t)9 << ht->bits) / 10; - + htable_adjust_capacity(ht); return true; } @@ -82,6 +88,19 @@ void htable_clear(struct htable *ht) htable_init(ht, ht->rehash, ht->priv); } +bool htable_copy(struct htable *dst, const struct htable *src) +{ + uintptr_t *htable = malloc(sizeof(size_t) << src->bits); + + if (!htable) + return false; + + *dst = *src; + dst->table = htable; + memcpy(dst->table, src->table, sizeof(size_t) << src->bits); + return true; +} + static size_t hash_bucket(const struct htable *ht, size_t h) { return h & ((1 << ht->bits)-1); @@ -174,8 +193,7 @@ static COLD bool double_table(struct htable *ht) return false; } ht->bits++; - ht->max = ((size_t)3 << ht->bits) / 4; - ht->max_with_deleted = ((size_t)9 << ht->bits) / 10; + htable_adjust_capacity(ht); /* If we lost our "perfect bit", get it back now. */ if (!ht->perfect_bit && ht->common_mask) { diff --git a/ccan/htable/htable.h b/ccan/htable/htable.h index e150c2ef..61ed9170 100644 --- a/ccan/htable/htable.h +++ b/ccan/htable/htable.h @@ -74,6 +74,25 @@ bool htable_init_sized(struct htable *ht, */ void htable_clear(struct htable *ht); +/** + * htable_copy - duplicate a hash table. + * @dst: the hash table to overwrite + * @src: the hash table to copy + * + * Only fails on out-of-memory. + * + * Equivalent to (but faster than): + * if (!htable_init_sized(dst, src->rehash, src->priv, 1U << src->bits)) + * return false; + * v = htable_first(src, &i); + * while (v) { + * htable_add(dst, v); + * v = htable_next(src, i); + * } + * return true; + */ +bool htable_copy(struct htable *dst, const struct htable *src); + /** * htable_rehash - use a hashtree's rehash function * @elem: the argument to rehash() diff --git a/ccan/htable/test/run-copy.c b/ccan/htable/test/run-copy.c new file mode 100644 index 00000000..02d5bbe4 --- /dev/null +++ b/ccan/htable/test/run-copy.c @@ -0,0 +1,44 @@ +#include +#include +#include +#include +#include + +#define NUM_VALS 512 + +static size_t hash(const void *elem, void *unused) +{ + size_t h = *(uint64_t *)elem / 2; + return h; +} + +static bool cmp(const void *candidate, void *ptr) +{ + return *(const uint64_t *)candidate == *(const uint64_t *)ptr; +} + +int main(int argc, char *argv[]) +{ + struct htable ht, ht2; + uint64_t val[NUM_VALS], i; + + plan_tests((NUM_VALS) * 3); + for (i = 0; i < NUM_VALS; i++) + val[i] = i; + + htable_init(&ht, 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_copy(&ht2, &ht); + htable_clear(&ht); + + for (i = 0; i < NUM_VALS; i++) + ok1(htable_get(&ht2, hash(&i, NULL), cmp, &i) == &val[i]); + htable_clear(&ht2); + + return exit_status(); +} -- 2.39.2