diff options
Diffstat (limited to 'src/block/bg_bf.c')
-rw-r--r-- | src/block/bg_bf.c | 116 |
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 | */ |
35 | struct BfGroupInternals { | 35 | struct 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 | */ |
63 | static int | 64 | static int |
64 | bf_group_serialize_cb(struct GNUNET_BLOCK_Group *bg, | 65 | bf_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 | */ |
97 | static void | 98 | static void |
98 | bf_group_mark_seen_cb(struct GNUNET_BLOCK_Group *bg, | 99 | bf_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 | */ |
126 | static int | 127 | static int |
127 | bf_group_merge_cb(struct GNUNET_BLOCK_Group *bg1, | 128 | bf_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 | */ |
148 | static void | 149 | static void |
149 | bf_group_destroy_cb(struct GNUNET_BLOCK_Group *bg) | 150 | bf_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 | */ |
172 | struct GNUNET_BLOCK_Group * | 173 | struct GNUNET_BLOCK_Group * |
173 | GNUNET_BLOCK_GROUP_bf_create(void *cls, | 174 | GNUNET_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 | */ |
211 | int | 213 | int |
212 | GNUNET_BLOCK_GROUP_bf_test_and_set(struct GNUNET_BLOCK_Group *bg, | 214 | GNUNET_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 | */ |
247 | size_t | 249 | size_t |
248 | GNUNET_BLOCK_GROUP_compute_bloomfilter_size(unsigned int entry_count, | 250 | GNUNET_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; |