diff options
author | Christian Grothoff <christian@grothoff.org> | 2011-09-27 11:29:11 +0000 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2011-09-27 11:29:11 +0000 |
commit | 926f5a24e5a30566a51effb0e1752c15b0fa1e88 (patch) | |
tree | 744173dbd29bf685d2424db58f620b53c24cce1d /src/block | |
parent | b9ae190b8cfaa9124e284cc46595fa3b52b16696 (diff) | |
download | gnunet-926f5a24e5a30566a51effb0e1752c15b0fa1e88.tar.gz gnunet-926f5a24e5a30566a51effb0e1752c15b0fa1e88.zip |
move bloomfilter recalculation to block library
Diffstat (limited to 'src/block')
-rw-r--r-- | src/block/block.c | 45 |
1 files changed, 43 insertions, 2 deletions
diff --git a/src/block/block.c b/src/block/block.c index 7ab420f7a..8efb0d477 100644 --- a/src/block/block.c +++ b/src/block/block.c | |||
@@ -25,6 +25,7 @@ | |||
25 | */ | 25 | */ |
26 | #include "platform.h" | 26 | #include "platform.h" |
27 | #include "gnunet_util_lib.h" | 27 | #include "gnunet_util_lib.h" |
28 | #include "gnunet_constants.h" | ||
28 | #include "gnunet_signatures.h" | 29 | #include "gnunet_signatures.h" |
29 | #include "gnunet_block_lib.h" | 30 | #include "gnunet_block_lib.h" |
30 | #include "gnunet_block_plugin.h" | 31 | #include "gnunet_block_plugin.h" |
@@ -249,6 +250,35 @@ GNUNET_BLOCK_get_key (struct GNUNET_BLOCK_Context *ctx, | |||
249 | } | 250 | } |
250 | 251 | ||
251 | 252 | ||
253 | /** | ||
254 | * How many bytes should a bloomfilter be if we have already seen | ||
255 | * entry_count responses? Note that GNUNET_CONSTANTS_BLOOMFILTER_K gives us the number | ||
256 | * of bits set per entry. Furthermore, we should not re-size the | ||
257 | * filter too often (to keep it cheap). | ||
258 | * | ||
259 | * Since other peers will also add entries but not resize the filter, | ||
260 | * we should generally pick a slightly larger size than what the | ||
261 | * strict math would suggest. | ||
262 | * | ||
263 | * @return must be a power of two and smaller or equal to 2^15. | ||
264 | */ | ||
265 | static size_t | ||
266 | compute_bloomfilter_size (unsigned int entry_count) | ||
267 | { | ||
268 | size_t size; | ||
269 | unsigned int ideal = (entry_count * GNUNET_CONSTANTS_BLOOMFILTER_K) / 4; | ||
270 | uint16_t max = 1 << 15; | ||
271 | |||
272 | if (entry_count > max) | ||
273 | return max; | ||
274 | size = 8; | ||
275 | while ((size < max) && (size < ideal)) | ||
276 | size *= 2; | ||
277 | if (size > max) | ||
278 | return max; | ||
279 | return size; | ||
280 | } | ||
281 | |||
252 | 282 | ||
253 | /** | 283 | /** |
254 | * Construct a bloom filter that would filter out the given | 284 | * Construct a bloom filter that would filter out the given |
@@ -265,8 +295,19 @@ GNUNET_BLOCK_construct_bloomfilter (int32_t bf_mutator, | |||
265 | const GNUNET_HashCode *seen_results, | 295 | const GNUNET_HashCode *seen_results, |
266 | unsigned int seen_results_count) | 296 | unsigned int seen_results_count) |
267 | { | 297 | { |
268 | GNUNET_break (0); | 298 | struct GNUNET_CONTAINER_BloomFilter *bf; |
269 | return NULL; | 299 | GNUNET_HashCode mhash; |
300 | unsigned int i; | ||
301 | size_t nsize; | ||
302 | |||
303 | nsize = compute_bloomfilter_size (seen_results_count); | ||
304 | bf = GNUNET_CONTAINER_bloomfilter_init (NULL, nsize, GNUNET_CONSTANTS_BLOOMFILTER_K); | ||
305 | for (i = 0; i < seen_results_count; i++) | ||
306 | { | ||
307 | GNUNET_BLOCK_mingle_hash (&seen_results[i], bf_mutator, &mhash); | ||
308 | GNUNET_CONTAINER_bloomfilter_add (bf, &mhash); | ||
309 | } | ||
310 | return bf; | ||
270 | } | 311 | } |
271 | 312 | ||
272 | 313 | ||