aboutsummaryrefslogtreecommitdiff
path: root/src/bloom.h
diff options
context:
space:
mode:
authorGavin Andresen <gavinandresen@gmail.com>2015-04-24 13:14:45 -0400
committerPieter Wuille <pieter.wuille@gmail.com>2015-04-30 07:58:29 -0700
commit69a5f8be0abda1e462f8ef44acadd2cbfaa850fb (patch)
tree0369fcb002ab0d63aba1522b151ff89248c44818 /src/bloom.h
parent8a10000222cb49eb253b41802ecf312adaf79439 (diff)
Rolling bloom filter class
For when you need to keep track of the last N items you've seen, and can tolerate some false-positives. Rebased-by: Pieter Wuille <pieter.wuille@gmail.com>
Diffstat (limited to 'src/bloom.h')
-rw-r--r--src/bloom.h28
1 files changed, 28 insertions, 0 deletions
diff --git a/src/bloom.h b/src/bloom.h
index 191ffa19b3..7bab379a39 100644
--- a/src/bloom.h
+++ b/src/bloom.h
@@ -53,6 +53,10 @@ private:
unsigned int Hash(unsigned int nHashNum, const std::vector<unsigned char>& vDataToHash) const;
+ // Private constructor for CRollingBloomFilter, no restrictions on size
+ CBloomFilter(unsigned int nElements, double nFPRate, unsigned int nTweak);
+ friend class CRollingBloomFilter;
+
public:
/**
* Creates a new bloom filter which will provide the given fp rate when filled with the given number of elements
@@ -97,4 +101,28 @@ public:
void UpdateEmptyFull();
};
+/**
+ * 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.
+ *
+ * contains(item) will always return true if item was one of the last N things
+ * insert()'ed ... but may also return true for items that were not inserted.
+ */
+class CRollingBloomFilter
+{
+public:
+ CRollingBloomFilter(unsigned int nElements, double nFPRate, unsigned int nTweak);
+
+ void insert(const std::vector<unsigned char>& vKey);
+ bool contains(const std::vector<unsigned char>& vKey) const;
+
+ void clear();
+
+private:
+ unsigned int nBloomSize;
+ unsigned int nInsertions;
+ CBloomFilter b1, b2;
+};
+
+
#endif // BITCOIN_BLOOM_H