X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=src%2Fset%2Fgnunet-service-set_intersection.c;h=258ad64436494fd02d5beca0007026f9c9b12ac1;hb=5b32752cd7b02adcb8e6fec7798637638c6f63a0;hp=b46044c352af779b8f99f64ec1010fac900e1955;hpb=7961175bdde4e1efe2140e04caa6e600d41bcf90;p=oweals%2Fgnunet.git diff --git a/src/set/gnunet-service-set_intersection.c b/src/set/gnunet-service-set_intersection.c index b46044c35..258ad6443 100644 --- a/src/set/gnunet-service-set_intersection.c +++ b/src/set/gnunet-service-set_intersection.c @@ -1,6 +1,6 @@ /* This file is part of GNUnet - (C) 2013 Christian Grothoff (and other contributing authors) + Copyright (C) 2013, 2014 GNUnet e.V. GNUnet is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published @@ -14,113 +14,148 @@ You should have received a copy of the GNU General Public License along with GNUnet; see the file COPYING. If not, write to the - Free Software Foundation, Inc., 59 Temple Place - Suite 330, - Boston, MA 02111-1307, USA. + Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, + Boston, MA 02110-1301, USA. */ - /** * @file set/gnunet-service-set_intersection.c * @brief two-peer set intersection * @author Christian Fuchs + * @author Christian Grothoff */ #include "platform.h" #include "gnunet_util_lib.h" #include "gnunet-service-set.h" -#include "strata_estimator.h" -#include "set_protocol.h" +#include "gnunet_block_lib.h" +#include "gnunet-service-set_protocol.h" #include + /** * Current phase we are in for a intersection operation. */ enum IntersectionOperationPhase { /** - * We get our tunnel but received no message as of now + * We are just starting. + */ + PHASE_INITIAL, + + /** + * We have send the number of our elements to the other + * peer, but did not setup our element set yet. */ - PHASE_EXPECT_INITIAL, + PHASE_COUNT_SENT, + /** - * We expect a BF + the number of the other peers elements + * We have initialized our set and are now reducing it by exchanging + * Bloom filters until one party notices the their element hashes + * are equal. */ PHASE_BF_EXCHANGE, + /** - * The protocol is over. - * Results may still have to be sent to the client. + * The protocol is over. Results may still have to be sent to the + * client. */ PHASE_FINISHED + }; /** - * State of an evaluate operation - * with another peer. + * State of an evaluate operation with another peer. */ struct OperationState { /** - * Tunnel to the remote peer. + * The bf we currently receive */ - struct GNUNET_MESH_Tunnel *tunnel; + struct GNUNET_CONTAINER_BloomFilter *remote_bf; /** - * Detail information about the set operation, - * including the set to use. + * BF of the set's element. */ - struct OperationSpecification *spec; + struct GNUNET_CONTAINER_BloomFilter *local_bf; /** - * Message queue for the peer. + * Remaining elements in the intersection operation. + * Maps element-id-hashes to 'elements in our set'. */ - struct GNUNET_MQ_Handle *mq; + struct GNUNET_CONTAINER_MultiHashMap *my_elements; /** - * The bf we currently receive + * Iterator for sending the final set of @e my_elements to the client. */ - struct GNUNET_CONTAINER_BloomFilter *remote_bf; + struct GNUNET_CONTAINER_MultiHashMapIterator *full_result_iter; /** - * BF of the set's element. + * Evaluate operations are held in a linked list. */ - struct GNUNET_CONTAINER_BloomFilter *local_bf; + struct OperationState *next; /** - * Current state of the operation. + * Evaluate operations are held in a linked list. */ - enum IntersectionOperationPhase phase; + struct OperationState *prev; /** - * Generation in which the operation handle - * was created. + * For multipart BF transmissions, we have to store the + * bloomfilter-data until we fully received it. */ - unsigned int generation_created; + char *bf_data; /** - * Set state of the set that this operation - * belongs to. + * XOR of the keys of all of the elements (remaining) in my set. + * Always updated when elements are added or removed to + * @e my_elements. */ - struct Set *set; - + struct GNUNET_HashCode my_xor; + /** - * Maps element-id-hashes to 'elements in our set'. + * XOR of the keys of all of the elements (remaining) in + * the other peer's set. Updated when we receive the + * other peer's Bloom filter. */ - struct GNUNET_CONTAINER_MultiHashMap *contained_elements; + struct GNUNET_HashCode other_xor; /** - * Iterator for sending elements on the key to element mapping to the client. + * How many bytes of @e bf_data are valid? */ - struct GNUNET_CONTAINER_MultiHashMap32Iterator *full_result_iter; - + uint32_t bf_data_offset; + /** - * Evaluate operations are held in - * a linked list. + * Current element count contained within @e my_elements. + * (May differ briefly during initialization.) */ - struct OperationState *next; + uint32_t my_element_count; - /** - * Evaluate operations are held in - * a linked list. - */ - struct OperationState *prev; + /** + * size of the bloomfilter in @e bf_data. + */ + uint32_t bf_data_size; + + /** + * size of the bloomfilter + */ + uint32_t bf_bits_per_element; + + /** + * Salt currently used for BF construction (by us or the other peer, + * depending on where we are in the code). + */ + uint32_t salt; + + /** + * Current state of the operation. + */ + enum IntersectionOperationPhase phase; + + /** + * Generation in which the operation handle + * was created. + */ + unsigned int generation_created; /** * Did we send the client that we are done? @@ -131,63 +166,211 @@ struct OperationState /** * Extra state required for efficient set intersection. + * Merely tracks the total number of elements. */ struct SetState { /** - * Evaluate operations are held in - * a linked list. + * Number of currently valid elements in the set which have not been + * removed. */ - struct OperationState *ops_head; - - /** - * Evaluate operations are held in - * a linked list. - */ - struct OperationState *ops_tail; + uint32_t current_set_element_count; }; /** - * Destroy a intersection operation, and free all resources - * associated with it. + * If applicable in the current operation mode, send a result message + * to the client indicating we removed an element. * - * @param eo the intersection operation to destroy + * @param op intersection operation + * @param element element to send */ static void -intersection_operation_destroy (struct OperationState *eo) +send_client_removed_element (struct Operation *op, + struct GNUNET_SET_Element *element) { - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "destroying intersection op\n"); - GNUNET_CONTAINER_DLL_remove (eo->set->state->ops_head, - eo->set->state->ops_tail, - eo); - if (NULL != eo->mq) + struct GNUNET_MQ_Envelope *ev; + struct GNUNET_SET_ResultMessage *rm; + + if (GNUNET_SET_RESULT_REMOVED != op->spec->result_mode) + return; /* Wrong mode for transmitting removed elements */ + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Sending removed element (size %u) to client\n", + element->size); + GNUNET_assert (0 != op->spec->client_request_id); + ev = GNUNET_MQ_msg_extra (rm, + element->size, + GNUNET_MESSAGE_TYPE_SET_RESULT); + if (NULL == ev) { - GNUNET_MQ_destroy (eo->mq); - eo->mq = NULL; + GNUNET_break (0); + return; } - if (NULL != eo->tunnel) + rm->result_status = htons (GNUNET_SET_STATUS_OK); + rm->request_id = htonl (op->spec->client_request_id); + rm->element_type = element->element_type; + GNUNET_memcpy (&rm[1], + element->data, + element->size); + GNUNET_MQ_send (op->spec->set->client_mq, + ev); +} + + +/** + * Fills the "my_elements" hashmap with all relevant elements. + * + * @param cls the `struct Operation *` we are performing + * @param key current key code + * @param value the `struct ElementEntry *` from the hash map + * @return #GNUNET_YES (we should continue to iterate) + */ +static int +filtered_map_initialization (void *cls, + const struct GNUNET_HashCode *key, + void *value) +{ + struct Operation *op = cls; + struct ElementEntry *ee = value; + struct GNUNET_HashCode mutated_hash; + + + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "FIMA called for %s:%u\n", + GNUNET_h2s (&ee->element_hash), + ee->element.size); + + if (GNUNET_NO == _GSS_is_element_of_operation (ee, op)) { - struct GNUNET_MESH_Tunnel *t = eo->tunnel; - eo->tunnel = NULL; - GNUNET_MESH_tunnel_destroy (t); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Reduced initialization, not starting with %s:%u (wrong generation)\n", + GNUNET_h2s (&ee->element_hash), + ee->element.size); + return GNUNET_YES; /* element not valid in our operation's generation */ } - // TODO: destroy set elements? - if (NULL != eo->spec) + + /* Test if element is in other peer's bloomfilter */ + GNUNET_BLOCK_mingle_hash (&ee->element_hash, + op->state->salt, + &mutated_hash); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Testing mingled hash %s with salt %u\n", + GNUNET_h2s (&mutated_hash), + op->state->salt); + if (GNUNET_NO == + GNUNET_CONTAINER_bloomfilter_test (op->state->remote_bf, + &mutated_hash)) { - if (NULL != eo->spec->context_msg) - { - GNUNET_free (eo->spec->context_msg); - eo->spec->context_msg = NULL; - } - GNUNET_free (eo->spec); - eo->spec = NULL; + /* remove this element */ + send_client_removed_element (op, + &ee->element); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Reduced initialization, not starting with %s:%u\n", + GNUNET_h2s (&ee->element_hash), + ee->element.size); + return GNUNET_YES; } - GNUNET_free (eo); + op->state->my_element_count++; + GNUNET_CRYPTO_hash_xor (&op->state->my_xor, + &ee->element_hash, + &op->state->my_xor); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Filtered initialization of my_elements, adding %s:%u\n", + GNUNET_h2s (&ee->element_hash), + ee->element.size); + GNUNET_break (GNUNET_YES == + GNUNET_CONTAINER_multihashmap_put (op->state->my_elements, + &ee->element_hash, + ee, + GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); + + return GNUNET_YES; +} - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "destroying intersection op done\n"); - /* FIXME: do a garbage collection of the set generations */ +/** + * Removes elements from our hashmap if they are not contained within the + * provided remote bloomfilter. + * + * @param cls closure with the `struct Operation *` + * @param key current key code + * @param value value in the hash map + * @return #GNUNET_YES (we should continue to iterate) + */ +static int +iterator_bf_reduce (void *cls, + const struct GNUNET_HashCode *key, + void *value) +{ + struct Operation *op = cls; + struct ElementEntry *ee = value; + struct GNUNET_HashCode mutated_hash; + + GNUNET_BLOCK_mingle_hash (&ee->element_hash, + op->state->salt, + &mutated_hash); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Testing mingled hash %s with salt %u\n", + GNUNET_h2s (&mutated_hash), + op->state->salt); + if (GNUNET_NO == + GNUNET_CONTAINER_bloomfilter_test (op->state->remote_bf, + &mutated_hash)) + { + GNUNET_break (0 < op->state->my_element_count); + op->state->my_element_count--; + GNUNET_CRYPTO_hash_xor (&op->state->my_xor, + &ee->element_hash, + &op->state->my_xor); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Bloom filter reduction of my_elements, removing %s:%u\n", + GNUNET_h2s (&ee->element_hash), + ee->element.size); + GNUNET_assert (GNUNET_YES == + GNUNET_CONTAINER_multihashmap_remove (op->state->my_elements, + &ee->element_hash, + ee)); + send_client_removed_element (op, + &ee->element); + } + else + { + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Bloom filter reduction of my_elements, keeping %s:%u\n", + GNUNET_h2s (&ee->element_hash), + ee->element.size); + } + return GNUNET_YES; +} + + +/** + * Create initial bloomfilter based on all the elements given. + * + * @param cls the `struct Operation *` + * @param key current key code + * @param value the `struct ElementEntry` to process + * @return #GNUNET_YES (we should continue to iterate) + */ +static int +iterator_bf_create (void *cls, + const struct GNUNET_HashCode *key, + void *value) +{ + struct Operation *op = cls; + struct ElementEntry *ee = value; + struct GNUNET_HashCode mutated_hash; + + GNUNET_BLOCK_mingle_hash (&ee->element_hash, + op->state->salt, + &mutated_hash); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Initializing BF with hash %s with salt %u\n", + GNUNET_h2s (&mutated_hash), + op->state->salt); + GNUNET_CONTAINER_bloomfilter_add (op->state->local_bf, + &mutated_hash); + return GNUNET_YES; } @@ -195,454 +378,779 @@ intersection_operation_destroy (struct OperationState *eo) * Inform the client that the intersection operation has failed, * and proceed to destroy the evaluate operation. * - * @param eo the intersection operation to fail + * @param op the intersection operation to fail */ static void -fail_intersection_operation (struct OperationState *eo) +fail_intersection_operation (struct Operation *op) { struct GNUNET_MQ_Envelope *ev; struct GNUNET_SET_ResultMessage *msg; - ev = GNUNET_MQ_msg (msg, GNUNET_MESSAGE_TYPE_SET_RESULT); + GNUNET_log (GNUNET_ERROR_TYPE_WARNING, + "Intersection operation failed\n"); + if (NULL != op->state->my_elements) + { + GNUNET_CONTAINER_multihashmap_destroy (op->state->my_elements); + op->state->my_elements = NULL; + } + ev = GNUNET_MQ_msg (msg, + GNUNET_MESSAGE_TYPE_SET_RESULT); msg->result_status = htons (GNUNET_SET_STATUS_FAILURE); - msg->request_id = htonl (eo->spec->client_request_id); + msg->request_id = htonl (op->spec->client_request_id); msg->element_type = htons (0); - GNUNET_MQ_send (eo->spec->set->client_mq, ev); - intersection_operation_destroy (eo); + GNUNET_MQ_send (op->spec->set->client_mq, + ev); + _GSS_operation_destroy (op, + GNUNET_YES); } /** - * Send a request for the evaluate operation to a remote peer + * Send a bloomfilter to our peer. After the result done message has + * been sent to the client, destroy the evaluate operation. * - * @param eo operation with the other peer + * @param op intersection operation */ static void -send_operation_request (struct Operation *op) +send_bloomfilter (struct Operation *op) { struct GNUNET_MQ_Envelope *ev; - struct OperationRequestMessage *msg; - - ev = GNUNET_MQ_msg_nested_mh (msg, GNUNET_MESSAGE_TYPE_SET_P2P_OPERATION_REQUEST, - op->spec->context_msg); - - if (NULL == ev) + struct BFMessage *msg; + uint32_t bf_size; + uint32_t bf_elementbits; + uint32_t chunk_size; + char *bf_data; + uint32_t offset; + + /* We consider the ratio of the set sizes to determine + the number of bits per element, as the smaller set + should use more bits to maximize its set reduction + potential and minimize overall bandwidth consumption. */ + bf_elementbits = 2 + ceil (log2((double) + (op->spec->remote_element_count / + (double) op->state->my_element_count))); + if (bf_elementbits < 1) + bf_elementbits = 1; /* make sure k is not 0 */ + /* optimize BF-size to ~50% of bits set */ + bf_size = ceil ((double) (op->state->my_element_count + * bf_elementbits / log(2))); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Sending Bloom filter (%u) of size %u bytes\n", + (unsigned int) bf_elementbits, + (unsigned int) bf_size); + op->state->local_bf = GNUNET_CONTAINER_bloomfilter_init (NULL, + bf_size, + bf_elementbits); + op->state->salt = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE, + UINT32_MAX); + GNUNET_CONTAINER_multihashmap_iterate (op->state->my_elements, + &iterator_bf_create, + op); + + /* send our Bloom filter */ + chunk_size = 60 * 1024 - sizeof (struct BFMessage); + if (bf_size <= chunk_size) { - /* the context message is too large */ - GNUNET_break (0); - GNUNET_SERVER_client_disconnect (op->spec->set->client); - return; + /* singlepart */ + chunk_size = bf_size; + ev = GNUNET_MQ_msg_extra (msg, + chunk_size, + GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF); + GNUNET_assert (GNUNET_SYSERR != + GNUNET_CONTAINER_bloomfilter_get_raw_data (op->state->local_bf, + (char*) &msg[1], + bf_size)); + msg->sender_element_count = htonl (op->state->my_element_count); + msg->bloomfilter_total_length = htonl (bf_size); + msg->bits_per_element = htonl (bf_elementbits); + msg->sender_mutator = htonl (op->state->salt); + msg->element_xor_hash = op->state->my_xor; + GNUNET_MQ_send (op->mq, ev); } - msg->operation = htonl (GNUNET_SET_OPERATION_INTERSECTION); - msg->app_id = op->spec->app_id; - msg->salt = htonl (op->spec->salt); - GNUNET_MQ_send (op->mq, ev); - - if (NULL != op->spec->context_msg) - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "sent op request with context message\n"); else - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "sent op request without context message\n"); - - if (NULL != op->spec->context_msg) { - GNUNET_free (op->spec->context_msg); - op->spec->context_msg = NULL; + /* multipart */ + bf_data = GNUNET_malloc (bf_size); + GNUNET_assert (GNUNET_SYSERR != + GNUNET_CONTAINER_bloomfilter_get_raw_data (op->state->local_bf, + bf_data, + bf_size)); + offset = 0; + while (offset < bf_size) + { + if (bf_size - chunk_size < offset) + chunk_size = bf_size - offset; + ev = GNUNET_MQ_msg_extra (msg, + chunk_size, + GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF); + GNUNET_memcpy (&msg[1], + &bf_data[offset], + chunk_size); + offset += chunk_size; + msg->sender_element_count = htonl (op->state->my_element_count); + msg->bloomfilter_total_length = htonl (bf_size); + msg->bits_per_element = htonl (bf_elementbits); + msg->sender_mutator = htonl (op->state->salt); + msg->element_xor_hash = op->state->my_xor; + GNUNET_MQ_send (op->mq, ev); + } + GNUNET_free (bf_data); } - + GNUNET_CONTAINER_bloomfilter_free (op->state->local_bf); + op->state->local_bf = NULL; } /** - * Handle an BF message from a remote peer. + * Signal to the client that the operation has finished and + * destroy the operation. * - * @param cls the intersection operation - * @param mh the header of the message + * @param cls operation to destroy */ static void -handle_p2p_bf (void *cls, const struct GNUNET_MessageHeader *mh) +send_client_done_and_destroy (void *cls) { - struct OperationState *eo = cls; - struct BFMessage *msg = (struct BFMessage *) mh; - unsigned int buckets_in_message; - - if (eo->phase == PHASE_EXPECT_INITIAL ) - { - eo->phase = PHASE_BF_EXCHANGE; - - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "creating new bf of size %u\n", 1<order); - - // if (the remote peer has less elements than us) - // run our elements through his bloomfilter - // else if (we have the same elements) - // done; - // - // evict elements we can exclude through the bloomfilter - // - // create a new bloomfilter over our remaining elements - // - // send our new count and the bloomfilter back - } - else if (eo->phase == PHASE_BF_EXCHANGE) - { - - } + struct Operation *op = cls; + struct GNUNET_MQ_Envelope *ev; + struct GNUNET_SET_ResultMessage *rm; + ev = GNUNET_MQ_msg (rm, + GNUNET_MESSAGE_TYPE_SET_RESULT); + rm->request_id = htonl (op->spec->client_request_id); + rm->result_status = htons (GNUNET_SET_STATUS_DONE); + rm->element_type = htons (0); + GNUNET_MQ_send (op->spec->set->client_mq, + ev); + _GSS_operation_destroy (op, + GNUNET_YES); } /** - * Send a result message to the client indicating - * that there is a new element. + * Send all elements in the full result iterator. * - * @param eo intersection operation - * @param element element to send + * @param cls the `struct Operation *` */ static void -send_client_element (struct OperationState *eo, - struct GNUNET_SET_Element *element) +send_remaining_elements (void *cls) { + struct Operation *op = cls; + const void *nxt; + const struct ElementEntry *ee; struct GNUNET_MQ_Envelope *ev; struct GNUNET_SET_ResultMessage *rm; + const struct GNUNET_SET_Element *element; + int res; - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "sending element (size %u) to client\n", element->size); - GNUNET_assert (0 != eo->spec->client_request_id); - ev = GNUNET_MQ_msg_extra (rm, element->size, GNUNET_MESSAGE_TYPE_SET_RESULT); - if (NULL == ev) + res = GNUNET_CONTAINER_multihashmap_iterator_next (op->state->full_result_iter, + NULL, + &nxt); + if (GNUNET_NO == res) { - GNUNET_MQ_discard (ev); - GNUNET_break (0); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Sending done and destroy because iterator ran out\n"); + op->keep--; + send_client_done_and_destroy (op); return; } + ee = nxt; + element = &ee->element; + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Sending element %s:%u to client (full set)\n", + GNUNET_h2s (&ee->element_hash), + element->size); + GNUNET_assert (0 != op->spec->client_request_id); + ev = GNUNET_MQ_msg_extra (rm, + element->size, + GNUNET_MESSAGE_TYPE_SET_RESULT); + GNUNET_assert (NULL != ev); rm->result_status = htons (GNUNET_SET_STATUS_OK); - rm->request_id = htonl (eo->spec->client_request_id); - rm->element_type = element->type; - memcpy (&rm[1], element->data, element->size); - GNUNET_MQ_send (eo->spec->set->client_mq, ev); + rm->request_id = htonl (op->spec->client_request_id); + rm->element_type = element->element_type; + GNUNET_memcpy (&rm[1], + element->data, + element->size); + GNUNET_MQ_notify_sent (ev, + &send_remaining_elements, + op); + GNUNET_MQ_send (op->spec->set->client_mq, + ev); } /** - * Send a result message to the client indicating - * that the operation is over. - * After the result done message has been sent to the client, - * destroy the evaluate operation. + * Inform the peer that this operation is complete. * - * @param eo intersection operation + * @param op the intersection operation to fail */ static void -send_client_done_and_destroy (struct OperationState *eo) +send_peer_done (struct Operation *op) { struct GNUNET_MQ_Envelope *ev; - struct GNUNET_SET_ResultMessage *rm; - - GNUNET_assert (GNUNET_NO == eo->client_done_sent); - - eo->client_done_sent = GNUNET_YES; - - ev = GNUNET_MQ_msg (rm, GNUNET_MESSAGE_TYPE_SET_RESULT); - rm->request_id = htonl (eo->spec->client_request_id); - rm->result_status = htons (GNUNET_SET_STATUS_DONE); - rm->element_type = htons (0); - GNUNET_MQ_send (eo->spec->set->client_mq, ev); - - intersection_operation_destroy (eo); + struct IntersectionDoneMessage *idm; + + op->state->phase = PHASE_FINISHED; + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Intersection succeeded, sending DONE\n"); + GNUNET_CONTAINER_bloomfilter_free (op->state->local_bf); + op->state->local_bf = NULL; + + ev = GNUNET_MQ_msg (idm, + GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_DONE); + idm->final_element_count = htonl (op->state->my_element_count); + idm->element_xor_hash = op->state->my_xor; + GNUNET_MQ_send (op->mq, + ev); } + /** - * Send a bloomfilter to our peer. - * that the operation is over. - * After the result done message has been sent to the client, - * destroy the evaluate operation. + * Process a Bloomfilter once we got all the chunks. * - * @param eo intersection operation + * @param op the intersection operation */ static void -send_bloomfilter (struct OperationState *eo){ - //get number of all elements still in the set - - // send the bloomfilter - unsigned int buckets_sent = 0; - struct BloomFilter *bf; - //TODO: - // add all our elements to the bloomfilter - // create new bloomfilter for all our elements & count elements - //GNUNET_CONTAINER_multihashmap32_remove - //eo->local_bf = GNUNET_CONTAINER_multihashmap32_iterate(eo->set->elements, add); - - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "sending bf of size %u\n", 1<local_bf; - - while (buckets_sent < (1 << bf_order)) +process_bf (struct Operation *op) +{ + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Received BF in phase %u, foreign count is %u, my element count is %u/%u\n", + op->state->phase, + op->spec->remote_element_count, + op->state->my_element_count, + GNUNET_CONTAINER_multihashmap_size (op->spec->set->content->elements)); + switch (op->state->phase) { - unsigned int buckets_in_message; - struct GNUNET_MQ_Envelope *ev; - struct IBFMessage *msg; - - buckets_in_message = (1 << bf_order) - buckets_sent; - /* limit to maximum */ - if (buckets_in_message > MAX_BUCKETS_PER_MESSAGE) - buckets_in_message = MAX_BUCKETS_PER_MESSAGE; - - ev = GNUNET_MQ_msg_extra (msg, buckets_in_message * IBF_BUCKET_SIZE, - GNUNET_MESSAGE_TYPE_SET_P2P_BF); - msg->reserved = 0; - msg->order = bf_order; - msg->offset = htons (buckets_sent); - ibf_write_slice (ibf, buckets_sent, - buckets_in_message, &msg[1]); - buckets_sent += buckets_in_message; - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ibf chunk size %u, %u/%u sent\n", - buckets_in_message, buckets_sent, 1<mq, ev); + case PHASE_INITIAL: + GNUNET_break_op (0); + fail_intersection_operation(op); + return; + case PHASE_COUNT_SENT: + /* This is the first BF being sent, build our initial map with + filtering in place */ + op->state->my_elements + = GNUNET_CONTAINER_multihashmap_create (op->spec->remote_element_count, + GNUNET_YES); + op->state->my_element_count = 0; + GNUNET_CONTAINER_multihashmap_iterate (op->spec->set->content->elements, + &filtered_map_initialization, + op); + break; + case PHASE_BF_EXCHANGE: + /* Update our set by reduction */ + GNUNET_CONTAINER_multihashmap_iterate (op->state->my_elements, + &iterator_bf_reduce, + op); + break; + case PHASE_FINISHED: + GNUNET_break_op (0); + fail_intersection_operation(op); + return; } - - eo->phase = PHASE_EXPECT_BF; + GNUNET_CONTAINER_bloomfilter_free (op->state->remote_bf); + op->state->remote_bf = NULL; + + if ( (0 == op->state->my_element_count) || /* fully disjoint */ + ( (op->state->my_element_count == op->spec->remote_element_count) && + (0 == memcmp (&op->state->my_xor, + &op->state->other_xor, + sizeof (struct GNUNET_HashCode))) ) ) + { + /* we are done */ + send_peer_done (op); + return; + } + op->state->phase = PHASE_BF_EXCHANGE; + send_bloomfilter (op); } + /** - * Handle a done message from a remote peer + * Handle an BF message from a remote peer. * * @param cls the intersection operation - * @param mh the message + * @param mh the header of the message */ static void -handle_p2p_done (void *cls, const struct GNUNET_MessageHeader *mh) +handle_p2p_bf (void *cls, + const struct GNUNET_MessageHeader *mh) { - struct OperationState *eo = cls; - struct GNUNET_MQ_Envelope *ev; - - if (eo->phase == PHASE_EXPECT_ELEMENTS_AND_REQUESTS) + struct Operation *op = cls; + const struct BFMessage *msg; + uint32_t bf_size; + uint32_t chunk_size; + uint32_t bf_bits_per_element; + uint16_t msize; + + msize = htons (mh->size); + if (msize < sizeof (struct BFMessage)) { - /* we got all requests, but still have to send our elements as response */ - - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "got DONE, sending final DONE after elements\n"); - eo->phase = PHASE_FINISHED; - ev = GNUNET_MQ_msg_header (GNUNET_MESSAGE_TYPE_SET_P2P_DONE); - GNUNET_MQ_send (eo->mq, ev); + GNUNET_break_op (0); + fail_intersection_operation (op); return; } - if (eo->phase == PHASE_EXPECT_ELEMENTS) + msg = (const struct BFMessage *) mh; + switch (op->state->phase) { - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "got final DONE\n"); - eo->phase = PHASE_FINISHED; - send_client_done_and_destroy (eo); - return; + case PHASE_INITIAL: + GNUNET_break_op (0); + fail_intersection_operation (op); + break; + case PHASE_COUNT_SENT: + case PHASE_BF_EXCHANGE: + bf_size = ntohl (msg->bloomfilter_total_length); + bf_bits_per_element = ntohl (msg->bits_per_element); + chunk_size = msize - sizeof (struct BFMessage); + op->state->other_xor = msg->element_xor_hash; + if (bf_size == chunk_size) + { + if (NULL != op->state->bf_data) + { + GNUNET_break_op (0); + fail_intersection_operation (op); + return; + } + /* single part, done here immediately */ + op->state->remote_bf + = GNUNET_CONTAINER_bloomfilter_init ((const char*) &msg[1], + bf_size, + bf_bits_per_element); + op->state->salt = ntohl (msg->sender_mutator); + op->spec->remote_element_count = ntohl (msg->sender_element_count); + process_bf (op); + return; + } + /* multipart chunk */ + if (NULL == op->state->bf_data) + { + /* first chunk, initialize */ + op->state->bf_data = GNUNET_malloc (bf_size); + op->state->bf_data_size = bf_size; + op->state->bf_bits_per_element = bf_bits_per_element; + op->state->bf_data_offset = 0; + op->state->salt = ntohl (msg->sender_mutator); + op->spec->remote_element_count = ntohl (msg->sender_element_count); + } + else + { + /* increment */ + if ( (op->state->bf_data_size != bf_size) || + (op->state->bf_bits_per_element != bf_bits_per_element) || + (op->state->bf_data_offset + chunk_size > bf_size) || + (op->state->salt != ntohl (msg->sender_mutator)) || + (op->spec->remote_element_count != ntohl (msg->sender_element_count)) ) + { + GNUNET_break_op (0); + fail_intersection_operation (op); + return; + } + } + GNUNET_memcpy (&op->state->bf_data[op->state->bf_data_offset], + (const char*) &msg[1], + chunk_size); + op->state->bf_data_offset += chunk_size; + if (op->state->bf_data_offset == bf_size) + { + /* last chunk, run! */ + op->state->remote_bf + = GNUNET_CONTAINER_bloomfilter_init (op->state->bf_data, + bf_size, + bf_bits_per_element); + GNUNET_free (op->state->bf_data); + op->state->bf_data = NULL; + op->state->bf_data_size = 0; + process_bf (op); + } + break; + default: + GNUNET_break_op (0); + fail_intersection_operation (op); + break; } - GNUNET_break (0); - fail_intersection_operation (eo); } /** - * Evaluate a union operation with - * a remote peer. + * Fills the "my_elements" hashmap with the initial set of + * (non-deleted) elements from the set of the specification. * - * @param op operation to evaluate + * @param cls closure with the `struct Operation *` + * @param key current key code for the element + * @param value value in the hash map with the `struct ElementEntry *` + * @return #GNUNET_YES (we should continue to iterate) */ -static void -intersection_evaluate (struct Operation *op) +static int +initialize_map_unfiltered (void *cls, + const struct GNUNET_HashCode *key, + void *value) { - op->state = GNUNET_new (struct OperationState); - /* we started the operation, thus we have to send the operation request */ - op->state->phase = PHASE_BF_EXCHANGE; - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "evaluating intersection operation"); - send_operation_request (op); + struct ElementEntry *ee = value; + struct Operation *op = cls; + + if (GNUNET_NO == _GSS_is_element_of_operation (ee, op)) + return GNUNET_YES; /* element not live in operation's generation */ + GNUNET_CRYPTO_hash_xor (&op->state->my_xor, + &ee->element_hash, + &op->state->my_xor); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Initial full initialization of my_elements, adding %s:%u\n", + GNUNET_h2s (&ee->element_hash), + ee->element.size); + GNUNET_break (GNUNET_YES == + GNUNET_CONTAINER_multihashmap_put (op->state->my_elements, + &ee->element_hash, + ee, + GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); + return GNUNET_YES; } /** - * Accept an union operation request from a remote peer. - * Only initializes the private operation state. + * Send our element count to the peer, in case our element count is + * lower than his. * - * @param op operation that will be accepted as a union operation + * @param op intersection operation */ static void -intersection_accept (struct Operation *op) +send_element_count (struct Operation *op) { - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "accepting set union operation\n"); - op->state = GNUNET_new (struct OperationState); - - op->state->contained_elements = GNUNET_CONTAINER_multihashmap_create(1, GNUNET_YES); - - if (NULL != op->state->remote_bf){ - // run the set through the remote bloomfilter - ; - } - - // - op->state->local_bf; - - /* kick off the operation */ - send_bloomfilter (op); + struct GNUNET_MQ_Envelope *ev; + struct IntersectionElementInfoMessage *msg; + + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Sending our element count (%u)\n", + op->state->my_element_count); + ev = GNUNET_MQ_msg (msg, + GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_ELEMENT_INFO); + msg->sender_element_count = htonl (op->state->my_element_count); + GNUNET_MQ_send (op->mq, ev); } /** - * Create a new set supporting the intersection operation + * We go first, initialize our map with all elements and + * send the first Bloom filter. * - * @return the newly created set + * @param op operation to start exchange for */ -static struct SetState * -intersection_set_create (void) +static void +begin_bf_exchange (struct Operation *op) { - struct SetState *set_state; - - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "intersection set created\n"); - - set_state = GNUNET_new (struct SetState); - - return set_state; + op->state->phase = PHASE_BF_EXCHANGE; + op->state->my_elements + = GNUNET_CONTAINER_multihashmap_create (op->state->my_element_count, + GNUNET_YES); + GNUNET_CONTAINER_multihashmap_iterate (op->spec->set->content->elements, + &initialize_map_unfiltered, + op); + send_bloomfilter (op); } /** - * Add the element from the given element message to the set. + * Handle the initial `struct IntersectionElementInfoMessage` from a + * remote peer. * - * @param set_state state of the set want to add to - * @param ee the element to add to the set + * @param cls the intersection operation + * @param mh the header of the message */ static void -intersection_add (struct SetState *set_state, struct ElementEntry *ee) +handle_p2p_element_info (void *cls, + const struct GNUNET_MessageHeader *mh) { - //nothing to do here + struct Operation *op = cls; + const struct IntersectionElementInfoMessage *msg; + + if (ntohs (mh->size) != sizeof (struct IntersectionElementInfoMessage)) + { + GNUNET_break_op (0); + fail_intersection_operation(op); + return; + } + msg = (const struct IntersectionElementInfoMessage *) mh; + op->spec->remote_element_count = ntohl (msg->sender_element_count); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Received remote element count (%u), I have %u\n", + op->spec->remote_element_count, + op->state->my_element_count); + if ( ( (PHASE_INITIAL != op->state->phase) && + (PHASE_COUNT_SENT != op->state->phase) ) || + (op->state->my_element_count > op->spec->remote_element_count) || + (0 == op->state->my_element_count) || + (0 == op->spec->remote_element_count) ) + { + GNUNET_break_op (0); + fail_intersection_operation(op); + return; + } + GNUNET_break (NULL == op->state->remote_bf); + begin_bf_exchange (op); } /** - * Destroy a set that supports the intersection operation + * Send a result message to the client indicating that the operation + * is over. After the result done message has been sent to the + * client, destroy the evaluate operation. * - * @param set_state the set to destroy + * @param op intersection operation */ static void -intersection_set_destroy (struct SetState *set_state) +finish_and_destroy (struct Operation *op) { - GNUNET_free (set_state); + GNUNET_assert (GNUNET_NO == op->state->client_done_sent); + + if (GNUNET_SET_RESULT_FULL == op->spec->result_mode) + { + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Sending full result set (%u elements)\n", + GNUNET_CONTAINER_multihashmap_size (op->state->my_elements)); + op->state->full_result_iter + = GNUNET_CONTAINER_multihashmap_iterator_create (op->state->my_elements); + op->keep++; + send_remaining_elements (op); + return; + } + send_client_done_and_destroy (op); } /** - * Remove the element given in the element message from the set. + * Remove all elements from our hashmap. * - * @param set_state state of the set to remove from - * @param element set element to remove + * @param cls closure with the `struct Operation *` + * @param key current key code + * @param value value in the hash map + * @return #GNUNET_YES (we should continue to iterate) */ -static void -intersection_remove (struct SetState *set_state, struct ElementEntry *element) +static int +filter_all (void *cls, + const struct GNUNET_HashCode *key, + void *value) { - //nothing to do here + struct Operation *op = cls; + struct ElementEntry *ee = value; + + GNUNET_break (0 < op->state->my_element_count); + op->state->my_element_count--; + GNUNET_CRYPTO_hash_xor (&op->state->my_xor, + &ee->element_hash, + &op->state->my_xor); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Final reduction of my_elements, removing %s:%u\n", + GNUNET_h2s (&ee->element_hash), + ee->element.size); + GNUNET_assert (GNUNET_YES == + GNUNET_CONTAINER_multihashmap_remove (op->state->my_elements, + &ee->element_hash, + ee)); + send_client_removed_element (op, + &ee->element); + return GNUNET_YES; } /** - * Dispatch messages for a intersection operation. + * Handle a done message from a remote peer * - * @param eo the state of the intersection evaluate operation - * @param mh the received message - * @return GNUNET_SYSERR if the tunnel should be disconnected, - * GNUNET_OK otherwise + * @param cls the intersection operation + * @param mh the message */ -int -intersection_handle_p2p_message (struct OperationState *eo, - const struct GNUNET_MessageHeader *mh) +static void +handle_p2p_done (void *cls, + const struct GNUNET_MessageHeader *mh) { - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "received p2p message (t: %u, s: %u)\n", - ntohs (mh->type), ntohs (mh->size)); - switch (ntohs (mh->type)) + struct Operation *op = cls; + const struct IntersectionDoneMessage *idm; + + if (PHASE_BF_EXCHANGE != op->state->phase) { - /* this message handler is not active until after we received an - * operation request message, thus the ops request is not handled here - */ - case GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF: - handle_p2p_bf (eo, mh); - break; - case GNUNET_MESSAGE_TYPE_SET_P2P_DONE: - handle_p2p_done (eo, mh); - break; - default: - /* something wrong with mesh's message handlers? */ - GNUNET_assert (0); + /* wrong phase to conclude? FIXME: Or should we allow this + if the other peer has _initially_ already an empty set? */ + GNUNET_break_op (0); + fail_intersection_operation (op); + return; } - return GNUNET_OK; + if (ntohs (mh->size) != sizeof (struct IntersectionDoneMessage)) + { + GNUNET_break_op (0); + fail_intersection_operation (op); + return; + } + idm = (const struct IntersectionDoneMessage *) mh; + if (0 == ntohl (idm->final_element_count)) + { + /* other peer determined empty set is the intersection, + remove all elements */ + GNUNET_CONTAINER_multihashmap_iterate (op->state->my_elements, + &filter_all, + op); + } + if ( (op->state->my_element_count != ntohl (idm->final_element_count)) || + (0 != memcmp (&op->state->my_xor, + &idm->element_xor_hash, + sizeof (struct GNUNET_HashCode))) ) + { + /* Other peer thinks we are done, but we disagree on the result! */ + GNUNET_break_op (0); + fail_intersection_operation (op); + return; + } + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Got IntersectionDoneMessage, have %u elements in intersection\n", + op->state->my_element_count); + op->state->phase = PHASE_FINISHED; + finish_and_destroy (op); } + /** - * Signal to the client that the operation has finished and - * destroy the operation. + * Initiate a set intersection operation with a remote peer. * - * @param cls operation to destroy + * @param op operation that is created, should be initialized to + * begin the evaluation + * @param opaque_context message to be transmitted to the listener + * to convince him to accept, may be NULL */ static void -send_done_and_destroy (void *cls) +intersection_evaluate (struct Operation *op, + const struct GNUNET_MessageHeader *opaque_context) { - struct Operation *op = cls; struct GNUNET_MQ_Envelope *ev; - struct GNUNET_SET_ResultMessage *rm; - ev = GNUNET_MQ_msg (rm, GNUNET_MESSAGE_TYPE_SET_RESULT); - rm->request_id = htonl (op->spec->client_request_id); - rm->result_status = htons (GNUNET_SET_STATUS_DONE); - rm->element_type = htons (0); - GNUNET_MQ_send (op->spec->set->client_mq, ev); - _GSS_operation_destroy (op); + struct OperationRequestMessage *msg; + + op->state = GNUNET_new (struct OperationState); + /* we started the operation, thus we have to send the operation request */ + op->state->phase = PHASE_INITIAL; + op->state->my_element_count = op->spec->set->state->current_set_element_count; + + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Initiating intersection operation evaluation\n"); + ev = GNUNET_MQ_msg_nested_mh (msg, + GNUNET_MESSAGE_TYPE_SET_P2P_OPERATION_REQUEST, + opaque_context); + if (NULL == ev) + { + /* the context message is too large!? */ + GNUNET_break (0); + GNUNET_SERVER_client_disconnect (op->spec->set->client); + return; + } + msg->operation = htonl (GNUNET_SET_OPERATION_INTERSECTION); + msg->element_count = htonl (op->state->my_element_count); + GNUNET_MQ_send (op->mq, + ev); + op->state->phase = PHASE_COUNT_SENT; + if (NULL != opaque_context) + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Sent op request with context message\n"); + else + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Sent op request without context message\n"); } + /** - * Send a result message to the client indicating - * that the operation is over. - * After the result done message has been sent to the client, - * destroy the evaluate operation. + * Accept an intersection operation request from a remote peer. Only + * initializes the private operation state. * - * @param op union operation + * @param op operation that will be accepted as an intersection operation */ static void -finish_and_destroy (struct Operation *op) +intersection_accept (struct Operation *op) { - GNUNET_assert (GNUNET_NO == op->state->client_done_sent); - - if (GNUNET_SET_RESULT_FULL == op->spec->result_mode) + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Accepting set intersection operation\n"); + op->state = GNUNET_new (struct OperationState); + op->state->phase = PHASE_INITIAL; + op->state->my_element_count + = op->spec->set->state->current_set_element_count; + op->state->my_elements + = GNUNET_CONTAINER_multihashmap_create + (GNUNET_MIN (op->state->my_element_count, + op->spec->remote_element_count), + GNUNET_YES); + if (op->spec->remote_element_count < op->state->my_element_count) { - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "sending full result set\n"); - GNUNET_assert (NULL == op->state->full_result_iter); - op->state->full_result_iter = - GNUNET_CONTAINER_multihashmap32_iterator_create (op->state->contained_elements); + /* If the other peer (Alice) has fewer elements than us (Bob), + we just send the count as Alice should send the first BF */ + send_element_count (op); + op->state->phase = PHASE_COUNT_SENT; return; } - send_done_and_destroy (op); + /* We have fewer elements, so we start with the BF */ + begin_bf_exchange (op); } +/** + * Dispatch messages for a intersection operation. + * + * @param op the state of the intersection evaluate operation + * @param mh the received message + * @return #GNUNET_SYSERR if the tunnel should be disconnected, + * #GNUNET_OK otherwise + */ +static int +intersection_handle_p2p_message (struct Operation *op, + const struct GNUNET_MessageHeader *mh) +{ + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Received p2p message (t: %u, s: %u)\n", + ntohs (mh->type), ntohs (mh->size)); + switch (ntohs (mh->type)) + { + /* this message handler is not active until after we received an + * operation request message, thus the ops request is not handled here + */ + case GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_ELEMENT_INFO: + handle_p2p_element_info (op, mh); + break; + case GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF: + handle_p2p_bf (op, mh); + break; + case GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_DONE: + handle_p2p_done (op, mh); + break; + default: + /* something wrong with cadet's message handlers? */ + GNUNET_assert (0); + } + return GNUNET_OK; +} + + +/** + * Handler for peer-disconnects, notifies the client about the aborted + * operation. If we did not expect anything from the other peer, we + * gracefully terminate the operation. + * + * @param op the destroyed operation + */ static void intersection_peer_disconnect (struct Operation *op) { if (PHASE_FINISHED != op->state->phase) { - struct GNUNET_MQ_Envelope *ev; - struct GNUNET_SET_ResultMessage *msg; - - ev = GNUNET_MQ_msg (msg, GNUNET_MESSAGE_TYPE_SET_RESULT); - msg->request_id = htonl (op->spec->client_request_id); - msg->result_status = htons (GNUNET_SET_STATUS_FAILURE); - msg->element_type = htons (0); - GNUNET_MQ_send (op->spec->set->client_mq, ev); - GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "other peer disconnected prematurely\n"); - _GSS_operation_destroy (op); + fail_intersection_operation (op); return; } - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "other peer disconnected (finished)\n"); + /* the session has already been concluded */ + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Other peer disconnected (finished)\n"); if (GNUNET_NO == op->state->client_done_sent) finish_and_destroy (op); } /** - * Destroy the union operation. Only things specific to the union operation are destroyed. - * - * @param op union operation to destroy + * Destroy the intersection operation. Only things specific to the + * intersection operation are destroyed. + * + * @param op intersection operation to destroy */ static void intersection_op_cancel (struct Operation *op) { - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "destroying intersection op\n"); /* check if the op was canceled twice */ GNUNET_assert (NULL != op->state); if (NULL != op->state->remote_bf) @@ -655,17 +1163,83 @@ intersection_op_cancel (struct Operation *op) GNUNET_CONTAINER_bloomfilter_free (op->state->local_bf); op->state->local_bf = NULL; } - if (NULL != op->state->contained_elements) + if (NULL != op->state->my_elements) { - // no need to free the elements, they are still part of the set - GNUNET_CONTAINER_multihashmap_destroy (op->state->contained_elements); - op->state->contained_elements = NULL; + GNUNET_CONTAINER_multihashmap_destroy (op->state->my_elements); + op->state->my_elements = NULL; } GNUNET_free (op->state); op->state = NULL; - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "destroying intersection op done\n"); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Destroying intersection op state done\n"); } + +/** + * Create a new set supporting the intersection operation. + * + * @return the newly created set + */ +static struct SetState * +intersection_set_create () +{ + struct SetState *set_state; + + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Intersection set created\n"); + set_state = GNUNET_new (struct SetState); + set_state->current_set_element_count = 0; + + return set_state; +} + + +/** + * Add the element from the given element message to the set. + * + * @param set_state state of the set want to add to + * @param ee the element to add to the set + */ +static void +intersection_add (struct SetState *set_state, + struct ElementEntry *ee) +{ + set_state->current_set_element_count++; +} + + +/** + * Destroy a set that supports the intersection operation + * + * @param set_state the set to destroy + */ +static void +intersection_set_destroy (struct SetState *set_state) +{ + GNUNET_free (set_state); +} + + +/** + * Remove the element given in the element message from the set. + * + * @param set_state state of the set to remove from + * @param element set element to remove + */ +static void +intersection_remove (struct SetState *set_state, + struct ElementEntry *element) +{ + GNUNET_assert (0 < set_state->current_set_element_count); + set_state->current_set_element_count--; +} + + +/** + * Get the table with implementing functions for set intersection. + * + * @return the operation specific VTable + */ const struct SetVT * _GSS_intersection_vt () {