Add mruset and use it for setInventoryKnown

4 files changed, 157 insertions, 1 deletions

diff --git a/bitcoin-qt.pro b/bitcoin-qt.pro
index 933f4a70da..04388fc4b0 100644
--- a/bitcoin-qt.pro
+++ b/bitcoin-qt.pro
@@ -118,6 +118,7 @@ HEADERS += src/qt/bitcoingui.h \
     src/init.h \
     src/headers.h \
     src/irc.h \
+    src/mruset.h \
     src/json/json_spirit_writer_template.h \
     src/json/json_spirit_writer.h \
     src/json/json_spirit_value.h \
diff --git a/src/mruset.h b/src/mruset.h
new file mode 100644
index 0000000000..0cf65853c4
--- /dev/null
+++ b/src/mruset.h
@@ -0,0 +1,63 @@
+// Copyright (c) 2012 The Bitcoin developers
+// Distributed under the MIT/X11 software license, see the accompanying
+// file license.txt or http://www.opensource.org/licenses/mit-license.php.
+#ifndef BITCOIN_MRUSET_H
+#define BITCOIN_MRUSET_H
+
+#include <set>
+#include <deque>
+
+template <typename T> class mruset
+{
+public:
+    typedef T key_type;
+    typedef T value_type;
+    typedef typename std::set<T>::iterator iterator;
+    typedef typename std::set<T>::const_iterator const_iterator;
+    typedef typename std::set<T>::size_type size_type;
+
+protected:
+    std::set<T> set;
+    std::deque<T> queue;
+    size_type nMaxSize;
+
+public:
+    mruset(size_type nMaxSizeIn = 0) { nMaxSize = nMaxSizeIn; }
+    iterator begin() const { return set.begin(); }
+    iterator end() const { return set.end(); }
+    size_type size() const { return set.size(); }
+    bool empty() const { return set.empty(); }
+    iterator find(const key_type& k) const { return set.find(k); }
+    size_type count(const key_type& k) const { return set.count(k); }
+    bool inline friend operator==(const mruset<T>& a, const mruset<T>& b) { return a.set == b.set; }
+    bool inline friend operator==(const mruset<T>& a, const std::set<T>& b) { return a.set == b; }
+    bool inline friend operator<(const mruset<T>& a, const mruset<T>& b) { return a.set < b.set; }
+    std::pair<iterator, bool> insert(const key_type& x)
+    {
+        std::pair<iterator, bool> ret = set.insert(x);
+        if (ret.second)
+        {
+            if (nMaxSize && queue.size() == nMaxSize)
+            {
+                set.erase(queue.front());
+                queue.pop_front();
+            }
+            queue.push_back(x);
+        }
+        return ret;
+    }
+    size_type max_size() const { return nMaxSize; }
+    size_type max_size(size_type s)
+    {
+        if (s)
+            while (queue.size() >= s)
+            {
+                set.erase(queue.front());
+                queue.pop_front();
+            }
+        nMaxSize = s;
+        return nMaxSize;
+    }
+};
+
+#endif
diff --git a/src/net.h b/src/net.h
index 51a816d4d3..d3e10f5a89 100644
--- a/src/net.h
+++ b/src/net.h
@@ -14,6 +14,7 @@
 #include <arpa/inet.h>
 #endif
 
+#include "mruset.h"
 #include "netbase.h"
 #include "protocol.h"
 
@@ -154,7 +155,7 @@ public:
     std::set<uint256> setKnown;
 
     // inventory based relay
-    std::set<CInv> setInventoryKnown;
+    mruset<CInv> setInventoryKnown;
     std::vector<CInv> vInventoryToSend;
     CCriticalSection cs_inventory;
     std::multimap<int64, CInv> mapAskFor;
@@ -193,6 +194,7 @@ public:
         fGetAddr = false;
         vfSubscribe.assign(256, false);
         nMisbehavior = 0;
+        setInventoryKnown.max_size(SendBufferSize() / 1000);
 
         // Be shy and don't send version until we hear
         if (!fInbound)
diff --git a/src/test/mruset_tests.cpp b/src/test/mruset_tests.cpp
new file mode 100644
index 0000000000..ca5a1f1b12
--- /dev/null
+++ b/src/test/mruset_tests.cpp
@@ -0,0 +1,90 @@
+#include <boost/test/unit_test.hpp>
+
+using namespace std;
+
+#include "mruset.h"
+#include "util.h"
+
+#define NUM_TESTS 16
+#define MAX_SIZE 100
+
+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_AUTO_TEST_SUITE(mruset_tests)
+
+// 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)
+{
+    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);
+        }
+    }
+}
+
+// 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 duplcate 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()