invbloom: add callback for when an element becomes a singleton.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

diff --git a/ccan/invbloom/_info b/ccan/invbloom/_info
index 03e9fe0bf11f26fead4da4fd688c7b94a4403495..4055a2c7812ff30078a37832c79d7ce2ca984728 100644 (file)
--- a/ccan/invbloom/_info
+++ b/ccan/invbloom/_info
@@ -59,6 +59,7 @@ int main(int argc, char *argv[])
                printf("ccan/hash\n");
                printf("ccan/short_types\n");
                printf("ccan/tal\n");
+               printf("ccan/typesafe_cb\n");
                return 0;
        }
 

diff --git a/ccan/invbloom/invbloom.c b/ccan/invbloom/invbloom.c
index 73e1825dc05d2d8e51407fa969a28d2e0fe1247c..08d83c882f8786786453c9981e34fb5c78359b76 100644 (file)
--- a/ccan/invbloom/invbloom.c
+++ b/ccan/invbloom/invbloom.c
@@ -23,6 +23,7 @@ struct invbloom *invbloom_new_(const tal_t *ctx,
                ib->n_elems = n_elems;
                ib->id_size = id_size;
                ib->salt = salt;
+               ib->singleton = NULL;
                ib->count = tal_arrz(ib, s32, n_elems);
                ib->idsum = tal_arrz(ib, u8, id_size * n_elems);
                if (!ib->count || !ib->idsum)
@@ -31,6 +32,15 @@ struct invbloom *invbloom_new_(const tal_t *ctx,
        return ib;
 }
 
+void invbloom_singleton_cb_(struct invbloom *ib,
+                           void (*cb)(struct invbloom *,
+                                      size_t bucket, void *),
+                           void *data)
+{
+       ib->singleton = cb;
+       ib->singleton_data = data;
+}
+
 static size_t hash_bucket(const struct invbloom *ib, const void *id, size_t i)
 {
        return hash((const char *)id, ib->id_size, ib->salt+i*7) % ib->n_elems;
@@ -41,6 +51,17 @@ 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)
+{
+       if (!ib->singleton)
+               return;
+
+       if (ib->count[bucket] != 1 && ib->count[bucket] != -1)
+               return;
+
+       ib->singleton(ib, bucket, ib->singleton_data);
+}
+
 static void add_to_bucket(struct invbloom *ib, size_t n, const u8 *id)
 {
        size_t i;
@@ -50,6 +71,8 @@ static void add_to_bucket(struct invbloom *ib, size_t n, const u8 *id)
 
        for (i = 0; i < ib->id_size; i++)
                idsum[i] ^= id[i];
+
+       check_for_singleton(ib, n);
 }
 
 static void remove_from_bucket(struct invbloom *ib, size_t n, const u8 *id)
@@ -60,6 +83,8 @@ static void remove_from_bucket(struct invbloom *ib, size_t n, const u8 *id)
        ib->count[n]--;
        for (i = 0; i < ib->id_size; i++)
                idsum[i] ^= id[i];
+
+       check_for_singleton(ib, n);
 }
 
 void invbloom_insert(struct invbloom *ib, const void *id)
@@ -150,11 +175,13 @@ 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++)
-               ib1->count[i] -= ib2->count[i];
-
        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);
+       }
 }
 
 bool invbloom_empty(const struct invbloom *ib)

diff --git a/ccan/invbloom/invbloom.h b/ccan/invbloom/invbloom.h
index 6306d5b84e0b8eb3c82069d8268ccfb9845d082c..d30223d2fe3e4d6f53e92c26217e3c47123bc114 100644 (file)
--- a/ccan/invbloom/invbloom.h
+++ b/ccan/invbloom/invbloom.h
@@ -2,6 +2,7 @@
 #ifndef CCAN_INVBLOOM_H
 #define CCAN_INVBLOOM_H
 #include <ccan/short_types/short_types.h>
+#include <ccan/typesafe_cb/typesafe_cb.h>
 #include <ccan/tal/tal.h>
 
 struct invbloom {
@@ -10,6 +11,8 @@ 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_data;
 };
 
 /**
@@ -27,6 +30,26 @@ struct invbloom *invbloom_new_(const tal_t *ctx,
                               size_t id_size,
                               size_t n_elems, u32 salt);
 
+/**
+ * invbloom_singleton_cb - set callback for when a singleton is found.
+ * @ib: the invertable bloom lookup table.
+ * @cb: the function to call (or NULL for none)
+ * @data: the data to hand to the function.
+ *
+ * This may be called by any function which mutates the table,
+ * possibly multiple times for a single call.  The particular
+ * @ib bucket will be consistent, but the rest of the table may
+ * not be.
+ */
+#define invbloom_singleton_cb(ib, cb, data)                    \
+       invbloom_singleton_cb_((ib),                            \
+              typesafe_cb_preargs(void, void *, (cb), (data),  \
+                                  struct invbloom *, size_t), (data))
+
+void invbloom_singleton_cb_(struct invbloom *ib,
+                           void (*cb)(struct invbloom *,
+                                      size_t bucket, void *),
+                           void *data);
 
 /**
  * invbloom_insert - add a new element

diff --git a/ccan/invbloom/test/run-singletoncb.c b/ccan/invbloom/test/run-singletoncb.c
new file mode 100644 (file)
index 0000000..2ecf71e
--- /dev/null
+++ b/ccan/invbloom/test/run-singletoncb.c
@@ -0,0 +1,65 @@
+#include <ccan/invbloom/invbloom.h>
+/* Include the C files directly. */
+#include <ccan/invbloom/invbloom.c>
+#include <ccan/tap/tap.h>
+
+static void singleton_cb(struct invbloom *ib, size_t n,
+                        unsigned *count)
+{
+       ok1(ib->count[n] == 1 || ib->count[n] == -1);
+       (*count)++;
+}      
+
+int main(void)
+{
+       struct invbloom *ib;
+       const tal_t *ctx = tal(NULL, char);
+       int val;
+       unsigned singleton_count;
+
+       /* This is how many tests you plan to run */
+       plan_tests(10 + 3 + NUM_HASHES * 2);
+
+       /* Single entry ib table keeps it simple. */
+       ib = invbloom_new(ctx, int, 1, 100);
+       invbloom_singleton_cb(ib, singleton_cb, &singleton_count);
+
+       val = 0;
+       singleton_count = 0;
+       invbloom_insert(ib, &val);
+       ok1(ib->count[0] == NUM_HASHES);
+       ok1(singleton_count == 1);
+       ok1(!invbloom_empty(ib));
+
+       /* First delete takes it via singleton. */
+       invbloom_delete(ib, &val);
+       ok1(singleton_count == 2);
+       ok1(invbloom_empty(ib));
+
+       /* Second delete creates negative singleton. */
+       invbloom_delete(ib, &val);
+       ok1(singleton_count == 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);
+
+       val = 0;
+       invbloom_insert(ib, &val);
+       ok1(singleton_count == NUM_HASHES);
+
+       /* First delete does nothing. */
+       invbloom_delete(ib, &val);
+       ok1(singleton_count == NUM_HASHES);
+       ok1(invbloom_empty(ib));
+
+       /* Second delete creates negative singletons. */
+       invbloom_delete(ib, &val);
+       ok1(singleton_count == NUM_HASHES * 2);
+
+       tal_free(ctx);
+
+       /* This exits depending on whether all tests passed */
+       return exit_status();
+}