summaryrefslogtreecommitdiff
path: root/src/block/bg_bf.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/block/bg_bf.c')
-rw-r--r--src/block/bg_bf.c120
1 files changed, 59 insertions, 61 deletions
diff --git a/src/block/bg_bf.c b/src/block/bg_bf.c
index 20aa59bbc..9814a28ec 100644
--- a/src/block/bg_bf.c
+++ b/src/block/bg_bf.c
@@ -11,12 +11,12 @@
11 WITHOUT ANY WARRANTY; without even the implied warranty of 11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Affero General Public License for more details. 13 Affero General Public License for more details.
14 14
15 You should have received a copy of the GNU Affero General Public License 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/>. 16 along with this program. If not, see <http://www.gnu.org/licenses/>.
17 17
18 SPDX-License-Identifier: AGPL3.0-or-later 18 SPDX-License-Identifier: AGPL3.0-or-later
19*/ 19 */
20/** 20/**
21 * @file block/bg_bf.c 21 * @file block/bg_bf.c
22 * @brief implementation of a block group using a Bloom filter 22 * @brief implementation of a block group using a Bloom filter
@@ -32,8 +32,7 @@
32/** 32/**
33 * Internal data structure for a block group. 33 * Internal data structure for a block group.
34 */ 34 */
35struct BfGroupInternals 35struct BfGroupInternals {
36{
37 /** 36 /**
38 * A Bloom filter to weed out duplicate replies probabilistically. 37 * A Bloom filter to weed out duplicate replies probabilistically.
39 */ 38 */
@@ -48,7 +47,6 @@ struct BfGroupInternals
48 * Size of @a bf. 47 * Size of @a bf.
49 */ 48 */
50 uint32_t bf_size; 49 uint32_t bf_size;
51
52}; 50};
53 51
54 52
@@ -63,24 +61,24 @@ struct BfGroupInternals
63 * supported, #GNUNET_SYSERR on error 61 * supported, #GNUNET_SYSERR on error
64 */ 62 */
65static int 63static int
66bf_group_serialize_cb (struct GNUNET_BLOCK_Group *bg, 64bf_group_serialize_cb(struct GNUNET_BLOCK_Group *bg,
67 uint32_t *nonce, 65 uint32_t *nonce,
68 void **raw_data, 66 void **raw_data,
69 size_t *raw_data_size) 67 size_t *raw_data_size)
70{ 68{
71 struct BfGroupInternals *gi = bg->internal_cls; 69 struct BfGroupInternals *gi = bg->internal_cls;
72 char *raw; 70 char *raw;
73 71
74 raw = GNUNET_malloc (gi->bf_size); 72 raw = GNUNET_malloc(gi->bf_size);
75 if (GNUNET_OK != 73 if (GNUNET_OK !=
76 GNUNET_CONTAINER_bloomfilter_get_raw_data (gi->bf, 74 GNUNET_CONTAINER_bloomfilter_get_raw_data(gi->bf,
77 raw, 75 raw,
78 gi->bf_size)) 76 gi->bf_size))
79 { 77 {
80 GNUNET_free (raw); 78 GNUNET_free(raw);
81 GNUNET_break (0); 79 GNUNET_break(0);
82 return GNUNET_SYSERR; 80 return GNUNET_SYSERR;
83 } 81 }
84 *nonce = gi->bf_mutator; 82 *nonce = gi->bf_mutator;
85 *raw_data = raw; 83 *raw_data = raw;
86 *raw_data_size = gi->bf_size; 84 *raw_data_size = gi->bf_size;
@@ -97,22 +95,22 @@ bf_group_serialize_cb (struct GNUNET_BLOCK_Group *bg,
97 * @param seen_results_count number of entries in @a seen_results 95 * @param seen_results_count number of entries in @a seen_results
98 */ 96 */
99static void 97static void
100bf_group_mark_seen_cb (struct GNUNET_BLOCK_Group *bg, 98bf_group_mark_seen_cb(struct GNUNET_BLOCK_Group *bg,
101 const struct GNUNET_HashCode *seen_results, 99 const struct GNUNET_HashCode *seen_results,
102 unsigned int seen_results_count) 100 unsigned int seen_results_count)
103{ 101{
104 struct BfGroupInternals *gi = bg->internal_cls; 102 struct BfGroupInternals *gi = bg->internal_cls;
105 103
106 for (unsigned int i=0;i<seen_results_count;i++) 104 for (unsigned int i = 0; i < seen_results_count; i++)
107 { 105 {
108 struct GNUNET_HashCode mhash; 106 struct GNUNET_HashCode mhash;
109 107
110 GNUNET_BLOCK_mingle_hash (&seen_results[i], 108 GNUNET_BLOCK_mingle_hash(&seen_results[i],
111 gi->bf_mutator, 109 gi->bf_mutator,
112 &mhash); 110 &mhash);
113 GNUNET_CONTAINER_bloomfilter_add (gi->bf, 111 GNUNET_CONTAINER_bloomfilter_add(gi->bf,
114 &mhash); 112 &mhash);
115 } 113 }
116} 114}
117 115
118 116
@@ -126,8 +124,8 @@ bf_group_mark_seen_cb (struct GNUNET_BLOCK_Group *bg,
126 * we failed. 124 * we failed.
127 */ 125 */
128static int 126static int
129bf_group_merge_cb (struct GNUNET_BLOCK_Group *bg1, 127bf_group_merge_cb(struct GNUNET_BLOCK_Group *bg1,
130 const struct GNUNET_BLOCK_Group *bg2) 128 const struct GNUNET_BLOCK_Group *bg2)
131{ 129{
132 struct BfGroupInternals *gi1 = bg1->internal_cls; 130 struct BfGroupInternals *gi1 = bg1->internal_cls;
133 struct BfGroupInternals *gi2 = bg2->internal_cls; 131 struct BfGroupInternals *gi2 = bg2->internal_cls;
@@ -136,8 +134,8 @@ bf_group_merge_cb (struct GNUNET_BLOCK_Group *bg1,
136 return GNUNET_NO; 134 return GNUNET_NO;
137 if (gi1->bf_size != gi2->bf_size) 135 if (gi1->bf_size != gi2->bf_size)
138 return GNUNET_NO; 136 return GNUNET_NO;
139 GNUNET_CONTAINER_bloomfilter_or2 (gi1->bf, 137 GNUNET_CONTAINER_bloomfilter_or2(gi1->bf,
140 gi2->bf); 138 gi2->bf);
141 return GNUNET_OK; 139 return GNUNET_OK;
142} 140}
143 141
@@ -148,13 +146,13 @@ bf_group_merge_cb (struct GNUNET_BLOCK_Group *bg1,
148 * @param bg group to destroy, NULL is allowed 146 * @param bg group to destroy, NULL is allowed
149 */ 147 */
150static void 148static void
151bf_group_destroy_cb (struct GNUNET_BLOCK_Group *bg) 149bf_group_destroy_cb(struct GNUNET_BLOCK_Group *bg)
152{ 150{
153 struct BfGroupInternals *gi = bg->internal_cls; 151 struct BfGroupInternals *gi = bg->internal_cls;
154 152
155 GNUNET_CONTAINER_bloomfilter_free (gi->bf); 153 GNUNET_CONTAINER_bloomfilter_free(gi->bf);
156 GNUNET_free (gi); 154 GNUNET_free(gi);
157 GNUNET_free (bg); 155 GNUNET_free(bg);
158} 156}
159 157
160 158
@@ -172,24 +170,24 @@ bf_group_destroy_cb (struct GNUNET_BLOCK_Group *bg)
172 * by this @a type of block (this is not an error) 170 * by this @a type of block (this is not an error)
173 */ 171 */
174struct GNUNET_BLOCK_Group * 172struct GNUNET_BLOCK_Group *
175GNUNET_BLOCK_GROUP_bf_create (void *cls, 173GNUNET_BLOCK_GROUP_bf_create(void *cls,
176 size_t bf_size, 174 size_t bf_size,
177 unsigned int bf_k, 175 unsigned int bf_k,
178 enum GNUNET_BLOCK_Type type, 176 enum GNUNET_BLOCK_Type type,
179 uint32_t nonce, 177 uint32_t nonce,
180 const void *raw_data, 178 const void *raw_data,
181 size_t raw_data_size) 179 size_t raw_data_size)
182{ 180{
183 struct BfGroupInternals *gi; 181 struct BfGroupInternals *gi;
184 struct GNUNET_BLOCK_Group *bg; 182 struct GNUNET_BLOCK_Group *bg;
185 183
186 gi = GNUNET_new (struct BfGroupInternals); 184 gi = GNUNET_new(struct BfGroupInternals);
187 gi->bf = GNUNET_CONTAINER_bloomfilter_init ((bf_size != raw_data_size) ? NULL : raw_data, 185 gi->bf = GNUNET_CONTAINER_bloomfilter_init((bf_size != raw_data_size) ? NULL : raw_data,
188 bf_size, 186 bf_size,
189 bf_k); 187 bf_k);
190 gi->bf_mutator = nonce; 188 gi->bf_mutator = nonce;
191 gi->bf_size = bf_size; 189 gi->bf_size = bf_size;
192 bg = GNUNET_new (struct GNUNET_BLOCK_Group); 190 bg = GNUNET_new(struct GNUNET_BLOCK_Group);
193 bg->type = type; 191 bg->type = type;
194 bg->serialize_cb = &bf_group_serialize_cb; 192 bg->serialize_cb = &bf_group_serialize_cb;
195 bg->mark_seen_cb = &bf_group_mark_seen_cb; 193 bg->mark_seen_cb = &bf_group_mark_seen_cb;
@@ -211,8 +209,8 @@ GNUNET_BLOCK_GROUP_bf_create (void *cls,
211 * #GNUNET_NO if @a hc was definitively not in @bg (but now is) 209 * #GNUNET_NO if @a hc was definitively not in @bg (but now is)
212 */ 210 */
213int 211int
214GNUNET_BLOCK_GROUP_bf_test_and_set (struct GNUNET_BLOCK_Group *bg, 212GNUNET_BLOCK_GROUP_bf_test_and_set(struct GNUNET_BLOCK_Group *bg,
215 const struct GNUNET_HashCode *hc) 213 const struct GNUNET_HashCode *hc)
216{ 214{
217 struct BfGroupInternals *gi; 215 struct BfGroupInternals *gi;
218 struct GNUNET_HashCode mhash; 216 struct GNUNET_HashCode mhash;
@@ -220,15 +218,15 @@ GNUNET_BLOCK_GROUP_bf_test_and_set (struct GNUNET_BLOCK_Group *bg,
220 if (NULL == bg) 218 if (NULL == bg)
221 return GNUNET_NO; 219 return GNUNET_NO;
222 gi = bg->internal_cls; 220 gi = bg->internal_cls;
223 GNUNET_BLOCK_mingle_hash (hc, 221 GNUNET_BLOCK_mingle_hash(hc,
224 gi->bf_mutator, 222 gi->bf_mutator,
225 &mhash); 223 &mhash);
226 if (GNUNET_YES == 224 if (GNUNET_YES ==
227 GNUNET_CONTAINER_bloomfilter_test (gi->bf, 225 GNUNET_CONTAINER_bloomfilter_test(gi->bf,
228 &mhash)) 226 &mhash))
229 return GNUNET_YES; 227 return GNUNET_YES;
230 GNUNET_CONTAINER_bloomfilter_add (gi->bf, 228 GNUNET_CONTAINER_bloomfilter_add(gi->bf,
231 &mhash); 229 &mhash);
232 return GNUNET_NO; 230 return GNUNET_NO;
233} 231}
234 232
@@ -247,8 +245,8 @@ GNUNET_BLOCK_GROUP_bf_test_and_set (struct GNUNET_BLOCK_Group *bg,
247 * @return must be a power of two and smaller or equal to 2^15. 245 * @return must be a power of two and smaller or equal to 2^15.
248 */ 246 */
249size_t 247size_t
250GNUNET_BLOCK_GROUP_compute_bloomfilter_size (unsigned int entry_count, 248GNUNET_BLOCK_GROUP_compute_bloomfilter_size(unsigned int entry_count,
251 unsigned int k) 249 unsigned int k)
252{ 250{
253 size_t size; 251 size_t size;
254 unsigned int ideal = (entry_count * k) / 4; 252 unsigned int ideal = (entry_count * k) / 4;