GNUnet  0.11.x
Macros | Functions
ibf.c File Reference

implementation of the invertible bloom filter More...

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

Functions

struct IBF_Key ibf_key_from_hashcode (const struct GNUNET_HashCode *hash)
 Create a key from a hashcode. More...
 
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. More...
 
struct InvertibleBloomFilteribf_create (uint32_t size, uint8_t hash_num)
 Create an invertible bloom filter. More...
 
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. More...
 
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. More...
 
void ibf_remove (struct InvertibleBloomFilter *ibf, struct IBF_Key key)
 Remove a key from an IBF. More...
 
static int ibf_is_empty (struct InvertibleBloomFilter *ibf)
 Test is the IBF is empty, i.e. More...
 
int ibf_decode (struct InvertibleBloomFilter *ibf, int *ret_side, struct IBF_Key *ret_id)
 Decode and remove an element from the IBF, if possible. More...
 
void ibf_write_slice (const struct InvertibleBloomFilter *ibf, uint32_t start, uint32_t count, void *buf)
 Write buckets from an ibf to a buffer. More...
 
void ibf_read_slice (const void *buf, uint32_t start, uint32_t count, struct InvertibleBloomFilter *ibf)
 Read buckets from a buffer into an ibf. More...
 
void ibf_subtract (struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2)
 Subtract ibf2 from ibf1, storing the result in ibf1. More...
 
struct InvertibleBloomFilteribf_dup (const struct InvertibleBloomFilter *ibf)
 Create a copy of an IBF, the copy has to be destroyed properly. More...
 
void ibf_destroy (struct InvertibleBloomFilter *ibf)
 Destroy all resources associated with the invertible bloom filter. More...
 

Detailed Description

implementation of the invertible bloom filter

Author
Florian Dold

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:106
Hash of an IBF key.
Definition: ibf.h:54

Compute the key's hash from the key.

Redefine to use a different hash function.

Definition at line 33 of file ibf.c.

Referenced by ibf_decode(), and ibf_insert_into().

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 43 of file ibf.c.

Referenced by insert_iterator(), and register_hashcode().

44 {
45  return *(struct IBF_Key *) hash;
46 }
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:45
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 57 of file ibf.c.

References p.

Referenced by iter_hashcodes(), and register_hashcode().

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 }
static struct GNUNET_OS_Process * p
Helper process we started.
Definition: gnunet-qr.c:59
A 512-bit hashcode.
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:45
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 79 of file ibf.c.

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

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

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 }
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:99
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
Invertible bloom filter (IBF).
Definition: ibf.h:82
#define GNUNET_new(type)
Allocate a struct or union of the given type.
#define GNUNET_malloc_large(size)
Wrapper around malloc.
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:87
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:93
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:105
static unsigned int size
Size of the "table".
Definition: peer.c:67
static unsigned int hash_num
Hash of an IBF key.
Definition: ibf.h:54
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:45
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
#define GNUNET_free(ptr)
Wrapper around free.
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 118 of file ibf.c.

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

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

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;
135 try_next:;
136  x = ((uint64_t) bucket << 32) | i;
137  bucket = GNUNET_CRYPTO_crc32_n (&x, sizeof x);
138  }
139 }
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:106
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:87
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:93
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 143 of file ibf.c.

References InvertibleBloomFilter::count, IBF_Count::count_val, InvertibleBloomFilter::hash_num, IBF_KEY_HASH_VAL, 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().

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
155  ^= IBF_KEY_HASH_VAL (key);
156  }
157 }
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:99
uint64_t key_val
Definition: ibf.h:47
uint32_t key_hash_val
Definition: ibf.h:56
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:93
#define IBF_KEY_HASH_VAL(k)
Compute the key&#39;s hash from the key.
Definition: ibf.c:33
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:105
int8_t count_val
Definition: ibf.h:65
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 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 167 of file ibf.c.

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

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

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 }
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
static void ibf_insert_into(struct InvertibleBloomFilter *ibf, struct IBF_Key key, const int *buckets, int side)
Definition: ibf.c:143
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:87
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:93
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:118
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 184 of file ibf.c.

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

Referenced by strata_estimator_remove().

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 }
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
static void ibf_insert_into(struct InvertibleBloomFilter *ibf, struct IBF_Key key, const int *buckets, int side)
Definition: ibf.c:143
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:87
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:93
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:118
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 198 of file ibf.c.

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

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 }
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:99
#define GNUNET_NO
Definition: gnunet_common.h:78
uint64_t key_val
Definition: ibf.h:47
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:87
uint32_t key_hash_val
Definition: ibf.h:56
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:105
int8_t count_val
Definition: ibf.h:65
#define GNUNET_YES
Definition: gnunet_common.h:77
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 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 228 of file ibf.c.

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(), run(), and strata_estimator_difference().

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 }
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:99
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
static void ibf_insert_into(struct InvertibleBloomFilter *ibf, struct IBF_Key key, const int *buckets, int side)
Definition: ibf.c:143
#define GNUNET_NO
Definition: gnunet_common.h:78
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:87
uint32_t key_hash_val
Definition: ibf.h:56
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:93
#define IBF_KEY_HASH_VAL(k)
Compute the key&#39;s hash from the key.
Definition: ibf.c:33
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:105
#define GNUNET_SYSERR
Definition: gnunet_common.h:76
Hash of an IBF key.
Definition: ibf.h:54
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:118
int8_t count_val
Definition: ibf.h:65
#define GNUNET_YES
Definition: gnunet_common.h:77
static int ibf_is_empty(struct InvertibleBloomFilter *ibf)
Test is the IBF is empty, i.e.
Definition: ibf.c:198
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:

◆ 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 290 of file ibf.c.

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

Referenced by send_ibf(), and strata_estimator_write().

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 }
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:99
static int start
Set if we are to start default services (including ARM).
Definition: gnunet-arm.c:39
#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.
static char buf[2048]
Type of the count field of IBF buckets.
Definition: ibf.h:63
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:105
static unsigned int size
Size of the "table".
Definition: peer.c:67
Hash of an IBF key.
Definition: ibf.h:54
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:45
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 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 323 of file ibf.c.

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

Referenced by handle_union_p2p_ibf(), and strata_estimator_read().

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 }
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:99
static int start
Set if we are to start default services (including ARM).
Definition: gnunet-arm.c:39
#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.
static char buf[2048]
Type of the count field of IBF buckets.
Definition: ibf.h:63
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:105
static unsigned int size
Size of the "table".
Definition: peer.c:67
Hash of an IBF key.
Definition: ibf.h:54
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:45
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 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 356 of file ibf.c.

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(), run(), and strata_estimator_difference().

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;
367  ibf1->key_hash_sum[i].key_hash_val ^= ibf2->key_hash_sum[i].key_hash_val;
368  ibf1->key_sum[i].key_val ^= ibf2->key_sum[i].key_val;
369  }
370 }
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:99
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
uint64_t key_val
Definition: ibf.h:47
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:87
uint32_t key_hash_val
Definition: ibf.h:56
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:93
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:105
int8_t count_val
Definition: ibf.h:65
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 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 379 of file ibf.c.

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(), strata_estimator_difference(), and strata_estimator_dup().

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 }
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:99
Invertible bloom filter (IBF).
Definition: ibf.h:82
#define GNUNET_memdup(buf, size)
Allocate and initialize a block of memory.
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:87
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:93
Type of the count field of IBF buckets.
Definition: ibf.h:63
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:105
Hash of an IBF key.
Definition: ibf.h:54
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:45
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
#define GNUNET_malloc(size)
Wrapper around malloc.
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 403 of file ibf.c.

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

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

404 {
405  GNUNET_free (ibf->key_sum);
406  GNUNET_free (ibf->key_hash_sum);
407  GNUNET_free (ibf->count);
408  GNUNET_free (ibf);
409 }
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:99
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:105
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
#define GNUNET_free(ptr)
Wrapper around free.
Here is the caller graph for this function: