diff options
author | Christian Fuchs <christian.fuchs@cfuchs.net> | 2013-12-11 14:47:13 +0000 |
---|---|---|
committer | Christian Fuchs <christian.fuchs@cfuchs.net> | 2013-12-11 14:47:13 +0000 |
commit | 21a433bd0d1a4410f6459fe0d59e5a27809bc735 (patch) | |
tree | 0dcf4649dc09d25048469e36f4ad378fca2e463c /src/set | |
parent | 95eb1398e2b27eb97c0bd01feb6a28d30917504c (diff) | |
download | gnunet-21a433bd0d1a4410f6459fe0d59e5a27809bc735.tar.gz gnunet-21a433bd0d1a4410f6459fe0d59e5a27809bc735.zip |
- more work on multipart sending
- separated bf-generation and reduction again, as this is now necessary with dynamic bf-lengths
Diffstat (limited to 'src/set')
-rw-r--r-- | src/set/gnunet-service-set_intersection.c | 73 |
1 files changed, 48 insertions, 25 deletions
diff --git a/src/set/gnunet-service-set_intersection.c b/src/set/gnunet-service-set_intersection.c index f2dfb1759..11527b04f 100644 --- a/src/set/gnunet-service-set_intersection.c +++ b/src/set/gnunet-service-set_intersection.c | |||
@@ -31,6 +31,13 @@ | |||
31 | #include <gcrypt.h> | 31 | #include <gcrypt.h> |
32 | 32 | ||
33 | #define BLOOMFILTER_SIZE GNUNET_CRYPTO_HASH_LENGTH | 33 | #define BLOOMFILTER_SIZE GNUNET_CRYPTO_HASH_LENGTH |
34 | |||
35 | #define CALCULATE_BF_SIZE(A, B, s, k) \ | ||
36 | do { \ | ||
37 | k = ceil(1 + log2((double) (2*B / (double) A)));\ | ||
38 | s = ceil((double) (A * k / log(2))); \ | ||
39 | } while (0) | ||
40 | |||
34 | /** | 41 | /** |
35 | * Current phase we are in for a intersection operation. | 42 | * Current phase we are in for a intersection operation. |
36 | */ | 43 | */ |
@@ -185,13 +192,6 @@ iterator_initialization_by_alice (void *cls, | |||
185 | &ee->element_hash, ee, | 192 | &ee->element_hash, ee, |
186 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); | 193 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); |
187 | 194 | ||
188 | /* create our own bloomfilter with salt+1 */ | ||
189 | GNUNET_BLOCK_mingle_hash (&ee->element_hash, | ||
190 | op->spec->salt + 1, | ||
191 | &mutated_hash); | ||
192 | GNUNET_CONTAINER_bloomfilter_add (op->state->local_bf, | ||
193 | &mutated_hash); | ||
194 | |||
195 | return GNUNET_YES; | 195 | return GNUNET_YES; |
196 | } | 196 | } |
197 | 197 | ||
@@ -224,11 +224,6 @@ iterator_initialization (void *cls, | |||
224 | GNUNET_CONTAINER_multihashmap_put (op->state->my_elements, | 224 | GNUNET_CONTAINER_multihashmap_put (op->state->my_elements, |
225 | &ee->element_hash, ee, | 225 | &ee->element_hash, ee, |
226 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); | 226 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); |
227 | GNUNET_BLOCK_mingle_hash (&ee->element_hash, | ||
228 | op->spec->salt, | ||
229 | &mutated_hash); | ||
230 | GNUNET_CONTAINER_bloomfilter_add (op->state->local_bf, | ||
231 | &mutated_hash); | ||
232 | return GNUNET_YES; | 227 | return GNUNET_YES; |
233 | } | 228 | } |
234 | 229 | ||
@@ -245,7 +240,7 @@ iterator_initialization (void *cls, | |||
245 | * #GNUNET_NO if not. | 240 | * #GNUNET_NO if not. |
246 | */ | 241 | */ |
247 | static int | 242 | static int |
248 | iterator_bf_round (void *cls, | 243 | iterator_bf_reduce (void *cls, |
249 | const struct GNUNET_HashCode *key, | 244 | const struct GNUNET_HashCode *key, |
250 | void *value) | 245 | void *value) |
251 | { | 246 | { |
@@ -264,17 +259,37 @@ iterator_bf_round (void *cls, | |||
264 | GNUNET_CONTAINER_multihashmap_remove (op->state->my_elements, | 259 | GNUNET_CONTAINER_multihashmap_remove (op->state->my_elements, |
265 | &ee->element_hash, | 260 | &ee->element_hash, |
266 | ee)); | 261 | ee)); |
267 | return GNUNET_YES; | ||
268 | } | 262 | } |
269 | GNUNET_BLOCK_mingle_hash(&ee->element_hash, | 263 | |
270 | op->spec->salt+1, | 264 | return GNUNET_YES; |
271 | &mutated_hash); | 265 | } |
266 | |||
267 | /** | ||
268 | * create a bloomfilter based on the elements given | ||
269 | * | ||
270 | * @param cls closure | ||
271 | * @param key current key code | ||
272 | * @param value value in the hash map | ||
273 | * @return #GNUNET_YES if we should continue to | ||
274 | * iterate, | ||
275 | * #GNUNET_NO if not. | ||
276 | */ | ||
277 | static int | ||
278 | iterator_bf_create (void *cls, | ||
279 | const struct GNUNET_HashCode *key, | ||
280 | void *value) | ||
281 | { | ||
282 | struct ElementEntry *ee = value; | ||
283 | struct Operation *op = cls; | ||
284 | struct GNUNET_HashCode mutated_hash; | ||
285 | |||
286 | GNUNET_BLOCK_mingle_hash(&ee->element_hash, op->spec->salt, &mutated_hash); | ||
287 | |||
272 | GNUNET_CONTAINER_bloomfilter_add (op->state->local_bf, | 288 | GNUNET_CONTAINER_bloomfilter_add (op->state->local_bf, |
273 | &mutated_hash); | 289 | &mutated_hash); |
274 | return GNUNET_YES; | 290 | return GNUNET_YES; |
275 | } | 291 | } |
276 | 292 | ||
277 | |||
278 | /** | 293 | /** |
279 | * Inform the client that the union operation has failed, | 294 | * Inform the client that the union operation has failed, |
280 | * and proceed to destroy the evaluate operation. | 295 | * and proceed to destroy the evaluate operation. |
@@ -522,8 +537,8 @@ handle_p2p_bf (void *cls, const struct GNUNET_MessageHeader *mh) | |||
522 | op->spec->salt = ntohl (msg->sender_mutator); | 537 | op->spec->salt = ntohl (msg->sender_mutator); |
523 | 538 | ||
524 | op->state->remote_bf = GNUNET_CONTAINER_bloomfilter_init ((const char*) &msg[1], | 539 | op->state->remote_bf = GNUNET_CONTAINER_bloomfilter_init ((const char*) &msg[1], |
525 | BLOOMFILTER_SIZE, | 540 | ntohl (msg->bloomfilter_length), |
526 | ntohl (msg->bloomfilter_length)); | 541 | GNUNET_CONSTANTS_BLOOMFILTER_K); |
527 | op->state->local_bf = GNUNET_CONTAINER_bloomfilter_init (NULL, | 542 | op->state->local_bf = GNUNET_CONTAINER_bloomfilter_init (NULL, |
528 | BLOOMFILTER_SIZE, | 543 | BLOOMFILTER_SIZE, |
529 | GNUNET_CONSTANTS_BLOOMFILTER_K); | 544 | GNUNET_CONSTANTS_BLOOMFILTER_K); |
@@ -541,7 +556,7 @@ handle_p2p_bf (void *cls, const struct GNUNET_MessageHeader *mh) | |||
541 | case PHASE_MAYBE_FINISHED: | 556 | case PHASE_MAYBE_FINISHED: |
542 | // if we are bob or alice and are continuing operation | 557 | // if we are bob or alice and are continuing operation |
543 | GNUNET_CONTAINER_multihashmap_iterate (op->spec->set->elements, | 558 | GNUNET_CONTAINER_multihashmap_iterate (op->spec->set->elements, |
544 | &iterator_bf_round, | 559 | &iterator_bf_reduce, |
545 | op); | 560 | op); |
546 | break; | 561 | break; |
547 | default: | 562 | default: |
@@ -586,6 +601,8 @@ handle_p2p_element_info (void *cls, const struct GNUNET_MessageHeader *mh) | |||
586 | { | 601 | { |
587 | struct Operation *op = cls; | 602 | struct Operation *op = cls; |
588 | struct BFMessage *msg = (struct BFMessage *) mh; | 603 | struct BFMessage *msg = (struct BFMessage *) mh; |
604 | uint32_t bf_size; | ||
605 | uint32_t bits_per_element; | ||
589 | 606 | ||
590 | op->spec->remote_element_count = ntohl(msg->sender_element_count); | 607 | op->spec->remote_element_count = ntohl(msg->sender_element_count); |
591 | if ((op->state->phase != PHASE_INITIAL) | 608 | if ((op->state->phase != PHASE_INITIAL) |
@@ -596,13 +613,19 @@ handle_p2p_element_info (void *cls, const struct GNUNET_MessageHeader *mh) | |||
596 | 613 | ||
597 | op->state->phase = PHASE_BF_EXCHANGE; | 614 | op->state->phase = PHASE_BF_EXCHANGE; |
598 | op->state->my_elements = GNUNET_CONTAINER_multihashmap_create (1, GNUNET_YES); | 615 | op->state->my_elements = GNUNET_CONTAINER_multihashmap_create (1, GNUNET_YES); |
599 | 616 | ||
600 | op->state->local_bf = GNUNET_CONTAINER_bloomfilter_init (NULL, | ||
601 | BLOOMFILTER_SIZE, | ||
602 | GNUNET_CONSTANTS_BLOOMFILTER_K); | ||
603 | GNUNET_CONTAINER_multihashmap_iterate (op->spec->set->elements, | 617 | GNUNET_CONTAINER_multihashmap_iterate (op->spec->set->elements, |
604 | &iterator_initialization, | 618 | &iterator_initialization, |
605 | op); | 619 | op); |
620 | |||
621 | CALCULATE_BF_SIZE(op->state->my_element_count, | ||
622 | op->spec->remote_element_count, | ||
623 | bf_size, | ||
624 | bits_per_element); | ||
625 | |||
626 | op->state->local_bf = GNUNET_CONTAINER_bloomfilter_init (NULL, | ||
627 | bf_size, | ||
628 | bits_per_element); | ||
606 | 629 | ||
607 | GNUNET_CONTAINER_bloomfilter_free (op->state->remote_bf); | 630 | GNUNET_CONTAINER_bloomfilter_free (op->state->remote_bf); |
608 | op->state->remote_bf = NULL; | 631 | op->state->remote_bf = NULL; |