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

[ccan] / ccan / invbloom / invbloom.c

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)