X-Git-Url: http://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Fhtable%2Fhtable.c;h=e6dc4fd817f886fa2676d0cefd9774f0fd9a690a;hp=788e71895b183db45768fd0327572dcf5ccf4fd5;hb=7a353c03e5e8cdd55cbc0917f9ecff5cf9beefdb;hpb=0473813acdfad62221ec9f2b9b41bc10d1f4586d diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c index 788e7189..e6dc4fd8 100644 --- a/ccan/htable/htable.c +++ b/ccan/htable/htable.c @@ -1,27 +1,39 @@ +/* Licensed under LGPLv2+ - see LICENSE file for details */ #include #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 +#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; -}; +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, @@ -56,35 +68,63 @@ static inline uintptr_t get_hash_ptr_bits(const struct htable *ht, & 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 = ((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); - ht = NULL; - } + struct htable empty = HTABLE_INITIALIZER(empty, NULL, NULL); + *ht = empty; + ht->rehash = rehash; + ht->priv = priv; + ht->table = &ht->perfect_bit; +} + +/* We've changed ht->bits, update ht->max and ht->max_with_deleted */ +static void htable_adjust_capacity(struct htable *ht) +{ + ht->max = ((size_t)3 << ht->bits) / 4; + ht->max_with_deleted = ((size_t)9 << ht->bits) / 10; +} + +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, sizeof(size_t) << ht->bits); + if (!ht->table) { + ht->table = &ht->perfect_bit; + return false; } - return ht; + htable_adjust_capacity(ht); + (void)htable_debug(ht, HTABLE_LOC); + return true; +} + +void htable_clear(struct htable *ht) +{ + if (ht->table != &ht->perfect_bit) + 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) { - free((void *)ht->table); - free((void *)ht); + uintptr_t *htable = htable_alloc(dst, sizeof(size_t) << src->bits); + + if (!htable) + return false; + + *dst = *src; + dst->table = htable; + memcpy(dst->table, src->table, sizeof(size_t) << src->bits); + return true; } static size_t hash_bucket(const struct htable *ht, size_t h) @@ -108,21 +148,21 @@ 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); } -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])) @@ -131,7 +171,7 @@ void *htable_first(const struct htable *ht, struct htable_iter *i) 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])) @@ -140,6 +180,17 @@ void *htable_next(const struct htable *ht, struct htable_iter *i) 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->table[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) { @@ -155,21 +206,20 @@ static void ht_add(struct htable *ht, const void *new, size_t 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; uintptr_t *oldtable, e; oldtable = ht->table; - ht->table = calloc(1 << (ht->bits+1), sizeof(size_t)); + ht->table = htable_alloc(ht, sizeof(size_t) << (ht->bits+1)); if (!ht->table) { ht->table = oldtable; return false; } ht->bits++; - ht->max *= 2; - ht->max_with_deleted *= 2; + htable_adjust_capacity(ht); /* If we lost our "perfect bit", get it back now. */ if (!ht->perfect_bit && ht->common_mask) { @@ -181,18 +231,22 @@ static COLD_ATTRIBUTE bool double_table(struct htable *ht) } } - 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)); + } } + htable_free(ht, oldtable); } ht->deleted = 0; - free(oldtable); + + (void)htable_debug(ht, HTABLE_LOC); 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; @@ -214,18 +268,29 @@ static COLD_ATTRIBUTE void rehash_table(struct htable *ht) } } ht->deleted = 0; + (void)htable_debug(ht, HTABLE_LOC); } /* 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; + (void)htable_debug(ht, HTABLE_LOC); return; } @@ -248,9 +313,10 @@ static COLD_ATTRIBUTE void update_common(struct htable *ht, const void *p) ht->common_mask &= ~maskdiff; ht->common_bits &= ~maskdiff; ht->perfect_bit &= ~maskdiff; + (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)) return false; @@ -265,7 +331,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; @@ -279,7 +345,7 @@ 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])); @@ -288,3 +354,53 @@ void htable_delval(struct htable *ht, struct htable_iter *i) ht->table[i->off] = HTABLE_DELETED; ht->deleted++; } + +struct htable *htable_check(const struct htable *ht, const char *abortstr) +{ + void *p; + struct htable_iter i; + size_t n = 0; + + /* 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; + } + + return (struct htable *)ht; +}