Inside Bitcoin

1001    // Pick an arbitrary Entry that occurs in this Cluster.
1002    const auto& entry = graph.m_entries[m_mapping[m_linearization.front()]];
1003    // See if there is a level whose Locator matches this Cluster, if so return that level.
1004    for (int level = 0; level < MAX_LEVELS; ++level) {
1005        if (entry.m_locator[level].cluster == this) return level;
1006    }
1007    // Given that we started with an Entry that occurs in this Cluster, one of its Locators must
1008    // point back to it.
1009    assert(false);
1010    return -1;
1011}
1012
1013int SingletonClusterImpl::GetLevel(const TxGraphImpl& graph) const noexcept
1014{
1015    // GetLevel() does not work for empty Clusters.
1016    if (!Assume(GetTxCount())) return -1;
1017
1018    // Get the Entry in this Cluster.
1019    const auto& entry = graph.m_entries[m_graph_index];
1020    // See if there is a level whose Locator matches this Cluster, if so return that level.
1021    for (int level = 0; level < MAX_LEVELS; ++level) {
1022        if (entry.m_locator[level].cluster == this) return level;
1023    }
1024    // Given that we started with an Entry that occurs in this Cluster, one of its Locators must
1025    // point back to it.
1026    assert(false);
1027    return -1;
1028}
1029
1030void TxGraphImpl::ClearLocator(int level, GraphIndex idx, bool oversized_tx) noexcept
1031{
1032    auto& entry = m_entries[idx];
1033    auto& clusterset = GetClusterSet(level);
1034    Assume(entry.m_locator[level].IsPresent());
1035    // Change the locator from Present to Missing or Removed.
1036    if (level == 0 || !entry.m_locator[level - 1].IsPresent()) {
1037        entry.m_locator[level].SetMissing();
1038    } else {
1039        entry.m_locator[level].SetRemoved();
1040        clusterset.m_removed.push_back(idx);
1041    }
1042    // Update the transaction count.
1043    --clusterset.m_txcount;
1044    clusterset.m_txcount_oversized -= oversized_tx;
1045    // If clearing main, adjust the status of Locators of this transaction in staging, if it exists.
1046    if (level == 0 && GetTopLevel() == 1) {
1047        if (entry.m_locator[1].IsRemoved()) {
1048            entry.m_locator[1].SetMissing();
1049        } else if (!entry.m_locator[1].IsPresent()) {
1050            --m_staging_clusterset->m_txcount;
1051            m_staging_clusterset->m_txcount_oversized -= oversized_tx;
1052        }
1053    }
1054    if (level == 0) ClearChunkData(entry);
1055}
1056
1057void GenericClusterImpl::RemoveChunkData(TxGraphImpl& graph) noexcept
1058{
1059    for (DepGraphIndex idx : m_linearization) {
1060        auto& entry = graph.m_entries[m_mapping[idx]];
1061        graph.ClearChunkData(entry);
1062    }
1063}
1064
1065void SingletonClusterImpl::RemoveChunkData(TxGraphImpl& graph) noexcept
1066{
1067    if (GetTxCount() == 0) return;
1068    auto& entry = graph.m_entries[m_graph_index];
1069    graph.ClearChunkData(entry);
1070}
1071
1072void GenericClusterImpl::Updated(TxGraphImpl& graph, int level, bool rename) noexcept
1073{
1074    // Update all the Locators for this Cluster's Entry objects.
1075    for (DepGraphIndex idx : m_linearization) {
1076        auto& entry = graph.m_entries[m_mapping[idx]];
1077        // Discard any potential ChunkData prior to modifying the Cluster (as that could
1078        // invalidate its ordering).
1079        if (level == 0 && !rename) graph.ClearChunkData(entry);
1080        entry.m_locator[level].SetPresent(this, idx);
1081    }
1082    // If this is for the main graph (level = 0), and the Cluster's quality is ACCEPTABLE or
1083    // OPTIMAL, compute its chunking and store its information in the Entry's m_main_lin_index
1084    // and m_main_chunk_feerate. These fields are only accessed after making the entire graph
1085    // ACCEPTABLE, so it is pointless to compute these if we haven't reached that quality level
1086    // yet.
1087    // When rename=true, this is always performed for level 0, to make sure the values inside the
1088    // entries remain consistent with the chunk index (otherwise unrelated chunk index operations
1089    // could cause the index to become corrupted, by inserting elements in the wrong place).
1090    if (level == 0 && (rename || IsAcceptable())) {
1091        auto chunking = ChunkLinearizationInfo(m_depgraph, m_linearization);
1092        LinearizationIndex lin_idx{0};
1093        /** The sum of all chunk feerate FeeFracs with the same feerate as the current chunk,
1094         *  up to and including the current chunk. */
1095        FeeFrac equal_feerate_chunk_feerate;
1096        // Iterate over the chunks.
1097        for (unsigned chunk_idx = 0; chunk_idx < chunking.size(); ++chunk_idx) {
1098            auto& chunk = chunking[chunk_idx];
1099            auto chunk_count = chunk.transactions.Count();
1100            Assume(chunk_count > 0);
1101            // Update equal_feerate_chunk_feerate to include this chunk, starting over when the
1102            // feerate changed.
1103            if (ByRatio{chunk.feerate} < ByRatio{equal_feerate_chunk_feerate}) {
1104                equal_feerate_chunk_feerate = chunk.feerate;
1105            } else {
1106                // Note that this is adding fees to fees, and sizes to sizes, so the overall
1107                // ratio remains the same; it's just accounting for the size of the added chunk.
1108                equal_feerate_chunk_feerate += chunk.feerate;
1109            }
1110            // Determine the m_fallback_order maximum transaction in the chunk.
1111            auto it = chunk.transactions.begin();
1112            GraphIndex max_element = m_mapping[*it];
1113            ++it;
1114            while (it != chunk.transactions.end()) {
1115                GraphIndex this_element = m_mapping[*it];
1116                if (graph.m_fallback_order(*graph.m_entries[this_element].m_ref, *graph.m_entries[max_element].m_ref) > 0) {
1117                    max_element = this_element;
1118                }
1119                ++it;
1120            }
1121            // Iterate over the transactions in the linearization, which must match those in chunk.
1122            while (true) {
1123                DepGraphIndex idx = m_linearization[lin_idx];
1124                GraphIndex graph_idx = m_mapping[idx];
1125                auto& entry = graph.m_entries[graph_idx];
1126                entry.m_main_lin_index = lin_idx++;
1127                entry.m_main_chunk_feerate = FeePerWeight::FromFeeFrac(chunk.feerate);
1128                entry.m_main_equal_feerate_chunk_prefix_size = equal_feerate_chunk_feerate.size;
1129                entry.m_main_max_chunk_fallback = max_element;
1130                Assume(chunk.transactions[idx]);
1131                chunk.transactions.Reset(idx);
1132                if (chunk.transactions.None()) {
1133                    // Last transaction in the chunk.
1134                    if (chunk_count == 1 && chunk_idx + 1 == chunking.size()) {
1135                        // If this is the final chunk of the cluster, and it contains just a single
1136                        // transaction (which will always be true for the very common singleton
1137                        // clusters), store the special value -1 as chunk count.
1138                        chunk_count = LinearizationIndex(-1);
1139                    }
1140                    if (!rename) graph.CreateChunkData(graph_idx, chunk_count);
1141                    break;
1142                }
1143            }
1144        }
1145    }
1146}
1147
1148void SingletonClusterImpl::Updated(TxGraphImpl& graph, int level, bool rename) noexcept
1149{
1150    // Don't do anything if this is empty.
1151    if (GetTxCount() == 0) return;
1152
1153    auto& entry = graph.m_entries[m_graph_index];
1154    // Discard any potential ChunkData prior to modifying the Cluster (as that could
1155    // invalidate its ordering).
1156    if (level == 0 && !rename) graph.ClearChunkData(entry);
1157    entry.m_locator[level].SetPresent(this, 0);
1158    // If this is for the main graph (level = 0), compute its chunking and store its information in
1159    // the Entry's m_main_lin_index and m_main_chunk_feerate.
1160    if (level == 0 && (rename || IsAcceptable())) {
1161        entry.m_main_lin_index = 0;
1162        entry.m_main_chunk_feerate = m_feerate;
1163        entry.m_main_equal_feerate_chunk_prefix_size = m_feerate.size;
1164        entry.m_main_max_chunk_fallback = m_graph_index;
1165        // Always use the special LinearizationIndex(-1), indicating singleton chunk at end of
1166        // Cluster, here.
1167        if (!rename) graph.CreateChunkData(m_graph_index, LinearizationIndex(-1));
1168    }
1169}
1170
1171void GenericClusterImpl::GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept
1172{
1173    for (auto i : m_linearization) {
1174        auto& entry = graph.m_entries[m_mapping[i]];
1175        // For every transaction Entry in this Cluster, if it also exists in a lower-level Cluster,
1176        // then that Cluster conflicts.
1177        if (entry.m_locator[0].IsPresent()) {
1178            out.push_back(entry.m_locator[0].cluster);
1179        }
1180    }
1181}
1182
1183void SingletonClusterImpl::GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept
1184{
1185    // Empty clusters have no conflicts.
1186    if (GetTxCount() == 0) return;
1187
1188    auto& entry = graph.m_entries[m_graph_index];
1189    // If the transaction in this Cluster also exists in a lower-level Cluster, then that Cluster
1190    // conflicts.
1191    if (entry.m_locator[0].IsPresent()) {
1192        out.push_back(entry.m_locator[0].cluster);
1193    }
1194}
1195
1196std::vector<Cluster*> TxGraphImpl::GetConflicts() const noexcept
1197{
1198    Assume(GetTopLevel() == 1);
1199    auto& clusterset = GetClusterSet(1);
1200    std::vector<Cluster*> ret;
1201    // All main Clusters containing transactions in m_removed (so (P,R) ones) are conflicts.
1202    for (auto i : clusterset.m_removed) {
1203        auto& entry = m_entries[i];
1204        if (entry.m_locator[0].IsPresent()) {
1205            ret.push_back(entry.m_locator[0].cluster);
1206        }
1207    }
1208    // Then go over all Clusters at this level, and find their conflicts (the (P,P) ones).
1209    for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) {
1210        auto& clusters = clusterset.m_clusters[quality];
1211        for (const auto& cluster : clusters) {
1212            cluster->GetConflicts(*this, ret);
1213        }
1214    }
1215    // Deduplicate the result (the same Cluster may appear multiple times).
1216    std::ranges::sort(ret, [](Cluster* a, Cluster* b) noexcept { return CompareClusters(a, b) < 0; });
1217    ret.erase(std::ranges::unique(ret).begin(), ret.end());
1218    return ret;
1219}
1220
1221Cluster* GenericClusterImpl::CopyToStaging(TxGraphImpl& graph) const noexcept
1222{
1223    // Construct an empty Cluster.
1224    auto ret = graph.CreateEmptyGenericCluster();
1225    auto ptr = ret.get();
1226    // Copy depgraph, mapping, and linearization.
1227    ptr->m_depgraph = m_depgraph;
1228    ptr->m_mapping = m_mapping;
1229    ptr->m_linearization = m_linearization;
1230    // Insert the new Cluster into the graph.
1231    graph.InsertCluster(/*level=*/1, std::move(ret), m_quality);
1232    // Update its Locators.
1233    ptr->Updated(graph, /*level=*/1, /*rename=*/false);
1234    // Update memory usage.
1235    graph.GetClusterSet(/*level=*/1).m_cluster_usage += ptr->TotalMemoryUsage();
1236    return ptr;
1237}
1238
1239Cluster* SingletonClusterImpl::CopyToStaging(TxGraphImpl& graph) const noexcept
1240{
1241    // Construct an empty Cluster.
1242    auto ret = graph.CreateEmptySingletonCluster();
1243    auto ptr = ret.get();
1244    // Copy data.
1245    ptr->m_graph_index = m_graph_index;
1246    ptr->m_feerate = m_feerate;
1247    // Insert the new Cluster into the graph.
1248    graph.InsertCluster(/*level=*/1, std::move(ret), m_quality);
1249    // Update its Locators.
1250    ptr->Updated(graph, /*level=*/1, /*rename=*/false);