X-Git-Url: http://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Fhtable%2Fhtable.c;h=b7e65d11966acc96be83dffbb25a273fec153145;hp=48a734071fa93e1cca12a438c129c008ec0e72ee;hb=6abc867fce8c3eba40eb26092d31e34b47dd9165;hpb=6ceee26828dcb8bf1d607a8221f0d9f8261d448b diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c index 48a73407..b7e65d11 100644 --- a/ccan/htable/htable.c +++ b/ccan/htable/htable.c @@ -1,26 +1,14 @@ +/* Licensed under LGPLv2+ - see LICENSE file for details */ #include #include -#include #include +#include #include #include -/* 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) -struct htable { - size_t (*rehash)(const void *elem, void *priv); - void *priv; - unsigned int bits; - 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 *table; -}; - /* We clear out the bits which are always the same, and put metadata there. */ static inline uintptr_t get_extra_ptr_bits(const struct htable *ht, uintptr_t e) @@ -50,37 +38,25 @@ 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), - void *priv) +void htable_init(struct htable *ht, + size_t (*rehash)(const void *elem, void *priv), void *priv) { - struct htable *ht = malloc(sizeof(struct htable)); - if (ht) { - ht->bits = HTABLE_BASE_BITS; - 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; - /* This guarantees we enter update_common first add. */ - ht->common_mask = -1; - ht->common_bits = 0; - ht->table = calloc(1 << ht->bits, sizeof(uintptr_t)); - if (!ht->table) { - free(ht); - ht = NULL; - } - } - return ht; + struct htable empty = HTABLE_INITIALIZER(empty, NULL, NULL); + *ht = empty; + ht->rehash = rehash; + ht->priv = priv; + ht->table = &ht->perfect_bit; } -void htable_free(const struct htable *ht) +void htable_clear(struct htable *ht) { - free((void *)ht->table); - free((void *)ht); + if (ht->table != &ht->perfect_bit) + free((void *)ht->table); + htable_init(ht, ht->rehash, ht->priv); } static size_t hash_bucket(const struct htable *ht, size_t h) @@ -89,9 +65,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) { @@ -99,6 +75,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; } @@ -107,14 +84,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) @@ -139,16 +116,18 @@ 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; @@ -161,21 +140,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; + } + } + } - 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; @@ -188,9 +179,11 @@ static COLD_ATTRIBUTE void rehash_table(struct htable *ht) e = ht->table[h]; if (!e) continue; - ht->table[h] = 0; - if (e != HTABLE_DELETED) { + 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)); } } @@ -198,14 +191,24 @@ 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; if (ht->elems == 0) { - ht->common_mask = -1; - ht->common_bits = (uintptr_t)p; + /* Always reveal one bit of the pointer in the bucket, + * so it's not zero or HTABLE_DELETED (1), even if + * hash happens to be 0. Assumes (void *)1 is not a + * valid pointer. */ + for (i = sizeof(uintptr_t)*CHAR_BIT - 1; i > 0; i--) { + if ((uintptr_t)p & ((uintptr_t)1 << i)) + break; + } + + ht->common_mask = ~((uintptr_t)1 << i); + ht->common_bits = ((uintptr_t)p & ht->common_mask); + ht->perfect_bit = 1; return; } @@ -224,9 +227,10 @@ 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)