src/test/skiplist_tests.cpp

   1 // Copyright (c) 2014-2016 The Bitcoin Core developers
   2 // Distributed under the MIT software license, see the accompanying
   3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
   4
   5 #include "chain.h"
   6 #include "util.h"
   7 #include "test/test_bitcoin.h"
   8 #include "test/test_random.h"
   9
  10 #include <vector>
  11
  12 #include <boost/test/unit_test.hpp>
  13
  14 #define SKIPLIST_LENGTH 300000
  15
  16 BOOST_FIXTURE_TEST_SUITE(skiplist_tests, BasicTestingSetup)
  17
  18 BOOST_AUTO_TEST_CASE(skiplist_test)
  19 {
  20     std::vector<CBlockIndex> vIndex(SKIPLIST_LENGTH);
  21
  22     for (int i=0; i<SKIPLIST_LENGTH; i++) {
  23         vIndex[i].nHeight = i;
  24         vIndex[i].pprev = (i == 0) ? NULL : &vIndex[i - 1];
  25         vIndex[i].BuildSkip();
  26     }
  27
  28     for (int i=0; i<SKIPLIST_LENGTH; i++) {
  29         if (i > 0) {
  30             BOOST_CHECK(vIndex[i].pskip == &vIndex[vIndex[i].pskip->nHeight]);
  31             BOOST_CHECK(vIndex[i].pskip->nHeight < i);
  32         } else {
  33             BOOST_CHECK(vIndex[i].pskip == NULL);
  34         }
  35     }
  36
  37     for (int i=0; i < 1000; i++) {
  38         int from = insecure_rand() % (SKIPLIST_LENGTH - 1);
  39         int to = insecure_rand() % (from + 1);
  40
  41         BOOST_CHECK(vIndex[SKIPLIST_LENGTH - 1].GetAncestor(from) == &vIndex[from]);
  42         BOOST_CHECK(vIndex[from].GetAncestor(to) == &vIndex[to]);
  43         BOOST_CHECK(vIndex[from].GetAncestor(0) == &vIndex[0]);
  44     }
  45 }
  46
  47 BOOST_AUTO_TEST_CASE(getlocator_test)
  48 {
  49     // Build a main chain 100000 blocks long.
  50     std::vector<uint256> vHashMain(100000);
  51     std::vector<CBlockIndex> vBlocksMain(100000);
  52     for (unsigned int i=0; i<vBlocksMain.size(); i++) {
  53         vHashMain[i] = ArithToUint256(i); // Set the hash equal to the height, so we can quickly check the distances.
  54         vBlocksMain[i].nHeight = i;
  55         vBlocksMain[i].pprev = i ? &vBlocksMain[i - 1] : NULL;
  56         vBlocksMain[i].phashBlock = &vHashMain[i];
  57         vBlocksMain[i].BuildSkip();
  58         BOOST_CHECK_EQUAL((int)UintToArith256(vBlocksMain[i].GetBlockHash()).GetLow64(), vBlocksMain[i].nHeight);
  59         BOOST_CHECK(vBlocksMain[i].pprev == NULL || vBlocksMain[i].nHeight == vBlocksMain[i].pprev->nHeight + 1);
  60     }
  61
  62     // Build a branch that splits off at block 49999, 50000 blocks long.
  63     std::vector<uint256> vHashSide(50000);
  64     std::vector<CBlockIndex> vBlocksSide(50000);
  65     for (unsigned int i=0; i<vBlocksSide.size(); i++) {
  66         vHashSide[i] = ArithToUint256(i + 50000 + (arith_uint256(1) << 128)); // Add 1<<128 to the hashes, so GetLow64() still returns the height.
  67         vBlocksSide[i].nHeight = i + 50000;
  68         vBlocksSide[i].pprev = i ? &vBlocksSide[i - 1] : &vBlocksMain[49999];
  69         vBlocksSide[i].phashBlock = &vHashSide[i];
  70         vBlocksSide[i].BuildSkip();
  71         BOOST_CHECK_EQUAL((int)UintToArith256(vBlocksSide[i].GetBlockHash()).GetLow64(), vBlocksSide[i].nHeight);
  72         BOOST_CHECK(vBlocksSide[i].pprev == NULL || vBlocksSide[i].nHeight == vBlocksSide[i].pprev->nHeight + 1);
  73     }
  74
  75     // Build a CChain for the main branch.
  76     CChain chain;
  77     chain.SetTip(&vBlocksMain.back());
  78
  79     // Test 100 random starting points for locators.
  80     for (int n=0; n<100; n++) {
  81         int r = insecure_rand() % 150000;
  82         CBlockIndex* tip = (r < 100000) ? &vBlocksMain[r] : &vBlocksSide[r - 100000];
  83         CBlockLocator locator = chain.GetLocator(tip);
  84
  85         // The first result must be the block itself, the last one must be genesis.
  86         BOOST_CHECK(locator.vHave.front() == tip->GetBlockHash());
  87         BOOST_CHECK(locator.vHave.back() == vBlocksMain[0].GetBlockHash());
  88
  89         // Entries 1 through 11 (inclusive) go back one step each.
  90         for (unsigned int i = 1; i < 12 && i < locator.vHave.size() - 1; i++) {
  91             BOOST_CHECK_EQUAL(UintToArith256(locator.vHave[i]).GetLow64(), tip->nHeight - i);
  92         }
  93
  94         // The further ones (excluding the last one) go back with exponential steps.
  95         unsigned int dist = 2;
  96         for (unsigned int i = 12; i < locator.vHave.size() - 1; i++) {
  97             BOOST_CHECK_EQUAL(UintToArith256(locator.vHave[i - 1]).GetLow64() - UintToArith256(locator.vHave[i]).GetLow64(), dist);
  98             dist *= 2;
  99         }
 100     }
 101 }
 102
 103 BOOST_AUTO_TEST_CASE(findearliestatleast_test)
 104 {
 105     std::vector<uint256> vHashMain(100000);
 106     std::vector<CBlockIndex> vBlocksMain(100000);
 107     for (unsigned int i=0; i<vBlocksMain.size(); i++) {
 108         vHashMain[i] = ArithToUint256(i); // Set the hash equal to the height
 109         vBlocksMain[i].nHeight = i;
 110         vBlocksMain[i].pprev = i ? &vBlocksMain[i - 1] : NULL;
 111         vBlocksMain[i].phashBlock = &vHashMain[i];
 112         vBlocksMain[i].BuildSkip();
 113         if (i < 10) {
 114             vBlocksMain[i].nTime = i;
 115             vBlocksMain[i].nTimeMax = i;
 116         } else {
 117             // randomly choose something in the range [MTP, MTP*2]
 118             int64_t medianTimePast = vBlocksMain[i].GetMedianTimePast();
 119             int r = insecure_rand() % medianTimePast;
 120             vBlocksMain[i].nTime = r + medianTimePast;
 121             vBlocksMain[i].nTimeMax = std::max(vBlocksMain[i].nTime, vBlocksMain[i-1].nTimeMax);
 122         }
 123     }
 124     // Check that we set nTimeMax up correctly.
 125     unsigned int curTimeMax = 0;
 126     for (unsigned int i=0; i<vBlocksMain.size(); ++i) {
 127         curTimeMax = std::max(curTimeMax, vBlocksMain[i].nTime);
 128         BOOST_CHECK(curTimeMax == vBlocksMain[i].nTimeMax);
 129     }
 130
 131     // Build a CChain for the main branch.
 132     CChain chain;
 133     chain.SetTip(&vBlocksMain.back());
 134
 135     // Verify that FindEarliestAtLeast is correct.
 136     for (unsigned int i=0; i<10000; ++i) {
 137         // Pick a random element in vBlocksMain.
 138         int r = insecure_rand() % vBlocksMain.size();
 139         int64_t test_time = vBlocksMain[r].nTime;
 140         CBlockIndex *ret = chain.FindEarliestAtLeast(test_time);
 141         BOOST_CHECK(ret->nTimeMax >= test_time);
 142         BOOST_CHECK((ret->pprev==NULL) || ret->pprev->nTimeMax < test_time);
 143         BOOST_CHECK(vBlocksMain[r].GetAncestor(ret->nHeight) == ret);
 144     }
 145 }
 146 BOOST_AUTO_TEST_SUITE_END()