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)

2 files changed, 132 insertions, 72 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()
diff --git a/src/test/mruset_tests.cpp b/src/test/mruset_tests.cpp
index bd4e9c1d3..2b68f8899 100644
--- a/src/test/mruset_tests.cpp
+++ b/src/test/mruset_tests.cpp
@@ -17,83 +17,65 @@
 
 using namespace std;
 
-class mrutester
-{
-private:
-    mruset<int> mru;
-    std::set<int> set;
-
-public:
-    mrutester() { mru.max_size(MAX_SIZE); }
-    int size() const { return set.size(); }
-
-    void insert(int n)
-    {
-        mru.insert(n);
-        set.insert(n);
-        BOOST_CHECK(mru == set);
-    }
-};
-
 BOOST_FIXTURE_TEST_SUITE(mruset_tests, BasicTestingSetup)
 
-// Test that an mruset behaves like a set, as long as no more than MAX_SIZE elements are in it
-BOOST_AUTO_TEST_CASE(mruset_like_set)
-{
-
-    for (int nTest=0; nTest<NUM_TESTS; nTest++)
-    {
-        mrutester tester;
-        while (tester.size() < MAX_SIZE)
-            tester.insert(GetRandInt(2 * MAX_SIZE));
-    }
-
-}
-
-// Test that an mruset's size never exceeds its max_size
-BOOST_AUTO_TEST_CASE(mruset_limited_size)
+BOOST_AUTO_TEST_CASE(mruset_test)
 {
-    for (int nTest=0; nTest<NUM_TESTS; nTest++)
-    {
-        mruset<int> mru(MAX_SIZE);
-        for (int nAction=0; nAction<3*MAX_SIZE; nAction++)
-        {
-            int n = GetRandInt(2 * MAX_SIZE);
-            mru.insert(n);
-            BOOST_CHECK(mru.size() <= MAX_SIZE);
+    // The mruset being tested.
+    mruset<int> mru(5000);
+
+    // Run the test 10 times.
+    for (int test = 0; test < 10; test++) {
+        // Reset mru.
+        mru.clear();
+
+        // A deque + set to simulate the mruset.
+        std::deque<int> rep;
+        std::set<int> all;
+
+        // Insert 10000 random integers below 15000.
+        for (int j=0; j<10000; j++) {
+            int add = GetRandInt(15000);
+            mru.insert(add);
+
+            // Add the number to rep/all as well.
+            if (all.count(add) == 0) {
+               all.insert(add);
+               rep.push_back(add);
+               if (all.size() == 5001) {
+                   all.erase(rep.front());
+                   rep.pop_front();
+               }
+            }
+
+            // Do a full comparison between mru and the simulated mru every 1000 and every 5001 elements.
+            if (j % 1000 == 0 || j % 5001 == 0) {
+                mruset<int> mru2 = mru; // Also try making a copy
+
+                // Check that all elements that should be in there, are in there.
+                BOOST_FOREACH(int x, rep) {
+                    BOOST_CHECK(mru.count(x));
+                    BOOST_CHECK(mru2.count(x));
+                }
+
+                // Check that all elements that are in there, should be in there.
+                BOOST_FOREACH(int x, mru) {
+                    BOOST_CHECK(all.count(x));
+                }
+
+                // Check that all elements that are in there, should be in there.
+                BOOST_FOREACH(int x, mru2) {
+                    BOOST_CHECK(all.count(x));
+                }
+
+                for (int t = 0; t < 10; t++) {
+                    int r = GetRandInt(15000);
+                    BOOST_CHECK(all.count(r) == mru.count(r));
+                    BOOST_CHECK(all.count(r) == mru2.count(r));
+                }
+            }
         }
     }
 }
 
-// 16-bit permutation function
-int static permute(int n)
-{
-    // hexadecimals of pi; verified to be linearly independent
-    static const int table[16] = {0x243F, 0x6A88, 0x85A3, 0x08D3, 0x1319, 0x8A2E, 0x0370, 0x7344,
-                                  0xA409, 0x3822, 0x299F, 0x31D0, 0x082E, 0xFA98, 0xEC4E, 0x6C89};
-
-    int ret = 0;
-    for (int bit=0; bit<16; bit++)
-         if (n & (1<<bit))
-             ret ^= table[bit];
-
-    return ret;
-}
-
-// Test that an mruset acts like a moving window, if no duplicate elements are added
-BOOST_AUTO_TEST_CASE(mruset_window)
-{
-    mruset<int> mru(MAX_SIZE);
-    for (int n=0; n<10*MAX_SIZE; n++)
-    {
-        mru.insert(permute(n));
-
-        set<int> tester;
-        for (int m=max(0,n-MAX_SIZE+1); m<=n; m++)
-            tester.insert(permute(m));
-
-        BOOST_CHECK(mru == tester);
-    }
-}
-
 BOOST_AUTO_TEST_SUITE_END()