Bloom filter

Bloom filter library. More...

Detailed Description

Bloom filter library.

Files
file	bloom.h
	Bloom filter API.

Data Structures
struct	bloom_t
	bloom_t bloom filter object More...

Typedefs
typedef uint32_t(*	hashfp_t) (const uint8_t *, size_t len)
	hash function to use in thee filter

Functions
void	bloom_init (bloom_t *bloom, size_t size, uint8_t *bitfield, hashfp_t *hashes, int hashes_numof)
	Initialize a Bloom Filter.
void	bloom_del (bloom_t *bloom)
	Delete a Bloom filter.
void	bloom_add (bloom_t *bloom, const uint8_t *buf, size_t len)
	Add a string to a Bloom filter.
bool	bloom_check (bloom_t *bloom, const uint8_t *buf, size_t len)
	Determine if a string is in the Bloom filter.

Typedef Documentation

hashfp_t

typedef uint32_t(* hashfp_t) (const uint8_t *, size_t len)

hash function to use in thee filter

Definition at line 137 of file bloom.h.

Function Documentation

bloom_add()

void bloom_add	(	bloom_t *	bloom,
		const uint8_t *	buf,
		size_t	len
	)

Add a string to a Bloom filter.

CAVEAT Once a string has been added to the filter, it cannot be "removed"!

Parameters

bloom	Bloom filter
buf	string to add
len	the length of the string buf

Returns

nothing

bloom_check()

bool bloom_check	(	bloom_t *	bloom,
		const uint8_t *	buf,
		size_t	len
	)

Determine if a string is in the Bloom filter.

The string 's' is hashed once for each of the 'k' hash functions, as though we were planning to add it to the filter. Instead of adding it however, we examine the bit that we would have set, and consider its value.

If the bit is 1 (set), the string we are hashing may be in the filter, since it would have set this bit when it was originally hashed. However, it may also be that another string just happened to produce a hash value that would also set this bit. That would be a false positive. This is why we have k > 1, so we can minimize the likelihood of false positives occurring.

If every bit corresponding to every one of the k hashes of our query string is set, we can say with some probability of being correct that the string we are holding is indeed "in" the filter. However, we can never be sure.

If, however, as we hash our string and peek at the resulting bit in the filter, we find the bit is 0 (not set)... well now, that's different. In this case, we can say with absolute certainty that the string we are holding is not in the filter, because if it were, this bit would have to be set.

In this way, the Bloom filter can answer NO with absolute surety, but can only speak a qualified YES.

Parameters

bloom	Bloom filter
buf	string to check
len	the length of the string buf

Returns

false if string does not exist in the filter

true if string is may be in the filter

bloom_del()

void bloom_del

(

bloom_t *

bloom

)

Delete a Bloom filter.

Parameters

bloom

The condemned

Returns

nothing

bloom_init()

void bloom_init	(	bloom_t *	bloom,
		size_t	size,
		uint8_t *	bitfield,
		hashfp_t *	hashes,
		int	hashes_numof
	)

Initialize a Bloom Filter.

Note

For best results, make 'size' a power of 2.

Parameters

bloom	bloom_t to initialize
size	size of the bloom filter in bits
bitfield	underlying bitfield of the bloom filter
hashes	array of hashes
hashes_numof	number of elements in hashes

Precondition

bitfield MUST be large enough to hold size bits.