invbloom: singleton callback for when destroying a singleton, too.
authorRusty Russell <rusty@rustcorp.com.au>
Mon, 16 Mar 2015 21:46:28 +0000 (08:16 +1030)
committerRusty Russell <rusty@rustcorp.com.au>
Mon, 16 Mar 2015 21:46:28 +0000 (08:16 +1030)
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
ccan/invbloom/invbloom.c
ccan/invbloom/invbloom.h
ccan/invbloom/test/run-singletoncb.c

index bda23462ae5d64ed91d7c1cd22966a19c40d0d0c..28dabec67d8c07f0f809f033aaaa49b27fe8d4a7 100644 (file)
@@ -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);
        }
 }
 
index d30223d2fe3e4d6f53e92c26217e3c47123bc114..a1c83c77641d6416032383abf4af4609f2922b8a 100644 (file)
@@ -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);
 
 /**
index 2ecf71e9655374a67ae73d881a6b7a9856c2ea85..f4f6455a7a2c79d554af2bdce7045c2364adda5d 100644 (file)
@@ -3,11 +3,11 @@
 #include <ccan/invbloom/invbloom.c>
 #include <ccan/tap/tap.h>
 
-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);