aboutsummaryrefslogtreecommitdiff
path: root/src/setu/ibf.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/setu/ibf.h')
-rw-r--r--src/setu/ibf.h255
1 files changed, 255 insertions, 0 deletions
diff --git a/src/setu/ibf.h b/src/setu/ibf.h
new file mode 100644
index 000000000..7c2ab33b1
--- /dev/null
+++ b/src/setu/ibf.h
@@ -0,0 +1,255 @@
1/*
2 This file is part of GNUnet
3 Copyright (C) 2012 GNUnet e.V.
4
5 GNUnet is free software: you can redistribute it and/or modify it
6 under the terms of the GNU Affero General Public License as published
7 by the Free Software Foundation, either version 3 of the License,
8 or (at your option) any later version.
9
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Affero General Public License for more details.
14
15 You should have received a copy of the GNU Affero General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
17
18 SPDX-License-Identifier: AGPL3.0-or-later
19 */
20
21/**
22 * @file set/ibf.h
23 * @brief invertible bloom filter
24 * @author Florian Dold
25 */
26
27#ifndef GNUNET_CONSENSUS_IBF_H
28#define GNUNET_CONSENSUS_IBF_H
29
30#include "platform.h"
31#include "gnunet_util_lib.h"
32
33#ifdef __cplusplus
34extern "C"
35{
36#if 0 /* keep Emacsens' auto-indent happy */
37}
38#endif
39#endif
40
41
42/**
43 * Keys that can be inserted into and removed from an IBF.
44 */
45struct IBF_Key
46{
47 uint64_t key_val;
48};
49
50
51/**
52 * Hash of an IBF key.
53 */
54struct IBF_KeyHash
55{
56 uint32_t key_hash_val;
57};
58
59
60/**
61 * Type of the count field of IBF buckets.
62 */
63struct IBF_Count
64{
65 int8_t count_val;
66};
67
68
69/**
70 * Size of one ibf bucket in bytes
71 */
72#define IBF_BUCKET_SIZE (sizeof(struct IBF_Count) + sizeof(struct IBF_Key) \
73 + sizeof(struct IBF_KeyHash))
74
75
76/**
77 * Invertible bloom filter (IBF).
78 *
79 * An IBF is a counting bloom filter that has the ability to restore
80 * the hashes of its stored elements with high probability.
81 */
82struct InvertibleBloomFilter
83{
84 /**
85 * How many cells does this IBF have?
86 */
87 uint32_t size;
88
89 /**
90 * In how many cells do we hash one element?
91 * Usually 4 or 3.
92 */
93 uint8_t hash_num;
94
95 /**
96 * Xor sums of the elements' keys, used to identify the elements.
97 * Array of 'size' elements.
98 */
99 struct IBF_Key *key_sum;
100
101 /**
102 * Xor sums of the hashes of the keys of inserted elements.
103 * Array of 'size' elements.
104 */
105 struct IBF_KeyHash *key_hash_sum;
106
107 /**
108 * How many times has a bucket been hit?
109 * Can be negative, as a result of IBF subtraction.
110 * Array of 'size' elements.
111 */
112 struct IBF_Count *count;
113};
114
115
116/**
117 * Write buckets from an ibf to a buffer.
118 * Exactly (IBF_BUCKET_SIZE*ibf->size) bytes are written to buf.
119 *
120 * @param ibf the ibf to write
121 * @param start with which bucket to start
122 * @param count how many buckets to write
123 * @param buf buffer to write the data to
124 */
125void
126ibf_write_slice (const struct InvertibleBloomFilter *ibf,
127 uint32_t start,
128 uint32_t count,
129 void *buf);
130
131
132/**
133 * Read buckets from a buffer into an ibf.
134 *
135 * @param buf pointer to the buffer to read from
136 * @param start which bucket to start at
137 * @param count how many buckets to read
138 * @param ibf the ibf to write to
139 */
140void
141ibf_read_slice (const void *buf,
142 uint32_t start,
143 uint32_t count,
144 struct InvertibleBloomFilter *ibf);
145
146
147/**
148 * Create a key from a hashcode.
149 *
150 * @param hash the hashcode
151 * @return a key
152 */
153struct IBF_Key
154ibf_key_from_hashcode (const struct GNUNET_HashCode *hash);
155
156
157/**
158 * Create a hashcode from a key, by replicating the key
159 * until the hascode is filled
160 *
161 * @param key the key
162 * @param dst hashcode to store the result in
163 */
164void
165ibf_hashcode_from_key (struct IBF_Key key, struct GNUNET_HashCode *dst);
166
167
168/**
169 * Create an invertible bloom filter.
170 *
171 * @param size number of IBF buckets
172 * @param hash_num number of buckets one element is hashed in, usually 3 or 4
173 * @return the newly created invertible bloom filter, NULL on error
174 */
175struct InvertibleBloomFilter *
176ibf_create (uint32_t size, uint8_t hash_num);
177
178
179/**
180 * Insert a key into an IBF.
181 *
182 * @param ibf the IBF
183 * @param key the element's hash code
184 */
185void
186ibf_insert (struct InvertibleBloomFilter *ibf, struct IBF_Key key);
187
188
189/**
190 * Remove a key from an IBF.
191 *
192 * @param ibf the IBF
193 * @param key the element's hash code
194 */
195void
196ibf_remove (struct InvertibleBloomFilter *ibf, struct IBF_Key key);
197
198
199/**
200 * Subtract ibf2 from ibf1, storing the result in ibf1.
201 * The two IBF's must have the same parameters size and hash_num.
202 *
203 * @param ibf1 IBF that is subtracted from
204 * @param ibf2 IBF that will be subtracted from ibf1
205 */
206void
207ibf_subtract (struct InvertibleBloomFilter *ibf1,
208 const struct InvertibleBloomFilter *ibf2);
209
210
211/**
212 * Decode and remove an element from the IBF, if possible.
213 *
214 * @param ibf the invertible bloom filter to decode
215 * @param ret_side sign of the cell's count where the decoded element came from.
216 * A negative sign indicates that the element was recovered
217 * resides in an IBF that was previously subtracted from.
218 * @param ret_id receives the hash code of the decoded element, if successful
219 * @return #GNUNET_YES if decoding an element was successful,
220 * #GNUNET_NO if the IBF is empty,
221 * #GNUNET_SYSERR if the decoding has failed
222 */
223int
224ibf_decode (struct InvertibleBloomFilter *ibf,
225 int *ret_side,
226 struct IBF_Key *ret_id);
227
228
229/**
230 * Create a copy of an IBF, the copy has to be destroyed properly.
231 *
232 * @param ibf the IBF to copy
233 */
234struct InvertibleBloomFilter *
235ibf_dup (const struct InvertibleBloomFilter *ibf);
236
237
238/**
239 * Destroy all resources associated with the invertible bloom filter.
240 * No more ibf_*-functions may be called on ibf after calling destroy.
241 *
242 * @param ibf the intertible bloom filter to destroy
243 */
244void
245ibf_destroy (struct InvertibleBloomFilter *ibf);
246
247
248#if 0 /* keep Emacsens' auto-indent happy */
249{
250#endif
251#ifdef __cplusplus
252}
253#endif
254
255#endif