X-Git-Url: http://git.ozlabs.org/?a=blobdiff_plain;f=ccan%2Finvbloom%2Finvbloom.c;h=d34ec1feeadded58b431be5e8aaa70bf9bc748ff;hb=8ad6ab9ce9b78c6b28b727b11d571d11856479c6;hp=73e1825dc05d2d8e51407fa969a28d2e0fe1247c;hpb=49bb40e9615ada5a3e0d06bc45613744f441895c;p=ccan

diff --git a/ccan/invbloom/invbloom.c b/ccan/invbloom/invbloom.c
index 73e1825d..d34ec1fe 100644
--- 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)