gnunet-service-setu_strata_estimator.h File Reference

#include "platform.h"
#include "gnunet_common.h"
#include "gnunet_util_lib.h"

Include dependency graph for gnunet-service-setu_strata_estimator.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	StrataEstimator
	A handle to a strata estimator. More...
struct	MultiStrataEstimator

Functions
uint8_t	determine_strata_count (uint64_t avg_element_size, uint64_t element_count)
	Deteminate how many strata estimators in the message are necessary. More...
size_t	strata_estimator_write (struct MultiStrataEstimator *se, uint16_t se_ibf_total_size, uint8_t number_se_send, void *buf)
	Write the given strata estimator to the buffer. More...
int	strata_estimator_read (const void *buf, size_t buf_len, int is_compressed, uint8_t number_se_received, uint16_t se_ibf_total_size, struct MultiStrataEstimator *se)
	Read strata from the buffer into the given strata estimator. More...
struct MultiStrataEstimator *	strata_estimator_create (unsigned int strata_count, uint32_t ibf_size, uint8_t ibf_hashnum)
	Create a new strata estimator with the given parameters. More...
void	strata_estimator_difference (const struct MultiStrataEstimator *se1, const struct MultiStrataEstimator *se2)
	Get an estimation of the symmetric difference of the elements contained in both strata estimators. More...
void	strata_estimator_insert (struct MultiStrataEstimator *se, struct IBF_Key key)
	Add a key to the strata estimator. More...
void	strata_estimator_remove (struct MultiStrataEstimator *se, struct IBF_Key key)
	Remove a key from the strata estimator. More...
void	strata_estimator_destroy (struct MultiStrataEstimator *se)
	Destroy a strata estimator, free all of its resources. More...
struct MultiStrataEstimator *	strata_estimator_dup (struct MultiStrataEstimator *se)
	Make a copy of a strata estimator. More...

Function Documentation

determine_strata_count()

uint8_t determine_strata_count	(	uint64_t	avg_element_size,
		uint64_t	element_count
	)

Deteminate how many strata estimators in the message are necessary.

Parameters

avg_element_size
element_count

Returns

number of strata's

Deteminate how many strata estimators in the message are necessary.

Parameters

avg_element_size
element_count

Returns

Definition at line 59 of file gnunet-service-setu_strata_estimator.c.

{
  uint64_t base_size = avg_element_size * element_count;
  /* >67kb total size of elements in set */
  if (base_size < AVG_BYTE_SIZE_SE * 16)
    return 1;
  /* >270kb total size of elements in set  */
  if (base_size < AVG_BYTE_SIZE_SE * 64)
    return 2;
  /* >1mb total size of elements in set */
  if (base_size < AVG_BYTE_SIZE_SE * 256)
    return 4;
  return 8;
}

References AVG_BYTE_SIZE_SE.

Referenced by handle_client_accept().

Here is the caller graph for this function:

strata_estimator_write()

size_t strata_estimator_write	(	struct MultiStrataEstimator *	se,
		uint16_t	se_ibf_total_size,
		uint8_t	number_se_send,
		void *	buf
	)

Write the given strata estimator to the buffer.

Parameters

	se	strata estimator to serialize
[out]	buf	buffer to write to, must be of appropriate size

Returns

number of bytes written to buf

Definition at line 118 of file gnunet-service-setu_strata_estimator.c.

{
  char *sbuf = buf;
  unsigned int i;
  size_t osize;
  uint64_t sbuf_offset = 0;
  se->size = number_se_send;
 
  GNUNET_assert (NULL != se);
  for (uint8_t strata_ctr = 0; strata_ctr < number_se_send; strata_ctr++)
  {
    for (i = 0; i < se->stratas[strata_ctr]->strata_count; i++)
    {
      ibf_write_slice (se->stratas[strata_ctr]->strata[i],
                       0,
                       se->stratas[strata_ctr]->ibf_size,
                       &sbuf[sbuf_offset],
                       8);
      sbuf_offset += se->stratas[strata_ctr]->ibf_size * IBF_BUCKET_SIZE;
    }
  }
  osize = ((se_ibf_total_size / 8) * number_se_send) * IBF_BUCKET_SIZE
          * se->stratas[0]->strata_count;
#if FAIL_10_1_COMPATIBILTIY
  {
    char *cbuf;
    size_t nsize;
 
    if (GNUNET_YES ==
        GNUNET_try_compression (buf,
                                osize,
                                &cbuf,
                                &nsize))
    {
      GNUNET_memcpy (buf,  cbuf, nsize);
      osize = nsize;
      GNUNET_free (cbuf);
    }
  }
#endif
  return osize;
}

