X-Git-Url: https://git.ozlabs.org/?a=blobdiff_plain;f=ccan%2Fhtable%2Fhtable.c;h=70e0afc1140d86ad17c3d5e3fdc822a84f5cab93;hb=0f144bfe0ca3cc06564e19a7f3ea40177d1a3c2c;hp=ba5f0de530a1a68d7acd5649cfeca6a67e64142b;hpb=45f24da35118db441e6153f02f6ddd937da1fa1c;p=ccan diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c index ba5f0de5..70e0afc1 100644 --- a/ccan/htable/htable.c +++ b/ccan/htable/htable.c @@ -1,25 +1,43 @@ /* Licensed under LGPLv2+ - see LICENSE file for details */ #include +#include #include -#include #include +#include #include #include #include +#include /* 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 perfect_bit; - uintptr_t *table; -}; +/* perfect_bitnum 63 means there's no perfect bitnum */ +#define NO_PERFECT_BIT (sizeof(uintptr_t) * CHAR_BIT - 1) + +static void *htable_default_alloc(struct htable *ht, size_t len) +{ + return calloc(len, 1); +} + +static void htable_default_free(struct htable *ht, void *p) +{ + free(p); +} + +static void *(*htable_alloc)(struct htable *, size_t) = htable_default_alloc; +static void (*htable_free)(struct htable *, void *) = htable_default_free; + +void htable_set_allocator(void *(*alloc)(struct htable *, size_t len), + void (*free)(struct htable *, void *p)) +{ + if (!alloc) + alloc = htable_default_alloc; + if (!free) + free = htable_default_free; + htable_alloc = alloc; + htable_free = free; +} /* 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, @@ -39,9 +57,67 @@ static inline uintptr_t make_hval(const struct htable *ht, return ((uintptr_t)p & ~ht->common_mask) | bits; } -static inline bool entry_is_valid(uintptr_t e) +static inline uintptr_t *actually_valid_pair(const struct htable *ht) +{ + return ht->table + ((size_t)1 << ht->bits); +} + +/* We have have two entries which look deleted, but we remember + * they are not! */ +static inline bool entry_actually_valid(const struct htable *ht, size_t off) { - return e > HTABLE_DELETED; + const uintptr_t *valid = actually_valid_pair(ht); + /* In the empty case, these are "common_mask" and "rehash" + * which cannot be 0 */ + return valid[0] == off || valid[1] == off; +} + +/* Initialize the "actually valid" pair. */ +static inline void init_actually_valid(struct htable *ht) +{ + uintptr_t *valid = actually_valid_pair(ht); + valid[0] = valid[1] = ((size_t)1 << ht->bits); +} + +/* Add to the "actually valid" pair: there can only ever be two! */ +static COLD void add_actually_valid(struct htable *ht, size_t off) +{ + uintptr_t *valid = actually_valid_pair(ht); + if (valid[0] == ((size_t)1 << ht->bits)) + valid[0] = off; + else { + assert(valid[1] == ((size_t)1 << ht->bits)); + valid[1] = off; + } +} + +static COLD void del_actually_valid(struct htable *ht, size_t off) +{ + uintptr_t *validpair = actually_valid_pair(ht); + if (validpair[0] == off) + validpair[0] = ((size_t)1 << ht->bits); + else { + assert(validpair[1] == off); + validpair[1] = ((size_t)1 << ht->bits); + } +} + +/* If this entry looks invalid, check entry_actually_valid! */ +static inline bool entry_looks_invalid(const struct htable *ht, size_t off) +{ + return ht->table[off] <= HTABLE_DELETED; +} + +static inline bool entry_is_valid(const struct htable *ht, size_t off) +{ + if (!entry_looks_invalid(ht, off)) + return true; + return entry_actually_valid(ht, off); +} + +static inline uintptr_t ht_perfect_mask(const struct htable *ht) +{ + return (uintptr_t)2 << ht->perfect_bitnum; } static inline uintptr_t get_hash_ptr_bits(const struct htable *ht, @@ -51,36 +127,75 @@ static inline uintptr_t get_hash_ptr_bits(const struct htable *ht, * end is quite expensive. But the lower bits are redundant, so * we fold the value first. */ 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) -{ - struct htable *ht = malloc(sizeof(struct htable)); - if (ht) { - ht->bits = 0; - ht->rehash = rehash; - ht->priv = priv; - ht->elems = 0; - ht->deleted = 0; - ht->max = 0; - ht->max_with_deleted = 0; - /* This guarantees we enter update_common first add. */ - ht->common_mask = -1; - ht->common_bits = 0; - ht->perfect_bit = 0; - /* Dummy table until first insert. */ - ht->table = &ht->perfect_bit; + & ht->common_mask & ~ht_perfect_mask(ht); +} + +void htable_init(struct htable *ht, + size_t (*rehash)(const void *elem, void *priv), void *priv) +{ + struct htable empty = HTABLE_INITIALIZER(empty, NULL, NULL); + *ht = empty; + ht->rehash = rehash; + ht->priv = priv; + ht->table = &ht->common_bits; +} + +static inline size_t ht_max(const struct htable *ht) +{ + 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; +} + +/* Includes the two trailing "not-deleted" entries */ +static size_t htable_alloc_size(size_t bits) +{ + return (sizeof(size_t) << bits) + 2 * sizeof(size_t); +} + +bool htable_init_sized(struct htable *ht, + size_t (*rehash)(const void *, void *), + void *priv, size_t expect) +{ + htable_init(ht, rehash, priv); + + /* Don't go insane with sizing. */ + for (ht->bits = 1; ((size_t)3 << ht->bits) / 4 < expect; ht->bits++) { + if (ht->bits == 30) + break; + } + + ht->table = htable_alloc(ht, htable_alloc_size(ht->bits)); + if (!ht->table) { + ht->table = &ht->common_bits; + return false; } - return ht; + init_actually_valid(ht); + (void)htable_debug(ht, HTABLE_LOC); + return true; +} + +void htable_clear(struct htable *ht) +{ + if (ht->table != &ht->common_bits) + htable_free(ht, (void *)ht->table); + htable_init(ht, ht->rehash, ht->priv); } -void htable_free(const struct htable *ht) +bool htable_copy_(struct htable *dst, const struct htable *src) { - if (ht->table != &ht->perfect_bit) - free((void *)ht->table); - free((void *)ht); + uintptr_t *htable = htable_alloc(dst, htable_alloc_size(src->bits)); + + if (!htable) + return false; + + *dst = *src; + dst->table = htable; + memcpy(dst->table, src->table, htable_alloc_size(src->bits)); + return true; } static size_t hash_bucket(const struct htable *ht, size_t h) @@ -92,11 +207,14 @@ static void *htable_val(const struct htable *ht, struct htable_iter *i, size_t hash, uintptr_t perfect) { uintptr_t h2 = get_hash_ptr_bits(ht, hash) | perfect; + const uintptr_t *valid = actually_valid_pair(ht); - while (ht->table[i->off]) { - if (ht->table[i->off] != HTABLE_DELETED) { - if (get_extra_ptr_bits(ht, ht->table[i->off]) == h2) - return get_raw_ptr(ht, ht->table[i->off]); + while (ht->table[i->off] || valid[0] == i->off || valid[1] == i->off) { + uintptr_t e = ht->table[i->off]; + if (e != HTABLE_DELETED || valid[0] == i->off || valid[1] == i->off) { + if (get_extra_ptr_bits(ht, e) == h2) { + return get_raw_ptr(ht, e); + } } i->off = (i->off + 1) & ((1 << ht->bits)-1); h2 &= ~perfect; @@ -104,114 +222,143 @@ static void *htable_val(const struct htable *ht, return NULL; } -void *htable_firstval(const struct htable *ht, - struct htable_iter *i, size_t hash) +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, ht->perfect_bit); + return htable_val(ht, i, hash, ht_perfect_mask(ht)); } -void *htable_nextval(const struct htable *ht, - struct htable_iter *i, size_t hash) +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, 0); } -void *htable_first(const struct htable *ht, struct htable_iter *i) +void *htable_first_(const struct htable *ht, struct htable_iter *i) { for (i->off = 0; i->off < (size_t)1 << ht->bits; i->off++) { - if (entry_is_valid(ht->table[i->off])) + if (entry_is_valid(ht, i->off)) return get_raw_ptr(ht, ht->table[i->off]); } return NULL; } -void *htable_next(const struct htable *ht, struct htable_iter *i) +void *htable_next_(const struct htable *ht, struct htable_iter *i) { for (i->off++; i->off < (size_t)1 << ht->bits; i->off++) { - if (entry_is_valid(ht->table[i->off])) + if (entry_is_valid(ht, i->off)) return get_raw_ptr(ht, ht->table[i->off]); } return NULL; } +void *htable_prev_(const struct htable *ht, struct htable_iter *i) +{ + for (;;) { + if (!i->off) + return NULL; + i->off--; + if (entry_is_valid(ht, i->off)) + return get_raw_ptr(ht, ht->table[i->off]); + } +} + /* 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) { size_t i; - uintptr_t perfect = ht->perfect_bit; + uintptr_t perfect = ht_perfect_mask(ht); i = hash_bucket(ht, h); - while (entry_is_valid(ht->table[i])) { + while (entry_is_valid(ht, i)) { perfect = 0; i = (i + 1) & ((1 << ht->bits)-1); } ht->table[i] = make_hval(ht, new, get_hash_ptr_bits(ht, h)|perfect); + + /* If it looks invalid, add it to exceptions */ + if (ht->table[i] <= HTABLE_DELETED) + add_actually_valid(ht, i); } static COLD bool double_table(struct htable *ht) { - unsigned int i; - size_t oldnum = (size_t)1 << ht->bits; - uintptr_t *oldtable, e; + size_t i; + struct htable oldht = *ht; - oldtable = ht->table; - ht->table = calloc(1 << (ht->bits+1), sizeof(size_t)); + ht->table = htable_alloc(ht, htable_alloc_size(ht->bits+1)); if (!ht->table) { - ht->table = oldtable; + ht->table = oldht.table; return false; } ht->bits++; - ht->max = ((size_t)3 << ht->bits) / 4; - ht->max_with_deleted = ((size_t)9 << ht->bits) / 10; + init_actually_valid(ht); /* If we lost our "perfect bit", get it back now. */ - if (!ht->perfect_bit && ht->common_mask) { + if (ht->perfect_bitnum == NO_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; + if (ht->common_mask & ((size_t)2 << i)) { + ht->perfect_bitnum = i; break; } } } - 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); + if (oldht.table != &ht->common_bits) { + for (i = 0; i < (size_t)1 << oldht.bits; i++) { + if (entry_is_valid(&oldht, i)) { + void *p = get_raw_ptr(&oldht, oldht.table[i]); ht_add(ht, p, ht->rehash(p, ht->priv)); } } - free(oldtable); + /* Pass ht here to callback: oldht is an internal figment */ + htable_free(ht, oldht.table); } ht->deleted = 0; + + (void)htable_debug(ht, HTABLE_LOC); return true; } static COLD void rehash_table(struct htable *ht) { size_t start, i; - uintptr_t e; + uintptr_t e, perfect = ht_perfect_mask(ht); + uintptr_t *validpair = actually_valid_pair(ht); /* 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); + uintptr_t *actually = NULL; e = ht->table[h]; - if (!e) - continue; - if (e == HTABLE_DELETED) - ht->table[h] = 0; - else if (!(e & ht->perfect_bit)) { + if (e <= HTABLE_DELETED) { + /* If it's actually valid, remember in case we move it! */ + if (validpair[0] == h) { + actually = &validpair[0]; + } else if (validpair[1] == h) { + actually = &validpair[1]; + } else { + ht->table[h] = 0; + continue; + } + } + + if (!(e & perfect)) { void *p = get_raw_ptr(ht, e); ht->table[h] = 0; + /* Clear actuallyvalid, let ht_add refill */ + if (actually) + *actually = ((size_t)1 << ht->bits); ht_add(ht, p, ht->rehash(p, ht->priv)); } } ht->deleted = 0; + (void)htable_debug(ht, HTABLE_LOC); } /* We stole some bits, now we need to put them back... */ @@ -222,8 +369,9 @@ static COLD 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; + ht->common_bits = ((uintptr_t)p & ht->common_mask); + ht->perfect_bitnum = 0; + (void)htable_debug(ht, HTABLE_LOC); return; } @@ -234,25 +382,31 @@ static COLD void update_common(struct htable *ht, const void *p) bitsdiff = ht->common_bits & maskdiff; for (i = 0; i < (size_t)1 << ht->bits; i++) { - if (!entry_is_valid(ht->table[i])) + if (!entry_is_valid(ht, i)) continue; /* Clear the bits no longer in the mask, set them as * expected. */ ht->table[i] &= ~maskdiff; ht->table[i] |= bitsdiff; + + /* Make sure it's not newly falsely invalid */ + if (ht->table[i] <= HTABLE_DELETED && !entry_actually_valid(ht, i)) + add_actually_valid(ht, i); } /* Take away those bits from our mask, bits and perfect bit. */ ht->common_mask &= ~maskdiff; ht->common_bits &= ~maskdiff; - ht->perfect_bit &= ~maskdiff; + if (ht_perfect_mask(ht) & maskdiff) + ht->perfect_bitnum = NO_PERFECT_BIT; + (void)htable_debug(ht, HTABLE_LOC); } -bool htable_add(struct htable *ht, size_t hash, 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) @@ -263,7 +417,7 @@ bool htable_add(struct htable *ht, size_t hash, const void *p) return true; } -bool htable_del(struct htable *ht, size_t h, const void *p) +bool htable_del_(struct htable *ht, size_t h, const void *p) { struct htable_iter i; void *c; @@ -277,12 +431,109 @@ bool htable_del(struct htable *ht, size_t h, const void *p) return false; } -void htable_delval(struct htable *ht, struct htable_iter *i) +void htable_delval_(struct htable *ht, struct htable_iter *i) { assert(i->off < (size_t)1 << ht->bits); - assert(entry_is_valid(ht->table[i->off])); + + if (entry_looks_invalid(ht, i->off)) + del_actually_valid(ht, i->off); ht->elems--; ht->table[i->off] = HTABLE_DELETED; ht->deleted++; } + +void *htable_pick_(const struct htable *ht, size_t seed, struct htable_iter *i) +{ + void *e; + struct htable_iter unwanted; + + if (!i) + i = &unwanted; + i->off = seed % ((size_t)1 << ht->bits); + e = htable_next(ht, i); + if (!e) + e = htable_first(ht, i); + return e; +} + +struct htable *htable_check(const struct htable *ht, const char *abortstr) +{ + void *p; + struct htable_iter i; + size_t n = 0; + const uintptr_t *validpair = actually_valid_pair(ht); + + /* Use non-DEBUG versions here, to avoid infinite recursion with + * CCAN_HTABLE_DEBUG! */ + for (p = htable_first_(ht, &i); p; p = htable_next_(ht, &i)) { + struct htable_iter i2; + void *c; + size_t h = ht->rehash(p, ht->priv); + bool found = false; + + n++; + + /* Open-code htable_get to avoid CCAN_HTABLE_DEBUG */ + for (c = htable_firstval_(ht, &i2, h); + c; + c = htable_nextval_(ht, &i2, h)) { + if (c == p) { + found = true; + break; + } + } + + if (!found) { + if (abortstr) { + fprintf(stderr, + "%s: element %p in position %zu" + " cannot find itself\n", + abortstr, p, i.off); + abort(); + } + return NULL; + } + } + if (n != ht->elems) { + if (abortstr) { + fprintf(stderr, + "%s: found %zu elems, expected %zu\n", + abortstr, n, ht->elems); + abort(); + } + return NULL; + } + + /* Check validpair does actually override invalid-looking entries! */ + if (ht->table != &ht->common_bits) { + size_t i; + for (i = 0; i < 2; i++) { + if (validpair[i] == ((size_t)1 << ht->bits)) + continue; + if (validpair[i] > ((size_t)1 << ht->bits)) { + if (abortstr) { + fprintf(stderr, + "%s: validpair[%zu] points at %zu" + " which is out of bounds\n", + abortstr, i, validpair[i]); + abort(); + } + return NULL; + } + if (entry_looks_invalid(ht, validpair[i])) + continue; + + if (abortstr) { + fprintf(stderr, + "%s: validpair[%zu] points at %zu" + " which seems valid\n", + abortstr, i, validpair[i]); + abort(); + } + return NULL; + } + } + + return (struct htable *)ht; +}