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