References GNUNET_assert, GNUNET_free, GNUNET_memcpy, GNUNET_try_compression(), GNUNET_YES, IBF_BUCKET_SIZE, StrataEstimator::ibf_size, ibf_write_slice(), MultiStrataEstimator::size, StrataEstimator::strata, StrataEstimator::strata_count, and MultiStrataEstimator::stratas.

Here is the call graph for this function:

strata_estimator_read()

int strata_estimator_read	(	const void *	buf,
		size_t	buf_len,
		int	is_compressed,
		uint8_t	number_se_received,
		uint16_t	se_ibf_total_size,
		struct MultiStrataEstimator *	se
	)

Read strata from the buffer into the given strata estimator.

The strata estimator must already be allocated.

Parameters

	buf	buffer to read from
	buf_len	number of bytes in buf
	is_compressed	is the data compressed?
[out]	se	strata estimator to write to

Returns

GNUNET_OK on success

Definition at line 176 of file gnunet-service-setu_strata_estimator.c.

{
  unsigned int i;
  size_t osize;
  char *dbuf;
 
  dbuf = NULL;
  if (GNUNET_YES == is_compressed)
  {
    osize = ((se_ibf_total_size / 8) * number_se_received) * IBF_BUCKET_SIZE
            * se->stratas[0]->strata_count;
    dbuf = GNUNET_decompress (buf,
                              buf_len,
                              osize);
    if (NULL == dbuf)
    {
      GNUNET_break_op (0);    /* bad compressed input data */
      return GNUNET_SYSERR;
    }
    buf = dbuf;
    buf_len = osize;
  }
 
  if (buf_len != se->stratas[0]->strata_count * ((se_ibf_total_size / 8)
                                                 * number_se_received)
      * IBF_BUCKET_SIZE)
  {
    GNUNET_break (0);  /* very odd error */
    GNUNET_free (dbuf);
    return GNUNET_SYSERR;
  }
 
  for (uint8_t strata_ctr = 0; strata_ctr < number_se_received; strata_ctr++)
  {
    for (i = 0; i < se->stratas[strata_ctr]->strata_count; i++)
    {
      ibf_read_slice (buf, 0, se->stratas[strata_ctr]->ibf_size,
                      se->stratas[strata_ctr]->strata[i], 8);
      buf += se->stratas[strata_ctr]->ibf_size * IBF_BUCKET_SIZE;
    }
  }
  se->size = number_se_received;
  GNUNET_free (dbuf);
  return GNUNET_OK;
}

References GNUNET_break, GNUNET_break_op, GNUNET_decompress(), GNUNET_free, GNUNET_OK, GNUNET_SYSERR, GNUNET_YES, IBF_BUCKET_SIZE, ibf_read_slice(), StrataEstimator::ibf_size, MultiStrataEstimator::size, StrataEstimator::strata, StrataEstimator::strata_count, and MultiStrataEstimator::stratas.

Here is the call graph for this function:

strata_estimator_create()

struct MultiStrataEstimator * strata_estimator_create	(	unsigned int	strata_count,
		uint32_t	ibf_size,
		uint8_t	ibf_hashnum
	)

Create a new strata estimator with the given parameters.

Parameters

strata_count	number of stratas, that is, number of ibfs in the estimator
ibf_size	size of each ibf stratum
ibf_hashnum	hashnum parameter of each ibf

Returns

a freshly allocated, empty strata estimator, NULL on error

Definition at line 182 of file gnunet-service-set_union_strata_estimator.c.

{
  struct StrataEstimator *se;
  unsigned int i;
  unsigned int j;
 
  se = GNUNET_new (struct StrataEstimator);
  se->strata_count = strata_count;
  se->ibf_size = ibf_size;
  se->strata = GNUNET_new_array (strata_count,
                                 struct InvertibleBloomFilter *);
  for (i = 0; i < strata_count; i++)
  {
    se->strata[i] = ibf_create (ibf_size, ibf_hashnum);
    if (NULL == se->strata[i])
    {
      GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
                  "Failed to allocate memory for strata estimator\n");
      for (j = 0; j < i; j++)
        ibf_destroy (se->strata[i]);
      GNUNET_free (se);
      return NULL;
    }
  }
  return se;
}

References GNUNET_ERROR_TYPE_ERROR, GNUNET_free, GNUNET_log, GNUNET_new, GNUNET_new_array, ibf_create(), ibf_destroy(), StrataEstimator::ibf_size, ibf_size, MULTI_SE_BASE_COUNT, MultiStrataEstimator::size, StrataEstimator::strata, StrataEstimator::strata_count, and MultiStrataEstimator::stratas.

