X-Git-Url: http://git.ozlabs.org/?a=blobdiff_plain;f=ccan%2Fhtable%2Fhtable.c;h=f3568230af6136e99da51d1434a435d51ac843cf;hb=97026cedabce510b2e2e547120f04fe0f6a5ecab;hp=5a773cd8876d2f36b53733c659757213811651ff;hpb=7b56762984ce66f38728b542ca347bcb6fe3e981;p=ccan diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c index 5a773cd8..f3568230 100644 --- a/ccan/htable/htable.c +++ b/ccan/htable/htable.c @@ -2,9 +2,11 @@ #include #include #include +#include #include #include #include +#include /* We use 0x1 as deleted marker. */ #define HTABLE_DELETED (0x1) @@ -52,6 +54,13 @@ void htable_init(struct htable *ht, 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) @@ -69,9 +78,8 @@ bool htable_init_sized(struct htable *ht, ht->table = &ht->perfect_bit; return false; } - ht->max = ((size_t)3 << ht->bits) / 4; - ht->max_with_deleted = ((size_t)9 << ht->bits) / 10; - + htable_adjust_capacity(ht); + (void)htable_debug(ht, HTABLE_LOC); return true; } @@ -82,6 +90,19 @@ void htable_clear(struct htable *ht) htable_init(ht, ht->rehash, ht->priv); } +bool htable_copy_(struct htable *dst, const struct htable *src) +{ + uintptr_t *htable = malloc(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) { return h & ((1 << ht->bits)-1); @@ -103,21 +124,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])) @@ -126,7 +147,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])) @@ -135,7 +156,7 @@ void *htable_next(const struct htable *ht, struct htable_iter *i) return NULL; } -void *htable_prev(const struct htable *ht, struct htable_iter *i) +void *htable_prev_(const struct htable *ht, struct htable_iter *i) { for (;;) { if (!i->off) @@ -174,8 +195,7 @@ static COLD bool double_table(struct htable *ht) return false; } ht->bits++; - ht->max = ((size_t)3 << ht->bits) / 4; - ht->max_with_deleted = ((size_t)9 << ht->bits) / 10; + htable_adjust_capacity(ht); /* If we lost our "perfect bit", get it back now. */ if (!ht->perfect_bit && ht->common_mask) { @@ -197,6 +217,8 @@ static COLD bool double_table(struct htable *ht) free(oldtable); } ht->deleted = 0; + + (void)htable_debug(ht, HTABLE_LOC); return true; } @@ -222,6 +244,7 @@ static COLD 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... */ @@ -243,6 +266,7 @@ static COLD void update_common(struct htable *ht, const void *p) 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; } @@ -265,9 +289,10 @@ static COLD 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; @@ -282,7 +307,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; @@ -296,7 +321,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])); @@ -305,3 +330,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; +}