- fixes problem that one misconfigured or malicious node can mess up progress bar
- implementation in src/util.h
- testcase in src/test/util_tests.cpp
static CBigNum bnProofOfWorkLimit(~uint256(0) >> 32);
const int nTotalBlocksEstimate = 140700; // Conservative estimate of total nr of blocks on main chain
const int nInitialBlockThreshold = 120; // Regard blocks up until N-threshold as "initial download"
-int nMaxBlocksOfPeers = 0; // Amount of blocks that other nodes claim to have
CBlockIndex* pindexGenesisBlock = NULL;
int nBestHeight = -1;
CBigNum bnBestChainWork = 0;
CBlockIndex* pindexBest = NULL;
int64 nTimeBestReceived = 0;
+CMedianFilter<int> cPeerBlockCounts(5, 0); // Amount of blocks that other nodes claim to have
+
map<uint256, CBlock*> mapOrphanBlocks;
multimap<uint256, CBlock*> mapOrphanBlocksByPrev;
#endif
-
-
-
-
-
//////////////////////////////////////////////////////////////////////////////
//
// dispatching functions
// Return maximum amount of blocks that other nodes claim to have
int GetNumBlocksOfPeers()
{
- return std::max(nMaxBlocksOfPeers, GetTotalBlocksEstimate());
+ return std::max(cPeerBlockCounts.median(), GetTotalBlocksEstimate());
}
bool IsInitialBlockDownload()
pfrom->fSuccessfullyConnected = true;
printf("version message: version %d, blocks=%d\n", pfrom->nVersion, pfrom->nStartingHeight);
- if(pfrom->nStartingHeight > nMaxBlocksOfPeers)
- {
- nMaxBlocksOfPeers = pfrom->nStartingHeight;
- }
+
+ cPeerBlockCounts.input(pfrom->nStartingHeight);
}
--- /dev/null
+#include <vector>
+#include <boost/test/unit_test.hpp>
+#include <boost/foreach.hpp>
+
+#include "../util.h"
+
+using namespace std;
+
+BOOST_AUTO_TEST_SUITE(util_tests)
+
+BOOST_AUTO_TEST_CASE(util_MedianFilter)
+{
+ CMedianFilter<int> filter(5, 15);
+
+ BOOST_CHECK(filter.median() == 15);
+
+ filter.input(20); // [15 20]
+ BOOST_CHECK(filter.median() == 17);
+
+ filter.input(30); // [15 20 30]
+ BOOST_CHECK(filter.median() == 20);
+
+ filter.input(3); // [3 15 20 30]
+ BOOST_CHECK(filter.median() == 17);
+
+ filter.input(7); // [3 7 15 20 30]
+ BOOST_CHECK(filter.median() == 15);
+
+ filter.input(18); // [3 7 18 20 30]
+ BOOST_CHECK(filter.median() == 18);
+
+ filter.input(0); // [0 3 7 18 30]
+ BOOST_CHECK(filter.median() == 7);
+}
+
+BOOST_AUTO_TEST_SUITE_END()
}
+// Median filter over a stream of values
+// Returns the median of the last N numbers
+template <typename T> class CMedianFilter
+{
+private:
+ std::vector<T> vValues;
+ std::vector<T> vSorted;
+ int nSize;
+public:
+ CMedianFilter(int size, T initial_value):
+ nSize(size)
+ {
+ vValues.reserve(size);
+ vValues.push_back(initial_value);
+ vSorted = vValues;
+ }
+
+ void input(T value)
+ {
+ if(vValues.size() == nSize)
+ {
+ vValues.erase(vValues.begin());
+ }
+ vValues.push_back(value);
+
+ vSorted.resize(vValues.size());
+ std::copy(vValues.begin(), vValues.end(), vSorted.begin());
+ std::sort(vSorted.begin(), vSorted.end());
+ }
+
+ T median() const
+ {
+ int size = vSorted.size();
+ if(size & 1) // Odd number of elements
+ {
+ return vSorted[size/2];
+ }
+ else // Even number of elements
+ {
+ return (vSorted[size/2-1] + vSorted[size/2]) / 2;
+ }
+ }
+};
+