Referenced by handle_client_create_set(), handle_union_p2p_strata_estimator(), and union_set_create().

Here is the call graph for this function:

Here is the caller graph for this function:

strata_estimator_difference()

void strata_estimator_difference	(	const struct MultiStrataEstimator *	se1,
		const struct MultiStrataEstimator *	se2
	)

Get an estimation of the symmetric difference of the elements contained in both strata estimators.

Parameters

se1	first strata estimator
se2	second strata estimator

Returns

nothing

Get an estimation of the symmetric difference of the elements contained in both strata estimators.

arrays of IBFs. Does not not modify its arguments.

Parameters

se1	first strata estimator
se2	second strata estimator

Returns

the estimated difference

Definition at line 359 of file gnunet-service-setu_strata_estimator.c.

{
  int avg_local_diff = 0;
  int avg_remote_diff = 0;
  uint8_t number_of_estimators = se1->size;
 
  for (uint8_t strata_ctr = 0; strata_ctr < number_of_estimators; strata_ctr++)
  {
    GNUNET_assert (se1->stratas[strata_ctr]->strata_count ==
                   se2->stratas[strata_ctr]->strata_count);
 
 
    for (int i = se1->stratas[strata_ctr]->strata_count - 1; i >= 0; i--)
    {
      struct InvertibleBloomFilter *diff;
      /* number of keys decoded from the ibf */
 
      /* FIXME: implement this without always allocating new IBFs */
      diff = ibf_dup (se1->stratas[strata_ctr]->strata[i]);
      diff->local_decoded_count = 0;
      diff->remote_decoded_count = 0;
 
      ibf_subtract (diff, se2->stratas[strata_ctr]->strata[i]);
 
      for (int ibf_count = 0; GNUNET_YES; ibf_count++)
      {
        int more;
 
        more = ibf_decode (diff, NULL, NULL);
        if (GNUNET_NO == more)
        {
          se1->stratas[strata_ctr]->strata[0]->local_decoded_count +=
            diff->local_decoded_count;
          se1->stratas[strata_ctr]->strata[0]->remote_decoded_count +=
            diff->remote_decoded_count;
          break;
        }
        /* Estimate if decoding fails or would not terminate */
        if ((GNUNET_SYSERR == more) || (ibf_count > diff->size))
        {
          se1->stratas[strata_ctr]->strata[0]->local_decoded_count =
            se1->stratas[strata_ctr]->strata[0]->local_decoded_count * (1 << (i
                                                                              +
                                                                              1));
          se1->stratas[strata_ctr]->strata[0]->remote_decoded_count =
            se1->stratas[strata_ctr]->strata[0]->remote_decoded_count * (1 << (i
                                                                               +
                                                                               1));
          ibf_destroy (diff);
          goto break_all_counting_loops;
        }
      }
      ibf_destroy (diff);
    }
break_all_counting_loops:;
    avg_local_diff += se1->stratas[strata_ctr]->strata[0]->local_decoded_count;
    avg_remote_diff +=
      se1->stratas[strata_ctr]->strata[0]->remote_decoded_count;
  }
  se1->stratas[0]->strata[0]->local_decoded_count = avg_local_diff
                                                    / number_of_estimators;
  se1->stratas[0]->strata[0]->remote_decoded_count = avg_remote_diff
                                                     / number_of_estimators;
}

References GNUNET_assert, GNUNET_NO, GNUNET_SYSERR, GNUNET_YES, ibf_decode(), ibf_destroy(), ibf_dup(), ibf_subtract(), InvertibleBloomFilter::local_decoded_count, InvertibleBloomFilter::remote_decoded_count, InvertibleBloomFilter::size, MultiStrataEstimator::size, StrataEstimator::strata, StrataEstimator::strata_count, and MultiStrataEstimator::stratas.

Here is the call graph for this function:

strata_estimator_insert()

void strata_estimator_insert	(	struct MultiStrataEstimator *	se,
		struct IBF_Key	key
	)

Add a key to the strata estimator.

Parameters

se	strata estimator to add the key to
key	key to add

Definition at line 235 of file gnunet-service-setu_strata_estimator.c.

