boxes::filter::bloom::Bloom< KeyT, HashT > Class Template Reference

A generic bloom filter implementation. More...

#include <bloom_filter.hpp>

Public Member Functions
	Bloom (std::size_t m, HashT h)
	Instantiates a new bloom filter. More...
void	insert (const KeyT &key)
	Inserts key into the filter. More...
bool	contains (const KeyT &key) const
	Checks if the filter contains the given key. More...
std::size_t	capacity () const BOXES_NOTHROW
	Returns number of bits in the filter. More...
std::size_t	k () const BOXES_NOTHROW
	Number of hash functions the filter uses. More...
std::size_t	size () const BOXES_NOTHROW
	Estimated number of elements in the filter. More...
std::size_t	count () const
	Returns number of bits set in the filter's bitmap. More...
void	swap (Bloom &other)
	Swaps the contents of this filter with another one. More...
void	clear () BOXES_NOTHROW
	Clears filter's bitmap. More...

Detailed Description

template<typename KeyT, hash::HashFamily64 HashT>
class boxes::filter::bloom::Bloom< KeyT, HashT >

A generic bloom filter implementation.

Template Parameters

KeyT	type of keys the filter will store
HashT	type of the hash family to use see HashFamily64 concept for more details and associated wrappers in hash_utils.hpp.

Definition at line 34 of file bloom_filter.hpp.

Constructor & Destructor Documentation

Bloom()

template<typename KeyT , hash::HashFamily64 HashT>

boxes::filter::bloom::Bloom< KeyT, HashT >::Bloom ( std::size_t  m, HashT  h  )

inline

Instantiates a new bloom filter.

Parameters

m	number of bits in the filter
h	an instance of the hash family to use

Definition at line 45 of file bloom_filter.hpp.

Member Function Documentation

capacity()

template<typename KeyT , hash::HashFamily64 HashT>

std::size_t boxes::filter::bloom::Bloom< KeyT, HashT >::capacity ( ) const

inline

Returns number of bits in the filter.

Returns

number of bits comprising filter's bitmap

Definition at line 89 of file bloom_filter.hpp.

clear()

template<typename KeyT , hash::HashFamily64 HashT>

void boxes::filter::bloom::Bloom< KeyT, HashT >::clear ( )

inline

Clears filter's bitmap.

Definition at line 134 of file bloom_filter.hpp.

contains()

template<typename KeyT , hash::HashFamily64 HashT>

bool boxes::filter::bloom::Bloom< KeyT, HashT >::contains ( const KeyT &  key ) const

inline

Checks if the filter contains the given key.

False positives are possible, but false negatives are not.

Parameters

key	key to check

Returns

true if the filter potentially contains the key, false if filter definitely does not contain the key

Definition at line 72 of file bloom_filter.hpp.

count()

template<typename KeyT , hash::HashFamily64 HashT>

std::size_t boxes::filter::bloom::Bloom< KeyT, HashT >::count ( ) const

inline

Returns number of bits set in the filter's bitmap.

Returns

number of bits set in the filter's bitmap

Definition at line 113 of file bloom_filter.hpp.

insert()

template<typename KeyT , hash::HashFamily64 HashT>

void boxes::filter::bloom::Bloom< KeyT, HashT >::insert ( const KeyT &  key )

inline

Inserts key into the filter.

Parameters

key	key to insert

Definition at line 54 of file bloom_filter.hpp.

k()

template<typename KeyT , hash::HashFamily64 HashT>

std::size_t boxes::filter::bloom::Bloom< KeyT, HashT >::k ( ) const

inline

Number of hash functions the filter uses.

Returns

number of hash functions

Definition at line 96 of file bloom_filter.hpp.

size()

template<typename KeyT , hash::HashFamily64 HashT>

std::size_t boxes::filter::bloom::Bloom< KeyT, HashT >::size ( ) const

inline

Estimated number of elements in the filter.

Returns

estimated number of elements in the filter

Definition at line 103 of file bloom_filter.hpp.

swap()

template<typename KeyT , hash::HashFamily64 HashT>

void boxes::filter::bloom::Bloom< KeyT, HashT >::swap ( Bloom< KeyT, HashT > &  other )

inline

Swaps the contents of this filter with another one.

Parameters

other

filter to swap with

Definition at line 124 of file bloom_filter.hpp.

---

The documentation for this class was generated from the following file:

• include/boxes/bloom_filter.hpp