gnunet-service-set_union_strata_estimator.h File Reference

estimator of set difference More...

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

Include dependency graph for gnunet-service-set_union_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...

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...
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)
	Get an estimation of the symmetric difference of the elements contained in both strata estimators. 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...
void	strata_estimator_destroy (struct StrataEstimator *se)
	Destroy a strata estimator, free all of its resources. More...
struct StrataEstimator *	strata_estimator_dup (struct StrataEstimator *se)
	Make a copy of a strata estimator. More...

Detailed Description

estimator of set difference

Author

Florian Dold

Definition in file gnunet-service-set_union_strata_estimator.h.

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_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;
}

strata_estimator_difference()

unsigned int strata_estimator_difference	(	const struct StrataEstimator *	se1,
		const struct StrataEstimator *	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

abs(|se1| - |se2|)

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_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_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:

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: