X-Git-Url: http://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Fhtable%2Fhtable.c;h=a15c54d7958a6b779c7e3b7c7b951eb360ef0409;hp=938d410ace7d2f638dde6a4f5f9e3b2b19ccfd13;hb=2488a379c4c8f9b565cf7f3062015714ec704936;hpb=198d85adf5e8d9a44b7436bdd046dbffce66b23a diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c index 938d410a..a15c54d7 100644 --- a/ccan/htable/htable.c +++ b/ccan/htable/htable.c @@ -2,6 +2,7 @@ #include #include #include +#include #include #include @@ -15,9 +16,10 @@ struct htable { 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; + uintptr_t perfect_bit; 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. */ - 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), @@ -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->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; + ht->perfect_bit = 0; 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, - 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) { @@ -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); + h2 &= ~perfect; } 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); - 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); - return htable_val(ht, i, hash); + return htable_val(ht, i, hash, 0); } 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; + uintptr_t perfect = ht->perfect_bit; 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); - - 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; - size_t *oldtable, e; + uintptr_t *oldtable, e; 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->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])) { @@ -167,12 +187,37 @@ static COLD_ATTRIBUTE bool double_table(struct htable *ht) ht_add(ht, p, ht->rehash(p, ht->priv)); } } + ht->deleted = 0; 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... */ -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; @@ -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; + ht->perfect_bit = 1; return; } @@ -198,15 +244,18 @@ static COLD_ATTRIBUTE void update_common(struct htable *ht, const void *p) 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->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; + 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); @@ -216,26 +265,6 @@ bool htable_add(struct htable *ht, size_t hash, const void *p) 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; @@ -257,5 +286,5 @@ void htable_delval(struct htable *ht, struct htable_iter *i) ht->elems--; ht->table[i->off] = HTABLE_DELETED; - delete_run(ht, i->off); + ht->deleted++; }