gnunet-service-set_union_strata_estimator.c File Reference

invertible bloom filter More...

#include "platform.h"
#include "gnunet_util_lib.h"
#include "ibf.h"
#include "gnunet-service-set_union_strata_estimator.h"

Include dependency graph for gnunet-service-set_union_strata_estimator.c:

Go to the source code of this file.

Macros
#define	FAIL_10_1_COMPATIBILTIY   1
	Should we try compressing the strata estimator? This will break compatibility with the 0.10.1-network. More...

Functions
size_t	strata_estimator_write (const struct StrataEstimator *se, 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, struct StrataEstimator *se)
	Read strata from the buffer into the given strata estimator. More...
void	strata_estimator_insert (struct StrataEstimator *se, struct IBF_Key key)
	Add a key to the strata estimator. More...
void	strata_estimator_remove (struct StrataEstimator *se, struct IBF_Key key)
	Remove a key from the strata estimator. More...
struct StrataEstimator *	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...
unsigned int	strata_estimator_difference (const struct StrataEstimator *se1, const struct StrataEstimator *se2)
	Estimate set difference with two strata estimators, i.e. More...
struct StrataEstimator *	strata_estimator_dup (struct StrataEstimator *se)
	Make a copy of a strata estimator. More...
void	strata_estimator_destroy (struct StrataEstimator *se)
	Destroy a strata estimator, free all of its resources. More...

Detailed Description

invertible bloom filter

Author

Florian Dold

Christian Grothoff

Definition in file gnunet-service-set_union_strata_estimator.c.

Macro Definition Documentation

FAIL_10_1_COMPATIBILTIY

#define FAIL_10_1_COMPATIBILTIY   1

Should we try compressing the strata estimator? This will break compatibility with the 0.10.1-network.

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

Function Documentation

strata_estimator_write()

size_t strata_estimator_write	(	const struct StrataEstimator *	se,
		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 47 of file gnunet-service-set_union_strata_estimator.c.

{
  char *sbuf = buf;
  unsigned int i;
  size_t osize;
 
  GNUNET_assert (NULL != se);
  for (i = 0; i < se->strata_count; i++)
  {
    ibf_write_slice (se->strata[i],
                     0,
                     se->ibf_size,
                     &sbuf[se->ibf_size * IBF_BUCKET_SIZE * i]);
  }
  osize = se->ibf_size * IBF_BUCKET_SIZE * se->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(), StrataEstimator::strata, and StrataEstimator::strata_count.

Referenced by handle_client_accept(), and union_accept().

Here is the call graph for this function:

Here is the caller graph for this function:

strata_estimator_read()

int strata_estimator_read	(	const void *	buf,
		size_t	buf_len,
		int	is_compressed,
		struct StrataEstimator *	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 95 of file gnunet-service-set_union_strata_estimator.c.

{
  unsigned int i;
  size_t osize;
  char *dbuf;
 
  dbuf = NULL;
  if (GNUNET_YES == is_compressed)
  {
    osize = se->ibf_size * IBF_BUCKET_SIZE * se->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->strata_count * se->ibf_size * IBF_BUCKET_SIZE)
  {
    GNUNET_break (0);  /* very odd error */
    GNUNET_free (dbuf);
    return GNUNET_SYSERR;
  }
 
  for (i = 0; i < se->strata_count; i++)
  {
    ibf_read_slice (buf, 0, se->ibf_size, se->strata[i]);
    buf += se->ibf_size * IBF_BUCKET_SIZE;
  }
  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, StrataEstimator::strata, and StrataEstimator::strata_count.

Referenced by handle_union_p2p_strata_estimator().

Here is the call graph for this function:

Here is the caller graph for this function:

strata_estimator_insert()

void strata_estimator_insert	(	struct StrataEstimator *	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 144 of file gnunet-service-set_union_strata_estimator.c.

{
  uint64_t v;
  unsigned int i;
 
  v = key.key_val;
  /* count trailing '1'-bits of v */
  for (i = 0; v & 1; v >>= 1, i++)
    /* empty */;
  ibf_insert (se->strata[i], key);
}

References ibf_insert(), key, and StrataEstimator::strata.

Referenced by handle_client_set_add(), and union_add().

Here is the call graph for this function:

Here is the caller graph for this function:

strata_estimator_remove()

void strata_estimator_remove	(	struct StrataEstimator *	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

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

{
  uint64_t v;
  unsigned int i;
 
  v = key.key_val;
  /* count trailing '1'-bits of v */
  for (i = 0; v & 1; v >>= 1, i++)
    /* empty */;
  ibf_remove (se->strata[i], key);
}

References ibf_remove(), key, and StrataEstimator::strata.

Referenced by union_remove().

Here is the call graph for this function:

Here is the caller graph for this function:

strata_estimator_create()

struct StrataEstimator * 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, StrataEstimator::strata, and StrataEstimator::strata_count.

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()

unsigned int strata_estimator_difference	(	const struct StrataEstimator *	se1,
		const struct StrataEstimator *	se2
	)

Estimate set difference with two strata estimators, i.e.

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 222 of file gnunet-service-set_union_strata_estimator.c.

{
  unsigned int count;
 
  GNUNET_assert (se1->strata_count == se2->strata_count);
  count = 0;
  for (int i = se1->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->strata[i]);
    ibf_subtract (diff, se2->strata[i]);
    for (int ibf_count = 0; GNUNET_YES; ibf_count++)
    {
      int more;
 
      more = ibf_decode (diff, NULL, NULL);
      if (GNUNET_NO == more)
      {
        count += ibf_count;
        break;
      }
      /* Estimate if decoding fails or would not terminate */
      if ((GNUNET_SYSERR == more) || (ibf_count > diff->size))
      {
        ibf_destroy (diff);
        return count * (1 << (i + 1));
      }
    }
    ibf_destroy (diff);
  }
  return count;
}

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

Referenced by handle_union_p2p_strata_estimator().

Here is the call graph for this function:

Here is the caller graph for this function:

strata_estimator_dup()

struct StrataEstimator * strata_estimator_dup

(

struct StrataEstimator *

se

)

Make a copy of a strata estimator.

Parameters

se	the strata estimator to copy

Returns

the copy

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

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

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

Referenced by handle_client_accept(), handle_client_evaluate(), union_accept(), union_copy_state(), and union_evaluate().

Here is the call graph for this function:

Here is the caller graph for this function:

strata_estimator_destroy()

void strata_estimator_destroy

(

struct StrataEstimator *

se

)

Destroy a strata estimator, free all of its resources.

Parameters

se	strata estimator to destroy.

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

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

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

Referenced by _GSS_operation_destroy(), client_disconnect_cb(), handle_union_p2p_strata_estimator(), union_op_cancel(), and union_set_destroy().

Here is the call graph for this function:

Here is the caller graph for this function: