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, 78 insertions, 0 deletions

diff --git a/src/test/bloom_tests.cpp b/src/test/bloom_tests.cpp
index 73a146f05..1bda8a7ea 100644
--- a/src/test/bloom_tests.cpp
+++ b/src/test/bloom_tests.cpp
@@ -8,6 +8,7 @@
 #include "clientversion.h"
 #include "key.h"
 #include "merkleblock.h"
+#include "random.h"
 #include "serialize.h"
 #include "streams.h"
 #include "uint256.h"
@@ -459,4 +460,81 @@ BOOST_AUTO_TEST_CASE(merkle_block_4_test_update_none)
     BOOST_CHECK(!filter.contains(COutPoint(uint256S("0x02981fa052f0481dbc5868f4fc2166035a10f27a03cfd2de67326471df5bc041"), 0)));
 }
 
+static std::vector<unsigned char> RandomData()
+{
+    uint256 r = GetRandHash();
+    return std::vector<unsigned char>(r.begin(), r.end());
+}
+
+BOOST_AUTO_TEST_CASE(rolling_bloom)
+{
+    // last-100-entry, 1% false positive:
+    CRollingBloomFilter rb1(100, 0.01, 0);
+
+    // Overfill:
+    static const int DATASIZE=399;
+    std::vector<unsigned char> data[DATASIZE];
+    for (int i = 0; i < DATASIZE; i++) {
+        data[i] = RandomData();
+        rb1.insert(data[i]);
+    }
+    // Last 100 guaranteed to be remembered:
+    for (int i = 299; i < DATASIZE; i++) {
+        BOOST_CHECK(rb1.contains(data[i]));
+    }
+
+    // false positive rate is 1%, so we should get about 100 hits if
+    // testing 10,000 random keys. We get worst-case false positive
+    // behavior when the filter is as full as possible, which is
+    // when we've inserted one minus an integer multiple of nElement*2.
+    unsigned int nHits = 0;
+    for (int i = 0; i < 10000; i++) {
+        if (rb1.contains(RandomData()))
+            ++nHits;
+    }
+    // Run test_bitcoin with --log_level=message to see BOOST_TEST_MESSAGEs:
+    BOOST_TEST_MESSAGE("RollingBloomFilter got " << nHits << " false positives (~100 expected)");
+
+    // Insanely unlikely to get a fp count outside this range:
+    BOOST_CHECK(nHits > 25);
+    BOOST_CHECK(nHits < 175);
+
+    BOOST_CHECK(rb1.contains(data[DATASIZE-1]));
+    rb1.clear();
+    BOOST_CHECK(!rb1.contains(data[DATASIZE-1]));
+
+    // Now roll through data, make sure last 100 entries
+    // are always remembered:
+    for (int i = 0; i < DATASIZE; i++) {
+        if (i >= 100)
+            BOOST_CHECK(rb1.contains(data[i-100]));
+        rb1.insert(data[i]);
+    }
+
+    // Insert 999 more random entries:
+    for (int i = 0; i < 999; i++) {
+        rb1.insert(RandomData());
+    }
+    // Sanity check to make sure the filter isn't just filling up:
+    nHits = 0;
+    for (int i = 0; i < DATASIZE; i++) {
+        if (rb1.contains(data[i]))
+            ++nHits;
+    }
+    // Expect about 5 false positives, more than 100 means
+    // something is definitely broken.
+    BOOST_TEST_MESSAGE("RollingBloomFilter got " << nHits << " false positives (~5 expected)");
+    BOOST_CHECK(nHits < 100);
+
+    // last-1000-entry, 0.01% false positive:
+    CRollingBloomFilter rb2(1000, 0.001, 0);
+    for (int i = 0; i < DATASIZE; i++) {
+        rb2.insert(data[i]);
+    }
+    // ... room for all of them:
+    for (int i = 0; i < DATASIZE; i++) {
+        BOOST_CHECK(rb2.contains(data[i]));
+    }
+}
+
 BOOST_AUTO_TEST_SUITE_END()