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,
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)
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;
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)
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)
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;
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)