htable: start empty.

[ccan] / ccan / htable / htable.c

diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c
index dec53127470a9f6b06a53555286a9fcbb153dbef..ba5f0de530a1a68d7acd5649cfeca6a67e64142b 100644 (file)
--- a/ccan/htable/htable.c
+++ b/ccan/htable/htable.c
@@ -1,13 +1,12 @@
+/* Licensed under LGPLv2+ - see LICENSE file for details */
 #include <ccan/htable/htable.h>
 #include <ccan/compiler/compiler.h>
 #include <stdint.h>
 #include <stdlib.h>
+#include <limits.h>
 #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)
 
@@ -60,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 = (1 << ht->bits) * 2 / 3;
-               ht->max_with_deleted = (1 << ht->bits) * 4 / 5;
+               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);
 }
 
@@ -154,7 +151,7 @@ static void ht_add(struct htable *ht, const void *new, size_t h)
        ht->table[i] = make_hval(ht, new, get_hash_ptr_bits(ht, h)|perfect);
 }
 
-static COLD_ATTRIBUTE bool double_table(struct htable *ht)
+static COLD bool double_table(struct htable *ht)
 {
        unsigned int i;
        size_t oldnum = (size_t)1 << ht->bits;
@@ -167,22 +164,33 @@ static COLD_ATTRIBUTE 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) {
+               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;
+                       }
+               }
+       }
 
-       /* FIXME: If we lost our perfect bit, we could reclaim it here! */
-       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;
 }
 
-static COLD_ATTRIBUTE void rehash_table(struct htable *ht)
+static COLD void rehash_table(struct htable *ht)
 {
        size_t start, i;
        uintptr_t e;
@@ -207,7 +215,7 @@ static COLD_ATTRIBUTE void rehash_table(struct htable *ht)
 }
 
 /* We stole some bits, now we need to put them back... */
-static COLD_ATTRIBUTE void update_common(struct htable *ht, const void *p)
+static COLD void update_common(struct htable *ht, const void *p)
 {
        unsigned int i;
        uintptr_t maskdiff, bitsdiff;