ibf.h File Reference

invertible bloom filter More...

#include "platform.h"
#include "gnunet_util_lib.h"

Include dependency graph for ibf.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	IBF_Key
	Keys that can be inserted into and removed from an IBF. More...
struct	IBF_KeyHash
	Hash of an IBF key. More...
struct	IBF_Count
	Type of the count field of IBF buckets. More...
struct	InvertibleBloomFilter
	Invertible bloom filter (IBF). More...

Macros
#define	IBF_BUCKET_SIZE
	Size of one ibf bucket in bytes.

Functions
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.
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 InvertibleBloomFilter *	ibf_create (uint32_t size, uint8_t hash_num)
	Create an invertible bloom filter.
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.
void	ibf_subtract (struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2)
	Subtract ibf2 from ibf1, storing the result in ibf1.
int	ibf_decode (struct InvertibleBloomFilter *ibf, int *ret_side, struct IBF_Key *ret_id)
	Decode and remove an element from the IBF, if possible.
struct InvertibleBloomFilter *	ibf_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

invertible bloom filter

Author

Florian Dold

Florian Dold

Elias Summermatter

Definition in file ibf.h.

Macro Definition Documentation

IBF_BUCKET_SIZE

#define IBF_BUCKET_SIZE

Value:

                         (sizeof(struct IBF_Count) + sizeof(struct IBF_Key)   \
                         + sizeof(struct IBF_KeyHash))

Size of one ibf bucket in bytes.

Definition at line 72 of file ibf.h.

{
  uint32_t size;
 
  uint8_t hash_num;
 
  struct IBF_Key *key_sum;
 
  struct IBF_KeyHash *key_hash_sum;
 
  struct IBF_Count *count;
};
 
 
void
ibf_write_slice (const struct InvertibleBloomFilter *ibf,
                 uint32_t start,
                 uint32_t count,
                 void *buf);
 
 
void
ibf_read_slice (const void *buf,
                uint32_t start,
                uint32_t count,
                struct InvertibleBloomFilter *ibf);
 
 
struct IBF_Key
ibf_key_from_hashcode (const struct GNUNET_HashCode *hash);
 
 
void
ibf_hashcode_from_key (struct IBF_Key key, struct GNUNET_HashCode *dst);
 
 
struct InvertibleBloomFilter *
ibf_create (uint32_t size, uint8_t hash_num);
 
 
void
ibf_insert (struct InvertibleBloomFilter *ibf, struct IBF_Key key);
 
 
void
ibf_remove (struct InvertibleBloomFilter *ibf, struct IBF_Key key);
 
 
void
ibf_subtract (struct InvertibleBloomFilter *ibf1,
              const struct InvertibleBloomFilter *ibf2);
 
 
int
ibf_decode (struct InvertibleBloomFilter *ibf,
            int *ret_side,
            struct IBF_Key *ret_id);
 
 
struct InvertibleBloomFilter *
ibf_dup (const struct InvertibleBloomFilter *ibf);
 
 
void
ibf_destroy (struct InvertibleBloomFilter *ibf);
 
 
 
#if 0                           /* keep Emacsens' auto-indent happy */
{
#endif
#ifdef __cplusplus
}
#endif
 
#endif

Function Documentation

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

ibf	the ibf to write
start	with which bucket to start
count	how many buckets to write
buf	buffer to write the data to

Definition at line 291 of file ibf.c.

{
  struct IBF_Key *key_dst;
  struct IBF_KeyHash *key_hash_dst;
  struct IBF_Count *count_dst;
 
    GNUNET_assert (start + count <= ibf->size);
 
  /* copy keys */
  key_dst = (struct IBF_Key *) buf;
  GNUNET_memcpy (key_dst, ibf->key_sum + start, count * sizeof *key_dst);
  key_dst += count;
  /* copy key hashes */
  key_hash_dst = (struct IBF_KeyHash *) key_dst;
  GNUNET_memcpy (key_hash_dst, ibf->key_hash_sum + start, count
                 * sizeof *key_hash_dst);
  key_hash_dst += count;
  /* copy counts */
  count_dst = (struct IBF_Count *) key_hash_dst;
  GNUNET_memcpy (count_dst, ibf->count + start, count * sizeof *count_dst);
}

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

buf	pointer to the buffer to read from
start	which bucket to start at
count	how many buckets to read
ibf	the ibf to write to
buf	pointer to the buffer to read from
start	which bucket to start at
count	how many buckets to read
ibf	the ibf to read from

Definition at line 324 of file ibf.c.

{
  struct IBF_Key *key_src;
  struct IBF_KeyHash *key_hash_src;
  struct IBF_Count *count_src;
 
  GNUNET_assert (count > 0);
  GNUNET_assert (start + count <= ibf->size);
 
  /* copy keys */
  key_src = (struct IBF_Key *) buf;
  GNUNET_memcpy (ibf->key_sum + start, key_src, count * sizeof *key_src);
  key_src += count;
  /* copy key hashes */
  key_hash_src = (struct IBF_KeyHash *) key_src;
  GNUNET_memcpy (ibf->key_hash_sum + start, key_hash_src, count
                 * sizeof *key_hash_src);
  key_hash_src += count;
  /* copy counts */
  count_src = (struct IBF_Count *) key_hash_src;
  GNUNET_memcpy (ibf->count + start, count_src, count * sizeof *count_src);
}

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

struct IBF_Key ibf_key_from_hashcode

(

const struct GNUNET_HashCode *

hash

)

Create a key from a hashcode.

Parameters

hash	the hashcode

Returns

a key

Definition at line 44 of file ibf.c.

{
  return *(struct IBF_Key *) hash;
}

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

key	the key
dst	hashcode to store the result in

Definition at line 58 of file ibf.c.

{
  struct IBF_Key *p;
  unsigned int i;
  const unsigned int keys_per_hashcode = sizeof(struct GNUNET_HashCode)
                                         / sizeof(struct IBF_Key);
 
  p = (struct IBF_Key *) dst;
  for (i = 0; i < keys_per_hashcode; i++)
    *p++ = key;
}

ibf_create()

struct InvertibleBloomFilter * ibf_create	(	uint32_t	size,
		uint8_t	hash_num
	)

Create an invertible bloom filter.

Parameters

size	number of IBF buckets
hash_num	number of buckets one element is hashed in, usually 3 or 4

Returns

the newly created invertible bloom filter, NULL on error

Parameters

size	number of IBF buckets
hash_num	number 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.

{
  struct InvertibleBloomFilter *ibf;
 
  GNUNET_assert (0 != size);
 
  ibf = GNUNET_new (struct InvertibleBloomFilter);
  ibf->count = GNUNET_malloc_large (size * sizeof(uint8_t));
  if (NULL == ibf->count)
  {
    GNUNET_free (ibf);
    return NULL;
  }
  ibf->key_sum = GNUNET_malloc_large (size * sizeof(struct IBF_Key));
  if (NULL == ibf->key_sum)
  {
    GNUNET_free (ibf->count);
    GNUNET_free (ibf);
    return NULL;
  }
  ibf->key_hash_sum = GNUNET_malloc_large (size * sizeof(struct IBF_KeyHash));
  if (NULL == ibf->key_hash_sum)
  {
    GNUNET_free (ibf->key_sum);
    GNUNET_free (ibf->count);
    GNUNET_free (ibf);
    return NULL;
  }
  ibf->size = size;
  ibf->hash_num = hash_num;
 
  return ibf;
}

ibf_insert()

void ibf_insert	(	struct InvertibleBloomFilter *	ibf,
		struct IBF_Key	key
	)

Insert a key into an IBF.

Parameters

ibf	the IBF
key	the element's hash code

Definition at line 168 of file ibf.c.

{
  int buckets[ibf->hash_num];
 
  GNUNET_assert (ibf->hash_num <= ibf->size);
  ibf_get_indices (ibf, key, buckets);
  ibf_insert_into (ibf, key, buckets, 1);
}

ibf_remove()

