From 8c2ee69f54a357078e75392659be3c46a228b7d0 Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Tue, 17 Mar 2015 08:16:28 +1030 Subject: [PATCH] invbloom: singleton callback for when destroying a singleton, too. Signed-off-by: Rusty Russell --- ccan/invbloom/invbloom.c | 19 ++++++++++----- ccan/invbloom/invbloom.h | 14 +++++++---- ccan/invbloom/test/run-singletoncb.c | 36 ++++++++++++++++------------ 3 files changed, 44 insertions(+), 25 deletions(-) diff --git a/ccan/invbloom/invbloom.c b/ccan/invbloom/invbloom.c index bda23462..28dabec6 100644 --- a/ccan/invbloom/invbloom.c +++ b/ccan/invbloom/invbloom.c @@ -34,7 +34,7 @@ struct invbloom *invbloom_new_(const tal_t *ctx, void invbloom_singleton_cb_(struct invbloom *ib, void (*cb)(struct invbloom *, - size_t bucket, void *), + size_t bucket, bool, void *), void *data) { ib->singleton = cb; @@ -51,7 +51,7 @@ static u8 *idsum_ptr(const struct invbloom *ib, size_t bucket) return (u8 *)ib->idsum + bucket * ib->id_size; } -static void check_for_singleton(struct invbloom *ib, size_t bucket) +static void check_for_singleton(struct invbloom *ib, size_t bucket, bool before) { if (!ib->singleton) return; @@ -59,7 +59,7 @@ static void check_for_singleton(struct invbloom *ib, size_t bucket) if (ib->count[bucket] != 1 && ib->count[bucket] != -1) return; - ib->singleton(ib, bucket, ib->singleton_data); + ib->singleton(ib, bucket, before, ib->singleton_data); } static void add_to_bucket(struct invbloom *ib, size_t n, const u8 *id) @@ -67,12 +67,14 @@ static void add_to_bucket(struct invbloom *ib, size_t n, const u8 *id) size_t i; u8 *idsum = idsum_ptr(ib, n); + check_for_singleton(ib, n, true); + ib->count[n]++; for (i = 0; i < ib->id_size; i++) idsum[i] ^= id[i]; - check_for_singleton(ib, n); + check_for_singleton(ib, n, false); } static void remove_from_bucket(struct invbloom *ib, size_t n, const u8 *id) @@ -80,11 +82,13 @@ static void remove_from_bucket(struct invbloom *ib, size_t n, const u8 *id) size_t i; u8 *idsum = idsum_ptr(ib, n); + check_for_singleton(ib, n, true); + ib->count[n]--; for (i = 0; i < ib->id_size; i++) idsum[i] ^= id[i]; - check_for_singleton(ib, n); + check_for_singleton(ib, n, false); } void invbloom_insert(struct invbloom *ib, const void *id) @@ -175,12 +179,15 @@ void invbloom_subtract(struct invbloom *ib1, const struct invbloom *ib2) assert(ib1->id_size == ib2->id_size); assert(ib1->salt == ib2->salt); + for (i = 0; i < ib1->n_elems; i++) + check_for_singleton(ib1, i, true); + for (i = 0; i < ib1->n_elems * ib1->id_size; i++) ib1->idsum[i] ^= ib2->idsum[i]; for (i = 0; i < ib1->n_elems; i++) { ib1->count[i] -= ib2->count[i]; - check_for_singleton(ib1, i); + check_for_singleton(ib1, i, false); } } diff --git a/ccan/invbloom/invbloom.h b/ccan/invbloom/invbloom.h index d30223d2..a1c83c77 100644 --- a/ccan/invbloom/invbloom.h +++ b/ccan/invbloom/invbloom.h @@ -11,7 +11,7 @@ struct invbloom { u32 salt; s32 *count; /* [n_elems] */ u8 *idsum; /* [n_elems][id_size] */ - void (*singleton)(struct invbloom *ib, size_t elem, void *); + void (*singleton)(struct invbloom *ib, size_t elem, bool, void *); void *singleton_data; }; @@ -31,7 +31,7 @@ struct invbloom *invbloom_new_(const tal_t *ctx, size_t n_elems, u32 salt); /** - * invbloom_singleton_cb - set callback for when a singleton is found. + * invbloom_singleton_cb - set callback for a singleton created/destroyed. * @ib: the invertable bloom lookup table. * @cb: the function to call (or NULL for none) * @data: the data to hand to the function. @@ -40,15 +40,21 @@ struct invbloom *invbloom_new_(const tal_t *ctx, * possibly multiple times for a single call. The particular * @ib bucket will be consistent, but the rest of the table may * not be. + * + * @cb is of form "void @cb(struct invbloom *ib, size_t bucket, bool + * before, data)". @before is true if the call is done before the + * singleton in @bucket is removed (ie. ib->counts[bucket] is -1 or 1, + * but is about to change). @before is false if the call is done + * after the operation, and the bucket is now a singleton. */ #define invbloom_singleton_cb(ib, cb, data) \ invbloom_singleton_cb_((ib), \ typesafe_cb_preargs(void, void *, (cb), (data), \ - struct invbloom *, size_t), (data)) + struct invbloom *, size_t, bool), (data)) void invbloom_singleton_cb_(struct invbloom *ib, void (*cb)(struct invbloom *, - size_t bucket, void *), + size_t bucket, bool before, void *), void *data); /** diff --git a/ccan/invbloom/test/run-singletoncb.c b/ccan/invbloom/test/run-singletoncb.c index 2ecf71e9..f4f6455a 100644 --- a/ccan/invbloom/test/run-singletoncb.c +++ b/ccan/invbloom/test/run-singletoncb.c @@ -3,11 +3,11 @@ #include #include -static void singleton_cb(struct invbloom *ib, size_t n, +static void singleton_cb(struct invbloom *ib, size_t n, bool before, unsigned *count) { ok1(ib->count[n] == 1 || ib->count[n] == -1); - (*count)++; + count[before]++; } int main(void) @@ -15,48 +15,54 @@ int main(void) struct invbloom *ib; const tal_t *ctx = tal(NULL, char); int val; - unsigned singleton_count; + unsigned singleton_count[2]; /* This is how many tests you plan to run */ - plan_tests(10 + 3 + NUM_HASHES * 2); + plan_tests(16 + 6 + NUM_HASHES * 3); /* Single entry ib table keeps it simple. */ ib = invbloom_new(ctx, int, 1, 100); - invbloom_singleton_cb(ib, singleton_cb, &singleton_count); + invbloom_singleton_cb(ib, singleton_cb, singleton_count); val = 0; - singleton_count = 0; + singleton_count[false] = singleton_count[true] = 0; invbloom_insert(ib, &val); ok1(ib->count[0] == NUM_HASHES); - ok1(singleton_count == 1); + ok1(singleton_count[true] == 1); + ok1(singleton_count[false] == 1); ok1(!invbloom_empty(ib)); /* First delete takes it via singleton. */ invbloom_delete(ib, &val); - ok1(singleton_count == 2); + ok1(singleton_count[true] == 2); + ok1(singleton_count[false] == 2); ok1(invbloom_empty(ib)); /* Second delete creates negative singleton. */ invbloom_delete(ib, &val); - ok1(singleton_count == 3); + ok1(singleton_count[true] == 3); + ok1(singleton_count[false] == 3); /* Now a larger table: this seed set so entries don't clash */ ib = invbloom_new(ctx, int, 1024, 0); - singleton_count = 0; - invbloom_singleton_cb(ib, singleton_cb, &singleton_count); + singleton_count[false] = singleton_count[true] = 0; + invbloom_singleton_cb(ib, singleton_cb, singleton_count); val = 0; invbloom_insert(ib, &val); - ok1(singleton_count == NUM_HASHES); + ok1(singleton_count[true] == 0); + ok1(singleton_count[false] == NUM_HASHES); - /* First delete does nothing. */ + /* First delete removes singletons. */ invbloom_delete(ib, &val); - ok1(singleton_count == NUM_HASHES); + ok1(singleton_count[true] == NUM_HASHES); + ok1(singleton_count[false] == NUM_HASHES); ok1(invbloom_empty(ib)); /* Second delete creates negative singletons. */ invbloom_delete(ib, &val); - ok1(singleton_count == NUM_HASHES * 2); + ok1(singleton_count[true] == NUM_HASHES); + ok1(singleton_count[false] == NUM_HASHES * 2); tal_free(ctx); -- 2.39.2