GNUnet  0.11.x
Macros | Functions
ibf.c File Reference
#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...
 

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.

44 {
45  return *(struct IBF_Key *) hash;
46 }
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:45

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

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

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

80 {
81  struct InvertibleBloomFilter *ibf;
82 
83  GNUNET_assert (0 != size);
84  ibf = GNUNET_new (struct InvertibleBloomFilter);
85  ibf->count = GNUNET_malloc_large (size * sizeof(uint8_t));
86  if (NULL == ibf->count)
87  {
88  GNUNET_free (ibf);
89  return NULL;
90  }
91  ibf->key_sum = GNUNET_malloc_large (size * sizeof(struct IBF_Key));
92  if (NULL == ibf->key_sum)
93  {
94  GNUNET_free (ibf->count);
95  GNUNET_free (ibf);
96  return NULL;
97  }
98  ibf->key_hash_sum = GNUNET_malloc_large (size * sizeof(struct IBF_KeyHash));
99  if (NULL == ibf->key_hash_sum)
100  {
101  GNUNET_free (ibf->key_sum);
102  GNUNET_free (ibf->count);
103  GNUNET_free (ibf);
104  return NULL;
105  }
106  ibf->size = size;
107  ibf->hash_num = hash_num;
108  return ibf;
109 }
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
Invertible bloom filter (IBF).
Definition: ibf.h:82
struct IBF_Count * count
How many times has a bucket been hit? Can be negative, as a result of IBF subtraction.
Definition: ibf.h:112
#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_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:99
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
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:105
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:45
#define GNUNET_free(ptr)
Wrapper around free.

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

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

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

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

