The friendly Operating System for the Internet of Things
Bloom filter

Bloom filter library. More...

Detailed Description

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 *, int 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. More...
 
void bloom_del (bloom_t *bloom)
 Delete a Bloom filter. More...
 
void bloom_add (bloom_t *bloom, const uint8_t *buf, size_t len)
 Add a string to a Bloom filter. More...
 
bool bloom_check (bloom_t *bloom, const uint8_t *buf, size_t len)
 Determine if a string is in the Bloom filter. More...
 

Function Documentation

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

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

Parameters
bloomBloom filter
bufstring to add
lenthe length of the string buf
Returns
nothing
bool bloom_check ( bloom_t bloom,
const uint8_t *  buf,
size_t  len 
)

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
bloomBloom filter
bufstring to check
lenthe length of the string buf
Returns
false if string does not exist in the filter
true if string is may be in the filter
void bloom_del ( bloom_t bloom)
Parameters
bloomThe condemned
Returns
nothing
void bloom_init ( bloom_t bloom,
size_t  size,
uint8_t *  bitfield,
hashfp_t hashes,
int  hashes_numof 
)
Note
For best results, make 'size' a power of 2.
Parameters
bloombloom_t to initialize
sizesize of the bloom filter in bits
bitfieldunderlying bitfield of the bloom filter
hashesarray of hashes
hashes_numofnumber of elements in hashes
Precondition
bitfield MUST be large enough to hold size bits.