1 /* Licensed under BSD-MIT - see LICENSE file for details */
2 #ifndef CCAN_INVBLOOM_H
3 #define CCAN_INVBLOOM_H
4 #include <ccan/short_types/short_types.h>
5 #include <ccan/typesafe_cb/typesafe_cb.h>
6 #include <ccan/tal/tal.h>
12 s32 *count; /* [n_elems] */
13 u8 *idsum; /* [n_elems][id_size] */
14 void (*singleton)(struct invbloom *ib, size_t elem, bool, void *);
19 * invbloom_new - create a new invertable bloom lookup table
20 * @ctx: context to tal() from, or NULL.
21 * @type: type to place into the buckets (must not contain padding)
22 * @n_elems: number of entries in table
23 * @salt: 32 bit seed for table
25 * Returns a new table, which can be freed with tal_free().
27 #define invbloom_new(ctx, type, n_elems, salt) \
28 invbloom_new_((ctx), sizeof(type), (n_elems), (salt))
29 struct invbloom *invbloom_new_(const tal_t *ctx,
31 size_t n_elems, u32 salt);
34 * invbloom_singleton_cb - set callback for a singleton created/destroyed.
35 * @ib: the invertable bloom lookup table.
36 * @cb: the function to call (or NULL for none)
37 * @data: the data to hand to the function.
39 * This may be called by any function which mutates the table,
40 * possibly multiple times for a single call. The particular
41 * @ib bucket will be consistent, but the rest of the table may
44 * @cb is of form "void @cb(struct invbloom *ib, size_t bucket, bool
45 * before, data)". @before is true if the call is done before the
46 * singleton in @bucket is removed (ie. ib->counts[bucket] is -1 or 1,
47 * but is about to change). @before is false if the call is done
48 * after the operation, and the bucket is now a singleton.
50 #define invbloom_singleton_cb(ib, cb, data) \
51 invbloom_singleton_cb_((ib), \
52 typesafe_cb_preargs(void, void *, (cb), (data), \
53 struct invbloom *, size_t, bool), (data))
55 void invbloom_singleton_cb_(struct invbloom *ib,
56 void (*cb)(struct invbloom *,
57 size_t bucket, bool before, void *),
61 * invbloom_insert - add a new element
62 * @ib: the invertable bloom lookup table.
65 * This is guaranteed to be the inverse of invbloom_delete.
67 void invbloom_insert(struct invbloom *ib, const void *elem);
70 * invbloom_delete - remove an element
71 * @ib: the invertable bloom lookup table.
74 * Note that this doesn't check the element was previously added (as
75 * that can not be done in general anyway).
77 * This is guaranteed to be the inverse of invbloom_delete.
79 void invbloom_delete(struct invbloom *ib, const void *elem);
82 * invbloom_get - check if an element is (probably) in the table.
83 * @ib: the invertable bloom lookup table.
86 * This may return a false negative if the table is too full.
88 * It will only return a false positive if deletions and insertions
89 * don't match, and have managed to produce a result which matches the
90 * element. This is much less likely.
92 bool invbloom_get(const struct invbloom *ib, const void *elem);
95 * invbloom_extract - try to recover an entry added to a bloom lookup table.
96 * @ctx: the context to tal() the return value from.
97 * @ib: the invertable bloom lookup table.
99 * This may be able to recover (and delete) an element which was
100 * invbloom_insert()ed into the table (and not deleted). This will
101 * not work if the table is too full.
103 * It may return a bogus element if deletions and insertions don't
106 void *invbloom_extract(const tal_t *ctx, struct invbloom *ib);
109 * invbloom_extract_negative - try to recover an entry deleted from a bloom lookup table.
110 * @ctx: the context to tal() the return value from.
111 * @ib: the invertable bloom lookup table.
113 * This may be able to recover (and insert/undo) an element which was
114 * invbloom_delete()ed from the table (and not inserted). This will
115 * not work if the table is too full.
117 * It may return a bogus element if deletions and insertions don't
120 void *invbloom_extract_negative(const tal_t *ctx, struct invbloom *ib);
123 * invbloom_subtract - return the differences of two IBLTs.
124 * @ib1: the invertable bloom lookup table to alter
125 * @ib2: the invertable bloom lookup table to subtract.
127 * This produces exactly the same result as if a new table had all the
128 * elements only in @ib1 inserted, then all the elements onlt in @ib2
131 * ie. if @ib1 and @ib2 are similar, the result may be a usable by
132 * invbloom_extract and invbloom_extract_negative.
134 void invbloom_subtract(struct invbloom *ib1, const struct invbloom *ib2);
137 * invbloom_empty - is an invertable bloom lookup table completely clean?
138 * @ib: the invertable bloom lookup table
140 * This is always true if @ib has had the same elements inserted and
141 * deleted. It is far less likely to be true if different ones were
142 * deleted than inserted.
144 bool invbloom_empty(const struct invbloom *ib);
145 #endif /* CCAN_INVBLOOM_H */