147 {
148  for (unsigned int i = 0; i < ibf->hash_num; i++)
149  {
150  const int bucket = buckets[i];
151 
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_Count * count
How many times has a bucket been hit? Can be negative, as a result of IBF subtraction.
Definition: ibf.h:112
uint64_t key_val
Definition: ibf.h:47
uint32_t key_hash_val
Definition: ibf.h:56
#define IBF_KEY_HASH_VAL(k)
Compute the key&#39;s hash from the key.
Definition: ibf.c:33
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:93
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:99
int8_t count_val
Definition: ibf.h:65
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:105
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.

169 {
170  int buckets[ibf->hash_num];
171 
172  GNUNET_assert (ibf->hash_num <= ibf->size);
173  ibf_get_indices (ibf,
174  key,
175  buckets);
176  ibf_insert_into (ibf,
177  key,
178  buckets,
179  1);
180 }
#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:116
Here is the call 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 190 of file ibf.c.

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

192 {
193  int buckets[ibf->hash_num];
194 
195  GNUNET_assert (ibf->hash_num <= ibf->size);
196  ibf_get_indices (ibf,
197  key,
198  buckets);
199  ibf_insert_into (ibf,
200  key,
201  buckets,
202  -1);
203 }
#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:116
Here is the call 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 210 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().

211 {
212  for (uint32_t i = 0; i < ibf->size; i++)
213  {
214  if (0 != ibf->count[i].count_val)
215  return GNUNET_NO;
216  if (0 != ibf->key_hash_sum[i].key_hash_val)
217  return GNUNET_NO;
218  if (0 != ibf->key_sum[i].key_val)
219  return GNUNET_NO;
220  }
221  return GNUNET_YES;
222 }
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
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_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:99
int8_t count_val
Definition: ibf.h:65
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:105
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 238 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.

241 {
242  struct IBF_KeyHash hash;
243  int buckets[ibf->hash_num];
244 
245  for (uint32_t i = 0; i < ibf->size; i++)
246  {
247  /* we can only decode from pure buckets */
248  if ( (1 != ibf->count[i].count_val) &&
249  (-1 != ibf->count[i].count_val) )
250  continue;
251 
252  hash.key_hash_val = IBF_KEY_HASH_VAL (ibf->key_sum[i]);
253 
254  /* test if the hash matches the key */
255  if (hash.key_hash_val != ibf->key_hash_sum[i].key_hash_val)
256  continue;
257 
258  /* test if key in bucket hits its own location,
259  * if not, the key hash was subject to collision */
260  {
261  bool hit = false;
262 
263  ibf_get_indices (ibf,
264  ibf->key_sum[i],
265  buckets);
266  for (int j = 0; j < ibf->hash_num; j++)
267  if (buckets[j] == i)
268  {
269  hit = true;
270  break;
271  }
272  if (! hit)
273  continue;
274  }
275  if (NULL != ret_side)
276  *ret_side = ibf->count[i].count_val;
277  if (NULL != ret_id)
278  *ret_id = ibf->key_sum[i];
279 
280  /* insert on the opposite side, effectively removing the element */
281  ibf_insert_into (ibf,
282  ibf->key_sum[i], buckets,
283  -ibf->count[i].count_val);
284  return GNUNET_YES;
285  }
286 
287  if (GNUNET_YES == ibf_is_empty (ibf))
288  return GNUNET_NO;
289  return GNUNET_SYSERR;
290 }
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
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
static int ibf_is_empty(struct InvertibleBloomFilter *ibf)
Test is the IBF is empty, i.e.
Definition: ibf.c:210
uint32_t key_hash_val
Definition: ibf.h:56
#define IBF_KEY_HASH_VAL(k)
Compute the key&#39;s hash from the key.
Definition: ibf.c:33
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:116
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:99
Hash of an IBF key.
Definition: ibf.h:54
int8_t count_val
Definition: ibf.h:65
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:105
Here is the call 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 303 of file ibf.c.

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

307 {
308  struct IBF_Key *key_dst;
309  struct IBF_KeyHash *key_hash_dst;
310  struct IBF_Count *count_dst;
311 
312  GNUNET_assert (start + count <= ibf->size);
313 
314  /* copy keys */
315  key_dst = (struct IBF_Key *) buf;
316  GNUNET_memcpy (key_dst,
317  ibf->key_sum + start,
318  count * sizeof *key_dst);
319  key_dst += count;
320  /* copy key hashes */
321  key_hash_dst = (struct IBF_KeyHash *) key_dst;
322  GNUNET_memcpy (key_hash_dst,
323  ibf->key_hash_sum + start,
324  count * sizeof *key_hash_dst);
325  key_hash_dst += count;
326  /* copy counts */
327  count_dst = (struct IBF_Count *) key_hash_dst;
328  GNUNET_memcpy (count_dst,
329  ibf->count + start,
330  count * sizeof *count_dst);
331 }
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.
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
static char buf[2048]
Type of the count field of IBF buckets.
Definition: ibf.h:63
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:99
static unsigned int size
Size of the "table".
Definition: peer.c:67
Hash of an IBF key.
Definition: ibf.h:54
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:105
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:45

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

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

347 {
348  struct IBF_Key *key_src;
349  struct IBF_KeyHash *key_hash_src;
350  struct IBF_Count *count_src;
351 
352  GNUNET_assert (count > 0);
353  GNUNET_assert (start + count <= ibf->size);
354 
355  /* copy keys */
356  key_src = (struct IBF_Key *) buf;
357  GNUNET_memcpy (ibf->key_sum + start,
358  key_src,
359  count * sizeof *key_src);
360  key_src += count;
361  /* copy key hashes */
362  key_hash_src = (struct IBF_KeyHash *) key_src;
364  key_hash_src,
365  count * sizeof *key_hash_src);
366  key_hash_src += count;
367  /* copy counts */
368  count_src = (struct IBF_Count *) key_hash_src;
369  GNUNET_memcpy (ibf->count + start,
370  count_src,
371  count * sizeof *count_src);
372 }
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.
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
static char buf[2048]
Type of the count field of IBF buckets.
Definition: ibf.h:63
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:99
static unsigned int size
Size of the "table".
Definition: peer.c:67
Hash of an IBF key.
Definition: ibf.h:54
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:105
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:45

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

385 {
386  GNUNET_assert (ibf1->size == ibf2->size);
387  GNUNET_assert (ibf1->hash_num == ibf2->hash_num);
388 
389  for (uint32_t i = 0; i < ibf1->size; i++)
390  {
391  ibf1->count[i].count_val -= ibf2->count[i].count_val;
392  ibf1->key_hash_sum[i].key_hash_val ^= ibf2->key_hash_sum[i].key_hash_val;
393  ibf1->key_sum[i].key_val ^= ibf2->key_sum[i].key_val;
394  }
395 }
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
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
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_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:99
int8_t count_val
Definition: ibf.h:65
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:105

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

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

405 {
406  struct InvertibleBloomFilter *copy;
407 
408  copy = GNUNET_malloc (sizeof *copy);
409  copy->hash_num = ibf->hash_num;
410  copy->size = ibf->size;
412  ibf->size * sizeof(struct IBF_KeyHash));
413  copy->key_sum = GNUNET_memdup (ibf->key_sum,
414  ibf->size * sizeof(struct IBF_Key));
415  copy->count = GNUNET_memdup (ibf->count,
416  ibf->size * sizeof(struct IBF_Count));
417  return copy;
418 }
Invertible bloom filter (IBF).
Definition: ibf.h:82
struct IBF_Count * count
How many times has a bucket been hit? Can be negative, as a result of IBF subtraction.
Definition: ibf.h:112
#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_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:99
Hash of an IBF key.
Definition: ibf.h:54
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:105
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:45
#define GNUNET_malloc(size)
Wrapper around malloc.

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

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

429 {
430  GNUNET_free (ibf->key_sum);
431  GNUNET_free (ibf->key_hash_sum);
432  GNUNET_free (ibf->count);
433  GNUNET_free (ibf);
434 }
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&#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
#define GNUNET_free(ptr)
Wrapper around free.