summaryrefslogtreecommitdiff
path: root/lib/ccan
diff options
context:
space:
mode:
Diffstat (limited to 'lib/ccan')
-rw-r--r--lib/ccan/htable/htable.c35
-rw-r--r--lib/ccan/htable/test/run-size.c36
-rw-r--r--lib/ccan/htable/test/run-type.c13
-rw-r--r--lib/ccan/htable/test/run.c42
4 files changed, 87 insertions, 39 deletions
diff --git a/lib/ccan/htable/htable.c b/lib/ccan/htable/htable.c
index 20b6f5ae2d..ba5f0de530 100644
--- a/lib/ccan/htable/htable.c
+++ b/lib/ccan/htable/htable.c
@@ -7,9 +7,6 @@
#include <stdbool.h>
#include <assert.h>
-/* 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/lib/ccan/htable/test/run-size.c b/lib/ccan/htable/test/run-size.c
new file mode 100644
index 0000000000..01e4bb41ac
--- /dev/null
+++ b/lib/ccan/htable/test/run-size.c
@@ -0,0 +1,36 @@
+#include <ccan/htable/htable.h>
+#include <ccan/htable/htable.c>
+#include <ccan/tap/tap.h>
+#include <stdbool.h>
+#include <string.h>
+
+#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/lib/ccan/htable/test/run-type.c b/lib/ccan/htable/test/run-type.c
index 02dac29e10..aca9c59488 100644
--- a/lib/ccan/htable/test/run-type.c
+++ b/lib/ccan/htable/test/run-type.c
@@ -4,7 +4,8 @@
#include <stdbool.h>
#include <string.h>
-#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/lib/ccan/htable/test/run.c b/lib/ccan/htable/test/run.c
index ece46a0fd7..5e9d23ee30 100644
--- a/lib/ccan/htable/test/run.c
+++ b/lib/ccan/htable/test/run.c
@@ -4,7 +4,8 @@
#include <stdbool.h>
#include <string.h>
-#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);
generated by cgit (git 2.34.1) at 2024-11-25 04:40:37 +0000