bg_bf.c File Reference

implementation of a block group using a Bloom filter to drop duplicate blocks More...

#include "platform.h"
#include "gnunet_util_lib.h"
#include "gnunet_block_group_lib.h"
#include "gnunet_block_plugin.h"

Include dependency graph for bg_bf.c:

Go to the source code of this file.

Data Structures
struct	BfGroupInternals
	Internal data structure for a block group. More...

Functions
static enum GNUNET_GenericReturnValue	bf_group_serialize_cb (struct GNUNET_BLOCK_Group *bg, void **raw_data, size_t *raw_data_size)
	Serialize state of a block group. More...
static void	bf_group_mark_seen_cb (struct GNUNET_BLOCK_Group *bg, const struct GNUNET_HashCode *seen_results, unsigned int seen_results_count)
	Mark elements as "seen" using a hash of the element. More...
static enum GNUNET_GenericReturnValue	bf_group_merge_cb (struct GNUNET_BLOCK_Group *bg1, const struct GNUNET_BLOCK_Group *bg2)
	Merge two groups, if possible. More...
static void	bf_group_destroy_cb (struct GNUNET_BLOCK_Group *bg)
	Destroy resources used by a block group. More...
struct GNUNET_BLOCK_Group *	GNUNET_BLOCK_GROUP_bf_create (void *cls, size_t bf_size, unsigned int bf_k, enum GNUNET_BLOCK_Type type, const void *raw_data, size_t raw_data_size)
	Create a new block group that filters duplicates using a Bloom filter. More...
enum GNUNET_GenericReturnValue	GNUNET_BLOCK_GROUP_bf_test_and_set (struct GNUNET_BLOCK_Group *bg, const struct GNUNET_HashCode *hc)
	Test if hc is contained in the Bloom filter of bg. More...
size_t	GNUNET_BLOCK_GROUP_compute_bloomfilter_size (unsigned int entry_count, unsigned int k)
	How many bytes should a bloomfilter be if we have already seen entry_count responses? Sized so that do not have to re-size the filter too often (to keep it cheap). More...

Detailed Description

implementation of a block group using a Bloom filter to drop duplicate blocks

Author

Christian Grothoff

Definition in file bg_bf.c.

Function Documentation

bf_group_serialize_cb()

static enum GNUNET_GenericReturnValue bf_group_serialize_cb ( struct GNUNET_BLOCK_Group *  bg, void **  raw_data, size_t *  raw_data_size  )

static

Serialize state of a block group.

Parameters

	bg	group to serialize
[out]	raw_data	set to the serialized state
[out]	raw_data_size	set to the number of bytes in raw_data

Returns

GNUNET_OK on success, GNUNET_NO if serialization is not supported, GNUNET_SYSERR on error

Definition at line 64 of file bg_bf.c.

{
  struct BfGroupInternals *gi = bg->internal_cls;
  void *raw;
 
  raw = GNUNET_malloc (gi->bf_size + sizeof (uint32_t));
  if (GNUNET_OK !=
      GNUNET_CONTAINER_bloomfilter_get_raw_data (gi->bf,
                                                 raw + sizeof (uint32_t),
                                                 gi->bf_size))
  {
    GNUNET_free (raw);
    GNUNET_break (0);
    return GNUNET_SYSERR;
  }
  memcpy (raw,
          &gi->bf_mutator,
          sizeof (uint32_t));
  *raw_data = raw;
  *raw_data_size = gi->bf_size + sizeof (uint32_t);
  return GNUNET_OK;
}

References BfGroupInternals::bf, BfGroupInternals::bf_mutator, BfGroupInternals::bf_size, GNUNET_break, GNUNET_CONTAINER_bloomfilter_get_raw_data(), GNUNET_free, GNUNET_malloc, GNUNET_OK, GNUNET_SYSERR, GNUNET_BLOCK_Group::internal_cls, and raw.

Referenced by GNUNET_BLOCK_GROUP_bf_create().

Here is the call graph for this function:

Here is the caller graph for this function:

bf_group_mark_seen_cb()

static void bf_group_mark_seen_cb ( struct GNUNET_BLOCK_Group *  bg, const struct GNUNET_HashCode *  seen_results, unsigned int  seen_results_count  )

static

Mark elements as "seen" using a hash of the element.

Not supported by all block plugins.

Parameters

bg	group to update
seen_results	results already seen
seen_results_count	number of entries in seen_results

Definition at line 99 of file bg_bf.c.

{
  struct BfGroupInternals *gi = bg->internal_cls;
 
  for (unsigned int i = 0; i < seen_results_count; i++)
  {
    struct GNUNET_HashCode mhash;
 
    GNUNET_BLOCK_mingle_hash (&seen_results[i],
                              gi->bf_mutator,
                              &mhash);
    GNUNET_CONTAINER_bloomfilter_add (gi->bf,
                                      &mhash);
  }
}

References BfGroupInternals::bf, BfGroupInternals::bf_mutator, GNUNET_BLOCK_mingle_hash(), GNUNET_CONTAINER_bloomfilter_add(), and GNUNET_BLOCK_Group::internal_cls.

Referenced by GNUNET_BLOCK_GROUP_bf_create().

Here is the call graph for this function:

Here is the caller graph for this function:

bf_group_merge_cb()

static enum GNUNET_GenericReturnValue bf_group_merge_cb ( struct GNUNET_BLOCK_Group *  bg1, const struct GNUNET_BLOCK_Group *  bg2  )

static

Merge two groups, if possible.

Not supported by all block plugins, can also fail if the nonces were different.

Parameters

bg1	group to update
bg2	group to merge into bg1

Returns

GNUNET_OK on success, GNUNET_NO if the nonces were different and thus we failed.

Definition at line 128 of file bg_bf.c.

{
  struct BfGroupInternals *gi1 = bg1->internal_cls;
  struct BfGroupInternals *gi2 = bg2->internal_cls;
 
  if (gi1->bf_mutator != gi2->bf_mutator)
    return GNUNET_NO;
  if (gi1->bf_size != gi2->bf_size)
    return GNUNET_NO;
  GNUNET_CONTAINER_bloomfilter_or2 (gi1->bf,
                                    gi2->bf);
  return GNUNET_OK;
}

References BfGroupInternals::bf, BfGroupInternals::bf_mutator, BfGroupInternals::bf_size, GNUNET_CONTAINER_bloomfilter_or2(), GNUNET_NO, GNUNET_OK, and GNUNET_BLOCK_Group::internal_cls.

Referenced by GNUNET_BLOCK_GROUP_bf_create().

Here is the call graph for this function:

Here is the caller graph for this function:

bf_group_destroy_cb()

static void bf_group_destroy_cb ( struct GNUNET_BLOCK_Group *  bg )

static

Destroy resources used by a block group.

Parameters

bg	group to destroy, NULL is allowed

Definition at line 150 of file bg_bf.c.

{
  struct BfGroupInternals *gi = bg->internal_cls;
 
  GNUNET_CONTAINER_bloomfilter_free (gi->bf);
  GNUNET_free (gi);
  GNUNET_free (bg);
}

References BfGroupInternals::bf, GNUNET_CONTAINER_bloomfilter_free(), GNUNET_free, and GNUNET_BLOCK_Group::internal_cls.

Referenced by GNUNET_BLOCK_GROUP_bf_create().

Here is the call graph for this function:

Here is the caller graph for this function: