htable: fix vanishing entries properly.

[ccan] / ccan / htable / htable.c

diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c
index 283ba3d7f1f41855370518c355d785f948794bc3..3247bea0879af34e2db5f47e1a3c5f9ac8a9fa9f 100644 (file)
--- a/ccan/htable/htable.c
+++ b/ccan/htable/htable.c
@@ -201,6 +201,77 @@ void *htable_prev_(const struct htable *ht, struct htable_iter *i)
        }
 }
 
+/* Another bit currently in mask needs to be exposed, so that a bucket with p in
+ * it won't appear invalid */
+static COLD void unset_another_common_bit(struct htable *ht,
+                                         uintptr_t *maskdiff,
+                                         const void *p)
+{
+       size_t i;
+
+       for (i = sizeof(uintptr_t) * CHAR_BIT - 1; i > 0; i--) {
+               if (((uintptr_t)p & ((uintptr_t)1 << i))
+                   && ht->common_mask & ~*maskdiff & ((uintptr_t)1 << i))
+                       break;
+       }
+       /* There must have been one, right? */
+       assert(i > 0);
+
+       *maskdiff |= ((uintptr_t)1 << i);
+}
+
+/* We want to change the common mask: this fixes up the table */
+static COLD void fixup_table_common(struct htable *ht, uintptr_t maskdiff)
+{
+       size_t i;
+       uintptr_t bitsdiff;
+
+again:
+       bitsdiff = ht->common_bits & maskdiff;
+
+       for (i = 0; i < (size_t)1 << ht->bits; i++) {
+               uintptr_t e;
+               if (!entry_is_valid(e = ht->table[i]))
+                       continue;
+
+               /* Clear the bits no longer in the mask, set them as
+                * expected. */
+               e &= ~maskdiff;
+               e |= bitsdiff;
+               /* If this made it invalid, restart with more exposed */
+               if (!entry_is_valid(e)) {
+                       unset_another_common_bit(ht, &maskdiff, get_raw_ptr(ht, e));
+                       goto again;
+               }
+               ht->table[i] = e;
+       }
+
+       /* Take away those bits from our mask, bits and perfect bit. */
+       ht->common_mask &= ~maskdiff;
+       ht->common_bits &= ~maskdiff;
+       if (ht_perfect_mask(ht) & maskdiff)
+               ht->perfect_bitnum = NO_PERFECT_BIT;
+}
+
+/* Limited recursion */
+static void ht_add(struct htable *ht, const void *new, size_t h);
+
+/* We tried to add this entry, but it looked invalid!  We need to
+ * let another pointer bit through mask */
+static COLD void update_common_fix_invalid(struct htable *ht, const void *p, size_t h)
+{
+       uintptr_t maskdiff;
+
+       assert(ht->elems != 0);
+
+       maskdiff = 0;
+       unset_another_common_bit(ht, &maskdiff, p);
+       fixup_table_common(ht, maskdiff);
+
+       /* Now won't recurse */
+       ht_add(ht, p, h);
+}
+
 /* This does not expand the hash table, that's up to caller. */
 static void ht_add(struct htable *ht, const void *new, size_t h)
 {
@@ -214,6 +285,8 @@ static void ht_add(struct htable *ht, const void *new, size_t h)
                i = (i + 1) & ((1 << ht->bits)-1);
        }
        ht->table[i] = make_hval(ht, new, get_hash_ptr_bits(ht, h)|perfect);
+       if (!entry_is_valid(ht->table[i]))
+               update_common_fix_invalid(ht, new, h);
 }
 
 static COLD bool double_table(struct htable *ht)
@@ -283,8 +356,7 @@ static COLD void rehash_table(struct htable *ht)
 /* We stole some bits, now we need to put them back... */
 static COLD void update_common(struct htable *ht, const void *p)
 {
-       unsigned int i;
-       uintptr_t maskdiff, bitsdiff;
+       uintptr_t maskdiff;
 
        if (ht->elems == 0) {
                ht->common_mask = -1;
@@ -297,33 +369,20 @@ static COLD void update_common(struct htable *ht, const void *p)
        /* Find bits which are unequal to old common set. */
        maskdiff = ht->common_bits ^ ((uintptr_t)p & ht->common_mask);
 
-       /* These are the bits which go there in existing entries. */
-       bitsdiff = ht->common_bits & maskdiff;
-
-       for (i = 0; i < (size_t)1 << ht->bits; i++) {
-               if (!entry_is_valid(ht->table[i]))
-                       continue;
-               /* Clear the bits no longer in the mask, set them as
-                * expected. */
-               ht->table[i] &= ~maskdiff;
-               ht->table[i] |= bitsdiff;
-       }
-
-       /* Take away those bits from our mask, bits and perfect bit. */
-       ht->common_mask &= ~maskdiff;
-       ht->common_bits &= ~maskdiff;
-       if (ht_perfect_mask(ht) & maskdiff)
-               ht->perfect_bitnum = NO_PERFECT_BIT;
+       fixup_table_common(ht, maskdiff);
        (void)htable_debug(ht, HTABLE_LOC);
 }
 
 bool htable_add_(struct htable *ht, size_t hash, const void *p)
 {
+       /* Cannot insert NULL, or (void *)1. */
+       assert(p);
+       assert(entry_is_valid((uintptr_t)p));
+
        if (ht->elems+1 > ht_max(ht) && !double_table(ht))
                return false;
        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)
                update_common(ht, p);