Line data    Source code

       1             : // Copyright (c) 2014 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 "random.h"
       7             : #include "util.h"
       8             : #include "test/test_bitcoin.h"
       9             : 
      10             : #include <vector>
      11             : 
      12             : #include <boost/test/unit_test.hpp>
      13             : 
      14             : #define SKIPLIST_LENGTH 300000
      15             : 
      16           1 : BOOST_FIXTURE_TEST_SUITE(skiplist_tests, BasicTestingSetup)
      17             : 
      18           6 : BOOST_AUTO_TEST_CASE(skiplist_test)
      19             : {
      20           2 :     std::vector<CBlockIndex> vIndex(SKIPLIST_LENGTH);
      21             : 
      22      300001 :     for (int i=0; i<SKIPLIST_LENGTH; i++) {
      23      600000 :         vIndex[i].nHeight = i;
      24      900000 :         vIndex[i].pprev = (i == 0) ? NULL : &vIndex[i - 1];
      25      300000 :         vIndex[i].BuildSkip();
      26             :     }
      27             : 
      28      300000 :     for (int i=0; i<SKIPLIST_LENGTH; i++) {
      29      300000 :         if (i > 0) {
      30     2999990 :             BOOST_CHECK(vIndex[i].pskip == &vIndex[vIndex[i].pskip->nHeight]);
      31     2699991 :             BOOST_CHECK(vIndex[i].pskip->nHeight < i);
      32             :         } else {
      33           9 :             BOOST_CHECK(vIndex[i].pskip == NULL);
      34             :         }
      35             :     }
      36             : 
      37        1000 :     for (int i=0; i < 1000; i++) {
      38        1000 :         int from = insecure_rand() % (SKIPLIST_LENGTH - 1);
      39        1000 :         int to = insecure_rand() % (from + 1);
      40             : 
      41       10000 :         BOOST_CHECK(vIndex[SKIPLIST_LENGTH - 1].GetAncestor(from) == &vIndex[from]);
      42        9000 :         BOOST_CHECK(vIndex[from].GetAncestor(to) == &vIndex[to]);
      43        9000 :         BOOST_CHECK(vIndex[from].GetAncestor(0) == &vIndex[0]);
      44             :     }
      45           1 : }
      46             : 
      47           6 : BOOST_AUTO_TEST_CASE(getlocator_test)
      48             : {
      49             :     // Build a main chain 100000 blocks long.
      50           2 :     std::vector<uint256> vHashMain(100000);
      51           2 :     std::vector<CBlockIndex> vBlocksMain(100000);
      52      200002 :     for (unsigned int i=0; i<vBlocksMain.size(); i++) {
      53      300000 :         vHashMain[i] = ArithToUint256(i); // Set the hash equal to the height, so we can quickly check the distances.
      54      200000 :         vBlocksMain[i].nHeight = i;
      55      200000 :         vBlocksMain[i].pprev = i ? &vBlocksMain[i - 1] : NULL;
      56      200000 :         vBlocksMain[i].phashBlock = &vHashMain[i];
      57      100000 :         vBlocksMain[i].BuildSkip();
      58      800000 :         BOOST_CHECK_EQUAL((int)UintToArith256(vBlocksMain[i].GetBlockHash()).GetLow64(), vBlocksMain[i].nHeight);
      59      900000 :         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           2 :     std::vector<uint256> vHashSide(50000);
      64           2 :     std::vector<CBlockIndex> vBlocksSide(50000);
      65      100002 :     for (unsigned int i=0; i<vBlocksSide.size(); i++) {
      66      200000 :         vHashSide[i] = ArithToUint256(i + 50000 + (arith_uint256(1) << 128)); // Add 1<<128 to the hashes, so GetLow64() still returns the height.
      67      100000 :         vBlocksSide[i].nHeight = i + 50000;
      68      100001 :         vBlocksSide[i].pprev = i ? &vBlocksSide[i - 1] : &vBlocksMain[49999];
      69      100000 :         vBlocksSide[i].phashBlock = &vHashSide[i];
      70       50000 :         vBlocksSide[i].BuildSkip();
      71      400000 :         BOOST_CHECK_EQUAL((int)UintToArith256(vBlocksSide[i].GetBlockHash()).GetLow64(), vBlocksSide[i].nHeight);
      72      450000 :         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           1 :     chain.SetTip(&vBlocksMain.back());
      78             : 
      79             :     // Test 100 random starting points for locators.
      80         100 :     for (int n=0; n<100; n++) {
      81         100 :         int r = insecure_rand() % 150000;
      82         233 :         CBlockIndex* tip = (r < 100000) ? &vBlocksMain[r] : &vBlocksSide[r - 100000];
      83         100 :         CBlockLocator locator = chain.GetLocator(tip);
      84             : 
      85             :         // The first result must be the block itself, the last one must be genesis.
      86        1000 :         BOOST_CHECK(locator.vHave.front() == tip->GetBlockHash());
      87        1000 :         BOOST_CHECK(locator.vHave.back() == vBlocksMain[0].GetBlockHash());
      88             : 
      89             :         // Entries 1 through 11 (inclusive) go back one step each.
      90        2200 :         for (unsigned int i = 1; i < 12 && i < locator.vHave.size() - 1; i++) {
      91        7700 :             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         100 :         unsigned int dist = 2;
      96        3042 :         for (unsigned int i = 12; i < locator.vHave.size() - 1; i++) {
      97       12789 :             BOOST_CHECK_EQUAL(UintToArith256(locator.vHave[i - 1]).GetLow64() - UintToArith256(locator.vHave[i]).GetLow64(), dist);
      98        1421 :             dist *= 2;
      99             :         }
     100             :     }
     101           1 : }
     102             : 
     103           3 : BOOST_AUTO_TEST_SUITE_END()