Line data    Source code

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