diff options
author | Christian Grothoff <christian@grothoff.org> | 2017-02-26 22:42:40 +0100 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2017-02-26 22:42:40 +0100 |
commit | 8d7c29c4684f807d5e9a3004bbbab132b158c5aa (patch) | |
tree | 9eca177e00a387d0c18395fde7dbf91289272d98 /src/block/bg_bf.c | |
parent | e87663cf00dd102e8bb60f400db4bad6d82b3b6c (diff) | |
download | gnunet-8d7c29c4684f807d5e9a3004bbbab132b158c5aa.tar.gz gnunet-8d7c29c4684f807d5e9a3004bbbab132b158c5aa.zip |
ensure all plugins properly use BF, move shared logic to shared library
Diffstat (limited to 'src/block/bg_bf.c')
-rw-r--r-- | src/block/bg_bf.c | 32 |
1 files changed, 32 insertions, 0 deletions
diff --git a/src/block/bg_bf.c b/src/block/bg_bf.c index 9c4dc9060..1a17ec84e 100644 --- a/src/block/bg_bf.c +++ b/src/block/bg_bf.c | |||
@@ -232,4 +232,36 @@ GNUNET_BLOCK_GROUP_bf_test_and_set (struct GNUNET_BLOCK_Group *bg, | |||
232 | } | 232 | } |
233 | 233 | ||
234 | 234 | ||
235 | /** | ||
236 | * How many bytes should a bloomfilter be if we have already seen | ||
237 | * entry_count responses? Sized so that do not have to | ||
238 | * re-size the filter too often (to keep it cheap). | ||
239 | * | ||
240 | * Since other peers will also add entries but not resize the filter, | ||
241 | * we should generally pick a slightly larger size than what the | ||
242 | * strict math would suggest. | ||
243 | * | ||
244 | * @param entry_count expected number of entries in the Bloom filter | ||
245 | * @param k number of bits set per entry | ||
246 | * @return must be a power of two and smaller or equal to 2^15. | ||
247 | */ | ||
248 | size_t | ||
249 | GNUNET_BLOCK_GROUP_compute_bloomfilter_size (unsigned int entry_count, | ||
250 | unsigned int k) | ||
251 | { | ||
252 | size_t size; | ||
253 | unsigned int ideal = (entry_count * k) / 4; | ||
254 | uint16_t max = 1 << 15; | ||
255 | |||
256 | if (entry_count > max) | ||
257 | return max; | ||
258 | size = 8; | ||
259 | while ((size < max) && (size < ideal)) | ||
260 | size *= 2; | ||
261 | if (size > max) | ||
262 | return max; | ||
263 | return size; | ||
264 | } | ||
265 | |||
266 | |||
235 | /* end of bg_bf.c */ | 267 | /* end of bg_bf.c */ |