diff options
Diffstat (limited to 'src/bloom.h')
| -rw-r--r-- | src/bloom.h | 28 |
1 files changed, 22 insertions, 6 deletions
diff --git a/src/bloom.h b/src/bloom.h index a4dba8cb4f..b0ad8b875d 100644 --- a/src/bloom.h +++ b/src/bloom.h @@ -1,4 +1,4 @@ -// Copyright (c) 2012-2014 The Bitcoin Core developers +// Copyright (c) 2012-2015 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. @@ -110,8 +110,11 @@ public: * 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 things + * 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) */ class CRollingBloomFilter { @@ -129,10 +132,23 @@ public: void reset(); private: - unsigned int nBloomSize; - unsigned int nInsertions; - CBloomFilter b1, b2; -}; + int nEntriesPerGeneration; + int nEntriesThisGeneration; + int nGeneration; + std::vector<uint32_t> data; + unsigned int nTweak; + int nHashFuncs; + + unsigned int Hash(unsigned int nHashNum, const std::vector<unsigned char>& vDataToHash) const; + inline int get(uint32_t position) const { + return (data[(position >> 4) % data.size()] >> (2 * (position & 0xF))) & 0x3; + } + + inline void put(uint32_t position, uint32_t val) { + uint32_t& cell = data[(position >> 4) % data.size()]; + cell = (cell & ~(((uint32_t)3) << (2 * (position & 0xF)))) | (val << (2 * (position & 0xF))); + } +}; #endif // BITCOIN_BLOOM_H |