Inside Bitcoin
Opening the selected file…
Inside Bitcoin
Opening the selected file…
The code behind the network, with room to understand it.
Release published 2026-10-28 · Snapshot fetched 2026-11-01. Latest stable release at fetch time; development branches and Git history are excluded. Only the selected code window and visible folders load here.
251} else {252// Append diff - total_size holes at the end, plus the new transaction.253total_size = diff;254reordering.push_back(total_size++);255}256} else {257// In case total_size == SetType::Size, it is not possible to insert the new258// transaction without exceeding SetType's size. Instead, interpret diff as an259// index into the holes, and overwrite a position there. This branch is never used260// when deserializing the output of the serializer, but gives meaning to otherwise261// invalid input.262diff %= (SetType::Size() - reordering.size());263SetType holes = SetType::Fill(SetType::Size());264for (auto pos : reordering) holes.Reset(pos);265for (auto pos : holes) {266if (diff == 0) {267reordering.push_back(pos);268break;269}270--diff;271}272}273// Stop if a read error was encountered during deserialization.274if (read_error) break;275}277// Construct the original cluster order depgraph.278depgraph = DepGraph(topo_depgraph, reordering, total_size);279}280};282/** Perform a sanity/consistency check on a DepGraph. */283template<typename SetType>284void SanityCheck(const DepGraph<SetType>& depgraph)285{286// Verify Positions and PositionRange consistency.287DepGraphIndex num_positions{0};288DepGraphIndex position_range{0};289for (DepGraphIndex i : depgraph.Positions()) {290++num_positions;291position_range = i + 1;292}293assert(num_positions == depgraph.TxCount());294assert(position_range == depgraph.PositionRange());295assert(position_range >= num_positions);296assert(position_range <= SetType::Size());297// Consistency check between ancestors internally.298for (DepGraphIndex i : depgraph.Positions()) {299// Transactions include themselves as ancestors.300assert(depgraph.Ancestors(i)[i]);301// If a is an ancestor of b, then b's ancestors must include all of a's ancestors.302for (auto a : depgraph.Ancestors(i)) {303assert(depgraph.Ancestors(i).IsSupersetOf(depgraph.Ancestors(a)));304}305}306// Consistency check between ancestors and descendants.307for (DepGraphIndex i : depgraph.Positions()) {308for (DepGraphIndex j : depgraph.Positions()) {309assert(depgraph.Ancestors(i)[j] == depgraph.Descendants(j)[i]);310}311// No transaction is a parent or child of itself.312auto parents = depgraph.GetReducedParents(i);313auto children = depgraph.GetReducedChildren(i);314assert(!parents[i]);315assert(!children[i]);316// Parents of a transaction do not have ancestors inside those parents (except itself).317// Note that even the transaction itself may be missing (if it is part of a cycle).318for (auto parent : parents) {319assert((depgraph.Ancestors(parent) & parents).IsSubsetOf(SetType::Singleton(parent)));320}321// Similar for children and descendants.322for (auto child : children) {323assert((depgraph.Descendants(child) & children).IsSubsetOf(SetType::Singleton(child)));324}325}326if (depgraph.IsAcyclic()) {327// If DepGraph is acyclic, serialize + deserialize must roundtrip.328std::vector<unsigned char> ser;329VectorWriter writer(ser, 0);330writer << Using<DepGraphFormatter>(depgraph);331SpanReader reader(ser);332DepGraph<SetType> decoded_depgraph;333reader >> Using<DepGraphFormatter>(decoded_depgraph);334assert(depgraph == decoded_depgraph);335assert(reader.empty());336// It must also deserialize correctly without the terminal 0 byte (as the deserializer337// will upon EOF still return what it read so far).338assert(ser.size() >= 1 && ser.back() == 0);339ser.pop_back();340reader = SpanReader{ser};341decoded_depgraph = {};342reader >> Using<DepGraphFormatter>(decoded_depgraph);343assert(depgraph == decoded_depgraph);344assert(reader.empty());346// In acyclic graphs, the union of parents with parents of parents etc. yields the347// full ancestor set (and similar for children and descendants).348std::vector<SetType> parents(depgraph.PositionRange()), children(depgraph.PositionRange());349for (DepGraphIndex i : depgraph.Positions()) {350parents[i] = depgraph.GetReducedParents(i);351children[i] = depgraph.GetReducedChildren(i);352}353for (auto i : depgraph.Positions()) {354// Initialize the set of ancestors with just the current transaction itself.355SetType ancestors = SetType::Singleton(i);356// Iteratively add parents of all transactions in the ancestor set to itself.357while (true) {358const auto old_ancestors = ancestors;359for (auto j : ancestors) ancestors |= parents[j];360// Stop when no more changes are being made.361if (old_ancestors == ancestors) break;362}363assert(ancestors == depgraph.Ancestors(i));365// Initialize the set of descendants with just the current transaction itself.366SetType descendants = SetType::Singleton(i);367// Iteratively add children of all transactions in the descendant set to itself.368while (true) {369const auto old_descendants = descendants;370for (auto j : descendants) descendants |= children[j];371// Stop when no more changes are being made.372if (old_descendants == descendants) break;373}374assert(descendants == depgraph.Descendants(i));375}376}377}379/** Perform a sanity check on a linearization. */380template<typename SetType>381void SanityCheck(const DepGraph<SetType>& depgraph, std::span<const DepGraphIndex> linearization)382{383// Check completeness.384assert(linearization.size() == depgraph.TxCount());385SetType done;386for (auto i : linearization) {387// Check transaction position is in range.388assert(depgraph.Positions()[i]);389// Check topology and lack of duplicates.390assert((depgraph.Ancestors(i) - done) == SetType::Singleton(i));391done.Set(i);392}393}395inline uint64_t MaxOptimalLinearizationCost(DepGraphIndex cluster_count)396{397// These are the largest numbers seen returned as cost by Linearize(), in a large randomized398// trial. There exist almost certainly far worse cases, but they are unlikely to be399// encountered in randomized tests. The purpose of these numbers is guaranteeing that for400// *some* reasonable cost bound, optimal linearizations are always found.401static constexpr uint64_t COSTS[65] = {4020,4030, 545, 928, 1633, 2647, 4065, 5598, 8258,4049505, 11471, 14137, 19553, 20460, 26191, 28397, 32599,40541631, 47419, 56329, 57767, 72196, 63652, 95366, 96537,406115653, 125407, 131734, 145090, 156349, 164665, 194224, 203953,407207710, 225878, 239971, 252284, 256534, 222142, 251332, 357098,408325788, 295867, 410053, 497483, 533892, 576572, 577845, 572400,409592536, 455082, 609249, 659130, 714091, 544507, 718788, 562378,410601926, 1025081, 732725, 708896, 738224, 900445, 1092519, 1139946411};412assert(cluster_count < std::size(COSTS));413// Multiply the table number by two, to account for the fact that they are not absolutes.414return COSTS[cluster_count] * 2;415}417} // namespace cluster_linearize419#endif // BITCOIN_TEST_UTIL_CLUSTER_LINEARIZE_H
Independent explanations by MyBitcoinExplorer. Not affiliated with or endorsed by Bitcoin Core. Guides are educational and do not replace the source or its tests.
Bitcoin Core source © its contributors, distributed under the MIT license. Original notices and bundled third-party licenses are retained in the source tree.