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