diff options
| -rw-r--r-- | bitcoin-qt.pro | 1 | ||||
| -rw-r--r-- | src/mruset.h | 63 | ||||
| -rw-r--r-- | src/net.h | 4 | ||||
| -rw-r--r-- | src/test/mruset_tests.cpp | 90 |
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 @@ -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() |