bloom_filter
etl::bloom_filter<const size_t WIDTH, typename THash1, typename THash2, typename THash3>
A Bloom filter that supports up to three hash functions. Thash2 & Thash3 are optional.
The width specified is the desired width,
The class may use more if the underlying bitset naturally has spare capacity.
i.e. A bloom filter with a specified capacity of 195 bits will be rounded up to 200 bits as the bitset has a block size of 8.
____________________________________________________________________________________________________
Example
#include "bloom_filter.h
#include "fnv-1.h"
#include "string.h"
struct hash_t
{
typedef const char* argument_type;
size_t operator ()(argument_type text) const
{
return etl::fnv_1a_32(text, text + strlen(text));
}
};
etl::bloom_filter<64, hash_t> bloom;
bloom.add("Hello");
bloom.add("World");
bloom.add("the");
bool test;
test = bloom.exists("Hello");
test = bloom.exists("You");
test = bloom.exists("you");
____________________________________________________________________________________________________
Constructor
The initial state of the Bloom filter is clear.
etl::bitset<const size_t WIDTH, typename THash1, typename THash2, typename THash3>();
____________________________________________________________________________________________________
Operations
void clear()
Clears the filter of all entries.
____________________________________________________________________________________________________
void add(parameter_t key)
Adds a key to the filter, where parameter_t is derived from the first hash argument type.
____________________________________________________________________________________________________
bool exists(parameter_t key)const
Checks to see if a key may exist in the filter, where parameter_t is derived from the first hash argument type.
____________________________________________________________________________________________________
size_t usage() const
Returns the usage of the filter in percent.
Equal to 100 * count() / width()
____________________________________________________________________________________________________
bool count() const
Returns the number of elements in use in the filter.
____________________________________________________________________________________________________
bool width() const
Returns the width of the filter.
Equal to the template parameter WIDTH.