GNUnet  0.11.x
Functions
gnunet-service-setu_strata_estimator.c File Reference
#include "platform.h"
#include "gnunet_util_lib.h"
#include "ibf.h"
#include "gnunet-service-setu_strata_estimator.h"
Include dependency graph for gnunet-service-setu_strata_estimator.c:

Go to the source code of this file.

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

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 40 of file gnunet-service-setu_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.

42 {
43  char *sbuf = buf;
44  size_t osize;
45 
46  GNUNET_assert (NULL != se);
47  for (unsigned int i = 0; i < se->strata_count; i++)
48  {
49  ibf_write_slice (se->strata[i],
50  0,
51  se->ibf_size,
52  &sbuf[se->ibf_size * IBF_BUCKET_SIZE * i]);
53  }
54  osize = se->ibf_size * IBF_BUCKET_SIZE * se->strata_count;
55  {
56  char *cbuf;
57  size_t nsize;
58 
59  if (GNUNET_YES ==
61  osize,
62  &cbuf,
63  &nsize))
64  {
66  cbuf,
67  nsize);
68  osize = nsize;
69  GNUNET_free (cbuf);
70  }
71  }
72  return osize;
73 }
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
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:290
#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.
struct InvertibleBloomFilter ** strata
The IBFs of this strata estimator.
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_free(ptr)
Wrapper around free.
unsigned int ibf_size
Size of each IBF stratum (in bytes)
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,
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 87 of file gnunet-service-setu_strata_estimator.c.

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.

91 {
92  size_t osize;
93  char *dbuf;
94 
95  dbuf = NULL;
96  if (GNUNET_YES == is_compressed)
97  {
98  osize = se->ibf_size * IBF_BUCKET_SIZE * se->strata_count;
99  dbuf = GNUNET_decompress (buf,
100  buf_len,
101  osize);
102  if (NULL == dbuf)
103  {
104  GNUNET_break_op (0); /* bad compressed input data */
105  return GNUNET_SYSERR;
106  }
107  buf = dbuf;
108  buf_len = osize;
109  }
110 
111  if (buf_len != se->strata_count * se->ibf_size * IBF_BUCKET_SIZE)
112  {
113  GNUNET_break (0); /* very odd error */
114  GNUNET_free (dbuf);
115  return GNUNET_SYSERR;
116  }
117 
118  for (unsigned int i = 0; i < se->strata_count; i++)
119  {
120  ibf_read_slice (buf, 0, se->ibf_size, se->strata[i]);
121  buf += se->ibf_size * IBF_BUCKET_SIZE;
122  }
123  GNUNET_free (dbuf);
124  return GNUNET_OK;
125 }
#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:323
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.
#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:

◆ 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 135 of file gnunet-service-setu_strata_estimator.c.

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

137 {
138  uint64_t v;
139  unsigned int i;
140 
141  v = key.key_val;
142  /* count trailing '1'-bits of v */
143  for (i = 0; v & 1; v >>= 1, i++)
144  /* empty */;
145  ibf_insert (se->strata[i], key);
146 }
uint64_t key_val
Definition: ibf.h:47
struct InvertibleBloomFilter ** strata
The IBFs of this strata estimator.
void ibf_insert(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Insert a key into an IBF.
Definition: ibf.c:167
Here is the call 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 156 of file gnunet-service-setu_strata_estimator.c.

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

158 {
159  uint64_t v;
160  unsigned int i;
161 
162  v = key.key_val;
163  /* count trailing '1'-bits of v */
164  for (i = 0; v & 1; v >>= 1, i++)
165  /* empty */;
166  ibf_remove (se->strata[i], key);
167 }
void ibf_remove(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Remove a key from an IBF.
Definition: ibf.c:184
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:

◆ 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 179 of file gnunet-service-setu_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.

182 {
183  struct StrataEstimator *se;
184 
185  se = GNUNET_new (struct StrataEstimator);
187  se->ibf_size = ibf_size;
189  struct InvertibleBloomFilter *);
190  for (unsigned int i = 0; i < strata_count; i++)
191  {
192  se->strata[i] = ibf_create (ibf_size, ibf_hashnum);
193  if (NULL == se->strata[i])
194  {
196  "Failed to allocate memory for strata estimator\n");
197  for (unsigned int j = 0; j < i; j++)
198  ibf_destroy (se->strata[i]);
199  GNUNET_free (se);
200  return NULL;
201  }
202  }
203  return se;
204 }
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:403
struct InvertibleBloomFilter * ibf_create(uint32_t size, uint8_t hash_num)
Create an invertible bloom filter.
Definition: ibf.c:79
struct InvertibleBloomFilter ** strata
The IBFs of this strata estimator.
#define GNUNET_log(kind,...)
#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:

◆ 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 217 of file gnunet-service-setu_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.

219 {
220  unsigned int count;
221 
222  GNUNET_assert (se1->strata_count == se2->strata_count);
223  count = 0;
224  for (int i = se1->strata_count - 1; i >= 0; i--)
225  {
226  struct InvertibleBloomFilter *diff;
227  /* number of keys decoded from the ibf */
228 
229  /* FIXME: implement this without always allocating new IBFs */
230  diff = ibf_dup (se1->strata[i]);
231  ibf_subtract (diff,
232  se2->strata[i]);
233  for (int ibf_count = 0; GNUNET_YES; ibf_count++)
234  {
235  int more;
236 
237  more = ibf_decode (diff,
238  NULL,
239  NULL);
240  if (GNUNET_NO == more)
241  {
242  count += ibf_count;
243  break;
244  }
245  /* Estimate if decoding fails or would not terminate */
246  if ( (GNUNET_SYSERR == more) ||
247  (ibf_count > diff->size) )
248  {
249  ibf_destroy (diff);
250  return count * (1 << (i + 1));
251  }
252  }
253  ibf_destroy (diff);
254  }
255  return count;
256 }
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
Invertible bloom filter (IBF).
Definition: ibf.h:82
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
struct InvertibleBloomFilter * ibf_dup(const struct InvertibleBloomFilter *ibf)
Create a copy of an IBF, the copy has to be destroyed properly.
Definition: ibf.c:379
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:228
void ibf_subtract(struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2)
Subtract ibf2 from ibf1, storing the result in ibf1.
Definition: ibf.c:356
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:403
struct InvertibleBloomFilter ** strata
The IBFs of this strata estimator.
Here is the call 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 266 of file gnunet-service-setu_strata_estimator.c.

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

267 {
268  struct StrataEstimator *c;
269 
270  c = GNUNET_new (struct StrataEstimator);
271  c->strata_count = se->strata_count;
272  c->ibf_size = se->ibf_size;
274  struct InvertibleBloomFilter *);
275  for (unsigned int i = 0; i < se->strata_count; i++)
276  c->strata[i] = ibf_dup (se->strata[i]);
277  return c;
278 }
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:379
#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:

◆ 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 287 of file gnunet-service-setu_strata_estimator.c.

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

288 {
289  for (unsigned int i = 0; i < se->strata_count; i++)
290  ibf_destroy (se->strata[i]);
291  GNUNET_free (se->strata);
292  GNUNET_free (se);
293 }
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:403
struct InvertibleBloomFilter ** strata
The IBFs of this strata estimator.
#define GNUNET_free(ptr)
Wrapper around free.
Here is the call graph for this function: