MultiApplicationOnlineProfiling
2.1

A bloom filter is a compact probabilistic data structure where elements can be added and where element existence can be queried. More...
Data Structures  
struct  Bloom_Filter 
This is the main structure defining the Bloom Filter. More...  
Functions  
void  Bloom_Filter_init (struct Bloom_Filter *bf, uint64_t size, size_t sizeof_payload) 
Initializes a Bloom_Filter. More...  
void  Bloom_Filter_release (struct Bloom_Filter *bf) 
Releases a Bloom_Filter. More...  
static uint64_t  Bloom_Filter_get_cell (struct Bloom_Filter *bf, void *payload) 
Gets the given element's index within internal bit array. More...  
static void  Bloom_Filter_push (struct Bloom_Filter *bf, void *payload) 
Adds an element to the filter. More...  
static int  Bloom_Filter_test (struct Bloom_Filter *bf, void *payload) 
Tests if the filter contains an element. More...  
void  Bloom_Filter_replicate (struct Bloom_Filter *dest, struct Bloom_Filter *src) 
Copies a Bloom_Filter within an other. More...  
A bloom filter is a compact probabilistic data structure where elements can be added and where element existence can be queried.
It consists of a bit array initially all set to 0. When an element is added to a Bloom filter, a number (n) of hashes are computed for the element, giving n indexes (indexes must be less than the bit array size). Then each bits of indexes given by the hashes are set to 1.
To test if an element has already been added to the filter, the indexes are computed and, if any of the bits is 0, the element has not been added, otherwise the element may exist in the filter.
In this manner, false positives are possible, but false negative are not.
This implementation is based on only one hash function (CRC64) and Bit_Array.

inlinestatic 
Gets the given element's index within internal bit array.
bf  the Bloom_Filter 
payload  the element for which the index is wanted 
Definition at line 69 of file Bloom_Filter.h.
void Bloom_Filter_init  (  struct Bloom_Filter *  bf, 
uint64_t  size,  
size_t  sizeof_payload  
) 
Initializes a Bloom_Filter.
bf  the filter to initialize 
size  the size of the filter's internal bit array 
sizeof_payload  the size of data that can be added to the filter 
Definition at line 24 of file Bloom_Filter.c.

inlinestatic 
Adds an element to the filter.
bf  the filter where to add the element 
payload  the element to add 
Definition at line 81 of file Bloom_Filter.h.
void Bloom_Filter_release  (  struct Bloom_Filter *  bf  ) 
Releases a Bloom_Filter.
bf  the filter to be freed 
Definition at line 32 of file Bloom_Filter.c.
void Bloom_Filter_replicate  (  struct Bloom_Filter *  dest, 
struct Bloom_Filter *  src  
) 
Copies a Bloom_Filter within an other.
dest  the destination filter 
src  the source filter 
Definition at line 42 of file Bloom_Filter.c.

inlinestatic 
Tests if the filter contains an element.
bf  the filter chere to search 
payload  the element to find in the filter 
Definition at line 96 of file Bloom_Filter.h.