1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
/* Licensed under BSD-MIT - see LICENSE file for details */
#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 salt;
s32 *count; /* [n_elems] */
u8 *idsum; /* [n_elems][id_size] */
void (*singleton)(struct invbloom *ib, size_t elem, bool, void *);
void *singleton_data;
};
/**
* invbloom_new - create a new invertable bloom lookup table
* @ctx: context to tal() from, or NULL.
* @type: type to place into the buckets (must not contain padding)
* @n_elems: number of entries in table
* @salt: 32 bit seed for table
*
* Returns a new table, which can be freed with tal_free().
*/
#define invbloom_new(ctx, type, n_elems, salt) \
invbloom_new_((ctx), sizeof(type), (n_elems), (salt))
struct invbloom *invbloom_new_(const tal_t *ctx,
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
* @ib: the invertable bloom lookup table.
* @elem: the element
*
* This is guaranteed to be the inverse of invbloom_delete.
*/
void invbloom_insert(struct invbloom *ib, const void *elem);
/**
* invbloom_delete - remove an element
* @ib: the invertable bloom lookup table.
* @elem: the element
*
* Note that this doesn't check the element was previously added (as
* that can not be done in general anyway).
*
* This is guaranteed to be the inverse of invbloom_delete.
*/
void invbloom_delete(struct invbloom *ib, const void *elem);
/**
* invbloom_get - check if an element is (probably) in the table.
* @ib: the invertable bloom lookup table.
* @elem: the element
*
* This may return a false negative if the table is too full.
*
* It will only return a false positive if deletions and insertions
* don't match, and have managed to produce a result which matches the
* element. This is much less likely.
*/
bool invbloom_get(const struct invbloom *ib, const void *elem);
/**
* invbloom_extract - try to recover an entry added to a bloom lookup table.
* @ctx: the context to tal() the return value from.
* @ib: the invertable bloom lookup table.
*
* This may be able to recover (and delete) an element which was
* invbloom_insert()ed into the table (and not deleted). This will
* not work if the table is too full.
*
* It may return a bogus element if deletions and insertions don't
* match.
*/
void *invbloom_extract(const tal_t *ctx, struct invbloom *ib);
/**
* invbloom_extract_negative - try to recover an entry deleted from a bloom lookup table.
* @ctx: the context to tal() the return value from.
* @ib: the invertable bloom lookup table.
*
* This may be able to recover (and insert/undo) an element which was
* invbloom_delete()ed from the table (and not inserted). This will
* not work if the table is too full.
*
* It may return a bogus element if deletions and insertions don't
* match.
*/
void *invbloom_extract_negative(const tal_t *ctx, struct invbloom *ib);
/**
* invbloom_subtract - return the differences of two IBLTs.
* @ib1: the invertable bloom lookup table to alter
* @ib2: the invertable bloom lookup table to subtract.
*
* This produces exactly the same result as if a new table had all the
* elements only in @ib1 inserted, then all the elements onlt in @ib2
* deleted.
*
* ie. if @ib1 and @ib2 are similar, the result may be a usable by
* invbloom_extract and invbloom_extract_negative.
*/
void invbloom_subtract(struct invbloom *ib1, const struct invbloom *ib2);
/**
* invbloom_empty - is an invertable bloom lookup table completely clean?
* @ib: the invertable bloom lookup table
*
* This is always true if @ib has had the same elements inserted and
* deleted. It is far less likely to be true if different ones were
* deleted than inserted.
*/
bool invbloom_empty(const struct invbloom *ib);
#endif /* CCAN_INVBLOOM_H */
|
