tal: rename tal_dup to tal_dup_arr, make tal_dup simpler.

[ccan] / ccan / invbloom / invbloom.c

diff --git a/ccan/invbloom/invbloom.c b/ccan/invbloom/invbloom.c
index 73e1825dc05d2d8e51407fa969a28d2e0fe1247c..d34ec1feeadded58b431be5e8aaa70bf9bc748ff 100644 (file)
--- a/ccan/invbloom/invbloom.c
+++ b/ccan/invbloom/invbloom.c
@@ -10,7 +10,7 @@
 
        Eppstein, David, et al. "What's the difference?: efficient set reconciliation without prior context." ACM SIGCOMM Computer Communication Review. Vol. 41. No. 4. ACM, 2011. http://conferences.sigcomm.org/sigcomm/2011/papers/sigcomm/p218.pdf
 */
-#define NUM_HASHES 4
+#define NUM_HASHES 3
 
 struct invbloom *invbloom_new_(const tal_t *ctx,
                               size_t id_size,
@@ -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, bool, 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,15 +51,30 @@ 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, bool before)
+{
+       if (!ib->singleton)
+               return;
+
+       if (ib->count[bucket] != 1 && ib->count[bucket] != -1)
+               return;
+
+       ib->singleton(ib, bucket, before, ib->singleton_data);
+}
+
 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, false);
 }
 
 static void remove_from_bucket(struct invbloom *ib, size_t n, const u8 *id)
@@ -57,9 +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, false);
 }
 
 void invbloom_insert(struct invbloom *ib, const void *id)
@@ -116,7 +145,7 @@ static void *extract(const tal_t *ctx, struct invbloom *ib, int count)
                if (ib->count[i] != count)
                        continue;
 
-               id = tal_dup(ctx, u8, idsum_ptr(ib, i), ib->id_size, 0);
+               id = tal_dup_arr(ctx, u8, idsum_ptr(ib, i), ib->id_size, 0);
                return id;
        }
        return NULL;
@@ -151,10 +180,15 @@ void invbloom_subtract(struct invbloom *ib1, const struct invbloom *ib2)
        assert(ib1->salt == ib2->salt);
 
        for (i = 0; i < ib1->n_elems; i++)
-               ib1->count[i] -= ib2->count[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, false);
+       }
 }
 
 bool invbloom_empty(const struct invbloom *ib)