CRollingBloomFilter Class Reference

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

#include <bloom.h>

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

Private Attributes
int	nEntriesPerGeneration
int	nEntriesThisGeneration
int	nGeneration
std::vector< uint64_t >	data
uint32_t	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. (More accurately: 3/(log(256)*log(2)) * log(1/fpRate) * nElements bytes)

Definition at line 115 of file bloom.h.

Constructor & Destructor Documentation

CRollingBloomFilter()

CRollingBloomFilter::CRollingBloomFilter	(	const uint32_t	nElements,
		const double	nFPRate
	)

Definition at line 173 of file bloom.cpp.

Here is the call graph for this function:

Member Function Documentation

contains()

bool CRollingBloomFilter::contains

(

Span< const uint8_t >

vKey

)

const

Definition at line 249 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 uint8_t >

vKey

)

Definition at line 215 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 263 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 128 of file bloom.h.

nEntriesPerGeneration

int CRollingBloomFilter::nEntriesPerGeneration

private

Definition at line 125 of file bloom.h.

nEntriesThisGeneration

int CRollingBloomFilter::nEntriesThisGeneration

private

Definition at line 126 of file bloom.h.

nGeneration

int CRollingBloomFilter::nGeneration

private

Definition at line 127 of file bloom.h.

nHashFuncs

int CRollingBloomFilter::nHashFuncs

private

Definition at line 130 of file bloom.h.

nTweak

uint32_t CRollingBloomFilter::nTweak

private

Definition at line 129 of file bloom.h.

---

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

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