Bitcoin ABC 0.30.3
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 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: