Bitcoin Core  21.99.0
P2P Digital Currency
Public Member Functions | Private Attributes | List of all members
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. For example, if we want 1000 elements, we'd need:

If we make these simplifying assumptions:

Then we get a more accurate estimate for filter bytes:

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

Definition at line 110 of file bloom.h.

Constructor & Destructor Documentation

◆ CRollingBloomFilter()

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

Definition at line 173 of file bloom.cpp.

Here is the call graph for this function:

Member Function Documentation

◆ contains() [1/2]

bool CRollingBloomFilter::contains ( const std::vector< unsigned char > &  vKey) const

Definition at line 250 of file bloom.cpp.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ contains() [2/2]

bool CRollingBloomFilter::contains ( const uint256 hash) const

Definition at line 264 of file bloom.cpp.

Here is the call graph for this function:

◆ insert() [1/2]

void CRollingBloomFilter::insert ( const std::vector< unsigned char > &  vKey)

Definition at line 213 of file bloom.cpp.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ insert() [2/2]

void CRollingBloomFilter::insert ( const uint256 hash)

Definition at line 244 of file bloom.cpp.

Here is the call graph for this function:

◆ reset()

void CRollingBloomFilter::reset ( )

Definition at line 270 of file bloom.cpp.

Here is the call graph for this function:
Here is the caller graph for this function:

Member Data Documentation

◆ data

std::vector<uint64_t> CRollingBloomFilter::data
private

Definition at line 126 of file bloom.h.

◆ nEntriesPerGeneration

int CRollingBloomFilter::nEntriesPerGeneration
private

Definition at line 123 of file bloom.h.

◆ nEntriesThisGeneration

int CRollingBloomFilter::nEntriesThisGeneration
private

Definition at line 124 of file bloom.h.

◆ nGeneration

int CRollingBloomFilter::nGeneration
private

Definition at line 125 of file bloom.h.

◆ nHashFuncs

int CRollingBloomFilter::nHashFuncs
private

Definition at line 128 of file bloom.h.

◆ nTweak

unsigned int CRollingBloomFilter::nTweak
private

Definition at line 127 of file bloom.h.


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