GNUnet  0.10.x
Macros | Functions
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 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)
 Estimate set difference with two strata estimators, i.e. More...
 
struct StrataEstimatorstrata_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
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.

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

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 }
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
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:284
#define GNUNET_memcpy(dst, src, n)
#define IBF_BUCKET_SIZE
Size of one ibf bucket in bytes.
Definition: ibf.h:72
static char buf[2048]
unsigned int strata_count
Size of the IBF array in strata.
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.
#define GNUNET_YES
Definition: gnunet_common.h:80
struct InvertibleBloomFilter ** strata
The IBFs of this strata estimator.
#define GNUNET_free(ptr)
Wrapper around free.
unsigned int ibf_size
Size of each IBF stratum (in bytes)
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.

References GNUNET_break, GNUNET_break_op, GNUNET_decompress(), GNUNET_free_non_null, 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().

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_non_null (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_non_null (dbuf);
133  return GNUNET_OK;
134 }
#define GNUNET_OK
Named constants for return values.
Definition: gnunet_common.h:78
#define GNUNET_free_non_null(ptr)
Free the memory pointed to by ptr if ptr is not NULL.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur...
#define GNUNET_break_op(cond)
Use this for assertion violations caused by other peers (i.e.
#define IBF_BUCKET_SIZE
Size of one ibf bucket in bytes.
Definition: ibf.h:72
static char buf[2048]
unsigned int strata_count
Size of the IBF array in strata.
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:315
#define GNUNET_SYSERR
Definition: gnunet_common.h:79
#define GNUNET_YES
Definition: gnunet_common.h:80
struct InvertibleBloomFilter ** strata
The IBFs of this strata estimator.
char * GNUNET_decompress(const char *input, size_t input_size, size_t output_size)
Decompress input, return the decompressed data as output.
unsigned int ibf_size
Size of each IBF stratum (in bytes)
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.

References ibf_insert(), IBF_Key::key_val, and StrataEstimator::strata.

Referenced by union_add().

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 }
uint64_t key_val
Definition: ibf.h:47
void ibf_insert(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Insert a key into an IBF.
Definition: ibf.c:164
struct InvertibleBloomFilter ** strata
The IBFs of this strata estimator.
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 165 of file gnunet-service-set_union_strata_estimator.c.

References ibf_remove(), IBF_Key::key_val, and StrataEstimator::strata.

Referenced by union_remove().

167 {
168  uint64_t v;
169  unsigned int i;
170 
171  v = key.key_val;
172  /* count trailing '1'-bits of v */
173  for (i = 0; v & 1; v>>=1, i++)
174  /* empty */;
175  ibf_remove (se->strata[i], key);
176 }
void ibf_remove(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Remove a key from an IBF.
Definition: ibf.c:180
uint64_t key_val
Definition: ibf.h:47
struct InvertibleBloomFilter ** strata
The IBFs of this 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 188 of file gnunet-service-set_union_strata_estimator.c.

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

Referenced by handle_union_p2p_strata_estimator(), and union_set_create().

191 {
192  struct StrataEstimator *se;
193  unsigned int i;
194  unsigned int j;
195 
196  se = GNUNET_new (struct StrataEstimator);
198  se->ibf_size = ibf_size;
200  struct InvertibleBloomFilter *);
201  for (i = 0; i < strata_count; i++)
202  {
203  se->strata[i] = ibf_create (ibf_size, ibf_hashnum);
204  if (NULL == se->strata[i])
205  {
207  "Failed to allocate memory for strata estimator\n");
208  for (j = 0; j < i; j++)
209  ibf_destroy (se->strata[i]);
210  GNUNET_free (se);
211  return NULL;
212  }
213  }
214  return se;
215 }
Invertible bloom filter (IBF).
Definition: ibf.h:82
#define GNUNET_new(type)
Allocate a struct or union of the given type.
A handle to a strata estimator.
static unsigned int ibf_size
#define GNUNET_new_array(n, type)
Allocate a size n array with structs or unions of the given type.
unsigned int strata_count
Size of the IBF array in strata.
void ibf_destroy(struct InvertibleBloomFilter *ibf)
Destroy all resources associated with the invertible bloom filter.
Definition: ibf.c:388
struct InvertibleBloomFilter * ibf_create(uint32_t size, uint8_t hash_num)
Create an invertible bloom filter.
Definition: ibf.c:76
#define GNUNET_log(kind,...)
struct InvertibleBloomFilter ** strata
The IBFs of this strata estimator.
#define GNUNET_free(ptr)
Wrapper around free.
unsigned int ibf_size
Size of each IBF stratum (in bytes)
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
se1first strata estimator
se2second strata estimator
Returns
the estimated difference

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

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

