CRollingBloomFilter Class Reference

RollingBloomFilter is a probabilistic "keep track of most recently inserted" set. More...

#include <bloom.h>

Public Member Functions
	CRollingBloomFilter (const unsigned int nElements, const double nFPRate)
void	insert (Span< const unsigned char > vKey)
bool	contains (Span< const unsigned char > vKey) const
void	reset ()

Private Attributes
int	nEntriesPerGeneration
int	nEntriesThisGeneration
int	nGeneration
std::vector< uint64_t >	data
unsigned int	nTweak
int	nHashFuncs

Detailed Description

RollingBloomFilter is a probabilistic "keep track of most recently inserted" set.

Construct it with the number of items to keep track of, and a false-positive rate. Unlike CBloomFilter, by default nTweak is set to a cryptographically secure random value for you. Similarly rather than clear() the method reset() is provided, which also changes nTweak to decrease the impact of false-positives.

contains(item) will always return true if item was one of the last N to 1.5*N insert()'ed ... but may also return true for items that were not inserted.

It needs around 1.8 bytes per element per factor 0.1 of false positive rate. For example, if we want 1000 elements, we'd need:

• ~1800 bytes for a false positive rate of 0.1
• ~3600 bytes for a false positive rate of 0.01
• ~5400 bytes for a false positive rate of 0.001

If we make these simplifying assumptions:

• logFpRate / log(0.5) doesn't get rounded or clamped in the nHashFuncs calculation
• nElements is even, so that nEntriesPerGeneration == nElements / 2

Then we get a more accurate estimate for filter bytes:

3/(log(256)*log(2)) * log(1/fpRate) * nElements

Definition at line 108 of file bloom.h.

Constructor & Destructor Documentation

CRollingBloomFilter()

CRollingBloomFilter::CRollingBloomFilter	(	const unsigned int	nElements,
		const double	nFPRate
	)

Definition at line 162 of file bloom.cpp.

Here is the call graph for this function:

Member Function Documentation

contains()

bool CRollingBloomFilter::contains

(

Span< const unsigned char >

vKey

)

const

Definition at line 226 of file bloom.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

insert()

void CRollingBloomFilter::insert

(

Span< const unsigned char >

vKey

)

Definition at line 195 of file bloom.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

reset()

void CRollingBloomFilter::reset

(

)

Definition at line 240 of file bloom.cpp.

Here is the caller graph for this function:

Member Data Documentation

data

std::vector<uint64_t> CRollingBloomFilter::data

private

Definition at line 122 of file bloom.h.

nEntriesPerGeneration

int CRollingBloomFilter::nEntriesPerGeneration

private

Definition at line 119 of file bloom.h.

nEntriesThisGeneration

int CRollingBloomFilter::nEntriesThisGeneration

private

Definition at line 120 of file bloom.h.

nGeneration

int CRollingBloomFilter::nGeneration

private

Definition at line 121 of file bloom.h.

nHashFuncs

int CRollingBloomFilter::nHashFuncs

private

Definition at line 124 of file bloom.h.

nTweak

unsigned int CRollingBloomFilter::nTweak

private

Definition at line 123 of file bloom.h.

---

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

• src/common/bloom.h
• src/common/bloom.cpp