24static constexpr int MAX_LEVELS{2};
30using LinearizationIndex = uint32_t;
32using ClusterSetIndex = uint32_t;
35enum class QualityLevel
40 NEEDS_SPLIT_ACCEPTABLE,
55 friend class TxGraphImpl;
63 std::vector<GraphIndex> m_mapping;
66 std::vector<DepGraphIndex> m_linearization;
70 ClusterSetIndex m_setindex{ClusterSetIndex(-1)};
78 Cluster() noexcept = delete;
80 explicit Cluster(uint64_t
sequence) noexcept;
82 explicit Cluster(uint64_t
sequence, TxGraphImpl& graph, const
FeePerWeight& feerate, GraphIndex graph_index) noexcept;
85 Cluster(const Cluster&) = delete;
86 Cluster& operator=(const Cluster&) = delete;
87 Cluster(Cluster&&) = delete;
88 Cluster& operator=(Cluster&&) = delete;
93 bool IsAcceptable(
bool after_split = false) const noexcept
95 return m_quality == QualityLevel::ACCEPTABLE || m_quality == QualityLevel::OPTIMAL ||
96 (after_split && m_quality == QualityLevel::NEEDS_SPLIT_ACCEPTABLE);
99 bool IsOptimal() const noexcept
101 return m_quality == QualityLevel::OPTIMAL;
104 bool NeedsSplitting() const noexcept
106 return m_quality == QualityLevel::NEEDS_SPLIT ||
107 m_quality == QualityLevel::NEEDS_SPLIT_ACCEPTABLE;
110 LinearizationIndex GetTxCount() const noexcept {
return m_linearization.size(); }
112 GraphIndex GetClusterEntry(
DepGraphIndex index)
const noexcept {
return m_mapping[index]; }
114 void UpdateMapping(
DepGraphIndex cluster_idx, GraphIndex graph_idx)
noexcept { m_mapping[cluster_idx] = graph_idx; }
116 void Updated(TxGraphImpl& graph)
noexcept;
118 Cluster* CopyToStaging(TxGraphImpl& graph)
const noexcept;
120 void GetConflicts(
const TxGraphImpl& graph, std::vector<Cluster*>&
out)
const noexcept;
123 void MakeStagingTransactionsMissing(TxGraphImpl& graph)
noexcept;
125 void Clear(TxGraphImpl& graph)
noexcept;
127 void MoveToMain(TxGraphImpl& graph)
noexcept;
133 void ApplyRemovals(TxGraphImpl& graph, std::span<GraphIndex>& to_remove)
noexcept;
136 [[nodiscard]]
bool Split(TxGraphImpl& graph)
noexcept;
138 void Merge(TxGraphImpl& graph, Cluster& cluster)
noexcept;
140 void ApplyDependencies(TxGraphImpl& graph, std::span<std::pair<GraphIndex, GraphIndex>> to_apply)
noexcept;
142 void Relinearize(TxGraphImpl& graph, uint64_t max_iters)
noexcept;
148 void GetAncestorRefs(
const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>&
args, std::vector<TxGraph::Ref*>& output)
noexcept;
151 void GetDescendantRefs(
const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>&
args, std::vector<TxGraph::Ref*>& output)
noexcept;
153 std::vector<TxGraph::Ref*> GetClusterRefs(
const TxGraphImpl& graph)
noexcept;
161 void SanityCheck(
const TxGraphImpl& graph,
int level)
const;
188class TxGraphImpl final :
public TxGraph
190 friend class Cluster;
201 uint32_t m_cluster_offset;
203 uint32_t m_cluster_count;
205 uint32_t m_deps_offset;
207 uint32_t m_deps_count;
214 std::vector<GroupEntry> m_groups;
216 std::vector<Cluster*> m_group_clusters;
219 bool m_group_oversized;
226 std::array<std::vector<std::unique_ptr<Cluster>>, int(
QualityLevel::NONE)> m_clusters;
228 std::vector<GraphIndex> m_to_remove;
231 std::vector<std::pair<GraphIndex, GraphIndex>> m_deps_to_add;
233 std::optional<GroupData> m_group_data = GroupData{};
237 std::vector<GraphIndex> m_removed;
240 GraphIndex m_txcount{0};
243 std::optional<bool> m_oversized{
false};
245 ClusterSet() noexcept = default;
249 ClusterSet m_main_clusterset;
251 std::optional<ClusterSet> m_staging_clusterset;
253 uint64_t m_next_sequence_counter{0};
288 Cluster* cluster{
nullptr};
293 void SetMissing() noexcept { cluster =
nullptr; index = 0; }
295 void SetRemoved() noexcept { cluster =
nullptr; index =
DepGraphIndex(-1); }
297 void SetPresent(Cluster* c,
DepGraphIndex i)
noexcept { cluster = c; index = i; }
299 bool IsMissing() const noexcept {
return cluster ==
nullptr && index == 0; }
301 bool IsRemoved() const noexcept {
return cluster ==
nullptr && index ==
DepGraphIndex(-1); }
303 bool IsPresent() const noexcept {
return cluster !=
nullptr; }
312 Locator m_locator[MAX_LEVELS];
316 LinearizationIndex m_main_lin_index;
320 std::vector<Entry> m_entries;
323 std::vector<GraphIndex> m_unlinked;
326 static std::strong_ordering CompareClusters(Cluster* a, Cluster* b)
noexcept
329 if (a ==
nullptr || b ==
nullptr) {
330 return (a !=
nullptr) <=> (b !=
nullptr);
333 Assume(a == b || a->m_sequence != b->m_sequence);
334 return a->m_sequence <=> b->m_sequence;
339 explicit TxGraphImpl(
DepGraphIndex max_cluster_count) noexcept :
340 m_max_cluster_count(max_cluster_count)
342 Assume(max_cluster_count >= 1);
347 ~TxGraphImpl() noexcept;
350 TxGraphImpl(const TxGraphImpl&) = delete;
351 TxGraphImpl& operator=(const TxGraphImpl&) = delete;
352 TxGraphImpl(TxGraphImpl&&) = delete;
353 TxGraphImpl& operator=(TxGraphImpl&&) = delete;
358 void SwapIndexes(GraphIndex a, GraphIndex b) noexcept;
361 Cluster* FindCluster(GraphIndex idx,
int level) const noexcept;
363 std::unique_ptr<Cluster> ExtractCluster(
int level, QualityLevel quality, ClusterSetIndex setindex) noexcept;
365 void DeleteCluster(Cluster& cluster) noexcept;
367 ClusterSetIndex InsertCluster(
int level,
std::unique_ptr<Cluster>&& cluster, QualityLevel quality) noexcept;
369 void SetClusterQuality(
int level, QualityLevel old_quality, ClusterSetIndex old_index, QualityLevel new_quality) noexcept;
371 int GetTopLevel() const noexcept {
return m_staging_clusterset.has_value(); }
373 int GetSpecifiedLevel(
bool main_only)
const noexcept {
return m_staging_clusterset.has_value() && !main_only; }
375 ClusterSet& GetClusterSet(
int level)
noexcept;
376 const ClusterSet& GetClusterSet(
int level)
const noexcept;
378 void ClearLocator(
int level, GraphIndex index)
noexcept;
380 std::vector<Cluster*> GetConflicts() const noexcept;
385 void UpdateRef(GraphIndex idx, Ref& new_location) noexcept final
387 auto& entry = m_entries[idx];
388 Assume(entry.m_ref !=
nullptr);
389 entry.m_ref = &new_location;
393 void UnlinkRef(GraphIndex idx)
noexcept final
395 auto& entry = m_entries[idx];
396 Assume(entry.m_ref !=
nullptr);
397 entry.m_ref =
nullptr;
400 bool exists_anywhere{
false};
402 for (
int level = 0; level <= GetTopLevel(); ++level) {
403 if (entry.m_locator[level].IsPresent()) {
404 exists_anywhere =
true;
406 }
else if (entry.m_locator[level].IsRemoved()) {
410 auto& clusterset = GetClusterSet(level);
411 clusterset.m_to_remove.push_back(idx);
413 clusterset.m_group_data = std::nullopt;
419 if (level == GetTopLevel() && clusterset.m_oversized ==
true) {
420 clusterset.m_oversized = std::nullopt;
424 m_unlinked.push_back(idx);
425 if (!exists_anywhere) Compact();
432 void Compact() noexcept;
436 Cluster* PullIn(Cluster* cluster) noexcept;
439 void ApplyRemovals(
int up_to_level) noexcept;
441 void Split(Cluster& cluster) noexcept;
443 void SplitAll(
int up_to_level) noexcept;
445 void GroupClusters(
int level) noexcept;
447 void Merge(
std::span<Cluster*> to_merge) noexcept;
449 void ApplyDependencies(
int level) noexcept;
451 void MakeAcceptable(Cluster& cluster) noexcept;
453 void MakeAllAcceptable(
int level) noexcept;
457 Ref AddTransaction(const
FeePerWeight& feerate) noexcept final;
458 void RemoveTransaction(const Ref& arg) noexcept final;
459 void AddDependency(const Ref& parent, const Ref& child) noexcept final;
460 void SetTransactionFee(const Ref&, int64_t
fee) noexcept final;
462 void DoWork() noexcept final;
464 void StartStaging() noexcept final;
465 void CommitStaging() noexcept final;
466 void AbortStaging() noexcept final;
467 bool HaveStaging() const noexcept final {
return m_staging_clusterset.has_value(); }
469 bool Exists(
const Ref& arg,
bool main_only =
false) noexcept final;
470 FeePerWeight GetMainChunkFeerate(const Ref& arg) noexcept final;
471 FeePerWeight GetIndividualFeerate(const Ref& arg) noexcept final;
472 std::vector<Ref*> GetCluster(const Ref& arg,
bool main_only = false) noexcept final;
473 std::vector<Ref*> GetAncestors(const Ref& arg,
bool main_only = false) noexcept final;
474 std::vector<Ref*> GetDescendants(const Ref& arg,
bool main_only = false) noexcept final;
475 std::vector<Ref*> GetAncestorsUnion(
std::span<const Ref* const>
args,
bool main_only = false) noexcept final;
476 std::vector<Ref*> GetDescendantsUnion(
std::span<const Ref* const>
args,
bool main_only = false) noexcept final;
477 GraphIndex GetTransactionCount(
bool main_only = false) noexcept final;
478 bool IsOversized(
bool main_only = false) noexcept final;
479 std::strong_ordering CompareMainOrder(const Ref& a, const Ref& b) noexcept final;
480 GraphIndex CountDistinctClusters(
std::span<const Ref* const> refs,
bool main_only = false) noexcept final;
482 void SanityCheck() const final;
485TxGraphImpl::ClusterSet& TxGraphImpl::GetClusterSet(
int level) noexcept
487 if (level == 0)
return m_main_clusterset;
489 Assume(m_staging_clusterset.has_value());
490 return *m_staging_clusterset;
493const TxGraphImpl::ClusterSet& TxGraphImpl::GetClusterSet(
int level)
const noexcept
495 if (level == 0)
return m_main_clusterset;
497 Assume(m_staging_clusterset.has_value());
498 return *m_staging_clusterset;
501void TxGraphImpl::ClearLocator(
int level, GraphIndex idx)
noexcept
503 auto& entry = m_entries[idx];
504 auto& clusterset = GetClusterSet(level);
505 Assume(entry.m_locator[level].IsPresent());
507 if (level == 0 || !entry.m_locator[level - 1].IsPresent()) {
508 entry.m_locator[level].SetMissing();
510 entry.m_locator[level].SetRemoved();
511 clusterset.m_removed.push_back(idx);
514 --clusterset.m_txcount;
516 if (level == 0 && GetTopLevel() == 1) {
517 if (entry.m_locator[1].IsRemoved()) {
518 entry.m_locator[1].SetMissing();
519 }
else if (!entry.m_locator[1].IsPresent()) {
520 --m_staging_clusterset->m_txcount;
525void Cluster::Updated(TxGraphImpl& graph)
noexcept
529 auto& entry = graph.m_entries[m_mapping[idx]];
530 entry.m_locator[m_level].SetPresent(
this, idx);
537 if (m_level == 0 && IsAcceptable()) {
539 LinearizationIndex lin_idx{0};
541 for (
unsigned chunk_idx = 0; chunk_idx < chunking.NumChunksLeft(); ++chunk_idx) {
542 auto chunk = chunking.GetChunk(chunk_idx);
543 Assume(chunk.transactions.Any());
547 GraphIndex graph_idx = m_mapping[idx];
548 auto& entry = graph.m_entries[graph_idx];
549 entry.m_main_lin_index = lin_idx++;
551 Assume(chunk.transactions[idx]);
552 chunk.transactions.Reset(idx);
553 }
while(chunk.transactions.Any());
558void Cluster::GetConflicts(
const TxGraphImpl& graph, std::vector<Cluster*>&
out)
const noexcept
561 for (
auto i : m_linearization) {
562 auto& entry = graph.m_entries[m_mapping[i]];
565 if (entry.m_locator[0].IsPresent()) {
566 out.push_back(entry.m_locator[0].cluster);
571std::vector<Cluster*> TxGraphImpl::GetConflicts() const noexcept
573 Assume(GetTopLevel() == 1);
574 auto& clusterset = GetClusterSet(1);
575 std::vector<Cluster*>
ret;
577 for (
auto i : clusterset.m_removed) {
578 auto& entry = m_entries[i];
579 if (entry.m_locator[0].IsPresent()) {
580 ret.push_back(entry.m_locator[0].cluster);
585 auto& clusters = clusterset.m_clusters[quality];
586 for (
const auto& cluster : clusters) {
587 cluster->GetConflicts(*
this,
ret);
591 std::sort(
ret.begin(),
ret.end(), [](Cluster* a, Cluster* b)
noexcept { return CompareClusters(a, b) < 0; });
592 ret.erase(std::unique(
ret.begin(),
ret.end()),
ret.end());
596Cluster* Cluster::CopyToStaging(TxGraphImpl& graph)
const noexcept
599 auto ret = std::make_unique<Cluster>(graph.m_next_sequence_counter++);
600 auto ptr =
ret.get();
602 ptr->m_depgraph = m_depgraph;
603 ptr->m_mapping = m_mapping;
604 ptr->m_linearization = m_linearization;
606 graph.InsertCluster(1, std::move(
ret), m_quality);
612void Cluster::ApplyRemovals(TxGraphImpl& graph, std::span<GraphIndex>& to_remove)
noexcept
615 Assume(!to_remove.empty());
618 GraphIndex idx = to_remove.front();
619 Assume(idx < graph.m_entries.size());
620 auto& entry = graph.m_entries[idx];
621 auto& locator = entry.m_locator[m_level];
623 if (locator.cluster !=
this)
break;
625 todo.Set(locator.index);
629 m_mapping[locator.index] = GraphIndex(-1);
632 entry.m_main_lin_index = LinearizationIndex(-1);
635 graph.ClearLocator(m_level, idx);
636 to_remove = to_remove.subspan(1);
637 }
while(!to_remove.empty());
639 auto quality = m_quality;
647 while (!m_linearization.empty() && todo[m_linearization.back()]) {
648 todo.Reset(m_linearization.back());
649 m_linearization.pop_back();
654 if (IsAcceptable(
true)) {
655 quality = QualityLevel::NEEDS_SPLIT_ACCEPTABLE;
657 quality = QualityLevel::NEEDS_SPLIT;
661 m_linearization.erase(std::remove_if(
662 m_linearization.begin(),
663 m_linearization.end(),
664 [&](
auto pos) { return todo[pos]; }), m_linearization.end());
665 quality = QualityLevel::NEEDS_SPLIT;
667 graph.SetClusterQuality(m_level, m_quality, m_setindex, quality);
671void Cluster::Clear(TxGraphImpl& graph)
noexcept
673 for (
auto i : m_linearization) {
674 graph.ClearLocator(m_level, m_mapping[i]);
677 m_linearization.clear();
681void Cluster::MoveToMain(TxGraphImpl& graph)
noexcept
684 for (
auto i : m_linearization) {
685 GraphIndex idx = m_mapping[i];
686 auto& entry = graph.m_entries[idx];
687 entry.m_locator[1].SetMissing();
689 auto quality = m_quality;
690 auto cluster = graph.ExtractCluster(1, quality, m_setindex);
691 graph.InsertCluster(0, std::move(cluster), quality);
700 QualityLevel new_quality = IsAcceptable(
true) ? QualityLevel::ACCEPTABLE
701 : QualityLevel::NEEDS_RELINEARIZE;
708 if (new_quality == QualityLevel::ACCEPTABLE) {
715 std::vector<std::pair<Cluster*, DepGraphIndex>> remap(m_depgraph.
PositionRange());
716 std::vector<Cluster*> new_clusters;
721 if (first && component == todo) {
724 graph.SetClusterQuality(m_level, m_quality, m_setindex, new_quality);
732 auto new_cluster = std::make_unique<Cluster>(graph.m_next_sequence_counter++);
733 new_clusters.push_back(new_cluster.get());
736 for (
auto i : component) {
739 graph.InsertCluster(m_level, std::move(new_cluster), new_quality);
743 for (
auto i : m_linearization) {
745 Cluster* new_cluster = remap[i].first;
747 remap[i].second = new_cluster->m_depgraph.AddTransaction(m_depgraph.
FeeRate(i));
749 new_cluster->m_mapping.push_back(m_mapping[i]);
752 new_cluster->m_linearization.push_back(remap[i].second);
755 for (
auto i : m_linearization) {
757 Cluster* new_cluster = remap[i].first;
760 for (
auto par : m_depgraph.
GetReducedParents(i)) new_parents.Set(remap[par].second);
761 new_cluster->m_depgraph.AddDependencies(new_parents, remap[i].second);
764 for (Cluster* new_cluster : new_clusters) {
765 new_cluster->Updated(graph);
770 m_linearization.clear();
774void Cluster::Merge(TxGraphImpl& graph, Cluster& other)
noexcept
777 std::vector<DepGraphIndex> remap(other.m_depgraph.PositionRange());
779 for (
auto pos : other.m_linearization) {
780 auto idx = other.m_mapping[pos];
782 auto new_pos = m_depgraph.
AddTransaction(other.m_depgraph.FeeRate(pos));
783 remap[pos] = new_pos;
784 if (new_pos == m_mapping.size()) {
785 m_mapping.push_back(idx);
787 m_mapping[new_pos] = idx;
789 m_linearization.push_back(new_pos);
794 for (
auto par : other.m_depgraph.GetReducedParents(pos)) {
795 parents.Set(remap[par]);
801 graph.m_entries[idx].m_locator[m_level].SetPresent(
this, new_pos);
805 other.m_linearization.clear();
806 other.m_mapping.clear();
809void Cluster::ApplyDependencies(TxGraphImpl& graph, std::span<std::pair<GraphIndex, GraphIndex>> to_apply)
noexcept
820 std::sort(to_apply.begin(), to_apply.end(), [](
auto& a,
auto& b) { return a.second < b.second; });
822 auto it = to_apply.begin();
823 while (it != to_apply.end()) {
824 auto& first_child = graph.m_entries[it->second].m_locator[m_level];
825 const auto child_idx = first_child.index;
829 while (it != to_apply.end()) {
830 auto& child = graph.m_entries[it->second].m_locator[m_level];
831 auto& parent = graph.m_entries[it->first].m_locator[m_level];
832 Assume(child.cluster ==
this && parent.cluster ==
this);
833 if (child.index != child_idx)
break;
834 parents.Set(parent.index);
852TxGraphImpl::~TxGraphImpl() noexcept
856 for (
auto& entry : m_entries) {
857 if (entry.m_ref !=
nullptr) {
858 GetRefGraph(*entry.m_ref) =
nullptr;
863std::unique_ptr<Cluster> TxGraphImpl::ExtractCluster(
int level, QualityLevel quality, ClusterSetIndex setindex)
noexcept
867 auto& clusterset = GetClusterSet(level);
868 auto& quality_clusters = clusterset.m_clusters[int(quality)];
869 Assume(setindex < quality_clusters.size());
872 std::unique_ptr<Cluster>
ret = std::move(quality_clusters[setindex]);
874 ret->m_setindex = ClusterSetIndex(-1);
878 auto max_setindex = quality_clusters.size() - 1;
879 if (setindex != max_setindex) {
881 quality_clusters.back()->m_setindex = setindex;
882 quality_clusters.back()->m_level = level;
883 quality_clusters[setindex] = std::move(quality_clusters.back());
886 quality_clusters.pop_back();
891ClusterSetIndex TxGraphImpl::InsertCluster(
int level, std::unique_ptr<Cluster>&& cluster, QualityLevel quality)
noexcept
899 auto& clusterset = GetClusterSet(level);
900 auto& quality_clusters = clusterset.m_clusters[int(quality)];
901 ClusterSetIndex
ret = quality_clusters.size();
902 cluster->m_quality = quality;
903 cluster->m_setindex =
ret;
904 cluster->m_level = level;
905 quality_clusters.push_back(std::move(cluster));
909void TxGraphImpl::SetClusterQuality(
int level, QualityLevel old_quality, ClusterSetIndex old_index, QualityLevel new_quality)
noexcept
914 if (old_quality == new_quality)
return;
916 auto cluster_ptr = ExtractCluster(level, old_quality, old_index);
918 InsertCluster(level, std::move(cluster_ptr), new_quality);
921void TxGraphImpl::DeleteCluster(Cluster& cluster)
noexcept
924 auto cluster_ptr = ExtractCluster(cluster.m_level, cluster.m_quality, cluster.m_setindex);
929Cluster* TxGraphImpl::FindCluster(GraphIndex idx,
int level)
const noexcept
931 Assume(level >= 0 && level <= GetTopLevel());
932 auto& entry = m_entries[idx];
934 for (
int l = level; l >= 0; --l) {
937 if (entry.m_locator[l].IsMissing())
continue;
939 if (entry.m_locator[l].IsRemoved())
break;
941 return entry.m_locator[l].cluster;
947Cluster* TxGraphImpl::PullIn(Cluster* cluster)
noexcept
949 int to_level = GetTopLevel();
951 int level = cluster->m_level;
952 Assume(level <= to_level);
957 MakeAcceptable(*cluster);
958 cluster = cluster->CopyToStaging(*
this);
963void TxGraphImpl::ApplyRemovals(
int up_to_level)
noexcept
965 Assume(up_to_level >= 0 && up_to_level <= GetTopLevel());
966 for (
int level = 0; level <= up_to_level; ++level) {
967 auto& clusterset = GetClusterSet(level);
968 auto& to_remove = clusterset.m_to_remove;
970 if (to_remove.empty())
continue;
973 for (GraphIndex index : to_remove) {
974 auto cluster = FindCluster(index, level);
975 if (cluster !=
nullptr) PullIn(cluster);
979 std::sort(to_remove.begin(), to_remove.end(), [&](GraphIndex a, GraphIndex b)
noexcept {
980 Cluster* cluster_a = m_entries[a].m_locator[level].cluster;
981 Cluster* cluster_b = m_entries[b].m_locator[level].cluster;
982 return CompareClusters(cluster_a, cluster_b) < 0;
985 std::span to_remove_span{to_remove};
986 while (!to_remove_span.empty()) {
987 Cluster* cluster = m_entries[to_remove_span.front()].m_locator[level].cluster;
988 if (cluster !=
nullptr) {
991 cluster->ApplyRemovals(*
this, to_remove_span);
995 to_remove_span = to_remove_span.subspan(1);
1003void TxGraphImpl::SwapIndexes(GraphIndex a, GraphIndex b)
noexcept
1005 Assume(a < m_entries.size());
1006 Assume(b < m_entries.size());
1008 std::swap(m_entries[a], m_entries[b]);
1010 for (
int i = 0; i < 2; ++i) {
1011 GraphIndex idx = i ? b : a;
1012 Entry& entry = m_entries[idx];
1014 if (entry.m_ref) GetRefIndex(*entry.m_ref) = idx;
1017 for (
int level = 0; level < MAX_LEVELS; ++level) {
1018 Locator& locator = entry.m_locator[level];
1019 if (locator.IsPresent()) {
1020 locator.cluster->UpdateMapping(locator.index, idx);
1026void TxGraphImpl::Compact() noexcept
1030 if (!m_main_clusterset.m_deps_to_add.empty())
return;
1031 if (!m_main_clusterset.m_to_remove.empty())
return;
1032 Assume(m_main_clusterset.m_removed.empty());
1033 if (m_staging_clusterset.has_value()) {
1034 if (!m_staging_clusterset->m_deps_to_add.empty())
return;
1035 if (!m_staging_clusterset->m_to_remove.empty())
return;
1036 if (!m_staging_clusterset->m_removed.empty())
return;
1043 std::sort(m_unlinked.begin(), m_unlinked.end(), std::greater{});
1045 auto last = GraphIndex(-1);
1046 for (GraphIndex idx : m_unlinked) {
1053 Entry& entry = m_entries[idx];
1054 Assume(entry.m_ref ==
nullptr);
1056 for (
int level = 0; level < MAX_LEVELS; ++level) {
1057 Assume(!entry.m_locator[level].IsPresent());
1061 if (idx != m_entries.size() - 1) SwapIndexes(idx, m_entries.size() - 1);
1063 m_entries.pop_back();
1072 ApplyRemovals(cluster.m_level);
1073 bool del = cluster.Split(*
this);
1076 DeleteCluster(cluster);
1080void TxGraphImpl::SplitAll(
int up_to_level)
noexcept
1082 Assume(up_to_level >= 0 && up_to_level <= GetTopLevel());
1084 ApplyRemovals(up_to_level);
1085 for (
int level = 0; level <= up_to_level; ++level) {
1086 for (
auto quality : {QualityLevel::NEEDS_SPLIT, QualityLevel::NEEDS_SPLIT_ACCEPTABLE}) {
1087 auto& queue = GetClusterSet(level).m_clusters[int(quality)];
1088 while (!queue.empty()) {
1089 Split(*queue.back().get());
1095void TxGraphImpl::GroupClusters(
int level)
noexcept
1097 auto& clusterset = GetClusterSet(level);
1099 if (clusterset.m_group_data.has_value())
return;
1109 std::vector<std::pair<Cluster*, uint64_t>> an_clusters;
1114 std::vector<std::pair<std::pair<GraphIndex, GraphIndex>, uint64_t>> an_deps;
1118 an_deps.reserve(clusterset.m_deps_to_add.size());
1119 for (
const auto& [par, chl] : clusterset.m_deps_to_add) {
1120 auto par_cluster = FindCluster(par, level);
1121 auto chl_cluster = FindCluster(chl, level);
1123 if (par_cluster ==
nullptr || chl_cluster ==
nullptr)
continue;
1124 an_clusters.emplace_back(par_cluster, par_cluster->m_sequence);
1127 if (chl_cluster != par_cluster) an_clusters.emplace_back(chl_cluster, chl_cluster->m_sequence);
1129 an_deps.emplace_back(std::pair{par, chl}, chl_cluster->m_sequence);
1133 std::sort(an_clusters.begin(), an_clusters.end(), [](
auto& a,
auto& b)
noexcept { return a.second < b.second; });
1134 an_clusters.erase(std::unique(an_clusters.begin(), an_clusters.end()), an_clusters.end());
1136 std::sort(an_deps.begin(), an_deps.end(), [&](
auto& a,
auto& b)
noexcept { return a.second < b.second; });
1142 struct PartitionData
1150 PartitionData* parent;
1156 std::vector<PartitionData> partition_data;
1159 auto locate_fn = [&](uint64_t
sequence)
noexcept -> PartitionData* {
1160 auto it = std::lower_bound(partition_data.begin(), partition_data.end(),
sequence,
1161 [](
auto& a, uint64_t seq)
noexcept { return a.sequence < seq; });
1162 Assume(it != partition_data.end());
1168 static constexpr auto find_root_fn = [](PartitionData*
data)
noexcept -> PartitionData* {
1172 auto par =
data->parent;
1173 data->parent = par->parent;
1181 static constexpr auto union_fn = [](PartitionData* arg1, PartitionData* arg2)
noexcept {
1184 auto rep1 = find_root_fn(arg1);
1185 auto rep2 = find_root_fn(arg2);
1186 if (rep1 == rep2)
return rep1;
1189 if (rep1->rank < rep2->rank) std::swap(rep1, rep2);
1190 rep2->parent = rep1;
1191 rep1->rank += (rep1->rank == rep2->rank);
1196 partition_data.resize(an_clusters.size());
1197 for (
size_t i = 0; i < an_clusters.size(); ++i) {
1198 partition_data[i].sequence = an_clusters[i].first->m_sequence;
1199 partition_data[i].parent = &partition_data[i];
1200 partition_data[i].rank = 0;
1205 Cluster* last_chl_cluster{
nullptr};
1206 PartitionData* last_partition{
nullptr};
1207 for (
const auto& [dep,
_] : an_deps) {
1208 auto [par, chl] = dep;
1209 auto par_cluster = FindCluster(par, level);
1210 auto chl_cluster = FindCluster(chl, level);
1211 Assume(chl_cluster !=
nullptr && par_cluster !=
nullptr);
1213 if (par_cluster == chl_cluster)
continue;
1215 if (chl_cluster == last_chl_cluster) {
1219 last_partition = union_fn(locate_fn(par_cluster->m_sequence), last_partition);
1221 last_chl_cluster = chl_cluster;
1222 last_partition = union_fn(locate_fn(par_cluster->m_sequence), locate_fn(chl_cluster->m_sequence));
1228 auto deps_it = an_deps.begin();
1229 for (
size_t i = 0; i < partition_data.size(); ++i) {
1230 auto&
data = partition_data[i];
1233 auto rep_seq = find_root_fn(&
data)->sequence;
1234 an_clusters[i].second = rep_seq;
1236 while (deps_it != an_deps.end()) {
1237 auto [par, chl] = deps_it->first;
1238 auto chl_cluster = FindCluster(chl, level);
1239 Assume(chl_cluster !=
nullptr);
1240 if (chl_cluster->m_sequence >
data.sequence)
break;
1241 deps_it->second = rep_seq;
1249 std::sort(an_deps.begin(), an_deps.end(), [](
auto& a,
auto& b)
noexcept { return a.second < b.second; });
1250 std::sort(an_clusters.begin(), an_clusters.end(), [](
auto& a,
auto& b)
noexcept { return a.second < b.second; });
1254 clusterset.m_group_data = GroupData{};
1255 clusterset.m_group_data->m_group_clusters.reserve(an_clusters.size());
1256 clusterset.m_group_data->m_group_oversized =
false;
1257 clusterset.m_deps_to_add.clear();
1258 clusterset.m_deps_to_add.reserve(an_deps.size());
1259 auto an_deps_it = an_deps.begin();
1260 auto an_clusters_it = an_clusters.begin();
1261 while (an_clusters_it != an_clusters.end()) {
1263 auto rep = an_clusters_it->second;
1265 auto& new_entry = clusterset.m_group_data->m_groups.emplace_back();
1266 new_entry.m_cluster_offset = clusterset.m_group_data->m_group_clusters.size();
1267 new_entry.m_cluster_count = 0;
1268 new_entry.m_deps_offset = clusterset.m_deps_to_add.size();
1269 new_entry.m_deps_count = 0;
1270 uint32_t total_count{0};
1272 while (an_clusters_it != an_clusters.end() && an_clusters_it->second == rep) {
1273 clusterset.m_group_data->m_group_clusters.push_back(an_clusters_it->first);
1274 total_count += an_clusters_it->first->GetTxCount();
1276 ++new_entry.m_cluster_count;
1279 while (an_deps_it != an_deps.end() && an_deps_it->second == rep) {
1280 clusterset.m_deps_to_add.push_back(an_deps_it->first);
1282 ++new_entry.m_deps_count;
1285 if (total_count > m_max_cluster_count) {
1286 clusterset.m_group_data->m_group_oversized =
true;
1289 Assume(an_deps_it == an_deps.end());
1290 Assume(an_clusters_it == an_clusters.end());
1291 clusterset.m_oversized = clusterset.m_group_data->m_group_oversized;
1295void TxGraphImpl::Merge(std::span<Cluster*> to_merge)
noexcept
1297 Assume(!to_merge.empty());
1299 if (to_merge.size() == 1)
return;
1304 size_t max_size_pos{0};
1305 DepGraphIndex max_size = to_merge[max_size_pos]->GetTxCount();
1306 for (
size_t i = 1; i < to_merge.size(); ++i) {
1308 if (size > max_size) {
1313 if (max_size_pos != 0) std::swap(to_merge[0], to_merge[max_size_pos]);
1316 for (
size_t i = 1; i < to_merge.size(); ++i) {
1317 to_merge[0]->Merge(*
this, *to_merge[i]);
1318 DeleteCluster(*to_merge[i]);
1322void TxGraphImpl::ApplyDependencies(
int level)
noexcept
1324 auto& clusterset = GetClusterSet(level);
1326 if (clusterset.m_oversized ==
true)
return;
1328 GroupClusters(level);
1329 Assume(clusterset.m_group_data.has_value());
1331 if (clusterset.m_deps_to_add.empty())
return;
1333 if (clusterset.m_group_data->m_group_oversized)
return;
1336 for (
const auto& group_entry : clusterset.m_group_data->m_groups) {
1337 auto cluster_span = std::span{clusterset.m_group_data->m_group_clusters}
1338 .subspan(group_entry.m_cluster_offset, group_entry.m_cluster_count);
1341 for (Cluster*& cluster : cluster_span) {
1342 cluster = PullIn(cluster);
1346 Merge(cluster_span);
1349 auto deps_span = std::span{clusterset.m_deps_to_add}
1350 .subspan(group_entry.m_deps_offset, group_entry.m_deps_count);
1351 Assume(!deps_span.empty());
1352 const auto& loc = m_entries[deps_span[0].second].m_locator[level];
1354 loc.cluster->ApplyDependencies(*
this, deps_span);
1358 clusterset.m_deps_to_add.clear();
1362 clusterset.m_group_data = GroupData{};
1365void Cluster::Relinearize(TxGraphImpl& graph, uint64_t max_iters)
noexcept
1368 Assume(!NeedsSplitting());
1370 if (IsOptimal())
return;
1372 uint64_t rng_seed = graph.m_rng.rand64();
1373 auto [linearization, optimal] =
Linearize(m_depgraph, max_iters, rng_seed, m_linearization);
1378 m_linearization = std::move(linearization);
1380 auto new_quality = optimal ? QualityLevel::OPTIMAL : QualityLevel::ACCEPTABLE;
1381 graph.SetClusterQuality(m_level, m_quality, m_setindex, new_quality);
1386void TxGraphImpl::MakeAcceptable(Cluster& cluster)
noexcept
1389 if (!cluster.NeedsSplitting() && !cluster.IsAcceptable()) {
1390 cluster.Relinearize(*
this, 10000);
1394void TxGraphImpl::MakeAllAcceptable(
int level)
noexcept
1396 ApplyDependencies(level);
1397 auto& clusterset = GetClusterSet(level);
1398 if (clusterset.m_oversized ==
true)
return;
1399 auto& queue = clusterset.m_clusters[int(QualityLevel::NEEDS_RELINEARIZE)];
1400 while (!queue.empty()) {
1401 MakeAcceptable(*queue.back().get());
1407Cluster::Cluster(uint64_t
sequence, TxGraphImpl& graph,
const FeePerWeight& feerate, GraphIndex graph_index) noexcept :
1412 m_mapping.push_back(graph_index);
1413 m_linearization.push_back(cluster_idx);
1421 auto idx = m_entries.size();
1422 m_entries.emplace_back();
1423 auto& entry = m_entries.back();
1425 GetRefGraph(
ret) =
this;
1426 GetRefIndex(
ret) = idx;
1428 auto cluster = std::make_unique<Cluster>(m_next_sequence_counter++, *
this, feerate, idx);
1429 auto cluster_ptr = cluster.get();
1430 int level = GetTopLevel();
1431 auto& clusterset = GetClusterSet(level);
1432 InsertCluster(level, std::move(cluster), QualityLevel::OPTIMAL);
1433 cluster_ptr->Updated(*
this);
1434 ++clusterset.m_txcount;
1439void TxGraphImpl::RemoveTransaction(
const Ref& arg)
noexcept
1443 if (GetRefGraph(arg) ==
nullptr)
return;
1444 Assume(GetRefGraph(arg) ==
this);
1446 int level = GetTopLevel();
1447 auto cluster = FindCluster(GetRefIndex(arg), level);
1448 if (cluster ==
nullptr)
return;
1450 auto& clusterset = GetClusterSet(level);
1451 clusterset.m_to_remove.push_back(GetRefIndex(arg));
1453 clusterset.m_group_data.reset();
1454 if (clusterset.m_oversized ==
true) clusterset.m_oversized = std::nullopt;
1457void TxGraphImpl::AddDependency(
const Ref& parent,
const Ref& child)
noexcept
1461 if (GetRefGraph(parent) ==
nullptr || GetRefGraph(child) ==
nullptr)
return;
1462 Assume(GetRefGraph(parent) ==
this && GetRefGraph(child) ==
this);
1464 if (GetRefIndex(parent) == GetRefIndex(child))
return;
1467 int level = GetTopLevel();
1468 auto par_cluster = FindCluster(GetRefIndex(parent), level);
1469 if (par_cluster ==
nullptr)
return;
1470 auto chl_cluster = FindCluster(GetRefIndex(child), level);
1471 if (chl_cluster ==
nullptr)
return;
1473 auto& clusterset = GetClusterSet(level);
1474 clusterset.m_deps_to_add.emplace_back(GetRefIndex(parent), GetRefIndex(child));
1476 clusterset.m_group_data.reset();
1477 if (clusterset.m_oversized ==
false) clusterset.m_oversized = std::nullopt;
1480bool TxGraphImpl::Exists(
const Ref& arg,
bool main_only)
noexcept
1482 if (GetRefGraph(arg) ==
nullptr)
return false;
1483 Assume(GetRefGraph(arg) ==
this);
1484 size_t level = GetSpecifiedLevel(main_only);
1486 ApplyRemovals(level);
1487 auto cluster = FindCluster(GetRefIndex(arg), level);
1488 return cluster !=
nullptr;
1491void Cluster::GetAncestorRefs(
const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>&
args, std::vector<TxGraph::Ref*>& output)
noexcept
1494 SetType ancestors_union;
1496 while (!
args.empty()) {
1497 if (
args.front().first !=
this)
break;
1498 ancestors_union |= m_depgraph.
Ancestors(
args.front().second);
1501 Assume(ancestors_union.Any());
1503 for (
auto idx : ancestors_union) {
1504 const auto& entry = graph.m_entries[m_mapping[idx]];
1505 Assume(entry.m_ref !=
nullptr);
1506 output.push_back(entry.m_ref);
1510void Cluster::GetDescendantRefs(
const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>&
args, std::vector<TxGraph::Ref*>& output)
noexcept
1513 SetType descendants_union;
1515 while (!
args.empty()) {
1516 if (
args.front().first !=
this)
break;
1520 Assume(descendants_union.Any());
1522 for (
auto idx : descendants_union) {
1523 const auto& entry = graph.m_entries[m_mapping[idx]];
1524 Assume(entry.m_ref !=
nullptr);
1525 output.push_back(entry.m_ref);
1529std::vector<TxGraph::Ref*> Cluster::GetClusterRefs(
const TxGraphImpl& graph)
noexcept
1531 std::vector<TxGraph::Ref*>
ret;
1532 ret.reserve(m_linearization.size());
1534 for (
auto idx : m_linearization) {
1535 const auto& entry = graph.m_entries[m_mapping[idx]];
1536 Assume(entry.m_ref !=
nullptr);
1537 ret.push_back(entry.m_ref);
1547void Cluster::MakeStagingTransactionsMissing(TxGraphImpl& graph)
noexcept
1552 for (
auto ci : m_linearization) {
1553 GraphIndex idx = m_mapping[ci];
1554 auto& entry = graph.m_entries[idx];
1555 entry.m_locator[1].SetMissing();
1559std::vector<TxGraph::Ref*> TxGraphImpl::GetAncestors(
const Ref& arg,
bool main_only)
noexcept
1562 if (GetRefGraph(arg) ==
nullptr)
return {};
1563 Assume(GetRefGraph(arg) ==
this);
1565 size_t level = GetSpecifiedLevel(main_only);
1566 ApplyDependencies(level);
1568 Assume(GetClusterSet(level).m_deps_to_add.empty());
1570 auto cluster = FindCluster(GetRefIndex(arg), level);
1571 if (cluster ==
nullptr)
return {};
1573 std::pair<Cluster*, DepGraphIndex> match = {cluster, m_entries[GetRefIndex(arg)].m_locator[cluster->m_level].index};
1574 auto matches = std::span(&match, 1);
1575 std::vector<TxGraph::Ref*>
ret;
1576 cluster->GetAncestorRefs(*
this, matches,
ret);
1580std::vector<TxGraph::Ref*> TxGraphImpl::GetDescendants(
const Ref& arg,
bool main_only)
noexcept
1583 if (GetRefGraph(arg) ==
nullptr)
return {};
1584 Assume(GetRefGraph(arg) ==
this);
1586 size_t level = GetSpecifiedLevel(main_only);
1587 ApplyDependencies(level);
1589 Assume(GetClusterSet(level).m_deps_to_add.empty());
1591 auto cluster = FindCluster(GetRefIndex(arg), level);
1592 if (cluster ==
nullptr)
return {};
1594 std::pair<Cluster*, DepGraphIndex> match = {cluster, m_entries[GetRefIndex(arg)].m_locator[cluster->m_level].index};
1595 auto matches = std::span(&match, 1);
1596 std::vector<TxGraph::Ref*>
ret;
1597 cluster->GetDescendantRefs(*
this, matches,
ret);
1601std::vector<TxGraph::Ref*> TxGraphImpl::GetAncestorsUnion(std::span<const Ref* const>
args,
bool main_only)
noexcept
1604 size_t level = GetSpecifiedLevel(main_only);
1605 ApplyDependencies(level);
1607 Assume(GetClusterSet(level).m_deps_to_add.empty());
1610 std::vector<std::pair<Cluster*, DepGraphIndex>> matches;
1611 matches.reserve(
args.size());
1612 for (
auto arg :
args) {
1615 if (GetRefGraph(*arg) ==
nullptr)
continue;
1616 Assume(GetRefGraph(*arg) ==
this);
1618 auto cluster = FindCluster(GetRefIndex(*arg), level);
1619 if (cluster ==
nullptr)
continue;
1621 matches.emplace_back(cluster, m_entries[GetRefIndex(*arg)].m_locator[cluster->m_level].index);
1624 std::sort(matches.begin(), matches.end(), [](
auto& a,
auto& b)
noexcept { return CompareClusters(a.first, b.first) < 0; });
1626 std::span match_span(matches);
1627 std::vector<TxGraph::Ref*>
ret;
1628 while (!match_span.empty()) {
1629 match_span.front().first->GetAncestorRefs(*
this, match_span,
ret);
1634std::vector<TxGraph::Ref*> TxGraphImpl::GetDescendantsUnion(std::span<const Ref* const>
args,
bool main_only)
noexcept
1637 size_t level = GetSpecifiedLevel(main_only);
1638 ApplyDependencies(level);
1640 Assume(GetClusterSet(level).m_deps_to_add.empty());
1643 std::vector<std::pair<Cluster*, DepGraphIndex>> matches;
1644 matches.reserve(
args.size());
1645 for (
auto arg :
args) {
1648 if (GetRefGraph(*arg) ==
nullptr)
continue;
1649 Assume(GetRefGraph(*arg) ==
this);
1651 auto cluster = FindCluster(GetRefIndex(*arg), level);
1652 if (cluster ==
nullptr)
continue;
1654 matches.emplace_back(cluster, m_entries[GetRefIndex(*arg)].m_locator[cluster->m_level].index);
1657 std::sort(matches.begin(), matches.end(), [](
auto& a,
auto& b)
noexcept { return CompareClusters(a.first, b.first) < 0; });
1659 std::span match_span(matches);
1660 std::vector<TxGraph::Ref*>
ret;
1661 while (!match_span.empty()) {
1662 match_span.front().first->GetDescendantRefs(*
this, match_span,
ret);
1667std::vector<TxGraph::Ref*> TxGraphImpl::GetCluster(
const Ref& arg,
bool main_only)
noexcept
1671 if (GetRefGraph(arg) ==
nullptr)
return {};
1672 Assume(GetRefGraph(arg) ==
this);
1674 size_t level = GetSpecifiedLevel(main_only);
1675 ApplyDependencies(level);
1677 Assume(GetClusterSet(level).m_deps_to_add.empty());
1679 auto cluster = FindCluster(GetRefIndex(arg), level);
1680 if (cluster ==
nullptr)
return {};
1682 MakeAcceptable(*cluster);
1683 return cluster->GetClusterRefs(*
this);
1688 size_t level = GetSpecifiedLevel(main_only);
1689 ApplyRemovals(level);
1690 return GetClusterSet(level).m_txcount;
1693FeePerWeight TxGraphImpl::GetIndividualFeerate(
const Ref& arg)
noexcept
1696 if (GetRefGraph(arg) ==
nullptr)
return {};
1697 Assume(GetRefGraph(arg) ==
this);
1700 Cluster* cluster{
nullptr};
1701 for (
int level = 0; level <= GetTopLevel(); ++level) {
1704 ApplyRemovals(level);
1705 if (m_entries[GetRefIndex(arg)].m_locator[level].IsPresent()) {
1706 cluster = m_entries[GetRefIndex(arg)].m_locator[level].cluster;
1710 if (cluster ==
nullptr)
return {};
1712 return cluster->GetIndividualFeerate(m_entries[GetRefIndex(arg)].m_locator[cluster->m_level].index);
1715FeePerWeight TxGraphImpl::GetMainChunkFeerate(
const Ref& arg)
noexcept
1718 if (GetRefGraph(arg) ==
nullptr)
return {};
1719 Assume(GetRefGraph(arg) ==
this);
1721 ApplyDependencies(0);
1723 Assume(m_main_clusterset.m_deps_to_add.empty());
1725 auto cluster = FindCluster(GetRefIndex(arg), 0);
1726 if (cluster ==
nullptr)
return {};
1729 MakeAcceptable(*cluster);
1730 const auto& entry = m_entries[GetRefIndex(arg)];
1731 return entry.m_main_chunk_feerate;
1734bool TxGraphImpl::IsOversized(
bool main_only)
noexcept
1736 size_t level = GetSpecifiedLevel(main_only);
1737 auto& clusterset = GetClusterSet(level);
1738 if (clusterset.m_oversized.has_value()) {
1740 return *clusterset.m_oversized;
1744 GroupClusters(level);
1745 Assume(clusterset.m_group_data.has_value());
1746 clusterset.m_oversized = clusterset.m_group_data->m_group_oversized;
1747 return *clusterset.m_oversized;
1750void TxGraphImpl::StartStaging() noexcept
1753 Assume(!m_staging_clusterset.has_value());
1760 ApplyDependencies(0);
1762 m_staging_clusterset.emplace();
1765 m_staging_clusterset->m_txcount = m_main_clusterset.m_txcount;
1766 m_staging_clusterset->m_deps_to_add = m_main_clusterset.m_deps_to_add;
1767 m_staging_clusterset->m_group_data = m_main_clusterset.m_group_data;
1768 m_staging_clusterset->m_oversized = m_main_clusterset.m_oversized;
1769 Assume(m_staging_clusterset->m_oversized.has_value());
1772void TxGraphImpl::AbortStaging() noexcept
1775 Assume(m_staging_clusterset.has_value());
1778 for (
auto idx : m_staging_clusterset->m_removed) {
1779 m_entries[idx].m_locator[1].SetMissing();
1783 for (
auto& cluster : m_staging_clusterset->m_clusters[quality]) {
1784 cluster->MakeStagingTransactionsMissing(*
this);
1788 m_staging_clusterset.reset();
1790 if (!m_main_clusterset.m_group_data.has_value()) {
1793 m_main_clusterset.m_oversized = std::nullopt;
1797void TxGraphImpl::CommitStaging() noexcept
1800 Assume(m_staging_clusterset.has_value());
1803 auto conflicts = GetConflicts();
1804 for (Cluster* conflict : conflicts) {
1805 conflict->Clear(*
this);
1806 DeleteCluster(*conflict);
1810 for (
auto idx : m_staging_clusterset->m_removed) {
1811 m_entries[idx].m_locator[1].SetMissing();
1815 auto& stage_sets = m_staging_clusterset->m_clusters[quality];
1816 while (!stage_sets.empty()) {
1817 stage_sets.back()->MoveToMain(*
this);
1821 m_main_clusterset.m_deps_to_add = std::move(m_staging_clusterset->m_deps_to_add);
1822 m_main_clusterset.m_to_remove = std::move(m_staging_clusterset->m_to_remove);
1823 m_main_clusterset.m_group_data = std::move(m_staging_clusterset->m_group_data);
1824 m_main_clusterset.m_oversized = std::move(m_staging_clusterset->m_oversized);
1825 m_main_clusterset.m_txcount = std::move(m_staging_clusterset->m_txcount);
1827 m_staging_clusterset.reset();
1831void Cluster::SetFee(TxGraphImpl& graph,
DepGraphIndex idx, int64_t
fee)
noexcept
1840 if (!NeedsSplitting()) {
1841 graph.SetClusterQuality(m_level, m_quality, m_setindex, QualityLevel::NEEDS_RELINEARIZE);
1843 graph.SetClusterQuality(m_level, m_quality, m_setindex, QualityLevel::NEEDS_SPLIT);
1848void TxGraphImpl::SetTransactionFee(
const Ref& ref, int64_t
fee)
noexcept
1851 if (GetRefGraph(ref) ==
nullptr)
return;
1852 Assume(GetRefGraph(ref) ==
this);
1854 auto& entry = m_entries[GetRefIndex(ref)];
1855 for (
int level = 0; level < MAX_LEVELS; ++level) {
1856 auto& locator = entry.m_locator[level];
1857 if (locator.IsPresent()) {
1858 locator.cluster->SetFee(*
this, locator.index,
fee);
1863std::strong_ordering TxGraphImpl::CompareMainOrder(
const Ref& a,
const Ref& b)
noexcept
1866 Assume(GetRefGraph(a) ==
this);
1867 Assume(GetRefGraph(b) ==
this);
1869 ApplyDependencies(0);
1870 Assume(m_main_clusterset.m_deps_to_add.empty());
1872 const auto& entry_a = m_entries[GetRefIndex(a)];
1873 const auto& entry_b = m_entries[GetRefIndex(b)];
1874 const auto& locator_a = entry_a.m_locator[0];
1875 const auto& locator_b = entry_b.m_locator[0];
1876 Assume(locator_a.IsPresent());
1877 Assume(locator_b.IsPresent());
1878 MakeAcceptable(*locator_a.cluster);
1879 MakeAcceptable(*locator_b.cluster);
1881 auto feerate_cmp = FeeRateCompare(entry_b.m_main_chunk_feerate, entry_a.m_main_chunk_feerate);
1882 if (feerate_cmp < 0)
return std::strong_ordering::less;
1883 if (feerate_cmp > 0)
return std::strong_ordering::greater;
1885 if (locator_a.cluster != locator_b.cluster) {
1886 return CompareClusters(locator_a.cluster, locator_b.cluster);
1889 return entry_a.m_main_lin_index <=> entry_b.m_main_lin_index;
1892TxGraph::GraphIndex TxGraphImpl::CountDistinctClusters(std::span<const Ref* const> refs,
bool main_only)
noexcept
1894 size_t level = GetSpecifiedLevel(main_only);
1895 ApplyDependencies(level);
1896 auto& clusterset = GetClusterSet(level);
1897 Assume(clusterset.m_deps_to_add.empty());
1899 std::vector<Cluster*> clusters;
1900 clusters.reserve(refs.size());
1901 for (
const Ref* ref : refs) {
1903 if (GetRefGraph(*ref) ==
nullptr)
continue;
1904 Assume(GetRefGraph(*ref) ==
this);
1905 auto cluster = FindCluster(GetRefIndex(*ref), level);
1906 if (cluster !=
nullptr) clusters.push_back(cluster);
1909 std::sort(clusters.begin(), clusters.end(), [](Cluster* a, Cluster* b)
noexcept { return CompareClusters(a, b) < 0; });
1910 Cluster* last{
nullptr};
1912 for (Cluster* cluster : clusters) {
1913 ret += (cluster != last);
1919void Cluster::SanityCheck(
const TxGraphImpl& graph,
int level)
const
1926 assert(m_linearization.size() <= graph.m_max_cluster_count);
1928 assert(m_level == level);
1936 LinearizationIndex linindex{0};
1938 for (
auto lin_pos : m_linearization) {
1939 assert(lin_pos < m_mapping.size());
1940 const auto& entry = graph.m_entries[m_mapping[lin_pos]];
1942 m_done.Set(lin_pos);
1945 assert(entry.m_locator[level].cluster ==
this);
1946 assert(entry.m_locator[level].index == lin_pos);
1948 if (level == 0 && IsAcceptable()) {
1949 assert(entry.m_main_lin_index == linindex);
1951 if (!linchunking.GetChunk(0).transactions[lin_pos]) {
1952 linchunking.MarkDone(linchunking.GetChunk(0).transactions);
1954 assert(entry.m_main_chunk_feerate == linchunking.GetChunk(0).feerate);
1963void TxGraphImpl::SanityCheck()
const
1966 std::set<GraphIndex> expected_unlinked;
1968 std::set<const Cluster*> expected_clusters[MAX_LEVELS];
1970 std::set<GraphIndex> expected_removed[MAX_LEVELS];
1972 std::set<uint64_t> sequences;
1974 bool compact_possible{
true};
1977 for (GraphIndex idx = 0; idx < m_entries.size(); ++idx) {
1978 const auto& entry = m_entries[idx];
1979 if (entry.m_ref ==
nullptr) {
1981 expected_unlinked.insert(idx);
1984 assert(GetRefGraph(*entry.m_ref) ==
this);
1985 assert(GetRefIndex(*entry.m_ref) == idx);
1988 bool was_present{
false}, was_removed{
false};
1989 for (
int level = 0; level < MAX_LEVELS; ++level) {
1990 const auto& locator = entry.m_locator[level];
1992 assert(locator.IsMissing() + locator.IsRemoved() + locator.IsPresent() == 1);
1993 if (locator.IsPresent()) {
1997 assert(locator.cluster->GetClusterEntry(locator.index) == idx);
1999 expected_clusters[level].insert(locator.cluster);
2001 }
else if (locator.IsRemoved()) {
2005 assert(was_present && !was_removed);
2007 expected_removed[level].insert(idx);
2014 for (
int level = 0; level <= GetTopLevel(); ++level) {
2015 assert(level < MAX_LEVELS);
2016 auto& clusterset = GetClusterSet(level);
2017 std::set<const Cluster*> actual_clusters;
2021 QualityLevel quality{qual};
2022 const auto& quality_clusters = clusterset.m_clusters[qual];
2024 for (ClusterSetIndex setindex = 0; setindex < quality_clusters.size(); ++setindex) {
2025 const auto& cluster = *quality_clusters[setindex];
2027 assert(cluster.m_sequence < m_next_sequence_counter);
2028 assert(sequences.count(cluster.m_sequence) == 0);
2029 sequences.insert(cluster.m_sequence);
2032 if (cluster.GetTxCount() != 0) {
2033 actual_clusters.insert(&cluster);
2036 cluster.SanityCheck(*
this, level);
2038 assert(cluster.m_quality == quality);
2039 assert(cluster.m_setindex == setindex);
2044 for (GraphIndex idx : clusterset.m_to_remove) {
2045 assert(idx < m_entries.size());
2053 for (
auto [par_idx, chl_idx] : clusterset.m_deps_to_add) {
2054 assert(par_idx != chl_idx);
2055 assert(par_idx < m_entries.size());
2056 assert(chl_idx < m_entries.size());
2060 assert(actual_clusters == expected_clusters[level]);
2063 std::set<GraphIndex> actual_removed(clusterset.m_removed.begin(), clusterset.m_removed.end());
2064 for (
auto i : expected_unlinked) {
2069 actual_removed.erase(i);
2070 expected_removed[level].erase(i);
2073 assert(actual_removed == expected_removed[level]);
2076 if (!clusterset.m_deps_to_add.empty()) compact_possible =
false;
2077 if (!clusterset.m_to_remove.empty()) compact_possible =
false;
2078 if (!clusterset.m_removed.empty()) compact_possible =
false;
2081 if (clusterset.m_group_data.has_value()) {
2082 assert(clusterset.m_oversized == clusterset.m_group_data->m_group_oversized);
2087 if (level < GetTopLevel())
assert(clusterset.m_oversized.has_value());
2091 std::set<GraphIndex> actual_unlinked(m_unlinked.begin(), m_unlinked.end());
2092 assert(actual_unlinked == expected_unlinked);
2096 if (compact_possible) {
2097 assert(actual_unlinked.empty());
2101void TxGraphImpl::DoWork() noexcept
2103 for (
int level = 0; level <= GetTopLevel(); ++level) {
2104 MakeAllAcceptable(level);
2114 m_graph->UnlinkRef(m_index);
2122 if (m_graph) m_graph->UnlinkRef(m_index);
2126 m_graph = other.m_graph;
2127 m_index = other.m_index;
2128 other.m_graph =
nullptr;
2136 if (other.m_graph) other.m_graph->UpdateRef(other.m_index, *
this);
2138 std::swap(m_graph, other.m_graph);
2139 std::swap(m_index, other.m_index);
2142std::unique_ptr<TxGraph>
MakeTxGraph(
unsigned max_cluster_count)
noexcept
2144 return std::make_unique<TxGraphImpl>(max_cluster_count);
std::conditional_t<(BITS<=32), bitset_detail::IntBitSet< uint32_t >, std::conditional_t<(BITS<=std::numeric_limits< size_t >::digits), bitset_detail::IntBitSet< size_t >, bitset_detail::MultiIntBitSet< size_t,(BITS+std::numeric_limits< size_t >::digits - 1)/std::numeric_limits< size_t >::digits > > > BitSet
#define Assume(val)
Assume is the identity function.
TxGraph * m_graph
Which Graph the Entry lives in.
virtual ~Ref()
Destroy this Ref.
Ref & operator=(Ref &&other) noexcept
Ref() noexcept=default
Construct an empty Ref.
Data structure to encapsulate fees, sizes, and dependencies for a set of transactions.
virtual void UpdateRef(GraphIndex index, Ref &new_location) noexcept=0
Inform the TxGraph implementation that a TxGraph::Ref has moved.
uint32_t GraphIndex
Internal identifier for a transaction within a TxGraph.
Data structure that holds a transaction graph's preprocessed data (fee, size, ancestors,...
const SetType & Ancestors(DepGraphIndex i) const noexcept
Get the ancestors of a given transaction i.
SetType GetReducedParents(DepGraphIndex i) const noexcept
Compute the (reduced) set of parents of node i in this graph.
const FeeFrac & FeeRate(DepGraphIndex i) const noexcept
Get the feerate of a given transaction i.
bool IsConnected(const SetType &subset) const noexcept
Determine if a subset is connected.
DepGraphIndex PositionRange() const noexcept
Get the range of positions in this DepGraph.
SetType FindConnectedComponent(const SetType &todo) const noexcept
Find some connected component within the subset "todo" of this graph.
DepGraphIndex AddTransaction(const FeeFrac &feefrac) noexcept
Add a new unconnected transaction to this transaction graph (in the first available position),...
void RemoveTransactions(const SetType &del) noexcept
Remove the specified positions from this DepGraph.
auto TxCount() const noexcept
Get the number of transactions in the graph.
const SetType & Descendants(DepGraphIndex i) const noexcept
Get the descendants of a given transaction i.
const SetType & Positions() const noexcept
Get the set of transactions positions in use.
void AddDependencies(const SetType &parents, DepGraphIndex child) noexcept
Modify this transaction graph, adding multiple parents to a specified child.
bool IsAcyclic() const noexcept
Check if this graph is acyclic.
Data structure encapsulating the chunking of a linearization, permitting removal of subsets.
std::pair< std::vector< DepGraphIndex >, bool > Linearize(const DepGraph< SetType > &depgraph, uint64_t max_iterations, uint64_t rng_seed, std::span< const DepGraphIndex > old_linearization={}) noexcept
Find or improve a linearization for a cluster.
void FixLinearization(const DepGraph< SetType > &depgraph, std::span< DepGraphIndex > linearization) noexcept
Make linearization topological, retaining its ordering where possible.
uint32_t DepGraphIndex
Data type to represent transaction indices in DepGraphs and the clusters they represent.
void PostLinearize(const DepGraph< SetType > &depgraph, std::span< DepGraphIndex > linearization)
Improve a given linearization.
std::vector< T > Split(const std::span< const char > &sp, std::string_view separators)
Split a string on any char found in separators, returning a vector.
Tagged wrapper around FeeFrac to avoid unit confusion.
static FeePerUnit FromFeeFrac(const FeeFrac &feefrac) noexcept
Convert a FeeFrac to a FeePerUnit.
consteval auto _(util::TranslatedLiteral str)
std::unique_ptr< TxGraph > MakeTxGraph(unsigned max_cluster_count) noexcept
Construct a new TxGraph with the specified limit on transactions within a cluster.
static constexpr unsigned MAX_CLUSTER_COUNT_LIMIT