A C++ template library for embedded applications
Designed and maintained by
Aster Consulting Ltd
Join the ETL community

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"); // Returns true
test = bloom.exists("You");   // Returns false
test = bloom.exists("You");   // Returns true (false positive)

____________________________________________________________________________________________________

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