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 (const std::vector< unsigned char > &vKey)
void	insert (const uint256 &hash)
bool	contains (const std::vector< unsigned char > &vKey) const
bool	contains (const uint256 &hash) 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. (More accurately: 3/(log(256)*log(2)) * log(1/fpRate) * nElements bytes)

Definition at line 126 of file bloom.h.

Constructor & Destructor Documentation

CRollingBloomFilter()

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

Definition at line 301 of file bloom.cpp.

References data, nEntriesPerGeneration, nHashFuncs, and reset().

Member Function Documentation

contains() [1/2]

bool CRollingBloomFilter::contains

(

const std::vector< unsigned char > &

vKey

)

const

Definition at line 378 of file bloom.cpp.

References data, FastMod(), nHashFuncs, nTweak, and RollingBloomHash().

Referenced by contains(), CNode::PushAddress(), RollingBloom(), and PeerLogicValidation::SendMessages().

contains() [2/2]

bool CRollingBloomFilter::contains

(

const uint256 &

hash

)

const

Definition at line 392 of file bloom.cpp.

References base_blob< BITS >::begin(), contains(), and base_blob< BITS >::end().

insert() [1/2]

void CRollingBloomFilter::insert

(

const std::vector< unsigned char > &

vKey

)

Definition at line 341 of file bloom.cpp.

References data, FastMod(), immer::detail::hamts::mask, nEntriesPerGeneration, nEntriesThisGeneration, nGeneration, nHashFuncs, nTweak, and RollingBloomHash().

Referenced by CNode::AddAddressKnown(), insert(), RollingBloom(), and PeerLogicValidation::SendMessages().

insert() [2/2]

void CRollingBloomFilter::insert

(

const uint256 &

hash

)

Definition at line 372 of file bloom.cpp.

References base_blob< BITS >::begin(), base_blob< BITS >::end(), and insert().

reset()

void CRollingBloomFilter::reset

(

)

Definition at line 398 of file bloom.cpp.

References data, GetRand(), nEntriesThisGeneration, nGeneration, and nTweak.

Referenced by CRollingBloomFilter().

Member Data Documentation

data

std::vector<uint64_t> CRollingBloomFilter::data

private

Definition at line 145 of file bloom.h.

Referenced by contains(), CRollingBloomFilter(), insert(), and reset().

nEntriesPerGeneration

int CRollingBloomFilter::nEntriesPerGeneration

private

Definition at line 142 of file bloom.h.

Referenced by CRollingBloomFilter(), and insert().

nEntriesThisGeneration

int CRollingBloomFilter::nEntriesThisGeneration

private

Definition at line 143 of file bloom.h.

Referenced by insert(), and reset().

nGeneration

int CRollingBloomFilter::nGeneration

private

Definition at line 144 of file bloom.h.

Referenced by insert(), and reset().

nHashFuncs

int CRollingBloomFilter::nHashFuncs

private

Definition at line 147 of file bloom.h.

Referenced by contains(), CRollingBloomFilter(), and insert().

nTweak

unsigned int CRollingBloomFilter::nTweak

private

Definition at line 146 of file bloom.h.

Referenced by contains(), insert(), and reset().

---

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

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