htable: reduce size of htable by calculating max every time.
authorRusty Russell <rusty@rustcorp.com.au>
Mon, 1 Apr 2019 23:20:37 +0000 (09:50 +1030)
committerRusty Russell <rusty@rustcorp.com.au>
Mon, 1 Apr 2019 23:20:37 +0000 (09:50 +1030)
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
ccan/htable/htable.c
ccan/htable/htable.h
ccan/htable/test/run-copy.c
ccan/htable/test/run-debug.c
ccan/htable/test/run-size.c
ccan/htable/test/run-type-int.c
ccan/htable/test/run-type.c
ccan/htable/test/run.c

index e6dc4fd817f886fa2676d0cefd9774f0fd9a690a..2028d336aec20bff59201c13074602dadd144ec7 100644 (file)
@@ -78,11 +78,14 @@ 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)
+static inline size_t ht_max(const struct htable *ht)
 {
-       ht->max = ((size_t)3 << ht->bits) / 4;
-       ht->max_with_deleted = ((size_t)9 << ht->bits) / 10;
+       return ((size_t)3 << ht->bits) / 4;
+}
+
+static inline size_t ht_max_with_deleted(const struct htable *ht)
+{
+       return ((size_t)9 << ht->bits) / 10;
 }
 
 bool htable_init_sized(struct htable *ht,
@@ -102,7 +105,6 @@ bool htable_init_sized(struct htable *ht,
                ht->table = &ht->perfect_bit;
                return false;
        }
-       htable_adjust_capacity(ht);
        (void)htable_debug(ht, HTABLE_LOC);
        return true;
 }
@@ -219,7 +221,6 @@ static COLD bool double_table(struct htable *ht)
                return false;
        }
        ht->bits++;
-       htable_adjust_capacity(ht);
 
        /* If we lost our "perfect bit", get it back now. */
        if (!ht->perfect_bit && ht->common_mask) {
@@ -318,9 +319,9 @@ static COLD void update_common(struct htable *ht, const void *p)
 
 bool htable_add_(struct htable *ht, size_t hash, const void *p)
 {
-       if (ht->elems+1 > ht->max && !double_table(ht))
+       if (ht->elems+1 > ht_max(ht) && !double_table(ht))
                return false;
-       if (ht->elems+1 + ht->deleted > ht->max_with_deleted)
+       if (ht->elems+1 + ht->deleted > ht_max_with_deleted(ht))
                rehash_table(ht);
        assert(p);
        if (((uintptr_t)p & ht->common_mask) != ht->common_bits)
index 28755d617d67b7766d44fe3e5ce93d7956a85d55..bdce920b552eb0e23a5bbe53877a146decf87d81 100644 (file)
@@ -25,7 +25,7 @@ struct htable {
        size_t (*rehash)(const void *elem, void *priv);
        void *priv;
        unsigned int bits;
-       size_t elems, deleted, max, max_with_deleted;
+       size_t elems, deleted;
        /* These are the bits which are the same in all pointers. */
        uintptr_t common_mask, common_bits;
        uintptr_t perfect_bit;
@@ -50,7 +50,7 @@ struct htable {
  *     static struct htable ht = HTABLE_INITIALIZER(ht, rehash, NULL);
  */
 #define HTABLE_INITIALIZER(name, rehash, priv)                         \
-       { rehash, priv, 0, 0, 0, 0, 0, -1, 0, 0, &name.perfect_bit }
+       { rehash, priv, 0, 0, 0, -1, 0, 0, &name.perfect_bit }
 
 /**
  * htable_init - initialize an empty hash table.
index d111495ad4c775c20a6875e141aef19c12f942da..f8a35006085d6efa5dc96e34f3f5fd0cf0473eb1 100644 (file)
@@ -28,8 +28,8 @@ int main(void)
 
        htable_init(&ht, hash, NULL);
        for (i = 0; i < NUM_VALS; i++) {
-               ok1(ht.max >= i);
-               ok1(ht.max <= i * 2);
+               ok1(ht_max(&ht) >= i);
+               ok1(ht_max(&ht) <= i * 2);
                htable_add(&ht, hash(&val[i], NULL), &val[i]);
        }
 
index d2d6b0ffac609bc496951c1fa6e355e2f23ee0e8..ce4c4103646ee3b69dc214205a5b01bebb32c418 100644 (file)
@@ -121,7 +121,7 @@ int main(void)
        dne = i;
 
        htable_init(&ht, hash, NULL);
-       ok1(ht.max == 0);
+       ok1(ht_max(&ht) == 0);
        ok1(ht.bits == 0);
 
        /* We cannot find an entry which doesn't exist. */
@@ -130,7 +130,7 @@ int main(void)
        /* This should increase it once. */
        add_vals(&ht, val, 0, 1);
        ok1(ht.bits == 1);
-       ok1(ht.max == 1);
+       ok1(ht_max(&ht) == 1);
        weight = 0;
        for (i = 0; i < sizeof(ht.common_mask) * CHAR_BIT; i++) {
                if (ht.common_mask & ((uintptr_t)1 << i)) {
@@ -146,7 +146,7 @@ int main(void)
        /* This should increase it again. */
        add_vals(&ht, val, 1, 1);
        ok1(ht.bits == 2);
-       ok1(ht.max == 3);
+       ok1(ht_max(&ht) == 3);
 
        /* Mask should be set. */
        ok1(ht.common_mask != 0);
@@ -208,15 +208,15 @@ int main(void)
        htable_clear(&ht);
 
        ok1(htable_init_sized(&ht, hash, NULL, 1024));
-       ok1(ht.max >= 1024);
+       ok1(ht_max(&ht) >= 1024);
        htable_clear(&ht);
 
        ok1(htable_init_sized(&ht, hash, NULL, 1023));
-       ok1(ht.max >= 1023);
+       ok1(ht_max(&ht) >= 1023);
        htable_clear(&ht);
 
        ok1(htable_init_sized(&ht, hash, NULL, 1025));
-       ok1(ht.max >= 1025);
+       ok1(ht_max(&ht) >= 1025);
        htable_clear(&ht);
        
        return exit_status();
index 1a2f5cdd1ef8cbbfc1ab84f8221b5bb61b9734ab..090ff99683428b30ac3b070b88a4e2df0238a69f 100644 (file)
@@ -26,8 +26,8 @@ int main(void)
 
        htable_init(&ht, hash, NULL);
        for (i = 0; i < NUM_VALS; i++) {
-               ok1(ht.max >= i);
-               ok1(ht.max <= i * 2);
+               ok1(ht_max(&ht) >= i);
+               ok1(ht_max(&ht) <= i * 2);
                htable_add(&ht, hash(&val[i], NULL), &val[i]);
        }
        htable_clear(&ht);
index 7b71815f3c38fef390a63ad4e420040939338c0e..16c4f56ed40a98d2384ee97d23472f11ec7eed9a 100644 (file)
@@ -127,7 +127,7 @@ int main(void)
        dne = i;
 
        htable_obj_init(&ht);
-       ok1(ht.raw.max == 0);
+       ok1(ht_max(&ht.raw) == 0);
        ok1(ht.raw.bits == 0);
 
        /* We cannot find an entry which doesn't exist. */
@@ -136,7 +136,7 @@ int main(void)
        /* Fill it, it should increase in size. */
        add_vals(&ht, val, NUM_VALS);
        ok1(ht.raw.bits == NUM_BITS + 1);
-       ok1(ht.raw.max < (1 << ht.raw.bits));
+       ok1(ht_max(&ht.raw) < (1 << ht.raw.bits));
 
        /* Mask should be set. */
        ok1(ht.raw.common_mask != 0);
index a3616a5a37b8fb1f2588d9d8e369136c6436665e..f097acb69fdec375acb8472fdc0034a452cd05ca 100644 (file)
@@ -122,7 +122,7 @@ int main(void)
        dne = i;
 
        htable_obj_init(&ht);
-       ok1(ht.raw.max == 0);
+       ok1(ht_max(&ht.raw) == 0);
        ok1(ht.raw.bits == 0);
 
        /* We cannot find an entry which doesn't exist. */
@@ -131,7 +131,7 @@ int main(void)
        /* Fill it, it should increase in size. */
        add_vals(&ht, val, NUM_VALS);
        ok1(ht.raw.bits == NUM_BITS + 1);
-       ok1(ht.raw.max < (1 << ht.raw.bits));
+       ok1(ht_max(&ht.raw) < (1 << ht.raw.bits));
 
        /* Mask should be set. */
        ok1(ht.raw.common_mask != 0);
index 46514c7202f2438b54b15aca2f9c0800ca5f5dd4..067816a9c51c474aef38d78337f2fab05937a759 100644 (file)
@@ -111,7 +111,7 @@ int main(void)
        dne = i;
 
        htable_init(&ht, hash, NULL);
-       ok1(ht.max == 0);
+       ok1(ht_max(&ht) == 0);
        ok1(ht.bits == 0);
 
        /* We cannot find an entry which doesn't exist. */
@@ -120,7 +120,7 @@ int main(void)
        /* This should increase it once. */
        add_vals(&ht, val, 0, 1);
        ok1(ht.bits == 1);
-       ok1(ht.max == 1);
+       ok1(ht_max(&ht) == 1);
        weight = 0;
        for (i = 0; i < sizeof(ht.common_mask) * CHAR_BIT; i++) {
                if (ht.common_mask & ((uintptr_t)1 << i)) {
@@ -136,7 +136,7 @@ int main(void)
        /* This should increase it again. */
        add_vals(&ht, val, 1, 1);
        ok1(ht.bits == 2);
-       ok1(ht.max == 3);
+       ok1(ht_max(&ht) == 3);
 
        /* Mask should be set. */
        ok1(ht.common_mask != 0);
@@ -197,15 +197,15 @@ int main(void)
        htable_clear(&ht);
 
        ok1(htable_init_sized(&ht, hash, NULL, 1024));
-       ok1(ht.max >= 1024);
+       ok1(ht_max(&ht) >= 1024);
        htable_clear(&ht);
 
        ok1(htable_init_sized(&ht, hash, NULL, 1023));
-       ok1(ht.max >= 1023);
+       ok1(ht_max(&ht) >= 1023);
        htable_clear(&ht);
 
        ok1(htable_init_sized(&ht, hash, NULL, 1025));
-       ok1(ht.max >= 1025);
+       ok1(ht_max(&ht) >= 1025);
        htable_clear(&ht);
        
        return exit_status();