printf("ccan/hash\n");
printf("ccan/short_types\n");
printf("ccan/tal\n");
+ printf("ccan/typesafe_cb\n");
return 0;
}
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)
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)
#ifndef CCAN_INVBLOOM_H
#define CCAN_INVBLOOM_H
#include <ccan/short_types/short_types.h>
+#include <ccan/typesafe_cb/typesafe_cb.h>
#include <ccan/tal/tal.h>
struct invbloom {
size_t n_elems;
size_t id_size;
- u32 hashsum_bytes; /* 0 - 4. */
u32 salt;
s32 *count; /* [n_elems] */
u8 *idsum; /* [n_elems][id_size] */
+ void (*singleton)(struct invbloom *ib, size_t elem, bool, void *);
+ void *singleton_data;
};
/**
size_t id_size,
size_t n_elems, u32 salt);
+/**
+ * invbloom_singleton_cb - set callback for a singleton created/destroyed.
+ * @ib: the invertable bloom lookup table.
+ * @cb: the function to call (or NULL for none)
+ * @data: the data to hand to the function.
+ *
+ * This may be called by any function which mutates the table,
+ * possibly multiple times for a single call. The particular
+ * @ib bucket will be consistent, but the rest of the table may
+ * not be.
+ *
+ * @cb is of form "void @cb(struct invbloom *ib, size_t bucket, bool
+ * before, data)". @before is true if the call is done before the
+ * singleton in @bucket is removed (ie. ib->counts[bucket] is -1 or 1,
+ * but is about to change). @before is false if the call is done
+ * after the operation, and the bucket is now a singleton.
+ */
+#define invbloom_singleton_cb(ib, cb, data) \
+ invbloom_singleton_cb_((ib), \
+ typesafe_cb_preargs(void, void *, (cb), (data), \
+ struct invbloom *, size_t, bool), (data))
+
+void invbloom_singleton_cb_(struct invbloom *ib,
+ void (*cb)(struct invbloom *,
+ size_t bucket, bool before, void *),
+ void *data);
/**
* invbloom_insert - add a new element
--- /dev/null
+#include <ccan/invbloom/invbloom.h>
+/* Include the C files directly. */
+#include <ccan/invbloom/invbloom.c>
+#include <ccan/tap/tap.h>
+
+static void singleton_cb(struct invbloom *ib, size_t n, bool before,
+ unsigned *count)
+{
+ ok1(ib->count[n] == 1 || ib->count[n] == -1);
+ count[before]++;
+}
+
+int main(void)
+{
+ struct invbloom *ib;
+ const tal_t *ctx = tal(NULL, char);
+ int val;
+ unsigned singleton_count[2];
+
+ /* This is how many tests you plan to run */
+ plan_tests(16 + 6 + NUM_HASHES * 3);
+
+ /* Single entry ib table keeps it simple. */
+ ib = invbloom_new(ctx, int, 1, 100);
+ invbloom_singleton_cb(ib, singleton_cb, singleton_count);
+
+ val = 0;
+ singleton_count[false] = singleton_count[true] = 0;
+ invbloom_insert(ib, &val);
+ ok1(ib->count[0] == NUM_HASHES);
+ ok1(singleton_count[true] == 1);
+ ok1(singleton_count[false] == 1);
+ ok1(!invbloom_empty(ib));
+
+ /* First delete takes it via singleton. */
+ invbloom_delete(ib, &val);
+ ok1(singleton_count[true] == 2);
+ ok1(singleton_count[false] == 2);
+ ok1(invbloom_empty(ib));
+
+ /* Second delete creates negative singleton. */
+ invbloom_delete(ib, &val);
+ ok1(singleton_count[true] == 3);
+ ok1(singleton_count[false] == 3);
+
+ /* Now a larger table: this seed set so entries don't clash */
+ ib = invbloom_new(ctx, int, 1024, 0);
+ singleton_count[false] = singleton_count[true] = 0;
+ invbloom_singleton_cb(ib, singleton_cb, singleton_count);
+
+ val = 0;
+ invbloom_insert(ib, &val);
+ ok1(singleton_count[true] == 0);
+ ok1(singleton_count[false] == NUM_HASHES);
+
+ /* First delete removes singletons. */
+ invbloom_delete(ib, &val);
+ ok1(singleton_count[true] == NUM_HASHES);
+ ok1(singleton_count[false] == NUM_HASHES);
+ ok1(invbloom_empty(ib));
+
+ /* Second delete creates negative singletons. */
+ invbloom_delete(ib, &val);
+ ok1(singleton_count[true] == NUM_HASHES);
+ ok1(singleton_count[false] == NUM_HASHES * 2);
+
+ tal_free(ctx);
+
+ /* This exits depending on whether all tests passed */
+ return exit_status();
+}
projects / ccan / commitdiff