aboutsummaryrefslogtreecommitdiff
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.c116
1 files changed, 59 insertions, 57 deletions
diff --git a/src/block/bg_bf.c b/src/block/bg_bf.c
index 9814a28ec..ae8ee0e51 100644
--- a/src/block/bg_bf.c
+++ b/src/block/bg_bf.c
@@ -32,7 +32,8 @@
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{
36 /** 37 /**
37 * A Bloom filter to weed out duplicate replies probabilistically. 38 * A Bloom filter to weed out duplicate replies probabilistically.
38 */ 39 */
@@ -61,24 +62,24 @@ struct BfGroupInternals {
61 * supported, #GNUNET_SYSERR on error 62 * supported, #GNUNET_SYSERR on error
62 */ 63 */
63static int 64static int
64bf_group_serialize_cb(struct GNUNET_BLOCK_Group *bg, 65bf_group_serialize_cb (struct GNUNET_BLOCK_Group *bg,
65 uint32_t *nonce, 66 uint32_t *nonce,
66 void **raw_data, 67 void **raw_data,
67 size_t *raw_data_size) 68 size_t *raw_data_size)
68{ 69{
69 struct BfGroupInternals *gi = bg->internal_cls; 70 struct BfGroupInternals *gi = bg->internal_cls;
70 char *raw; 71 char *raw;
71 72
72 raw = GNUNET_malloc(gi->bf_size); 73 raw = GNUNET_malloc (gi->bf_size);
73 if (GNUNET_OK != 74 if (GNUNET_OK !=
74 GNUNET_CONTAINER_bloomfilter_get_raw_data(gi->bf, 75 GNUNET_CONTAINER_bloomfilter_get_raw_data (gi->bf,
75 raw, 76 raw,
76 gi->bf_size)) 77 gi->bf_size))
77 { 78 {
78 GNUNET_free(raw); 79 GNUNET_free (raw);
79 GNUNET_break(0); 80 GNUNET_break (0);
80 return GNUNET_SYSERR; 81 return GNUNET_SYSERR;
81 } 82 }
82 *nonce = gi->bf_mutator; 83 *nonce = gi->bf_mutator;
83 *raw_data = raw; 84 *raw_data = raw;
84 *raw_data_size = gi->bf_size; 85 *raw_data_size = gi->bf_size;
@@ -95,22 +96,22 @@ bf_group_serialize_cb(struct GNUNET_BLOCK_Group *bg,
95 * @param seen_results_count number of entries in @a seen_results 96 * @param seen_results_count number of entries in @a seen_results
96 */ 97 */
97static void 98static void
98bf_group_mark_seen_cb(struct GNUNET_BLOCK_Group *bg, 99bf_group_mark_seen_cb (struct GNUNET_BLOCK_Group *bg,
99 const struct GNUNET_HashCode *seen_results, 100 const struct GNUNET_HashCode *seen_results,
100 unsigned int seen_results_count) 101 unsigned int seen_results_count)
101{ 102{
102 struct BfGroupInternals *gi = bg->internal_cls; 103 struct BfGroupInternals *gi = bg->internal_cls;
103 104
104 for (unsigned int i = 0; i < seen_results_count; i++) 105 for (unsigned int i = 0; i < seen_results_count; i++)
105 { 106 {
106 struct GNUNET_HashCode mhash; 107 struct GNUNET_HashCode mhash;
107 108
108 GNUNET_BLOCK_mingle_hash(&seen_results[i], 109 GNUNET_BLOCK_mingle_hash (&seen_results[i],
109 gi->bf_mutator, 110 gi->bf_mutator,
110 &mhash); 111 &mhash);
111 GNUNET_CONTAINER_bloomfilter_add(gi->bf, 112 GNUNET_CONTAINER_bloomfilter_add (gi->bf,
112 &mhash); 113 &mhash);
113 } 114 }
114} 115}
115 116
116 117
@@ -124,8 +125,8 @@ bf_group_mark_seen_cb(struct GNUNET_BLOCK_Group *bg,
124 * we failed. 125 * we failed.
125 */ 126 */
126static int 127static int
127bf_group_merge_cb(struct GNUNET_BLOCK_Group *bg1, 128bf_group_merge_cb (struct GNUNET_BLOCK_Group *bg1,
128 const struct GNUNET_BLOCK_Group *bg2) 129 const struct GNUNET_BLOCK_Group *bg2)
129{ 130{
130 struct BfGroupInternals *gi1 = bg1->internal_cls; 131 struct BfGroupInternals *gi1 = bg1->internal_cls;
131 struct BfGroupInternals *gi2 = bg2->internal_cls; 132 struct BfGroupInternals *gi2 = bg2->internal_cls;
@@ -134,8 +135,8 @@ bf_group_merge_cb(struct GNUNET_BLOCK_Group *bg1,
134 return GNUNET_NO; 135 return GNUNET_NO;
135 if (gi1->bf_size != gi2->bf_size) 136 if (gi1->bf_size != gi2->bf_size)
136 return GNUNET_NO; 137 return GNUNET_NO;
137 GNUNET_CONTAINER_bloomfilter_or2(gi1->bf, 138 GNUNET_CONTAINER_bloomfilter_or2 (gi1->bf,
138 gi2->bf); 139 gi2->bf);
139 return GNUNET_OK; 140 return GNUNET_OK;
140} 141}
141 142
@@ -146,13 +147,13 @@ bf_group_merge_cb(struct GNUNET_BLOCK_Group *bg1,
146 * @param bg group to destroy, NULL is allowed 147 * @param bg group to destroy, NULL is allowed
147 */ 148 */
148static void 149static void
149bf_group_destroy_cb(struct GNUNET_BLOCK_Group *bg) 150bf_group_destroy_cb (struct GNUNET_BLOCK_Group *bg)
150{ 151{
151 struct BfGroupInternals *gi = bg->internal_cls; 152 struct BfGroupInternals *gi = bg->internal_cls;
152 153
153 GNUNET_CONTAINER_bloomfilter_free(gi->bf); 154 GNUNET_CONTAINER_bloomfilter_free (gi->bf);
154 GNUNET_free(gi); 155 GNUNET_free (gi);
155 GNUNET_free(bg); 156 GNUNET_free (bg);
156} 157}
157 158
158 159
@@ -170,24 +171,25 @@ bf_group_destroy_cb(struct GNUNET_BLOCK_Group *bg)
170 * by this @a type of block (this is not an error) 171 * by this @a type of block (this is not an error)
171 */ 172 */
172struct GNUNET_BLOCK_Group * 173struct GNUNET_BLOCK_Group *
173GNUNET_BLOCK_GROUP_bf_create(void *cls, 174GNUNET_BLOCK_GROUP_bf_create (void *cls,
174 size_t bf_size, 175 size_t bf_size,
175 unsigned int bf_k, 176 unsigned int bf_k,
176 enum GNUNET_BLOCK_Type type, 177 enum GNUNET_BLOCK_Type type,
177 uint32_t nonce, 178 uint32_t nonce,
178 const void *raw_data, 179 const void *raw_data,
179 size_t raw_data_size) 180 size_t raw_data_size)
180{ 181{
181 struct BfGroupInternals *gi; 182 struct BfGroupInternals *gi;
182 struct GNUNET_BLOCK_Group *bg; 183 struct GNUNET_BLOCK_Group *bg;
183 184
184 gi = GNUNET_new(struct BfGroupInternals); 185 gi = GNUNET_new (struct BfGroupInternals);
185 gi->bf = GNUNET_CONTAINER_bloomfilter_init((bf_size != raw_data_size) ? NULL : raw_data, 186 gi->bf = GNUNET_CONTAINER_bloomfilter_init ((bf_size != raw_data_size) ?
186 bf_size, 187 NULL : raw_data,
187 bf_k); 188 bf_size,
189 bf_k);
188 gi->bf_mutator = nonce; 190 gi->bf_mutator = nonce;
189 gi->bf_size = bf_size; 191 gi->bf_size = bf_size;
190 bg = GNUNET_new(struct GNUNET_BLOCK_Group); 192 bg = GNUNET_new (struct GNUNET_BLOCK_Group);
191 bg->type = type; 193 bg->type = type;
192 bg->serialize_cb = &bf_group_serialize_cb; 194 bg->serialize_cb = &bf_group_serialize_cb;
193 bg->mark_seen_cb = &bf_group_mark_seen_cb; 195 bg->mark_seen_cb = &bf_group_mark_seen_cb;
@@ -209,8 +211,8 @@ GNUNET_BLOCK_GROUP_bf_create(void *cls,
209 * #GNUNET_NO if @a hc was definitively not in @bg (but now is) 211 * #GNUNET_NO if @a hc was definitively not in @bg (but now is)
210 */ 212 */
211int 213int
212GNUNET_BLOCK_GROUP_bf_test_and_set(struct GNUNET_BLOCK_Group *bg, 214GNUNET_BLOCK_GROUP_bf_test_and_set (struct GNUNET_BLOCK_Group *bg,
213 const struct GNUNET_HashCode *hc) 215 const struct GNUNET_HashCode *hc)
214{ 216{
215 struct BfGroupInternals *gi; 217 struct BfGroupInternals *gi;
216 struct GNUNET_HashCode mhash; 218 struct GNUNET_HashCode mhash;
@@ -218,15 +220,15 @@ GNUNET_BLOCK_GROUP_bf_test_and_set(struct GNUNET_BLOCK_Group *bg,
218 if (NULL == bg) 220 if (NULL == bg)
219 return GNUNET_NO; 221 return GNUNET_NO;
220 gi = bg->internal_cls; 222 gi = bg->internal_cls;
221 GNUNET_BLOCK_mingle_hash(hc, 223 GNUNET_BLOCK_mingle_hash (hc,
222 gi->bf_mutator, 224 gi->bf_mutator,
223 &mhash); 225 &mhash);
224 if (GNUNET_YES == 226 if (GNUNET_YES ==
225 GNUNET_CONTAINER_bloomfilter_test(gi->bf, 227 GNUNET_CONTAINER_bloomfilter_test (gi->bf,
226 &mhash)) 228 &mhash))
227 return GNUNET_YES; 229 return GNUNET_YES;
228 GNUNET_CONTAINER_bloomfilter_add(gi->bf, 230 GNUNET_CONTAINER_bloomfilter_add (gi->bf,
229 &mhash); 231 &mhash);
230 return GNUNET_NO; 232 return GNUNET_NO;
231} 233}
232 234
@@ -245,8 +247,8 @@ GNUNET_BLOCK_GROUP_bf_test_and_set(struct GNUNET_BLOCK_Group *bg,
245 * @return must be a power of two and smaller or equal to 2^15. 247 * @return must be a power of two and smaller or equal to 2^15.
246 */ 248 */
247size_t 249size_t
248GNUNET_BLOCK_GROUP_compute_bloomfilter_size(unsigned int entry_count, 250GNUNET_BLOCK_GROUP_compute_bloomfilter_size (unsigned int entry_count,
249 unsigned int k) 251 unsigned int k)
250{ 252{
251 size_t size; 253 size_t size;
252 unsigned int ideal = (entry_count * k) / 4; 254 unsigned int ideal = (entry_count * k) / 4;