GNUnet debian-0.24.3-29-g453fda2cf
 
Loading...
Searching...
No Matches
ibf.c File Reference

implementation of the invertible bloom filter More...

#include "platform.h"
#include "ibf.h"
Include dependency graph for ibf.c:

Go to the source code of this file.

Macros

#define IBF_KEY_HASH_VAL(k)
 Compute the key's hash from the key.
 

Functions

struct IBF_Key ibf_key_from_hashcode (const struct GNUNET_HashCode *hash)
 Create a key from a hashcode.
 
void ibf_hashcode_from_key (struct IBF_Key key, struct GNUNET_HashCode *dst)
 Create a hashcode from a key, by replicating the key until the hascode is filled.
 
struct InvertibleBloomFilteribf_create (uint32_t size, uint8_t hash_num)
 Create an invertible bloom filter.
 
static void ibf_get_indices (const struct InvertibleBloomFilter *ibf, struct IBF_Key key, int *dst)
 Store unique bucket indices for the specified key in dst.
 
static void ibf_insert_into (struct InvertibleBloomFilter *ibf, struct IBF_Key key, const int *buckets, int side)
 
void ibf_insert (struct InvertibleBloomFilter *ibf, struct IBF_Key key)
 Insert a key into an IBF.
 
void ibf_remove (struct InvertibleBloomFilter *ibf, struct IBF_Key key)
 Remove a key from an IBF.
 
static int ibf_is_empty (struct InvertibleBloomFilter *ibf)
 Test is the IBF is empty, i.e.
 
int ibf_decode (struct InvertibleBloomFilter *ibf, int *ret_side, struct IBF_Key *ret_id)
 Decode and remove an element from the IBF, if possible.
 
void ibf_write_slice (const struct InvertibleBloomFilter *ibf, uint32_t start, uint32_t count, void *buf)
 Write buckets from an ibf to a buffer.
 
void ibf_read_slice (const void *buf, uint32_t start, uint32_t count, struct InvertibleBloomFilter *ibf)
 Read buckets from a buffer into an ibf.
 
void ibf_subtract (struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2)
 Subtract ibf2 from ibf1, storing the result in ibf1.
 
struct InvertibleBloomFilteribf_dup (const struct InvertibleBloomFilter *ibf)
 Create a copy of an IBF, the copy has to be destroyed properly.
 
void ibf_destroy (struct InvertibleBloomFilter *ibf)
 Destroy all resources associated with the invertible bloom filter.
 

Detailed Description

implementation of the invertible bloom filter

Author
Florian Dold
Florian Dold
Elias Summermatter

Definition in file ibf.c.

Macro Definition Documentation

◆ IBF_KEY_HASH_VAL

#define IBF_KEY_HASH_VAL (   k)
Value:
(GNUNET_CRYPTO_crc32_n (&(k), sizeof(struct \
int32_t GNUNET_CRYPTO_crc32_n(const void *buf, size_t len)
Compute the CRC32 checksum for the first len bytes of the buffer.
Definition crypto_crc.c:99
Hash of an IBF key.
Definition ibf.h:55

Compute the key's hash from the key.

Redefine to use a different hash function.

Definition at line 34 of file ibf.c.

44{
45 return *(struct IBF_Key *) hash;
46}
47
48
56void
58 struct GNUNET_HashCode *dst)
59{
60 struct IBF_Key *p;
61 unsigned int i;
62 const unsigned int keys_per_hashcode = sizeof(struct GNUNET_HashCode)
63 / sizeof(struct IBF_Key);
64
65 p = (struct IBF_Key *) dst;
66 for (i = 0; i < keys_per_hashcode; i++)
67 *p++ = key;
68}
69
70
79ibf_create (uint32_t size, uint8_t hash_num)
80{
81 struct InvertibleBloomFilter *ibf;
82
83 GNUNET_assert (0 != size);
84
85 ibf = GNUNET_new (struct InvertibleBloomFilter);
86 ibf->count = GNUNET_malloc_large (size * sizeof(uint8_t));
87 if (NULL == ibf->count)
88 {
89 GNUNET_free (ibf);
90 return NULL;
91 }
92 ibf->key_sum = GNUNET_malloc_large (size * sizeof(struct IBF_Key));
93 if (NULL == ibf->key_sum)
94 {
95 GNUNET_free (ibf->count);
96 GNUNET_free (ibf);
97 return NULL;
98 }
99 ibf->key_hash_sum = GNUNET_malloc_large (size * sizeof(struct IBF_KeyHash));
100 if (NULL == ibf->key_hash_sum)
101 {
102 GNUNET_free (ibf->key_sum);
103 GNUNET_free (ibf->count);
104 GNUNET_free (ibf);
105 return NULL;
106 }
107 ibf->size = size;
108 ibf->hash_num = hash_num;
109
110 return ibf;
111}
112
113
117static void
118ibf_get_indices (const struct InvertibleBloomFilter *ibf,
119 struct IBF_Key key,
120 int *dst)
121{
122 uint32_t filled;
123 uint32_t i;
124 uint32_t bucket;
125
126 bucket = GNUNET_CRYPTO_crc32_n (&key, sizeof key);
127 for (i = 0, filled = 0; filled < ibf->hash_num; i++)
128 {
129 unsigned int j;
130 uint64_t x;
131 for (j = 0; j < filled; j++)
132 if (dst[j] == bucket)
133 goto try_next;
134 dst[filled++] = bucket % ibf->size;
135try_next:;
136 x = ((uint64_t) bucket << 32) | i;
137 bucket = GNUNET_CRYPTO_crc32_n (&x, sizeof x);
138 }
139}
140
141
142static void
144 struct IBF_Key key,
145 const int *buckets, int side)
146{
147 int i;
148
149 for (i = 0; i < ibf->hash_num; i++)
150 {
151 const int bucket = buckets[i];
152 ibf->count[bucket].count_val += side;
153 ibf->key_sum[bucket].key_val ^= key.key_val;
154 ibf->key_hash_sum[bucket].key_hash_val
156 }
157}
158
159
166void
167ibf_insert (struct InvertibleBloomFilter *ibf, struct IBF_Key key)
168{
169 int buckets[ibf->hash_num];
170
171 GNUNET_assert (ibf->hash_num <= ibf->size);
172 ibf_get_indices (ibf, key, buckets);
173 ibf_insert_into (ibf, key, buckets, 1);
174}
175
176
183void
184ibf_remove (struct InvertibleBloomFilter *ibf, struct IBF_Key key)
185{
186 int buckets[ibf->hash_num];
187
188 GNUNET_assert (ibf->hash_num <= ibf->size);
189 ibf_get_indices (ibf, key, buckets);
190 ibf_insert_into (ibf, key, buckets, -1);
191}
192
193
197static int
199{
200 int i;
201
202 for (i = 0; i < ibf->size; i++)
203 {
204 if (0 != ibf->count[i].count_val)
205 return GNUNET_NO;
206 if (0 != ibf->key_hash_sum[i].key_hash_val)
207 return GNUNET_NO;
208 if (0 != ibf->key_sum[i].key_val)
209 return GNUNET_NO;
210 }
211 return GNUNET_YES;
212}
213
214
227int
229 int *ret_side, struct IBF_Key *ret_id)
230{
231 struct IBF_KeyHash hash;
232 int i;
233 int buckets[ibf->hash_num];
234
235 GNUNET_assert (NULL != ibf);
236
237 for (i = 0; i < ibf->size; i++)
238 {
239 int j;
240 int hit;
241
242 /* we can only decode from pure buckets */
243 if ((1 != ibf->count[i].count_val) && (-1 != ibf->count[i].count_val))
244 continue;
245
246 hash.key_hash_val = IBF_KEY_HASH_VAL (ibf->key_sum[i]);
247
248 /* test if the hash matches the key */
249 if (hash.key_hash_val != ibf->key_hash_sum[i].key_hash_val)
250 continue;
251
252 /* test if key in bucket hits its own location,
253 * if not, the key hash was subject to collision */
254 hit = GNUNET_NO;
255 ibf_get_indices (ibf, ibf->key_sum[i], buckets);
256 for (j = 0; j < ibf->hash_num; j++)
257 if (buckets[j] == i)
258 hit = GNUNET_YES;
259
260 if (GNUNET_NO == hit)
261 continue;
262
263 if (NULL != ret_side)
264 *ret_side = ibf->count[i].count_val;
265 if (NULL != ret_id)
266 *ret_id = ibf->key_sum[i];
267
268 /* insert on the opposite side, effectively removing the element */
269 ibf_insert_into (ibf, ibf->key_sum[i], buckets, -ibf->count[i].count_val);
270
271 return GNUNET_YES;
272 }
273
274 if (GNUNET_YES == ibf_is_empty (ibf))
275 return GNUNET_NO;
276 return GNUNET_SYSERR;
277}
278
279
289void
290ibf_write_slice (const struct InvertibleBloomFilter *ibf, uint32_t start,
291 uint32_t count, void *buf)
292{
293 struct IBF_Key *key_dst;
294 struct IBF_KeyHash *key_hash_dst;
295 struct IBF_Count *count_dst;
296
297 GNUNET_assert (start + count <= ibf->size);
298
299 /* copy keys */
300 key_dst = (struct IBF_Key *) buf;
301 GNUNET_memcpy (key_dst, ibf->key_sum + start, count * sizeof *key_dst);
302 key_dst += count;
303 /* copy key hashes */
304 key_hash_dst = (struct IBF_KeyHash *) key_dst;
305 GNUNET_memcpy (key_hash_dst, ibf->key_hash_sum + start, count
306 * sizeof *key_hash_dst);
307 key_hash_dst += count;
308 /* copy counts */
309 count_dst = (struct IBF_Count *) key_hash_dst;
310 GNUNET_memcpy (count_dst, ibf->count + start, count * sizeof *count_dst);
311}
312
313
322void
323ibf_read_slice (const void *buf, uint32_t start, uint32_t count, struct
325{
326 struct IBF_Key *key_src;
327 struct IBF_KeyHash *key_hash_src;
328 struct IBF_Count *count_src;
329
330 GNUNET_assert (count > 0);
331 GNUNET_assert (start + count <= ibf->size);
332
333 /* copy keys */
334 key_src = (struct IBF_Key *) buf;
335 GNUNET_memcpy (ibf->key_sum + start, key_src, count * sizeof *key_src);
336 key_src += count;
337 /* copy key hashes */
338 key_hash_src = (struct IBF_KeyHash *) key_src;
339 GNUNET_memcpy (ibf->key_hash_sum + start, key_hash_src, count
340 * sizeof *key_hash_src);
341 key_hash_src += count;
342 /* copy counts */
343 count_src = (struct IBF_Count *) key_hash_src;
344 GNUNET_memcpy (ibf->count + start, count_src, count * sizeof *count_src);
345}
346
347
355void
356ibf_subtract (struct InvertibleBloomFilter *ibf1, const struct
358{
359 int i;
360
361 GNUNET_assert (ibf1->size == ibf2->size);
362 GNUNET_assert (ibf1->hash_num == ibf2->hash_num);
363
364 for (i = 0; i < ibf1->size; i++)
365 {
366 ibf1->count[i].count_val -= ibf2->count[i].count_val;
368 ibf1->key_sum[i].key_val ^= ibf2->key_sum[i].key_val;
369 }
370}
371
372
379ibf_dup (const struct InvertibleBloomFilter *ibf)
380{
381 struct InvertibleBloomFilter *copy;
382
383 copy = GNUNET_malloc (sizeof *copy);
384 copy->hash_num = ibf->hash_num;
385 copy->size = ibf->size;
386 copy->key_hash_sum = GNUNET_memdup (ibf->key_hash_sum, ibf->size
387 * sizeof(struct IBF_KeyHash));
388 copy->key_sum = GNUNET_memdup (ibf->key_sum, ibf->size * sizeof(struct
389 IBF_Key));
390 copy->count = GNUNET_memdup (ibf->count, ibf->size * sizeof(struct
391 IBF_Count));
392 return copy;
393}
394
395
402void
404{
405 GNUNET_free (ibf->key_sum);
407 GNUNET_free (ibf->count);
408 GNUNET_free (ibf);
409}
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
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
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_KEY_HASH_VAL(k)
Compute the key's hash from the key.
Definition ibf.c:34
static void ibf_get_indices(const struct InvertibleBloomFilter *ibf, struct IBF_Key key, int *dst)
Store unique bucket indices for the specified key in dst.
Definition ibf.c:119
void ibf_hashcode_from_key(struct IBF_Key key, struct GNUNET_HashCode *dst)
Create a hashcode from a key, by replicating the key until the hascode is filled.
Definition ibf.c:58
void ibf_insert(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Insert a key into an IBF.
Definition ibf.c:168
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
static void ibf_insert_into(struct InvertibleBloomFilter *ibf, struct IBF_Key key, const int *buckets, int side)
Definition ibf.c:144
struct InvertibleBloomFilter * ibf_create(uint32_t size, uint8_t hash_num)
Create an invertible bloom filter.
Definition ibf.c:80
static int ibf_is_empty(struct InvertibleBloomFilter *ibf)
Test is the IBF is empty, i.e.
Definition ibf.c:199
void ibf_remove(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Remove a key from an IBF.
Definition ibf.c:185
void ibf_destroy(struct InvertibleBloomFilter *ibf)
Destroy all resources associated with the invertible bloom filter.
Definition ibf.c:404
static int start
Set if we are to start default services (including ARM).
Definition gnunet-arm.c:38
struct GNUNET_HashCode key
The key used in the DHT.
static unsigned int hash_num
static struct GNUNET_OS_Process * p
Helper process we started.
Definition gnunet-uri.c:38
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
@ GNUNET_YES
@ GNUNET_NO
@ GNUNET_SYSERR
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
#define GNUNET_malloc_large(size)
Wrapper around malloc.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
#define GNUNET_malloc(size)
Wrapper around malloc.
#define GNUNET_free(ptr)
Wrapper around free.
#define GNUNET_memdup(buf, size)
Allocate and initialize a block of memory.
static unsigned int size
Size of the "table".
Definition peer.c:68
A 512-bit hashcode.
Type of the count field of IBF buckets.
Definition ibf.h:64
int8_t count_val
Definition ibf.h:65
uint32_t key_hash_val
Definition ibf.h:56
Keys that can be inserted into and removed from an IBF.
Definition ibf.h:46
uint64_t key_val
Definition ibf.h:47
Invertible bloom filter (IBF).
Definition ibf.h:83
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition ibf.h:105
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
struct IBF_Key * key_sum
Xor sums of the elements' keys, used to identify the elements.
Definition ibf.h:99
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition ibf.h:93

Function Documentation

◆ ibf_key_from_hashcode()

struct IBF_Key ibf_key_from_hashcode ( const struct GNUNET_HashCode hash)

Create a key from a hashcode.

Parameters
hashthe hashcode
Returns
a key

Definition at line 44 of file ibf.c.

45{
46 return *(struct IBF_Key *) hash;
47}

Referenced by insert_iterator(), insert_iterator(), register_hashcode(), and register_hashcode().

Here is the caller graph for this function:

◆ ibf_hashcode_from_key()

void ibf_hashcode_from_key ( struct IBF_Key  key,
struct GNUNET_HashCode dst 
)

Create a hashcode from a key, by replicating the key until the hascode is filled.

Parameters
keythe key
dsthashcode to store the result in

Definition at line 58 of file ibf.c.

60{
61 struct IBF_Key *p;
62 unsigned int i;
63 const unsigned int keys_per_hashcode = sizeof(struct GNUNET_HashCode)
64 / sizeof(struct IBF_Key);
65
66 p = (struct IBF_Key *) dst;
67 for (i = 0; i < keys_per_hashcode; i++)
68 *p++ = key;
69}

References key, and p.

Referenced by iter_hashcodes(), iter_hashcodes(), register_hashcode(), and register_hashcode().

Here is the caller graph for this function:

◆ ibf_create()

struct InvertibleBloomFilter * ibf_create ( uint32_t  size,
uint8_t  hash_num 
)

Create an invertible bloom filter.

Parameters
sizenumber of IBF buckets
hash_numnumber of buckets one element is hashed in
Returns
the newly created invertible bloom filter, NULL on error

Definition at line 80 of file ibf.c.

81{
82 struct InvertibleBloomFilter *ibf;
83
84 GNUNET_assert (0 != size);
85
86 ibf = GNUNET_new (struct InvertibleBloomFilter);
87 ibf->count = GNUNET_malloc_large (size * sizeof(uint8_t));
88 if (NULL == ibf->count)
89 {
90 GNUNET_free (ibf);
91 return NULL;
92 }
93 ibf->key_sum = GNUNET_malloc_large (size * sizeof(struct IBF_Key));
94 if (NULL == ibf->key_sum)
95 {
96 GNUNET_free (ibf->count);
97 GNUNET_free (ibf);
98 return NULL;
99 }
100 ibf->key_hash_sum = GNUNET_malloc_large (size * sizeof(struct IBF_KeyHash));
101 if (NULL == ibf->key_hash_sum)
102 {
103 GNUNET_free (ibf->key_sum);
104 GNUNET_free (ibf->count);
105 GNUNET_free (ibf);
106 return NULL;
107 }
108 ibf->size = size;
109 ibf->hash_num = hash_num;
110
111 return ibf;
112}

References InvertibleBloomFilter::count, GNUNET_assert, GNUNET_free, GNUNET_malloc_large, GNUNET_new, hash_num, InvertibleBloomFilter::hash_num, InvertibleBloomFilter::key_hash_sum, InvertibleBloomFilter::key_sum, InvertibleBloomFilter::size, and size.

Referenced by handle_union_p2p_ibf(), handle_union_p2p_ibf(), prepare_ibf(), prepare_ibf(), run(), run(), and strata_estimator_create().

Here is the caller graph for this function:

◆ ibf_get_indices()

static void ibf_get_indices ( const struct InvertibleBloomFilter ibf,
struct IBF_Key  key,
int *  dst 
)
static

Store unique bucket indices for the specified key in dst.

Definition at line 119 of file ibf.c.

122{
123 uint32_t filled;
124 uint32_t i;
125 uint32_t bucket;
126
127 bucket = GNUNET_CRYPTO_crc32_n (&key, sizeof key);
128 for (i = 0, filled = 0; filled < ibf->hash_num; i++)
129 {
130 unsigned int j;
131 uint64_t x;
132 for (j = 0; j < filled; j++)
133 if (dst[j] == bucket)
134 goto try_next;
135 dst[filled++] = bucket % ibf->size;
136try_next:;
137 x = ((uint64_t) bucket << 32) | i;
138 bucket = GNUNET_CRYPTO_crc32_n (&x, sizeof x);
139 }
140}

References GNUNET_CRYPTO_crc32_n(), InvertibleBloomFilter::hash_num, key, and InvertibleBloomFilter::size.

Referenced by ibf_decode(), ibf_insert(), and ibf_remove().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ ibf_insert_into()

static void ibf_insert_into ( struct InvertibleBloomFilter ibf,
struct IBF_Key  key,
const int *  buckets,
int  side 
)
static

Definition at line 144 of file ibf.c.

147{
148 int i;
149
150 for (i = 0; i < ibf->hash_num; i++)
151 {
152 const int bucket = buckets[i];
153 ibf->count[bucket].count_val += side;
154 ibf->key_sum[bucket].key_val ^= key.key_val;
155 ibf->key_hash_sum[bucket].key_hash_val
157 }
158}

References InvertibleBloomFilter::count, IBF_Count::count_val, InvertibleBloomFilter::hash_num, IBF_KEY_HASH_VAL, key, InvertibleBloomFilter::key_hash_sum, IBF_KeyHash::key_hash_val, InvertibleBloomFilter::key_sum, and IBF_Key::key_val.

Referenced by ibf_decode(), ibf_insert(), and ibf_remove().

Here is the caller graph for this function:

◆ ibf_insert()

void ibf_insert ( struct InvertibleBloomFilter ibf,
struct IBF_Key  key 
)

Insert a key into an IBF.

Parameters
ibfthe IBF
keythe element's hash code

Definition at line 168 of file ibf.c.

169{
170 int buckets[ibf->hash_num];
171
172 GNUNET_assert (ibf->hash_num <= ibf->size);
173 ibf_get_indices (ibf, key, buckets);
174 ibf_insert_into (ibf, key, buckets, 1);
175}

References GNUNET_assert, InvertibleBloomFilter::hash_num, ibf_get_indices(), ibf_insert_into(), key, and InvertibleBloomFilter::size.

Referenced by insert_iterator(), insert_iterator(), prepare_ibf_iterator(), prepare_ibf_iterator(), strata_estimator_insert(), and strata_estimator_insert().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ ibf_remove()

void ibf_remove ( struct InvertibleBloomFilter ibf,
struct IBF_Key  key 
)

Remove a key from an IBF.

Parameters
ibfthe IBF
keythe element's hash code

Definition at line 185 of file ibf.c.

186{
187 int buckets[ibf->hash_num];
188
189 GNUNET_assert (ibf->hash_num <= ibf->size);
190 ibf_get_indices (ibf, key, buckets);
191 ibf_insert_into (ibf, key, buckets, -1);
192}

References GNUNET_assert, InvertibleBloomFilter::hash_num, ibf_get_indices(), ibf_insert_into(), key, and InvertibleBloomFilter::size.

Referenced by strata_estimator_remove(), and strata_estimator_remove().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ ibf_is_empty()

static int ibf_is_empty ( struct InvertibleBloomFilter ibf)
static

Test is the IBF is empty, i.e.

all counts, keys and key hashes are zero.

Definition at line 199 of file ibf.c.

200{
201 int i;
202
203 for (i = 0; i < ibf->size; i++)
204 {
205 if (0 != ibf->count[i].count_val)
206 return GNUNET_NO;
207 if (0 != ibf->key_hash_sum[i].key_hash_val)
208 return GNUNET_NO;
209 if (0 != ibf->key_sum[i].key_val)
210 return GNUNET_NO;
211 }
212 return GNUNET_YES;
213}

References InvertibleBloomFilter::count, IBF_Count::count_val, GNUNET_NO, GNUNET_YES, InvertibleBloomFilter::key_hash_sum, IBF_KeyHash::key_hash_val, InvertibleBloomFilter::key_sum, IBF_Key::key_val, and InvertibleBloomFilter::size.

Referenced by ibf_decode().

Here is the caller graph for this function:

◆ ibf_decode()

int ibf_decode ( struct InvertibleBloomFilter ibf,
int *  ret_side,
struct IBF_Key ret_id 
)

Decode and remove an element from the IBF, if possible.

Parameters
ibfthe invertible bloom filter to decode
ret_sidesign of the cell's count where the decoded element came from. A negative sign indicates that the element was recovered resides in an IBF that was previously subtracted from.
ret_idreceives the hash code of the decoded element, if successful
Returns
GNUNET_YES if decoding an element was successful, GNUNET_NO if the IBF is empty, GNUNET_SYSERR if the decoding has failed

Definition at line 229 of file ibf.c.

231{
232 struct IBF_KeyHash hash;
233 int i;
234 int buckets[ibf->hash_num];
235
236 GNUNET_assert (NULL != ibf);
237
238 for (i = 0; i < ibf->size; i++)
239 {
240 int j;
241 int hit;
242
243 /* we can only decode from pure buckets */
244 if ((1 != ibf->count[i].count_val) && (-1 != ibf->count[i].count_val))
245 continue;
246
247 hash.key_hash_val = IBF_KEY_HASH_VAL (ibf->key_sum[i]);
248
249 /* test if the hash matches the key */
250 if (hash.key_hash_val != ibf->key_hash_sum[i].key_hash_val)
251 continue;
252
253 /* test if key in bucket hits its own location,
254 * if not, the key hash was subject to collision */
255 hit = GNUNET_NO;
256 ibf_get_indices (ibf, ibf->key_sum[i], buckets);
257 for (j = 0; j < ibf->hash_num; j++)
258 if (buckets[j] == i)
259 hit = GNUNET_YES;
260
261 if (GNUNET_NO == hit)
262 continue;
263
264 if (NULL != ret_side)
265 *ret_side = ibf->count[i].count_val;
266 if (NULL != ret_id)
267 *ret_id = ibf->key_sum[i];
268
269 /* insert on the opposite side, effectively removing the element */
270 ibf_insert_into (ibf, ibf->key_sum[i], buckets, -ibf->count[i].count_val);
271
272 return GNUNET_YES;
273 }
274
275 if (GNUNET_YES == ibf_is_empty (ibf))
276 return GNUNET_NO;
277 return GNUNET_SYSERR;
278}

References InvertibleBloomFilter::count, IBF_Count::count_val, GNUNET_assert, GNUNET_NO, GNUNET_SYSERR, GNUNET_YES, InvertibleBloomFilter::hash_num, ibf_get_indices(), ibf_insert_into(), ibf_is_empty(), IBF_KEY_HASH_VAL, InvertibleBloomFilter::key_hash_sum, IBF_KeyHash::key_hash_val, InvertibleBloomFilter::key_sum, and InvertibleBloomFilter::size.

Referenced by decode_and_send(), decode_and_send(), run(), run(), strata_estimator_difference(), and strata_estimator_difference().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ ibf_write_slice()

void ibf_write_slice ( const struct InvertibleBloomFilter ibf,
uint32_t  start,
uint32_t  count,
void *  buf 
)

Write buckets from an ibf to a buffer.

Exactly (IBF_BUCKET_SIZE*ibf->size) bytes are written to buf.

Parameters
ibfthe ibf to write
startwith which bucket to start
counthow many buckets to write
bufbuffer to write the data to

Definition at line 291 of file ibf.c.

293{
294 struct IBF_Key *key_dst;
295 struct IBF_KeyHash *key_hash_dst;
296 struct IBF_Count *count_dst;
297
298 GNUNET_assert (start + count <= ibf->size);
299
300 /* copy keys */
301 key_dst = (struct IBF_Key *) buf;
302 GNUNET_memcpy (key_dst, ibf->key_sum + start, count * sizeof *key_dst);
303 key_dst += count;
304 /* copy key hashes */
305 key_hash_dst = (struct IBF_KeyHash *) key_dst;
306 GNUNET_memcpy (key_hash_dst, ibf->key_hash_sum + start, count
307 * sizeof *key_hash_dst);
308 key_hash_dst += count;
309 /* copy counts */
310 count_dst = (struct IBF_Count *) key_hash_dst;
311 GNUNET_memcpy (count_dst, ibf->count + start, count * sizeof *count_dst);
312}

References InvertibleBloomFilter::count, GNUNET_assert, GNUNET_memcpy, InvertibleBloomFilter::key_hash_sum, InvertibleBloomFilter::key_sum, size, and start.

Referenced by send_ibf(), send_ibf(), strata_estimator_write(), and strata_estimator_write().

Here is the caller graph for this function:

◆ ibf_read_slice()

void ibf_read_slice ( const void *  buf,
uint32_t  start,
uint32_t  count,
struct InvertibleBloomFilter ibf 
)

Read buckets from a buffer into an ibf.

Parameters
bufpointer to the buffer to read from
startwhich bucket to start at
counthow many buckets to read
ibfthe ibf to read from

Definition at line 324 of file ibf.c.

326{
327 struct IBF_Key *key_src;
328 struct IBF_KeyHash *key_hash_src;
329 struct IBF_Count *count_src;
330
331 GNUNET_assert (count > 0);
332 GNUNET_assert (start + count <= ibf->size);
333
334 /* copy keys */
335 key_src = (struct IBF_Key *) buf;
336 GNUNET_memcpy (ibf->key_sum + start, key_src, count * sizeof *key_src);
337 key_src += count;
338 /* copy key hashes */
339 key_hash_src = (struct IBF_KeyHash *) key_src;
340 GNUNET_memcpy (ibf->key_hash_sum + start, key_hash_src, count
341 * sizeof *key_hash_src);
342 key_hash_src += count;
343 /* copy counts */
344 count_src = (struct IBF_Count *) key_hash_src;
345 GNUNET_memcpy (ibf->count + start, count_src, count * sizeof *count_src);
346}

References InvertibleBloomFilter::count, GNUNET_assert, GNUNET_memcpy, InvertibleBloomFilter::key_hash_sum, InvertibleBloomFilter::key_sum, size, and start.

Referenced by handle_union_p2p_ibf(), handle_union_p2p_ibf(), strata_estimator_read(), and strata_estimator_read().

Here is the caller graph for this function:

◆ ibf_subtract()

void ibf_subtract ( struct InvertibleBloomFilter ibf1,
const struct InvertibleBloomFilter ibf2 
)

Subtract ibf2 from ibf1, storing the result in ibf1.

The two IBF's must have the same parameters size and hash_num.

Parameters
ibf1IBF that is subtracted from
ibf2IBF that will be subtracted from ibf1

Definition at line 357 of file ibf.c.

359{
360 int i;
361
362 GNUNET_assert (ibf1->size == ibf2->size);
363 GNUNET_assert (ibf1->hash_num == ibf2->hash_num);
364
365 for (i = 0; i < ibf1->size; i++)
366 {
367 ibf1->count[i].count_val -= ibf2->count[i].count_val;
369 ibf1->key_sum[i].key_val ^= ibf2->key_sum[i].key_val;
370 }
371}

References InvertibleBloomFilter::count, IBF_Count::count_val, GNUNET_assert, InvertibleBloomFilter::hash_num, InvertibleBloomFilter::key_hash_sum, IBF_KeyHash::key_hash_val, InvertibleBloomFilter::key_sum, IBF_Key::key_val, and InvertibleBloomFilter::size.

Referenced by decode_and_send(), decode_and_send(), run(), run(), strata_estimator_difference(), and strata_estimator_difference().

Here is the caller graph for this function:

◆ ibf_dup()

struct InvertibleBloomFilter * ibf_dup ( const struct InvertibleBloomFilter ibf)

Create a copy of an IBF, the copy has to be destroyed properly.

Parameters
ibfthe IBF to copy

Definition at line 380 of file ibf.c.

381{
382 struct InvertibleBloomFilter *copy;
383
384 copy = GNUNET_malloc (sizeof *copy);
385 copy->hash_num = ibf->hash_num;
386 copy->size = ibf->size;
387 copy->key_hash_sum = GNUNET_memdup (ibf->key_hash_sum, ibf->size
388 * sizeof(struct IBF_KeyHash));
389 copy->key_sum = GNUNET_memdup (ibf->key_sum, ibf->size * sizeof(struct
390 IBF_Key));
391 copy->count = GNUNET_memdup (ibf->count, ibf->size * sizeof(struct
392 IBF_Count));
393 return copy;
394}

References InvertibleBloomFilter::count, GNUNET_malloc, GNUNET_memdup, InvertibleBloomFilter::hash_num, InvertibleBloomFilter::key_hash_sum, InvertibleBloomFilter::key_sum, and InvertibleBloomFilter::size.

Referenced by decode_and_send(), decode_and_send(), strata_estimator_difference(), strata_estimator_difference(), strata_estimator_dup(), and strata_estimator_dup().

Here is the caller graph for this function:

◆ ibf_destroy()

void ibf_destroy ( struct InvertibleBloomFilter ibf)

Destroy all resources associated with the invertible bloom filter.

No more ibf_*-functions may be called on ibf after calling destroy.

Parameters
ibfthe intertible bloom filter to destroy

Definition at line 404 of file ibf.c.

405{
406 GNUNET_free (ibf->key_sum);
408 GNUNET_free (ibf->count);
409 GNUNET_free (ibf);
410}

References InvertibleBloomFilter::count, GNUNET_free, InvertibleBloomFilter::key_hash_sum, and InvertibleBloomFilter::key_sum.

Referenced by _GSS_operation_destroy(), decode_and_send(), decode_and_send(), prepare_ibf(), prepare_ibf(), strata_estimator_create(), strata_estimator_destroy(), strata_estimator_destroy(), strata_estimator_difference(), strata_estimator_difference(), and union_op_cancel().

Here is the caller graph for this function: