htable: push capacity limit from 66 to 75%

[ccan] / ccan / htable / htable.c

diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c
index dec53127470a9f6b06a53555286a9fcbb153dbef..788e71895b183db45768fd0327572dcf5ccf4fd5 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 <limits.h>
 #include <stdbool.h>
 #include <assert.h>
 
@@ -65,8 +66,8 @@ struct htable *htable_new(size_t (*rehash)(const void *elem, void *priv),
                ht->priv = priv;
                ht->elems = 0;
                ht->deleted = 0;
-               ht->max = (1 << ht->bits) * 2 / 3;
-               ht->max_with_deleted = (1 << ht->bits) * 4 / 5;
+               ht->max = ((size_t)1 << ht->bits) * 3 / 4;
+               ht->max_with_deleted = ((size_t)1 << ht->bits) * 9 / 10;
                /* This guarantees we enter update_common first add. */
                ht->common_mask = -1;
                ht->common_bits = 0;
@@ -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);