GNUnet 0.21.1
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}
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
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.
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 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}
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
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.

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_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}
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
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.
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
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}
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
@ GNUNET_NO
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}
void ibf_insert(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Insert a key into an IBF.
Definition: ibf.c:168
struct GNUNET_HashCode key
The key used in the DHT.

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: