1  // Copyright (c) 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 <boost/test/unit_test.hpp>
 6  
 7  #include <chain.h>
 8  #include <test/util/setup_common.h>
 9  
10  #include <memory>
11  
12  BOOST_FIXTURE_TEST_SUITE(chain_tests, BasicTestingSetup)
13  
14  namespace {
15  
16  const CBlockIndex* NaiveGetAncestor(const CBlockIndex* a, int height)
17  {
18      while (a->nHeight > height) {
19          a = a->pprev;
20      }
21      BOOST_REQUIRE_EQUAL(a->nHeight, height);
22      return a;
23  }
24  
25  const CBlockIndex* NaiveLastCommonAncestor(const CBlockIndex* a, const CBlockIndex* b)
26  {
27      while (a->nHeight > b->nHeight) {
28          a = a->pprev;
29      }
30      while (b->nHeight > a->nHeight) {
31          b = b->pprev;
32      }
33      while (a != b) {
34          BOOST_REQUIRE_EQUAL(a->nHeight, b->nHeight);
35          a = a->pprev;
36          b = b->pprev;
37      }
38      BOOST_REQUIRE_EQUAL(a, b);
39      return a;
40  }
41  
42  } // namespace
43  
44  BOOST_AUTO_TEST_CASE(chain_test)
45  {
46      FastRandomContext ctx;
47      std::vector<std::unique_ptr<CBlockIndex>> block_index;
48      // Run 10 iterations of the whole test.
49      for (int i = 0; i < 10; ++i) {
50          block_index.clear();
51          // Create genesis block.
52          auto genesis = std::make_unique<CBlockIndex>();
53          genesis->nHeight = 0;
54          block_index.push_back(std::move(genesis));
55          // Create 10000 more blocks.
56          for (int b = 0; b < 10000; ++b) {
57              auto new_index = std::make_unique<CBlockIndex>();
58              // 95% of blocks build on top of the last block; the others fork off randomly.
59              if (ctx.randrange(20) != 0) {
60                  new_index->pprev = block_index.back().get();
61              } else {
62                  new_index->pprev = block_index[ctx.randrange(block_index.size())].get();
63              }
64              new_index->nHeight = new_index->pprev->nHeight + 1;
65              new_index->BuildSkip();
66              block_index.push_back(std::move(new_index));
67          }
68          // Run 10000 random GetAncestor queries.
69          for (int q = 0; q < 10000; ++q) {
70              const CBlockIndex* block = block_index[ctx.randrange(block_index.size())].get();
71              unsigned height = ctx.randrange<unsigned>(block->nHeight + 1);
72              const CBlockIndex* result = block->GetAncestor(height);
73              BOOST_CHECK(result == NaiveGetAncestor(block, height));
74          }
75          // Run 10000 random LastCommonAncestor queries.
76          for (int q = 0; q < 10000; ++q) {
77              const CBlockIndex* block1 = block_index[ctx.randrange(block_index.size())].get();
78              const CBlockIndex* block2 = block_index[ctx.randrange(block_index.size())].get();
79              const CBlockIndex* result = LastCommonAncestor(block1, block2);
80              BOOST_CHECK(result == NaiveLastCommonAncestor(block1, block2));
81          }
82      }
83  }
84  
85  BOOST_AUTO_TEST_SUITE_END()