Bloom filter

Bloom filter library.

uint32_t(* hashfp_t()

hash function to use in thee filter

void bloom_init(bloom_t * bloom, msp430_types.h::size_t size, uint8_t * bitfield, bloom.h::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

void bloom_del(bloom_t * bloom)

Delete a Bloom filter.

Parameters

bloom:The condemned

Return values

• nothing

void bloom_add(bloom_t * bloom, const uint8_t * buf, msp430_types.h::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

Return values

• nothing

bool bloom_check(bloom_t * bloom, const uint8_t * buf, msp430_types.h::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 occuring.

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

Return values

• false if string does not exist in the filter
• true if string is may be in the filter

struct bloom_t

bloom_t bloom filter object

msp430_types.h::size_t m

number of bits in the bloom array

msp430_types.h::size_t k

number of hash functions

uint8_t * a

the bloom array

bloom.h::hashfp_t * hash

the hash functions