Bitcoin Core  0.15.99
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. (More accurately: 3/(log(256)*log(2)) * log(1/fpRate) * nElements bytes)

Definition at line 119 of file bloom.h.

Constructor & Destructor Documentation

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

Definition at line 216 of file bloom.cpp.

Here is the call graph for this function:

Member Function Documentation

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

Definition at line 284 of file bloom.cpp.

Here is the caller graph for this function:

bool CRollingBloomFilter::contains ( const uint256 hash) const

Definition at line 298 of file bloom.cpp.

Here is the call graph for this function:

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

Definition at line 248 of file bloom.cpp.

Here is the caller graph for this function:

void CRollingBloomFilter::insert ( const uint256 hash)

Definition at line 278 of file bloom.cpp.

Here is the call graph for this function:

void CRollingBloomFilter::reset ( )

Definition at line 304 of file bloom.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

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

Definition at line 138 of file bloom.h.

int CRollingBloomFilter::nEntriesPerGeneration
private

Definition at line 135 of file bloom.h.

int CRollingBloomFilter::nEntriesThisGeneration
private

Definition at line 136 of file bloom.h.

int CRollingBloomFilter::nGeneration
private

Definition at line 137 of file bloom.h.

int CRollingBloomFilter::nHashFuncs
private

Definition at line 140 of file bloom.h.

unsigned int CRollingBloomFilter::nTweak
private

Definition at line 139 of file bloom.h.


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