X-Git-Url: https://git.ozlabs.org/?a=blobdiff_plain;f=ccan%2Finvbloom%2Finvbloom.c;h=d34ec1feeadded58b431be5e8aaa70bf9bc748ff;hb=ee77e470b467cf85dc533cee8c08e08bd4c9be06;hp=08d83c882f8786786453c9981e34fb5c78359b76;hpb=d92975243f4975a08d6581a2f9cf8091a0695e04;p=ccan

diff --git a/ccan/invbloom/invbloom.c b/ccan/invbloom/invbloom.c
index 08d83c88..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,
@@ -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)
@@ -141,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;
@@ -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);
 	}
 }