void ibf_remove	(	struct InvertibleBloomFilter *	ibf,
		struct IBF_Key	key
	)

Remove a key from an IBF.

Parameters

ibf	the IBF
key	the element's hash code

Definition at line 185 of file ibf.c.

{
  int buckets[ibf->hash_num];
 
  GNUNET_assert (ibf->hash_num <= ibf->size);
  ibf_get_indices (ibf, key, buckets);
  ibf_insert_into (ibf, key, buckets, -1);
}

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

ibf1	IBF that is subtracted from
ibf2	IBF that will be subtracted from ibf1

Definition at line 357 of file ibf.c.

{
  int i;
 
  GNUNET_assert (ibf1->size == ibf2->size);
  GNUNET_assert (ibf1->hash_num == ibf2->hash_num);
 
  for (i = 0; i < ibf1->size; i++)
  {
    ibf1->count[i].count_val -= ibf2->count[i].count_val;
    ibf1->key_hash_sum[i].key_hash_val ^= ibf2->key_hash_sum[i].key_hash_val;
    ibf1->key_sum[i].key_val ^= ibf2->key_sum[i].key_val;
  }
}

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

ibf	the invertible bloom filter to decode
ret_side	sign 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_id	receives 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

Parameters

ibf	the invertible bloom filter to decode
ret_side	sign 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_id	receives 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.

{
  struct IBF_KeyHash hash;
  int i;
  int buckets[ibf->hash_num];
 
  GNUNET_assert (NULL != ibf);
 
  for (i = 0; i < ibf->size; i++)
  {
    int j;
    int hit;
 
    /* we can only decode from pure buckets */
    if ((1 != ibf->count[i].count_val) && (-1 != ibf->count[i].count_val))
      continue;
 
    hash.key_hash_val = IBF_KEY_HASH_VAL (ibf->key_sum[i]);
 
    /* test if the hash matches the key */
    if (hash.key_hash_val != ibf->key_hash_sum[i].key_hash_val)
      continue;
 
    /* test if key in bucket hits its own location,
     * if not, the key hash was subject to collision */
    hit = GNUNET_NO;
    ibf_get_indices (ibf, ibf->key_sum[i], buckets);
    for (j = 0; j < ibf->hash_num; j++)
      if (buckets[j] == i)
        hit = GNUNET_YES;
 
    if (GNUNET_NO == hit)
      continue;
 
    if (NULL != ret_side)
      *ret_side = ibf->count[i].count_val;
    if (NULL != ret_id)
      *ret_id = ibf->key_sum[i];
 
    /* insert on the opposite side, effectively removing the element */
    ibf_insert_into (ibf, ibf->key_sum[i], buckets, -ibf->count[i].count_val);
 
    return GNUNET_YES;
  }
 
  if (GNUNET_YES == ibf_is_empty (ibf))
    return GNUNET_NO;
  return GNUNET_SYSERR;
}

ibf_dup()

struct InvertibleBloomFilter * ibf_dup

(

const struct InvertibleBloomFilter *

ibf

)

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

Parameters

ibf	the IBF to copy

Definition at line 380 of file ibf.c.

{
  struct InvertibleBloomFilter *copy;
 
  copy = GNUNET_malloc (sizeof *copy);
  copy->hash_num = ibf->hash_num;
  copy->size = ibf->size;
  copy->key_hash_sum = GNUNET_memdup (ibf->key_hash_sum, ibf->size
                                      * sizeof(struct IBF_KeyHash));
  copy->key_sum = GNUNET_memdup (ibf->key_sum, ibf->size * sizeof(struct
                                                                  IBF_Key));
  copy->count = GNUNET_memdup (ibf->count, ibf->size * sizeof(struct
                                                              IBF_Count));
  return copy;
}

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

ibf	the intertible bloom filter to destroy

Definition at line 404 of file ibf.c.

{
  GNUNET_free (ibf->key_sum);
  GNUNET_free (ibf->key_hash_sum);
  GNUNET_free (ibf->count);
  GNUNET_free (ibf);
}