Bloom Filter

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

Detailed Description

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.

Function Documentation

static uint64_t Bloom_Filter_get_cell ( struct Bloom_Filter *  bf, void *  payload  )

inlinestatic

Gets the given element's index within internal bit array.

Parameters

bf	the Bloom_Filter
payload	the element for which the index is wanted

Returns

the index of the element (crc64 of the element modulo the size of the array)

Definition at line 69 of file Bloom_Filter.h.

Here is the call graph for this function:

Here is the caller graph for this function:

void Bloom_Filter_init	(	struct Bloom_Filter *	bf,
		uint64_t	size,
		size_t	sizeof_payload
	)

Initializes a Bloom_Filter.

Parameters

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.

Here is the call graph for this function:

static void Bloom_Filter_push ( struct Bloom_Filter *  bf, void *  payload  )

inlinestatic

Adds an element to the filter.

Parameters

bf	the filter where to add the element
payload	the element to add

Definition at line 81 of file Bloom_Filter.h.

Here is the call graph for this function:

void Bloom_Filter_release

(

struct Bloom_Filter *

bf

)

Releases a Bloom_Filter.

Parameters

bf	the filter to be freed

Definition at line 32 of file Bloom_Filter.c.

Here is the call graph for this function:

void Bloom_Filter_replicate	(	struct Bloom_Filter *	dest,
		struct Bloom_Filter *	src
	)

Copies a Bloom_Filter within an other.

Parameters

dest	the destination filter
src	the source filter

Warning

As only the internal bit array is copied, src and dest must be initialized with the same parameters before replicate.

Definition at line 42 of file Bloom_Filter.c.

Here is the call graph for this function:

static int Bloom_Filter_test ( struct Bloom_Filter *  bf, void *  payload  )

inlinestatic

Tests if the filter contains an element.

Parameters

bf	the filter chere to search
payload	the element to find in the filter

Returns

0 if the element is not in the filter, 1 if it may be.

Definition at line 96 of file Bloom_Filter.h.

Here is the call graph for this function: