GNUnet  0.20.0
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 StrataEstimatorstrata_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 StrataEstimatorstrata_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
sestrata estimator to serialize
[out]bufbuffer 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.

49 {
50  char *sbuf = buf;
51  unsigned int i;
52  size_t osize;
53 
54  GNUNET_assert (NULL != se);
55  for (i = 0; i < se->strata_count; i++)
56  {
57  ibf_write_slice (se->strata[i],
58  0,
59  se->ibf_size,
60  &sbuf[se->ibf_size * IBF_BUCKET_SIZE * i]);
61  }
62  osize = se->ibf_size * IBF_BUCKET_SIZE * se->strata_count;
63 #if FAIL_10_1_COMPATIBILTIY
64  {
65  char *cbuf;
66  size_t nsize;
67 
68  if (GNUNET_YES ==
70  osize,
71  &cbuf,
72  &nsize))
73  {
74  GNUNET_memcpy (buf, cbuf, nsize);
75  osize = nsize;
76  GNUNET_free (cbuf);
77  }
78  }
79 #endif
80  return osize;
81 }
static char buf[2048]
int GNUNET_try_compression(const char *data, size_t old_size, char **result, size_t *new_size)
Try to compress the given block of data using libz.
Definition: compress.c:33
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
@ GNUNET_YES
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
#define GNUNET_free(ptr)
Wrapper around free.
void ibf_write_slice(const struct InvertibleBloomFilter *ibf, uint32_t start, uint32_t count, void *buf)
Write buckets from an ibf to a buffer.
Definition: ibf.c:291
#define IBF_BUCKET_SIZE
Size of one ibf bucket in bytes.
Definition: ibf.h:72
unsigned int ibf_size
Size of each IBF stratum (in bytes)
struct InvertibleBloomFilter ** strata
The IBFs of this strata estimator.
unsigned int strata_count
Size of the IBF array in strata.

References buf, 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
bufbuffer to read from
buf_lennumber of bytes in buf
is_compressedis the data compressed?
[out]sestrata estimator to write to
Returns
GNUNET_OK on success

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

99 {
100  unsigned int i;
101  size_t osize;
102  char *dbuf;
103 
104  dbuf = NULL;
105  if (GNUNET_YES == is_compressed)
106  {
107  osize = se->ibf_size * IBF_BUCKET_SIZE * se->strata_count;
108  dbuf = GNUNET_decompress (buf,
109  buf_len,
110  osize);
111  if (NULL == dbuf)
112  {
113  GNUNET_break_op (0); /* bad compressed input data */
114  return GNUNET_SYSERR;
115  }
116  buf = dbuf;
117  buf_len = osize;
118  }
119 
120  if (buf_len != se->strata_count * se->ibf_size * IBF_BUCKET_SIZE)
121  {
122  GNUNET_break (0); /* very odd error */
123  GNUNET_free (dbuf);
124  return GNUNET_SYSERR;
125  }
126 
127  for (i = 0; i < se->strata_count; i++)
128  {
129  ibf_read_slice (buf, 0, se->ibf_size, se->strata[i]);
130  buf += se->ibf_size * IBF_BUCKET_SIZE;
131  }
132  GNUNET_free (dbuf);
133  return GNUNET_OK;
134 }
char * GNUNET_decompress(const char *input, size_t input_size, size_t output_size)
Decompress input, return the decompressed data as output.
Definition: compress.c:70
@ GNUNET_OK
@ GNUNET_SYSERR
#define GNUNET_break_op(cond)
Use this for assertion violations caused by other peers (i.e.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur.
void ibf_read_slice(const void *buf, uint32_t start, uint32_t count, struct InvertibleBloomFilter *ibf)
Read buckets from a buffer into an ibf.
Definition: ibf.c:324

References buf, 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_countnumber of stratas, that is, number of ibfs in the estimator
ibf_sizesize of each ibf stratum
ibf_hashnumhashnum 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.

185 {
186  struct StrataEstimator *se;
187  unsigned int i;
188  unsigned int j;
189 
190  se = GNUNET_new (struct StrataEstimator);
192  se->ibf_size = ibf_size;
194  struct InvertibleBloomFilter *);
195  for (i = 0; i < strata_count; i++)
196  {
197  se->strata[i] = ibf_create (ibf_size, ibf_hashnum);
198  if (NULL == se->strata[i])
199  {
201  "Failed to allocate memory for strata estimator\n");
202  for (j = 0; j < i; j++)
203  ibf_destroy (se->strata[i]);
204  GNUNET_free (se);
205  return NULL;
206  }
207  }
208  return se;
209 }
static unsigned int ibf_size
#define GNUNET_log(kind,...)
@ GNUNET_ERROR_TYPE_ERROR
#define GNUNET_new(type)
Allocate a struct or union of the given type.
#define GNUNET_new_array(n, type)
Allocate a size n array with structs or unions of the given type.
struct InvertibleBloomFilter * ibf_create(uint32_t size, uint8_t hash_num)
Create an invertible bloom filter.
Definition: ibf.c:80
void ibf_destroy(struct InvertibleBloomFilter *ibf)
Destroy all resources associated with the invertible bloom filter.
Definition: ibf.c:404
Invertible bloom filter (IBF).
Definition: ibf.h:83
A handle to a strata estimator.

◆ 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
se1first strata estimator
se2second 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
se1first strata estimator
se2second strata estimator
Returns
the estimated difference

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

224 {
225  unsigned int count;
226 
227  GNUNET_assert (se1->strata_count == se2->strata_count);
228  count = 0;
229  for (int i = se1->strata_count - 1; i >= 0; i--)
230  {
231  struct InvertibleBloomFilter *diff;
232  /* number of keys decoded from the ibf */
233 
234  /* FIXME: implement this without always allocating new IBFs */
235  diff = ibf_dup (se1->strata[i]);
236  ibf_subtract (diff, se2->strata[i]);
237  for (int ibf_count = 0; GNUNET_YES; ibf_count++)
238  {
239  int more;
240 
241  more = ibf_decode (diff, NULL, NULL);
242  if (GNUNET_NO == more)
243  {
244  count += ibf_count;
245  break;
246  }
247  /* Estimate if decoding fails or would not terminate */
248  if ((GNUNET_SYSERR == more) || (ibf_count > diff->size))
249  {
250  ibf_destroy (diff);
251  return count * (1 << (i + 1));
252  }
253  }
254  ibf_destroy (diff);
255  }
256  return count;
257 }
@ GNUNET_NO
void ibf_subtract(struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2)
Subtract ibf2 from ibf1, storing the result in ibf1.
Definition: ibf.c:357
int ibf_decode(struct InvertibleBloomFilter *ibf, int *ret_side, struct IBF_Key *ret_id)
Decode and remove an element from the IBF, if possible.
Definition: ibf.c:229
struct InvertibleBloomFilter * ibf_dup(const struct InvertibleBloomFilter *ibf)
Create a copy of an IBF, the copy has to be destroyed properly.
Definition: ibf.c:380
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:87
struct IBF_Count * count
How many times has a bucket been hit? Can be negative, as a result of IBF subtraction.
Definition: ibf.h:112

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
sestrata estimator to add the key to
keykey to add

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

146 {
147  uint64_t v;
148  unsigned int i;
149 
150  v = key.key_val;
151  /* count trailing '1'-bits of v */
152  for (i = 0; v & 1; v >>= 1, i++)
153  /* empty */;
154  ibf_insert (se->strata[i], key);
155 }
struct GNUNET_HashCode key
The key used in the DHT.
void ibf_insert(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Insert a key into an IBF.
Definition: ibf.c:168

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
sestrata estimator to remove the key from
keykey to remove

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

161 {
162  uint64_t v;
163  unsigned int i;
164 
165  v = key.key_val;
166  /* count trailing '1'-bits of v */
167  for (i = 0; v & 1; v >>= 1, i++)
168  /* empty */;
169  ibf_remove (se->strata[i], key);
170 }
void ibf_remove(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Remove a key from an IBF.
Definition: ibf.c:185

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
sestrata estimator to destroy.

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

290 {
291  unsigned int i;
292 
293  for (i = 0; i < se->strata_count; i++)
294  ibf_destroy (se->strata[i]);
295  GNUNET_free (se->strata);
296  GNUNET_free (se);
297 }

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
sethe strata estimator to copy
Returns
the copy

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

268 {
269  struct StrataEstimator *c;
270  unsigned int i;
271 
272  c = GNUNET_new (struct StrataEstimator);
273  c->strata_count = se->strata_count;
274  c->ibf_size = se->ibf_size;
276  struct InvertibleBloomFilter *);
277  for (i = 0; i < se->strata_count; i++)
278  c->strata[i] = ibf_dup (se->strata[i]);
279  return c;
280 }

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: