GNUnet  0.10.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)   (GNUNET_CRYPTO_crc32_n(&(k), sizeof(struct IBF_KeyHash)))
 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)    (GNUNET_CRYPTO_crc32_n(&(k), sizeof(struct IBF_KeyHash)))

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

Referenced by insert_iterator(), and register_hashcode().

43 {
44  return *(struct IBF_Key *)hash;
45 }
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 55 of file ibf.c.

References p.

Referenced by iter_hashcodes(), and register_hashcode().

57 {
58  struct IBF_Key *p;
59  unsigned int i;
60  const unsigned int keys_per_hashcode = sizeof(struct GNUNET_HashCode) / sizeof(struct IBF_Key);
61 
62  p = (struct IBF_Key *)dst;
63  for (i = 0; i < keys_per_hashcode; i++)
64  *p++ = key;
65 }
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 76 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().

77 {
78  struct InvertibleBloomFilter *ibf;
79 
80  GNUNET_assert(0 != size);
81 
82  ibf = GNUNET_new(struct InvertibleBloomFilter);
83  ibf->count = GNUNET_malloc_large(size * sizeof(uint8_t));
84  if (NULL == ibf->count)
85  {
86  GNUNET_free(ibf);
87  return NULL;
88  }
89  ibf->key_sum = GNUNET_malloc_large(size * sizeof(struct IBF_Key));
90  if (NULL == ibf->key_sum)
91  {
92  GNUNET_free(ibf->count);
93  GNUNET_free(ibf);
94  return NULL;
95  }
96  ibf->key_hash_sum = GNUNET_malloc_large(size * sizeof(struct IBF_KeyHash));
97  if (NULL == ibf->key_hash_sum)
98  {
99  GNUNET_free(ibf->key_sum);
100  GNUNET_free(ibf->count);
101  GNUNET_free(ibf);
102  return NULL;
103  }
104  ibf->size = size;
105  ibf->hash_num = hash_num;
106 
107  return ibf;
108 }
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:95
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
Invertible bloom filter (IBF).
Definition: ibf.h:79
#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:83
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:89
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:101
static unsigned int size
Size of the "table".
Definition: peer.c:66
static unsigned int hash_num
Hash of an IBF key.
Definition: ibf.h:53
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:108
#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 115 of file ibf.c.

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

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

118 {
119  uint32_t filled;
120  uint32_t i;
121  uint32_t bucket;
122 
123  bucket = GNUNET_CRYPTO_crc32_n(&key, sizeof key);
124  for (i = 0, filled = 0; filled < ibf->hash_num; i++)
125  {
126  unsigned int j;
127  uint64_t x;
128  for (j = 0; j < filled; j++)
129  if (dst[j] == bucket)
130  goto try_next;
131  dst[filled++] = bucket % ibf->size;
132 try_next:;
133  x = ((uint64_t)bucket << 32) | i;
134  bucket = GNUNET_CRYPTO_crc32_n(&x, sizeof x);
135  }
136 }
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:105
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:83
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:89
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 140 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().

143 {
144  int i;
145 
146  for (i = 0; i < ibf->hash_num; i++)
147  {
148  const int bucket = buckets[i];
149  ibf->count[bucket].count_val += side;
150  ibf->key_sum[bucket].key_val ^= key.key_val;
151  ibf->key_hash_sum[bucket].key_hash_val
152  ^= IBF_KEY_HASH_VAL(key);
153  }
154 }
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:95
uint64_t key_val
Definition: ibf.h:46
uint32_t key_hash_val
Definition: ibf.h:54
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:89
#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:101
int8_t count_val
Definition: ibf.h:62
struct IBF_Count * count
How many times has a bucket been hit? Can be negative, as a result of IBF subtraction.
Definition: ibf.h:108
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 164 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().

165 {
166  int buckets[ibf->hash_num];
167 
168  GNUNET_assert(ibf->hash_num <= ibf->size);
169  ibf_get_indices(ibf, key, buckets);
170  ibf_insert_into(ibf, key, buckets, 1);
171 }
#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:140
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:83
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:89
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:115
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 181 of file ibf.c.

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

Referenced by strata_estimator_remove().

182 {
183  int buckets[ibf->hash_num];
184 
185  GNUNET_assert(ibf->hash_num <= ibf->size);
186  ibf_get_indices(ibf, key, buckets);
187  ibf_insert_into(ibf, key, buckets, -1);
188 }
#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:140
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:83
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:89
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:115
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 195 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().

196 {
197  int i;
198 
199  for (i = 0; i < ibf->size; i++)
200  {
201  if (0 != ibf->count[i].count_val)
202  return GNUNET_NO;
203  if (0 != ibf->key_hash_sum[i].key_hash_val)
204  return GNUNET_NO;
205  if (0 != ibf->key_sum[i].key_val)
206  return GNUNET_NO;
207  }
208  return GNUNET_YES;
209 }
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:95
#define GNUNET_NO
Definition: gnunet_common.h:78
uint64_t key_val
Definition: ibf.h:46
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:83
uint32_t key_hash_val
Definition: ibf.h:54
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:101
int8_t count_val
Definition: ibf.h:62
#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:108
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 225 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().

227 {
228  struct IBF_KeyHash hash;
229  int i;
230  int buckets[ibf->hash_num];
231 
232  GNUNET_assert(NULL != ibf);
233 
234  for (i = 0; i < ibf->size; i++)
235  {
236  int j;
237  int hit;
238 
239  /* we can only decode from pure buckets */
240  if ((1 != ibf->count[i].count_val) && (-1 != ibf->count[i].count_val))
241  continue;
242 
243  hash.key_hash_val = IBF_KEY_HASH_VAL(ibf->key_sum[i]);
244 
245  /* test if the hash matches the key */
246  if (hash.key_hash_val != ibf->key_hash_sum[i].key_hash_val)
247  continue;
248 
249  /* test if key in bucket hits its own location,
250  * if not, the key hash was subject to collision */
251  hit = GNUNET_NO;
252  ibf_get_indices(ibf, ibf->key_sum[i], buckets);
253  for (j = 0; j < ibf->hash_num; j++)
254  if (buckets[j] == i)
255  hit = GNUNET_YES;
256 
257  if (GNUNET_NO == hit)
258  continue;
259 
260  if (NULL != ret_side)
261  *ret_side = ibf->count[i].count_val;
262  if (NULL != ret_id)
263  *ret_id = ibf->key_sum[i];
264 
265  /* insert on the opposite side, effectively removing the element */
266  ibf_insert_into(ibf, ibf->key_sum[i], buckets, -ibf->count[i].count_val);
267 
268  return GNUNET_YES;
269  }
270 
271  if (GNUNET_YES == ibf_is_empty(ibf))
272  return GNUNET_NO;
273  return GNUNET_SYSERR;
274 }
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:95
#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:140
#define GNUNET_NO
Definition: gnunet_common.h:78
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:83
uint32_t key_hash_val
Definition: ibf.h:54
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:89
#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:101
#define GNUNET_SYSERR
Definition: gnunet_common.h:76
Hash of an IBF key.
Definition: ibf.h:53
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:115
int8_t count_val
Definition: ibf.h:62
#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:195
struct IBF_Count * count
How many times has a bucket been hit? Can be negative, as a result of IBF subtraction.
Definition: ibf.h:108
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 287 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().

288 {
289  struct IBF_Key *key_dst;
290  struct IBF_KeyHash *key_hash_dst;
291  struct IBF_Count *count_dst;
292 
293  GNUNET_assert(start + count <= ibf->size);
294 
295  /* copy keys */
296  key_dst = (struct IBF_Key *)buf;
297  GNUNET_memcpy(key_dst, ibf->key_sum + start, count * sizeof *key_dst);
298  key_dst += count;
299  /* copy key hashes */
300  key_hash_dst = (struct IBF_KeyHash *)key_dst;
301  GNUNET_memcpy(key_hash_dst, ibf->key_hash_sum + start, count * sizeof *key_hash_dst);
302  key_hash_dst += count;
303  /* copy counts */
304  count_dst = (struct IBF_Count *)key_hash_dst;
305  GNUNET_memcpy(count_dst, ibf->count + start, count * sizeof *count_dst);
306 }
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:95
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:61
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:101
static unsigned int size
Size of the "table".
Definition: peer.c:66
Hash of an IBF key.
Definition: ibf.h:53
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:108
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 318 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().

319 {
320  struct IBF_Key *key_src;
321  struct IBF_KeyHash *key_hash_src;
322  struct IBF_Count *count_src;
323 
324  GNUNET_assert(count > 0);
325  GNUNET_assert(start + count <= ibf->size);
326 
327  /* copy keys */
328  key_src = (struct IBF_Key *)buf;
329  GNUNET_memcpy(ibf->key_sum + start, key_src, count * sizeof *key_src);
330  key_src += count;
331  /* copy key hashes */
332  key_hash_src = (struct IBF_KeyHash *)key_src;
333  GNUNET_memcpy(ibf->key_hash_sum + start, key_hash_src, count * sizeof *key_hash_src);
334  key_hash_src += count;
335  /* copy counts */
336  count_src = (struct IBF_Count *)key_hash_src;
337  GNUNET_memcpy(ibf->count + start, count_src, count * sizeof *count_src);
338 }
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:95
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:61
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:101
static unsigned int size
Size of the "table".
Definition: peer.c:66
Hash of an IBF key.
Definition: ibf.h:53
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:108
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 349 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().

350 {
351  int i;
352 
353  GNUNET_assert(ibf1->size == ibf2->size);
354  GNUNET_assert(ibf1->hash_num == ibf2->hash_num);
355 
356  for (i = 0; i < ibf1->size; i++)
357  {
358  ibf1->count[i].count_val -= ibf2->count[i].count_val;
359  ibf1->key_hash_sum[i].key_hash_val ^= ibf2->key_hash_sum[i].key_hash_val;
360  ibf1->key_sum[i].key_val ^= ibf2->key_sum[i].key_val;
361  }
362 }
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:95
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
uint64_t key_val
Definition: ibf.h:46
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:83
uint32_t key_hash_val
Definition: ibf.h:54
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:89
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:101
int8_t count_val
Definition: ibf.h:62
struct IBF_Count * count
How many times has a bucket been hit? Can be negative, as a result of IBF subtraction.
Definition: ibf.h:108
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 371 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().

372 {
373  struct InvertibleBloomFilter *copy;
374 
375  copy = GNUNET_malloc(sizeof *copy);
376  copy->hash_num = ibf->hash_num;
377  copy->size = ibf->size;
378  copy->key_hash_sum = GNUNET_memdup(ibf->key_hash_sum, ibf->size * sizeof(struct IBF_KeyHash));
379  copy->key_sum = GNUNET_memdup(ibf->key_sum, ibf->size * sizeof(struct IBF_Key));
380  copy->count = GNUNET_memdup(ibf->count, ibf->size * sizeof(struct IBF_Count));
381  return copy;
382 }
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:95
Invertible bloom filter (IBF).
Definition: ibf.h:79
#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:83
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:89
Type of the count field of IBF buckets.
Definition: ibf.h:61
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:101
Hash of an IBF key.
Definition: ibf.h:53
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:108
#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 392 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().

393 {
394  GNUNET_free(ibf->key_sum);
396  GNUNET_free(ibf->count);
397  GNUNET_free(ibf);
398 }
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:95
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:101
struct IBF_Count * count
How many times has a bucket been hit? Can be negative, as a result of IBF subtraction.
Definition: ibf.h:108
#define GNUNET_free(ptr)
Wrapper around free.
Here is the caller graph for this function: