Bitcoin Core 30.99.0
P2P Digital Currency
chain_tests.cpp
Go to the documentation of this file.
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>
9
10#include <memory>
11
13
14namespace {
15
16const 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
25const 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
45{
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
const CBlockIndex * LastCommonAncestor(const CBlockIndex *pa, const CBlockIndex *pb)
Find the last common ancestor two blocks have.
Definition: chain.cpp:161
BOOST_AUTO_TEST_CASE(chain_test)
Definition: chain_tests.cpp:44
The block chain is a tree shaped structure starting with the genesis block at the root,...
Definition: chain.h:141
CBlockIndex * pprev
pointer to the index of the predecessor of this block
Definition: chain.h:147
CBlockIndex * GetAncestor(int height)
Efficiently find an ancestor of this block.
Definition: chain.cpp:116
int nHeight
height of the entry in the chain. The genesis block has height 0
Definition: chain.h:153
Fast randomness source.
Definition: random.h:386
I randrange(I range) noexcept
Generate a random integer in the range [0..range), with range > 0.
Definition: random.h:254
BOOST_FIXTURE_TEST_SUITE(cuckoocache_tests, BasicTestingSetup)
Test Suite for CuckooCache.
BOOST_AUTO_TEST_SUITE_END()
#define BOOST_CHECK(expr)
Definition: object.cpp:17
Basic testing setup.
Definition: setup_common.h:64