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>

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