InvertibleBloomFilter Struct Reference

Invertible bloom filter (IBF). More...

#include </home/buildbot/bb-worker/worker/gnunet_firefly/build/src/contrib/service/set/ibf.h>

Collaboration diagram for InvertibleBloomFilter:

Data Fields
uint32_t	size
	How many cells does this IBF have? More...
uint8_t	hash_num
	In how many cells do we hash one element? Usually 4 or 3. More...
struct IBF_Key *	key_sum
	Xor sums of the elements' keys, used to identify the elements. More...
struct IBF_KeyHash *	key_hash_sum
	Xor sums of the hashes of the keys of inserted elements. More...
struct IBF_Count *	count
	How many times has a bucket been hit? Can be negative, as a result of IBF subtraction. More...
int	local_decoded_count
	If an IBF is decoded this count stores how many elements are on the local site. More...
int	remote_decoded_count
	If an IBF is decoded this count stores how many elements are on the remote site. More...

Detailed Description

Invertible bloom filter (IBF).

An IBF is a counting bloom filter that has the ability to restore the hashes of its stored elements with high probability.

Definition at line 82 of file ibf.h.

Field Documentation

size

uint32_t InvertibleBloomFilter::size

How many cells does this IBF have?

Definition at line 87 of file ibf.h.

Referenced by decode_and_send(), ibf_create(), ibf_decode(), ibf_dup(), ibf_get_indices(), ibf_get_max_counter(), ibf_insert(), ibf_is_empty(), ibf_remove(), ibf_subtract(), and strata_estimator_difference().

hash_num

uint8_t InvertibleBloomFilter::hash_num

In how many cells do we hash one element? Usually 4 or 3.

Definition at line 93 of file ibf.h.

Referenced by ibf_create(), ibf_decode(), ibf_dup(), ibf_get_indices(), ibf_insert(), ibf_insert_into(), ibf_remove(), and ibf_subtract().

key_sum

struct IBF_Key * InvertibleBloomFilter::key_sum

Xor sums of the elements' keys, used to identify the elements.

Array of 'size' elements.

Definition at line 99 of file ibf.h.

Referenced by ibf_create(), ibf_decode(), ibf_destroy(), ibf_dup(), ibf_insert_into(), ibf_is_empty(), ibf_read_slice(), ibf_subtract(), and ibf_write_slice().

key_hash_sum

struct IBF_KeyHash * InvertibleBloomFilter::key_hash_sum

Xor sums of the hashes of the keys of inserted elements.

Array of 'size' elements.

Definition at line 105 of file ibf.h.

Referenced by ibf_create(), ibf_decode(), ibf_destroy(), ibf_dup(), ibf_insert_into(), ibf_is_empty(), ibf_read_slice(), ibf_subtract(), and ibf_write_slice().

count

struct IBF_Count * InvertibleBloomFilter::count

How many times has a bucket been hit? Can be negative, as a result of IBF subtraction.

Array of 'size' elements.

Definition at line 112 of file ibf.h.

Referenced by ibf_create(), ibf_decode(), ibf_destroy(), ibf_dup(), ibf_get_max_counter(), ibf_insert_into(), ibf_is_empty(), ibf_read_slice(), ibf_subtract(), ibf_write_slice(), pack_counter(), strata_estimator_difference(), and unpack_counter().

local_decoded_count

int InvertibleBloomFilter::local_decoded_count

If an IBF is decoded this count stores how many elements are on the local site.

This is used to estimate the set difference on a site

Definition at line 101 of file ibf.h.

Referenced by handle_union_p2p_strata_estimator(), ibf_decode(), and strata_estimator_difference().

remote_decoded_count

int InvertibleBloomFilter::remote_decoded_count

If an IBF is decoded this count stores how many elements are on the remote site.

This is used to estimate the set difference on a site

Definition at line 108 of file ibf.h.

Referenced by handle_union_p2p_strata_estimator(), ibf_decode(), and strata_estimator_difference().

---

The documentation for this struct was generated from the following files:

• src/contrib/service/set/ibf.h
• src/service/setu/ibf.h