230 {
231  unsigned int count;
232 
233  GNUNET_assert (se1->strata_count == se2->strata_count);
234  count = 0;
235  for (int i = se1->strata_count - 1; i >= 0; i--)
236  {
237  struct InvertibleBloomFilter *diff;
238  /* number of keys decoded from the ibf */
239 
240  /* FIXME: implement this without always allocating new IBFs */
241  diff = ibf_dup (se1->strata[i]);
242  ibf_subtract (diff, se2->strata[i]);
243  for (int ibf_count = 0; GNUNET_YES; ibf_count++)
244  {
245  int more;
246 
247  more = ibf_decode (diff, NULL, NULL);
248  if (GNUNET_NO == more)
249  {
250  count += ibf_count;
251  break;
252  }
253  /* Estimate if decoding fails or would not terminate */
254  if ((GNUNET_SYSERR == more) || (ibf_count > diff->size))
255  {
256  ibf_destroy (diff);
257  return count * (1 << (i + 1));
258  }
259  }
260  ibf_destroy (diff);
261  }
262  return count;
263 }
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
Invertible bloom filter (IBF).
Definition: ibf.h:82
#define GNUNET_NO
Definition: gnunet_common.h:81
struct InvertibleBloomFilter * ibf_dup(const struct InvertibleBloomFilter *ibf)
Create a copy of an IBF, the copy has to be destroyed properly.
Definition: ibf.c:368
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:87
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:222
void ibf_subtract(struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2)
Subtract ibf2 from ibf1, storing the result in ibf1.
Definition: ibf.c:346
unsigned int strata_count
Size of the IBF array in strata.
#define GNUNET_SYSERR
Definition: gnunet_common.h:79
void ibf_destroy(struct InvertibleBloomFilter *ibf)
Destroy all resources associated with the invertible bloom filter.
Definition: ibf.c:388
#define GNUNET_YES
Definition: gnunet_common.h:80
struct InvertibleBloomFilter ** strata
The IBFs of this strata estimator.
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
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 273 of file gnunet-service-set_union_strata_estimator.c.

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

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

274 {
275  struct StrataEstimator *c;
276  unsigned int i;
277 
278  c = GNUNET_new (struct StrataEstimator);
279  c->strata_count = se->strata_count;
280  c->ibf_size = se->ibf_size;
282  struct InvertibleBloomFilter *);
283  for (i = 0; i < se->strata_count; i++)
284  c->strata[i] = ibf_dup (se->strata[i]);
285  return c;
286 }
Invertible bloom filter (IBF).
Definition: ibf.h:82
#define GNUNET_new(type)
Allocate a struct or union of the given type.
A handle to a strata estimator.
struct InvertibleBloomFilter * ibf_dup(const struct InvertibleBloomFilter *ibf)
Create a copy of an IBF, the copy has to be destroyed properly.
Definition: ibf.c:368
#define GNUNET_new_array(n, type)
Allocate a size n array with structs or unions of the given type.
unsigned int strata_count
Size of the IBF array in strata.
struct InvertibleBloomFilter ** strata
The IBFs of this strata estimator.
unsigned int ibf_size
Size of each IBF stratum (in bytes)
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 295 of file gnunet-service-set_union_strata_estimator.c.

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

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

296 {
297  unsigned int i;
298 
299  for (i = 0; i < se->strata_count; i++)
300  ibf_destroy (se->strata[i]);
301  GNUNET_free (se->strata);
302  GNUNET_free (se);
303 }
unsigned int strata_count
Size of the IBF array in strata.
void ibf_destroy(struct InvertibleBloomFilter *ibf)
Destroy all resources associated with the invertible bloom filter.
Definition: ibf.c:388
struct InvertibleBloomFilter ** strata
The IBFs of this strata estimator.
#define GNUNET_free(ptr)
Wrapper around free.
Here is the call graph for this function:
Here is the caller graph for this function: