Changeset View
Changeset View
Standalone View
Standalone View
src/bloom.cpp
Show All 24 Lines | |||||
* protocol limits | * protocol limits | ||||
* | * | ||||
* The ideal number of hash functions is filter size * ln(2) / number of | * The ideal number of hash functions is filter size * ln(2) / number of | ||||
* elements. Again, we ignore filter parameters which will create a bloom filter | * elements. Again, we ignore filter parameters which will create a bloom filter | ||||
* with more hash functions than the protocol limits. | * with more hash functions than the protocol limits. | ||||
* See https://en.wikipedia.org/wiki/Bloom_filter for an explanation of these | * See https://en.wikipedia.org/wiki/Bloom_filter for an explanation of these | ||||
* formulas. | * formulas. | ||||
*/ | */ | ||||
CBloomFilter::CBloomFilter(uint32_t nElements, double nFPRate, | CBloomFilter::CBloomFilter(const uint32_t nElements, const double nFPRate, | ||||
uint32_t nTweakIn, uint8_t nFlagsIn) | const uint32_t nTweakIn, uint8_t nFlagsIn) | ||||
: vData(std::min<uint32_t>(-1 / LN2SQUARED * nElements * log(nFPRate), | : vData(std::min<uint32_t>(-1 / LN2SQUARED * nElements * log(nFPRate), | ||||
MAX_BLOOM_FILTER_SIZE * 8) / | MAX_BLOOM_FILTER_SIZE * 8) / | ||||
8), | 8), | ||||
isFull(false), isEmpty(true), | isFull(false), isEmpty(true), | ||||
nHashFuncs(std::min<uint32_t>(vData.size() * 8 / nElements * LN2, | nHashFuncs(std::min<uint32_t>(vData.size() * 8 / nElements * LN2, | ||||
MAX_HASH_FUNCS)), | MAX_HASH_FUNCS)), | ||||
nTweak(nTweakIn), nFlags(nFlagsIn) {} | nTweak(nTweakIn), nFlags(nFlagsIn) {} | ||||
// Private constructor used by CRollingBloomFilter | // Private constructor used by CRollingBloomFilter | ||||
CBloomFilter::CBloomFilter(uint32_t nElements, double nFPRate, | CBloomFilter::CBloomFilter(const uint32_t nElements, const double nFPRate, | ||||
uint32_t nTweakIn) | const uint32_t nTweakIn) | ||||
: vData(uint32_t(-1 / LN2SQUARED * nElements * log(nFPRate)) / 8), | : vData(uint32_t(-1 / LN2SQUARED * nElements * log(nFPRate)) / 8), | ||||
isFull(false), isEmpty(true), | isFull(false), isEmpty(true), | ||||
nHashFuncs(uint32_t(vData.size() * 8 / nElements * LN2)), | nHashFuncs(uint32_t(vData.size() * 8 / nElements * LN2)), | ||||
nTweak(nTweakIn), nFlags(BLOOM_UPDATE_NONE) {} | nTweak(nTweakIn), nFlags(BLOOM_UPDATE_NONE) {} | ||||
inline uint32_t | inline uint32_t | ||||
CBloomFilter::Hash(uint32_t nHashNum, | CBloomFilter::Hash(uint32_t nHashNum, | ||||
const std::vector<uint8_t> &vDataToHash) const { | const std::vector<uint8_t> &vDataToHash) const { | ||||
▲ Show 20 Lines • Show All 58 Lines • ▼ Show 20 Lines | |||||
} | } | ||||
void CBloomFilter::clear() { | void CBloomFilter::clear() { | ||||
vData.assign(vData.size(), 0); | vData.assign(vData.size(), 0); | ||||
isFull = false; | isFull = false; | ||||
isEmpty = true; | isEmpty = true; | ||||
} | } | ||||
void CBloomFilter::reset(uint32_t nNewTweak) { | void CBloomFilter::reset(const uint32_t nNewTweak) { | ||||
clear(); | clear(); | ||||
nTweak = nNewTweak; | nTweak = nNewTweak; | ||||
} | } | ||||
bool CBloomFilter::IsWithinSizeConstraints() const { | bool CBloomFilter::IsWithinSizeConstraints() const { | ||||
return vData.size() <= MAX_BLOOM_FILTER_SIZE && | return vData.size() <= MAX_BLOOM_FILTER_SIZE && | ||||
nHashFuncs <= MAX_HASH_FUNCS; | nHashFuncs <= MAX_HASH_FUNCS; | ||||
} | } | ||||
▲ Show 20 Lines • Show All 85 Lines • ▼ Show 20 Lines | void CBloomFilter::UpdateEmptyFull() { | ||||
for (const auto d : vData) { | for (const auto d : vData) { | ||||
full &= (d == 0xff); | full &= (d == 0xff); | ||||
empty &= (d == 0); | empty &= (d == 0); | ||||
} | } | ||||
isFull = full; | isFull = full; | ||||
isEmpty = empty; | isEmpty = empty; | ||||
} | } | ||||
CRollingBloomFilter::CRollingBloomFilter(uint32_t nElements, double fpRate) { | CRollingBloomFilter::CRollingBloomFilter(const uint32_t nElements, | ||||
const double fpRate) { | |||||
double logFpRate = log(fpRate); | double logFpRate = log(fpRate); | ||||
/* The optimal number of hash functions is log(fpRate) / log(0.5), but | /* The optimal number of hash functions is log(fpRate) / log(0.5), but | ||||
* restrict it to the range 1-50. */ | * restrict it to the range 1-50. */ | ||||
nHashFuncs = std::max(1, std::min<int>(round(logFpRate / log(0.5)), 50)); | nHashFuncs = std::max(1, std::min<int>(round(logFpRate / log(0.5)), 50)); | ||||
/* In this rolling bloom filter, we'll store between 2 and 3 generations of | /* In this rolling bloom filter, we'll store between 2 and 3 generations of | ||||
* nElements / 2 entries. */ | * nElements / 2 entries. */ | ||||
nEntriesPerGeneration = (nElements + 1) / 2; | nEntriesPerGeneration = (nElements + 1) / 2; | ||||
uint32_t nMaxElements = nEntriesPerGeneration * 3; | uint32_t nMaxElements = nEntriesPerGeneration * 3; | ||||
▲ Show 20 Lines • Show All 97 Lines • Show Last 20 Lines |