Merge pull request #6064

f46a680 Better mruset unit test (Pieter Wuille)
d4d5022 Use ring buffer of set iterators instead of deque of copies in mruset (Pieter Wuille)
d81cff3 Replace mruset setAddrKnown with CRollingBloomFilter addrKnown (Gavin Andresen)
69a5f8b Rolling bloom filter class (Gavin Andresen)

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