talloc: spelling fix.

[ccan] / ccan / htable / htable.c

diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c
index 938d410ace7d2f638dde6a4f5f9e3b2b19ccfd13..a15c54d7958a6b779c7e3b7c7b951eb360ef0409 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 <ccan/compiler/compiler.h>
 #include <stdint.h>
 #include <stdlib.h>

+#include <limits.h>

 #include <stdbool.h>
 #include <assert.h>
 
 #include <stdbool.h>
 #include <assert.h>
 


@@ -15,9 +16,10 @@ struct htable {
        size_t (*rehash)(const void *elem, void *priv);
        void *priv;
        unsigned int bits;
        size_t (*rehash)(const void *elem, void *priv);
        void *priv;
        unsigned int bits;

-       size_t elems, max;
+       size_t elems, deleted, max, max_with_deleted;

        /* These are the bits which are the same in all pointers. */
        uintptr_t common_mask, common_bits;
        /* These are the bits which are the same in all pointers. */
        uintptr_t common_mask, common_bits;

+       uintptr_t perfect_bit;

        uintptr_t *table;
 };
 
        uintptr_t *table;
 };
 


@@ -50,7 +52,8 @@ static inline uintptr_t get_hash_ptr_bits(const struct htable *ht,
        /* Shuffling the extra bits (as specified in mask) down the
         * end is quite expensive.  But the lower bits are redundant, so
         * we fold the value first. */
        /* Shuffling the extra bits (as specified in mask) down the
         * end is quite expensive.  But the lower bits are redundant, so
         * we fold the value first. */

-       return (hash ^ (hash >> ht->bits)) & ht->common_mask;
+       return (hash ^ (hash >> ht->bits))
+               & ht->common_mask & ~ht->perfect_bit;

 }
 
 struct htable *htable_new(size_t (*rehash)(const void *elem, void *priv),
 }
 
 struct htable *htable_new(size_t (*rehash)(const void *elem, void *priv),


@@ -62,10 +65,13 @@ struct htable *htable_new(size_t (*rehash)(const void *elem, void *priv),
                ht->rehash = rehash;
                ht->priv = priv;
                ht->elems = 0;
                ht->rehash = rehash;
                ht->priv = priv;
                ht->elems = 0;

-               ht->max = (1 << ht->bits) * 3 / 4;
+               ht->deleted = 0;
+               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;
                /* 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->table = calloc(1 << ht->bits, sizeof(uintptr_t));
                if (!ht->table) {
                        free(ht);


@@ -87,9 +93,9 @@ static size_t hash_bucket(const struct htable *ht, size_t h)
 }
 
 static void *htable_val(const struct htable *ht,
 }
 
 static void *htable_val(const struct htable *ht,

-                       struct htable_iter *i, size_t hash)
+                       struct htable_iter *i, size_t hash, uintptr_t perfect)

 {
 {

-       uintptr_t h2 = get_hash_ptr_bits(ht, hash);
+       uintptr_t h2 = get_hash_ptr_bits(ht, hash) | perfect;

 
        while (ht->table[i->off]) {
                if (ht->table[i->off] != HTABLE_DELETED) {
 
        while (ht->table[i->off]) {
                if (ht->table[i->off] != HTABLE_DELETED) {


@@ -97,6 +103,7 @@ static void *htable_val(const struct htable *ht,
                                return get_raw_ptr(ht, ht->table[i->off]);
                }
                i->off = (i->off + 1) & ((1 << ht->bits)-1);
                                return get_raw_ptr(ht, ht->table[i->off]);
                }
                i->off = (i->off + 1) & ((1 << ht->bits)-1);

+               h2 &= ~perfect;

        }
        return NULL;
 }
        }
        return NULL;
 }


@@ -105,14 +112,14 @@ void *htable_firstval(const struct htable *ht,
                      struct htable_iter *i, size_t hash)
 {
        i->off = hash_bucket(ht, hash);
                      struct htable_iter *i, size_t hash)
 {
        i->off = hash_bucket(ht, hash);

-       return htable_val(ht, i, hash);
+       return htable_val(ht, i, hash, ht->perfect_bit);

 }
 
 void *htable_nextval(const struct htable *ht,
                     struct htable_iter *i, size_t hash)
 {
        i->off = (i->off + 1) & ((1 << ht->bits)-1);
 }
 
 void *htable_nextval(const struct htable *ht,
                     struct htable_iter *i, size_t hash)
 {
        i->off = (i->off + 1) & ((1 << ht->bits)-1);

-       return htable_val(ht, i, hash);
+       return htable_val(ht, i, hash, 0);

 }
 
 void *htable_first(const struct htable *ht, struct htable_iter *i)
 }
 
 void *htable_first(const struct htable *ht, struct htable_iter *i)


@@ -137,20 +144,22 @@ void *htable_next(const struct htable *ht, struct htable_iter *i)
 static void ht_add(struct htable *ht, const void *new, size_t h)
 {
        size_t i;
 static void ht_add(struct htable *ht, const void *new, size_t h)
 {
        size_t i;

+       uintptr_t perfect = ht->perfect_bit;

 
        i = hash_bucket(ht, h);
 
 
        i = hash_bucket(ht, h);
 

-       while (entry_is_valid(ht->table[i]))
+       while (entry_is_valid(ht->table[i])) {
+               perfect = 0;

                i = (i + 1) & ((1 << ht->bits)-1);
                i = (i + 1) & ((1 << ht->bits)-1);

-
-       ht->table[i] = make_hval(ht, new, get_hash_ptr_bits(ht, 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;
 {
        unsigned int i;
        size_t oldnum = (size_t)1 << ht->bits;

-       size_t *oldtable, e;
+       uintptr_t *oldtable, e;

 
        oldtable = ht->table;
        ht->table = calloc(1 << (ht->bits+1), sizeof(size_t));
 
        oldtable = ht->table;
        ht->table = calloc(1 << (ht->bits+1), sizeof(size_t));


@@ -160,6 +169,17 @@ static COLD_ATTRIBUTE bool double_table(struct htable *ht)
        }
        ht->bits++;
        ht->max *= 2;
        }
        ht->bits++;
        ht->max *= 2;

+       ht->max_with_deleted *= 2;
+
+       /* 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])) {
 
        for (i = 0; i < oldnum; i++) {
                if (entry_is_valid(e = oldtable[i])) {


@@ -167,12 +187,37 @@ static COLD_ATTRIBUTE bool double_table(struct htable *ht)
                        ht_add(ht, p, ht->rehash(p, ht->priv));
                }
        }
                        ht_add(ht, p, ht->rehash(p, ht->priv));
                }
        }

+       ht->deleted = 0;

        free(oldtable);
        return true;
 }
 
        free(oldtable);
        return true;
 }
 

+static COLD void rehash_table(struct htable *ht)
+{
+       size_t start, i;
+       uintptr_t e;
+
+       /* Beware wrap cases: we need to start from first empty bucket. */
+       for (start = 0; ht->table[start]; start++);
+
+       for (i = 0; i < (size_t)1 << ht->bits; i++) {
+               size_t h = (i + start) & ((1 << ht->bits)-1);
+               e = ht->table[h];
+               if (!e)
+                       continue;
+               if (e == HTABLE_DELETED)
+                       ht->table[h] = 0;
+               else if (!(e & ht->perfect_bit)) {
+                       void *p = get_raw_ptr(ht, e);
+                       ht->table[h] = 0;
+                       ht_add(ht, p, ht->rehash(p, ht->priv));
+               }
+       }
+       ht->deleted = 0;
+}
+

 /* We stole some bits, now we need to put them back... */
 /* 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;
 {
        unsigned int i;
        uintptr_t maskdiff, bitsdiff;


@@ -180,6 +225,7 @@ static COLD_ATTRIBUTE void update_common(struct htable *ht, const void *p)
        if (ht->elems == 0) {
                ht->common_mask = -1;
                ht->common_bits = (uintptr_t)p;
        if (ht->elems == 0) {
                ht->common_mask = -1;
                ht->common_bits = (uintptr_t)p;

+               ht->perfect_bit = 1;

                return;
        }
 
                return;
        }
 


@@ -198,15 +244,18 @@ static COLD_ATTRIBUTE void update_common(struct htable *ht, const void *p)
                ht->table[i] |= bitsdiff;
        }
 
                ht->table[i] |= bitsdiff;
        }
 

-       /* Take away those bits from our mask and set. */
+       /* Take away those bits from our mask, bits and perfect bit. */

        ht->common_mask &= ~maskdiff;
        ht->common_bits &= ~maskdiff;
        ht->common_mask &= ~maskdiff;
        ht->common_bits &= ~maskdiff;

+       ht->perfect_bit &= ~maskdiff;

 }
 
 bool htable_add(struct htable *ht, size_t hash, const void *p)
 {
        if (ht->elems+1 > ht->max && !double_table(ht))
                return false;
 }
 
 bool htable_add(struct htable *ht, size_t hash, const void *p)
 {
        if (ht->elems+1 > ht->max && !double_table(ht))
                return false;

+       if (ht->elems+1 + ht->deleted > ht->max_with_deleted)
+               rehash_table(ht);

        assert(p);
        if (((uintptr_t)p & ht->common_mask) != ht->common_bits)
                update_common(ht, p);
        assert(p);
        if (((uintptr_t)p & ht->common_mask) != ht->common_bits)
                update_common(ht, p);


@@ -216,26 +265,6 @@ bool htable_add(struct htable *ht, size_t hash, const void *p)
        return true;
 }
 
        return true;
 }
 

-/* If every one of the following buckets are DELETED (up to the next unused
-   one), we can actually mark them all unused. */
-static void delete_run(struct htable *ht, unsigned int num)
-{
-       unsigned int i, last = num + 1;
-       size_t mask = (((size_t)1 << ht->bits)-1);
-
-       while (ht->table[last & mask]) {
-               if (entry_is_valid(ht->table[last & mask]))
-                       return;
-               last++;
-       }
-
-       /* Now see if we can step backwards to find previous deleted ones. */
-       for (i = num-1; ht->table[i & mask] == HTABLE_DELETED; i--);
-
-       for (i++; i < last; i++)
-               ht->table[i & ((1 << ht->bits)-1)] = 0;
-}
-

 bool htable_del(struct htable *ht, size_t h, const void *p)
 {
        struct htable_iter i;
 bool htable_del(struct htable *ht, size_t h, const void *p)
 {
        struct htable_iter i;


@@ -257,5 +286,5 @@ void htable_delval(struct htable *ht, struct htable_iter *i)
 
        ht->elems--;
        ht->table[i->off] = HTABLE_DELETED;
 
        ht->elems--;
        ht->table[i->off] = HTABLE_DELETED;

-       delete_run(ht, i->off);
+       ht->deleted++;

 }
 }