{
 
 
  /* count trailing '1'-bits of v */
  for (int strata_ctr = 0; strata_ctr < MULTI_SE_BASE_COUNT; strata_ctr++)
  {
    unsigned int i;
    uint64_t v;
 
    struct IBF_Key salted_key;
    salt_key (&key,
              strata_ctr * (64 / MULTI_SE_BASE_COUNT),
              &salted_key);
    v = salted_key.key_val;
    for (i = 0; v & 1; v >>= 1, i++)
    {
      ibf_insert (se->stratas[strata_ctr]->strata[i], salted_key);
    }
  }
  /* empty */;
 
}

References ibf_insert(), key, IBF_Key::key_val, MULTI_SE_BASE_COUNT, salt_key(), StrataEstimator::strata, and MultiStrataEstimator::stratas.

Here is the call graph for this function:

strata_estimator_remove()

void strata_estimator_remove	(	struct MultiStrataEstimator *	se,
		struct IBF_Key	key
	)

Remove a key from the strata estimator.

Parameters

se	strata estimator to remove the key from
key	key to remove

(NOT USED)

Parameters

se	strata estimator to remove the key from
key	key to remove

Definition at line 268 of file gnunet-service-setu_strata_estimator.c.

{
 
  /* count trailing '1'-bits of v */
  for (int strata_ctr = 0; strata_ctr < se->size; strata_ctr++)
  {
    uint64_t v;
    unsigned int i;
 
    struct IBF_Key unsalted_key;
    unsalt_key (&key,
                strata_ctr * (64 / MULTI_SE_BASE_COUNT),
                &unsalted_key);
 
    v = unsalted_key.key_val;
    for (i = 0; v & 1; v >>= 1, i++)
    {
      /* empty */;
      ibf_remove (se->stratas[strata_ctr]->strata[i], unsalted_key);
    }
  }
}

References ibf_remove(), key, IBF_Key::key_val, MULTI_SE_BASE_COUNT, MultiStrataEstimator::size, StrataEstimator::strata, MultiStrataEstimator::stratas, and unsalt_key().

Here is the call graph for this function:

strata_estimator_destroy()

void strata_estimator_destroy

(

struct MultiStrataEstimator *

se

)

Destroy a strata estimator, free all of its resources.

Parameters

se	strata estimator to destroy.

Definition at line 464 of file gnunet-service-setu_strata_estimator.c.

{
  unsigned int i;
  for (uint8_t strata_ctr = 0; strata_ctr < MULTI_SE_BASE_COUNT; strata_ctr++)
  {
    for (i = 0; i < se->stratas[strata_ctr]->strata_count; i++)
      ibf_destroy (se->stratas[strata_ctr]->strata[i]);
    GNUNET_free (se->stratas[strata_ctr]->strata);
    GNUNET_free (se->stratas[strata_ctr]);
  }
  GNUNET_free (se->stratas);
  GNUNET_free (se);
}

References GNUNET_free, ibf_destroy(), MULTI_SE_BASE_COUNT, StrataEstimator::strata, StrataEstimator::strata_count, and MultiStrataEstimator::stratas.

Here is the call graph for this function:

strata_estimator_dup()

struct MultiStrataEstimator * strata_estimator_dup

(

struct MultiStrataEstimator *

se

)

Make a copy of a strata estimator.

Parameters

se	the strata estimator to copy

Returns

the copy

Definition at line 433 of file gnunet-service-setu_strata_estimator.c.

{
  struct MultiStrataEstimator *c;
  unsigned int i;
 
  c = GNUNET_new (struct MultiStrataEstimator);
  c->stratas = GNUNET_new_array (MULTI_SE_BASE_COUNT,struct StrataEstimator *);
  for (uint8_t strata_ctr = 0; strata_ctr < MULTI_SE_BASE_COUNT; strata_ctr++)
  {
    c->stratas[strata_ctr] = GNUNET_new (struct StrataEstimator);
    c->stratas[strata_ctr]->strata_count =
      se->stratas[strata_ctr]->strata_count;
    c->stratas[strata_ctr]->ibf_size = se->stratas[strata_ctr]->ibf_size;
    c->stratas[strata_ctr]->strata = GNUNET_new_array (
      se->stratas[strata_ctr]->strata_count,
      struct
      InvertibleBloomFilter *);
    for (i = 0; i < se->stratas[strata_ctr]->strata_count; i++)
      c->stratas[strata_ctr]->strata[i] = ibf_dup (
        se->stratas[strata_ctr]->strata[i]);
  }
  return c;
}

References GNUNET_new, GNUNET_new_array, ibf_dup(), StrataEstimator::ibf_size, MULTI_SE_BASE_COUNT, StrataEstimator::strata, StrataEstimator::strata_count, and MultiStrataEstimator::stratas.

Here is the call graph for this function: