Changeset View
Changeset View
Standalone View
Standalone View
src/bloom.h
Show First 20 Lines • Show All 49 Lines • ▼ Show 20 Lines | private: | ||||
uint32_t nHashFuncs; | uint32_t nHashFuncs; | ||||
uint32_t nTweak; | uint32_t nTweak; | ||||
uint8_t nFlags; | uint8_t nFlags; | ||||
uint32_t Hash(uint32_t nHashNum, | uint32_t Hash(uint32_t nHashNum, | ||||
const std::vector<uint8_t> &vDataToHash) const; | const std::vector<uint8_t> &vDataToHash) const; | ||||
// Private constructor for CRollingBloomFilter, no restrictions on size | // Private constructor for CRollingBloomFilter, no restrictions on size | ||||
CBloomFilter(uint32_t nElements, double nFPRate, uint32_t nTweak); | CBloomFilter(const uint32_t nElements, const double nFPRate, | ||||
const uint32_t nTweak); | |||||
friend class CRollingBloomFilter; | friend class CRollingBloomFilter; | ||||
public: | public: | ||||
/** | /** | ||||
* Creates a new bloom filter which will provide the given fp rate when | * Creates a new bloom filter which will provide the given fp rate when | ||||
* filled with the given number of elements. Note that if the given | * filled with the given number of elements. Note that if the given | ||||
* parameters will result in a filter outside the bounds of the protocol | * parameters will result in a filter outside the bounds of the protocol | ||||
* limits, the filter created will be as close to the given parameters as | * limits, the filter created will be as close to the given parameters as | ||||
* possible within the protocol limits. This will apply if nFPRate is very | * possible within the protocol limits. This will apply if nFPRate is very | ||||
* low or nElements is unreasonably high. nTweak is a constant which is | * low or nElements is unreasonably high. nTweak is a constant which is | ||||
* added to the seed value passed to the hash function. It should generally | * added to the seed value passed to the hash function. It should generally | ||||
* always be a random value (and is largely only exposed for unit testing) | * always be a random value (and is largely only exposed for unit testing) | ||||
* nFlags should be one of the BLOOM_UPDATE_* enums (not _MASK) | * nFlags should be one of the BLOOM_UPDATE_* enums (not _MASK) | ||||
*/ | */ | ||||
CBloomFilter(uint32_t nElements, double nFPRate, uint32_t nTweak, | CBloomFilter(const uint32_t nElements, const double nFPRate, | ||||
uint8_t nFlagsIn); | const uint32_t nTweak, uint8_t nFlagsIn); | ||||
CBloomFilter() | CBloomFilter() | ||||
: isFull(true), isEmpty(false), nHashFuncs(0), nTweak(0), nFlags(0) {} | : isFull(true), isEmpty(false), nHashFuncs(0), nTweak(0), nFlags(0) {} | ||||
ADD_SERIALIZE_METHODS; | ADD_SERIALIZE_METHODS; | ||||
template <typename Stream, typename Operation> | template <typename Stream, typename Operation> | ||||
inline void SerializationOp(Stream &s, Operation ser_action) { | inline void SerializationOp(Stream &s, Operation ser_action) { | ||||
READWRITE(vData); | READWRITE(vData); | ||||
READWRITE(nHashFuncs); | READWRITE(nHashFuncs); | ||||
READWRITE(nTweak); | READWRITE(nTweak); | ||||
READWRITE(nFlags); | READWRITE(nFlags); | ||||
} | } | ||||
void insert(const std::vector<uint8_t> &vKey); | void insert(const std::vector<uint8_t> &vKey); | ||||
void insert(const COutPoint &outpoint); | void insert(const COutPoint &outpoint); | ||||
void insert(const uint256 &hash); | void insert(const uint256 &hash); | ||||
bool contains(const std::vector<uint8_t> &vKey) const; | bool contains(const std::vector<uint8_t> &vKey) const; | ||||
bool contains(const COutPoint &outpoint) const; | bool contains(const COutPoint &outpoint) const; | ||||
bool contains(const uint256 &hash) const; | bool contains(const uint256 &hash) const; | ||||
void clear(); | void clear(); | ||||
void reset(uint32_t nNewTweak); | void reset(const uint32_t nNewTweak); | ||||
//! True if the size is <= MAX_BLOOM_FILTER_SIZE and the number of hash | //! True if the size is <= MAX_BLOOM_FILTER_SIZE and the number of hash | ||||
//! functions is <= MAX_HASH_FUNCS (catch a filter which was just | //! functions is <= MAX_HASH_FUNCS (catch a filter which was just | ||||
//! deserialized which was too big) | //! deserialized which was too big) | ||||
bool IsWithinSizeConstraints() const; | bool IsWithinSizeConstraints() const; | ||||
//! Scans output scripts for matches and adds those outpoints to the filter | //! Scans output scripts for matches and adds those outpoints to the filter | ||||
//! for spend detection. Returns true if any output matched, or the txid | //! for spend detection. Returns true if any output matched, or the txid | ||||
Show All 29 Lines | |||||
* It needs around 1.8 bytes per element per factor 0.1 of false positive rate. | * 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) | * (More accurately: 3/(log(256)*log(2)) * log(1/fpRate) * nElements bytes) | ||||
*/ | */ | ||||
class CRollingBloomFilter { | class CRollingBloomFilter { | ||||
public: | public: | ||||
// A random bloom filter calls GetRand() at creation time. Don't create | // A random bloom filter calls GetRand() at creation time. Don't create | ||||
// global CRollingBloomFilter objects, as they may be constructed before the | // global CRollingBloomFilter objects, as they may be constructed before the | ||||
// randomizer is properly initialized. | // randomizer is properly initialized. | ||||
CRollingBloomFilter(uint32_t nElements, double nFPRate); | CRollingBloomFilter(const uint32_t nElements, const double nFPRate); | ||||
void insert(const std::vector<uint8_t> &vKey); | void insert(const std::vector<uint8_t> &vKey); | ||||
void insert(const uint256 &hash); | void insert(const uint256 &hash); | ||||
bool contains(const std::vector<uint8_t> &vKey) const; | bool contains(const std::vector<uint8_t> &vKey) const; | ||||
bool contains(const uint256 &hash) const; | bool contains(const uint256 &hash) const; | ||||
void reset(); | void reset(); | ||||
Show All 10 Lines |