19#include <unordered_set>
27static constexpr int MAX_LEVELS{2};
33using LinearizationIndex = uint32_t;
35using ClusterSetIndex = uint32_t;
38enum class QualityLevel
46 NEEDS_SPLIT_ACCEPTABLE,
74 uint32_t m_parent_count;
76 uint32_t m_parent_offset;
78 uint32_t m_children_count;
80 uint32_t m_children_offset;
92 TrimTxData* m_uf_parent;
102 friend class TxGraphImpl;
103 friend class BlockBuilderImpl;
111 ClusterSetIndex m_setindex{ClusterSetIndex(-1)};
120 virtual ~Cluster() =
default;
123 Cluster(
const Cluster&) =
delete;
124 Cluster& operator=(
const Cluster&) =
delete;
125 Cluster(Cluster&&) =
delete;
126 Cluster& operator=(Cluster&&) =
delete;
131 bool IsAcceptable(
bool after_split =
false) const noexcept
133 return m_quality == QualityLevel::ACCEPTABLE || m_quality == QualityLevel::OPTIMAL ||
134 (after_split && m_quality == QualityLevel::NEEDS_SPLIT_ACCEPTABLE);
137 bool IsOptimal() const noexcept
139 return m_quality == QualityLevel::OPTIMAL;
144 bool IsOversized() const noexcept {
return m_quality == QualityLevel::OVERSIZED_SINGLETON; }
146 bool NeedsSplitting() const noexcept
148 return m_quality == QualityLevel::NEEDS_SPLIT ||
149 m_quality == QualityLevel::NEEDS_SPLIT_ACCEPTABLE;
153 virtual DepGraphIndex GetMinIntendedTxCount() const noexcept = 0;
158 virtual
size_t TotalMemoryUsage() const noexcept = 0;
160 virtual
DepGraphIndex GetDepGraphIndexRange() const noexcept = 0;
162 virtual LinearizationIndex GetTxCount() const noexcept = 0;
164 virtual uint64_t GetTotalTxSize() const noexcept = 0;
166 virtual GraphIndex GetClusterEntry(
DepGraphIndex index) const noexcept = 0;
171 virtual
void AddDependencies(SetType parents,
DepGraphIndex child) noexcept = 0;
176 virtual
int GetLevel(const TxGraphImpl& graph) const noexcept = 0;
178 virtual
void UpdateMapping(
DepGraphIndex cluster_idx, GraphIndex graph_idx) noexcept = 0;
180 virtual
void Updated(TxGraphImpl& graph,
int level) noexcept = 0;
182 virtual Cluster* CopyToStaging(TxGraphImpl& graph) const noexcept = 0;
184 virtual
void GetConflicts(const TxGraphImpl& graph,
std::vector<Cluster*>&
out) const noexcept = 0;
187 virtual
void MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept = 0;
189 virtual
void Clear(TxGraphImpl& graph,
int level) noexcept = 0;
191 virtual
void MoveToMain(TxGraphImpl& graph) noexcept = 0;
193 virtual
void Compact() noexcept = 0;
199 virtual
void ApplyRemovals(TxGraphImpl& graph,
int level,
std::span<GraphIndex>& to_remove) noexcept = 0;
202 [[nodiscard]] virtual
bool Split(TxGraphImpl& graph,
int level) noexcept = 0;
204 virtual
void Merge(TxGraphImpl& graph,
int level, Cluster& cluster) noexcept = 0;
206 virtual
void ApplyDependencies(TxGraphImpl& graph,
int level,
std::span<
std::pair<GraphIndex, GraphIndex>> to_apply) noexcept = 0;
209 virtual
std::pair<uint64_t,
bool> Relinearize(TxGraphImpl& graph,
int level, uint64_t max_iters) noexcept = 0;
211 virtual
void AppendChunkFeerates(
std::vector<
FeeFrac>&
ret) const noexcept = 0;
215 virtual uint64_t AppendTrimData(
std::vector<TrimTxData>&
ret,
std::vector<
std::pair<GraphIndex, GraphIndex>>& deps) const noexcept = 0;
228 virtual
bool GetClusterRefs(TxGraphImpl& graph,
std::span<
TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept = 0;
232 virtual
void SetFee(TxGraphImpl& graph,
int level,
DepGraphIndex idx, int64_t
fee) noexcept = 0;
236 virtual
void SanityCheck(const TxGraphImpl& graph,
int level) const = 0;
241class GenericClusterImpl final : public Cluster
243 friend class TxGraphImpl;
249 std::vector<GraphIndex> m_mapping;
252 std::vector<DepGraphIndex> m_linearization;
258 static constexpr DepGraphIndex MAX_TX_COUNT{SetType::Size()};
260 GenericClusterImpl() noexcept = delete;
262 explicit GenericClusterImpl(uint64_t
sequence) noexcept;
264 size_t TotalMemoryUsage() const noexcept final;
265 constexpr
DepGraphIndex GetMinIntendedTxCount() const noexcept final {
return MIN_INTENDED_TX_COUNT; }
266 constexpr DepGraphIndex GetMaxTxCount() const noexcept final {
return MAX_TX_COUNT; }
268 LinearizationIndex GetTxCount() const noexcept final {
return m_linearization.size(); }
269 uint64_t GetTotalTxSize() const noexcept final;
270 GraphIndex GetClusterEntry(
DepGraphIndex index) const noexcept final {
return m_mapping[index]; }
272 void AddDependencies(SetType parents,
DepGraphIndex child)
noexcept final;
273 void ExtractTransactions(
const std::function<
void (
DepGraphIndex, GraphIndex,
FeePerWeight, SetType)>& visit_fn)
noexcept final;
274 int GetLevel(
const TxGraphImpl& graph)
const noexcept final;
275 void UpdateMapping(
DepGraphIndex cluster_idx, GraphIndex graph_idx)
noexcept final { m_mapping[cluster_idx] = graph_idx; }
276 void Updated(TxGraphImpl& graph,
int level)
noexcept final;
277 Cluster* CopyToStaging(TxGraphImpl& graph)
const noexcept final;
278 void GetConflicts(
const TxGraphImpl& graph, std::vector<Cluster*>&
out)
const noexcept final;
279 void MakeStagingTransactionsMissing(TxGraphImpl& graph)
noexcept final;
280 void Clear(TxGraphImpl& graph,
int level)
noexcept final;
281 void MoveToMain(TxGraphImpl& graph)
noexcept final;
282 void Compact() noexcept final;
283 void ApplyRemovals(TxGraphImpl& graph,
int level,
std::span<GraphIndex>& to_remove) noexcept final;
284 [[nodiscard]]
bool Split(TxGraphImpl& graph,
int level) noexcept final;
285 void Merge(TxGraphImpl& graph,
int level, Cluster& cluster) noexcept final;
286 void ApplyDependencies(TxGraphImpl& graph,
int level,
std::span<
std::pair<GraphIndex, GraphIndex>> to_apply) noexcept final;
287 std::pair<uint64_t,
bool> Relinearize(TxGraphImpl& graph,
int level, uint64_t max_iters) noexcept final;
288 void AppendChunkFeerates(
std::vector<
FeeFrac>&
ret) const noexcept final;
289 uint64_t AppendTrimData(
std::vector<TrimTxData>&
ret,
std::vector<
std::pair<GraphIndex, GraphIndex>>& deps) const noexcept final;
292 bool GetClusterRefs(TxGraphImpl& graph,
std::span<
TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept final;
294 void SetFee(TxGraphImpl& graph,
int level,
DepGraphIndex idx, int64_t
fee) noexcept final;
295 void SanityCheck(const TxGraphImpl& graph,
int level) const final;
299class SingletonClusterImpl final : public Cluster
301 friend class TxGraphImpl;
306 static constexpr auto NO_GRAPH_INDEX = GraphIndex(-1);
308 GraphIndex m_graph_index = NO_GRAPH_INDEX;
316 SingletonClusterImpl() noexcept = delete;
318 explicit SingletonClusterImpl(uint64_t
sequence) noexcept : Cluster(
sequence) {}
320 size_t TotalMemoryUsage() const noexcept final;
321 constexpr
DepGraphIndex GetMinIntendedTxCount() const noexcept final {
return MIN_INTENDED_TX_COUNT; }
322 constexpr DepGraphIndex GetMaxTxCount() const noexcept final {
return MAX_TX_COUNT; }
323 LinearizationIndex GetTxCount() const noexcept final {
return m_graph_index != NO_GRAPH_INDEX; }
324 DepGraphIndex GetDepGraphIndexRange() const noexcept final {
return GetTxCount(); }
325 uint64_t GetTotalTxSize() const noexcept final {
return GetTxCount() ? m_feerate.
size : 0; }
326 GraphIndex GetClusterEntry(
DepGraphIndex index)
const noexcept final {
Assume(index == 0);
Assume(GetTxCount());
return m_graph_index; }
328 void AddDependencies(SetType parents,
DepGraphIndex child)
noexcept final;
329 void ExtractTransactions(
const std::function<
void (
DepGraphIndex, GraphIndex,
FeePerWeight, SetType)>& visit_fn)
noexcept final;
330 int GetLevel(
const TxGraphImpl& graph)
const noexcept final;
331 void UpdateMapping(
DepGraphIndex cluster_idx, GraphIndex graph_idx)
noexcept final {
Assume(cluster_idx == 0); m_graph_index = graph_idx; }
332 void Updated(TxGraphImpl& graph,
int level)
noexcept final;
333 Cluster* CopyToStaging(TxGraphImpl& graph)
const noexcept final;
334 void GetConflicts(
const TxGraphImpl& graph, std::vector<Cluster*>&
out)
const noexcept final;
335 void MakeStagingTransactionsMissing(TxGraphImpl& graph)
noexcept final;
336 void Clear(TxGraphImpl& graph,
int level)
noexcept final;
337 void MoveToMain(TxGraphImpl& graph)
noexcept final;
338 void Compact() noexcept final;
339 void ApplyRemovals(TxGraphImpl& graph,
int level,
std::span<GraphIndex>& to_remove) noexcept final;
340 [[nodiscard]]
bool Split(TxGraphImpl& graph,
int level) noexcept final;
341 void Merge(TxGraphImpl& graph,
int level, Cluster& cluster) noexcept final;
342 void ApplyDependencies(TxGraphImpl& graph,
int level,
std::span<
std::pair<GraphIndex, GraphIndex>> to_apply) noexcept final;
343 std::pair<uint64_t,
bool> Relinearize(TxGraphImpl& graph,
int level, uint64_t max_iters) noexcept final;
344 void AppendChunkFeerates(
std::vector<
FeeFrac>&
ret) const noexcept final;
345 uint64_t AppendTrimData(
std::vector<TrimTxData>&
ret,
std::vector<
std::pair<GraphIndex, GraphIndex>>& deps) const noexcept final;
348 bool GetClusterRefs(TxGraphImpl& graph,
std::span<
TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept final;
350 void SetFee(TxGraphImpl& graph,
int level,
DepGraphIndex idx, int64_t
fee) noexcept final;
351 void SanityCheck(const TxGraphImpl& graph,
int level) const final;
377class TxGraphImpl final : public
TxGraph
379 friend class Cluster;
380 friend class SingletonClusterImpl;
381 friend class GenericClusterImpl;
382 friend class BlockBuilderImpl;
389 const uint64_t m_max_cluster_size;
392 const uint64_t m_acceptable_iters;
398 uint32_t m_cluster_offset;
400 uint32_t m_cluster_count;
402 uint32_t m_deps_offset;
404 uint32_t m_deps_count;
411 std::vector<GroupEntry> m_groups;
413 std::vector<Cluster*> m_group_clusters;
420 std::array<std::vector<std::unique_ptr<Cluster>>, int(
QualityLevel::NONE)> m_clusters;
422 std::vector<GraphIndex> m_to_remove;
425 std::vector<std::pair<GraphIndex, GraphIndex>> m_deps_to_add;
427 std::optional<GroupData> m_group_data = GroupData{};
431 std::vector<GraphIndex> m_removed;
434 GraphIndex m_txcount{0};
436 GraphIndex m_txcount_oversized{0};
438 std::optional<bool> m_oversized{
false};
441 size_t m_cluster_usage{0};
443 ClusterSet() noexcept = default;
447 ClusterSet m_main_clusterset;
449 std::optional<ClusterSet> m_staging_clusterset;
451 uint64_t m_next_sequence_counter{0};
457 mutable GraphIndex m_graph_index;
459 LinearizationIndex m_chunk_count;
461 ChunkData(GraphIndex graph_index, LinearizationIndex chunk_count) noexcept :
462 m_graph_index{graph_index}, m_chunk_count{chunk_count} {}
466 static std::strong_ordering CompareClusters(Cluster* a, Cluster* b)
noexcept
469 if (a ==
nullptr || b ==
nullptr) {
470 return (a !=
nullptr) <=> (b !=
nullptr);
473 Assume(a == b || a->m_sequence != b->m_sequence);
474 return a->m_sequence <=> b->m_sequence;
478 std::strong_ordering CompareMainTransactions(GraphIndex a, GraphIndex b)
const noexcept
480 Assume(a < m_entries.size() && b < m_entries.size());
481 const auto& entry_a = m_entries[a];
482 const auto& entry_b = m_entries[b];
484 auto feerate_cmp = FeeRateCompare(entry_b.m_main_chunk_feerate, entry_a.m_main_chunk_feerate);
485 if (feerate_cmp < 0)
return std::strong_ordering::less;
486 if (feerate_cmp > 0)
return std::strong_ordering::greater;
488 const auto& locator_a = entry_a.m_locator[0];
489 const auto& locator_b = entry_b.m_locator[0];
490 Assume(locator_a.IsPresent() && locator_b.IsPresent());
491 if (locator_a.cluster != locator_b.cluster) {
492 return CompareClusters(locator_a.cluster, locator_b.cluster);
495 return entry_a.m_main_lin_index <=> entry_b.m_main_lin_index;
501 const TxGraphImpl*
const m_graph;
503 explicit ChunkOrder(
const TxGraphImpl* graph) : m_graph(graph) {}
505 bool operator()(
const ChunkData& a,
const ChunkData& b)
const noexcept
507 return m_graph->CompareMainTransactions(a.m_graph_index, b.m_graph_index) < 0;
512 using ChunkIndex = std::set<ChunkData, ChunkOrder>;
516 ChunkIndex m_main_chunkindex;
518 size_t m_main_chunkindex_observers{0};
520 std::vector<ChunkIndex::node_type> m_main_chunkindex_discarded;
555 Cluster* cluster{
nullptr};
560 void SetMissing() noexcept { cluster =
nullptr; index = 0; }
562 void SetRemoved() noexcept { cluster =
nullptr; index =
DepGraphIndex(-1); }
564 void SetPresent(Cluster* c,
DepGraphIndex i)
noexcept { cluster = c; index = i; }
566 bool IsMissing() const noexcept {
return cluster ==
nullptr && index == 0; }
568 bool IsRemoved() const noexcept {
return cluster ==
nullptr && index ==
DepGraphIndex(-1); }
570 bool IsPresent() const noexcept {
return cluster !=
nullptr; }
580 ChunkIndex::iterator m_main_chunkindex_iterator;
582 Locator m_locator[MAX_LEVELS];
586 LinearizationIndex m_main_lin_index;
590 std::vector<Entry> m_entries;
593 std::vector<GraphIndex> m_unlinked;
597 explicit TxGraphImpl(
DepGraphIndex max_cluster_count, uint64_t max_cluster_size, uint64_t acceptable_iters) noexcept :
598 m_max_cluster_count(max_cluster_count),
599 m_max_cluster_size(max_cluster_size),
600 m_acceptable_iters(acceptable_iters),
601 m_main_chunkindex(ChunkOrder(
this))
603 Assume(max_cluster_count >= 1);
608 ~TxGraphImpl() noexcept;
611 TxGraphImpl(const TxGraphImpl&) = delete;
612 TxGraphImpl& operator=(const TxGraphImpl&) = delete;
613 TxGraphImpl(TxGraphImpl&&) = delete;
614 TxGraphImpl& operator=(TxGraphImpl&&) = delete;
619 void SwapIndexes(GraphIndex a, GraphIndex b) noexcept;
622 Cluster* FindCluster(GraphIndex idx,
int level) const noexcept {
return FindClusterAndLevel(idx, level).first; }
624 std::pair<Cluster*, int> FindClusterAndLevel(GraphIndex idx,
int level)
const noexcept;
626 std::unique_ptr<Cluster> ExtractCluster(
int level, QualityLevel quality, ClusterSetIndex setindex)
noexcept;
628 void DeleteCluster(Cluster& cluster,
int level)
noexcept;
630 ClusterSetIndex InsertCluster(
int level, std::unique_ptr<Cluster>&& cluster, QualityLevel quality)
noexcept;
632 void SetClusterQuality(
int level, QualityLevel old_quality, ClusterSetIndex old_index, QualityLevel new_quality)
noexcept;
634 int GetTopLevel() const noexcept {
return m_staging_clusterset.has_value(); }
636 int GetSpecifiedLevel(
Level level)
const noexcept {
return level == Level::TOP && m_staging_clusterset.has_value(); }
638 ClusterSet& GetClusterSet(
int level)
noexcept;
639 const ClusterSet& GetClusterSet(
int level)
const noexcept;
643 void ClearLocator(
int level, GraphIndex index,
bool oversized_tx)
noexcept;
645 std::vector<Cluster*> GetConflicts() const noexcept;
647 void ClearChunkData(Entry& entry) noexcept;
649 void CreateChunkData(GraphIndex idx, LinearizationIndex chunk_count) noexcept;
651 std::unique_ptr<GenericClusterImpl> CreateEmptyGenericCluster() noexcept
653 return std::make_unique<GenericClusterImpl>(m_next_sequence_counter++);
656 std::unique_ptr<SingletonClusterImpl> CreateEmptySingletonCluster() noexcept
658 return std::make_unique<SingletonClusterImpl>(m_next_sequence_counter++);
662 std::unique_ptr<Cluster> CreateEmptyCluster(
DepGraphIndex tx_count)
noexcept
664 if (tx_count >= SingletonClusterImpl::MIN_INTENDED_TX_COUNT && tx_count <= SingletonClusterImpl::MAX_TX_COUNT) {
665 return CreateEmptySingletonCluster();
667 if (tx_count >= GenericClusterImpl::MIN_INTENDED_TX_COUNT && tx_count <= GenericClusterImpl::MAX_TX_COUNT) {
668 return CreateEmptyGenericCluster();
677 void UpdateRef(GraphIndex idx, Ref& new_location)
noexcept final
679 auto& entry = m_entries[idx];
680 Assume(entry.m_ref !=
nullptr);
681 entry.m_ref = &new_location;
685 void UnlinkRef(GraphIndex idx)
noexcept final
687 auto& entry = m_entries[idx];
688 Assume(entry.m_ref !=
nullptr);
689 Assume(m_main_chunkindex_observers == 0 || !entry.m_locator[0].IsPresent());
690 entry.m_ref =
nullptr;
693 bool exists_anywhere{
false};
695 for (
int level = 0; level <= GetTopLevel(); ++level) {
696 if (entry.m_locator[level].IsPresent()) {
697 exists_anywhere =
true;
699 }
else if (entry.m_locator[level].IsRemoved()) {
703 auto& clusterset = GetClusterSet(level);
704 clusterset.m_to_remove.push_back(idx);
706 clusterset.m_group_data = std::nullopt;
712 if (level == GetTopLevel() && clusterset.m_oversized ==
true) {
713 clusterset.m_oversized = std::nullopt;
717 m_unlinked.push_back(idx);
718 if (!exists_anywhere) Compact();
725 void Compact() noexcept;
729 Cluster* PullIn(Cluster* cluster,
int level) noexcept;
732 void ApplyRemovals(
int up_to_level) noexcept;
734 void Split(Cluster& cluster,
int level) noexcept;
736 void SplitAll(
int up_to_level) noexcept;
738 void GroupClusters(
int level) noexcept;
740 void Merge(
std::span<Cluster*> to_merge,
int level) noexcept;
742 void ApplyDependencies(
int level) noexcept;
744 void MakeAcceptable(Cluster& cluster,
int level) noexcept;
746 void MakeAllAcceptable(
int level) noexcept;
750 Ref AddTransaction(const
FeePerWeight& feerate) noexcept final;
751 void RemoveTransaction(const Ref& arg) noexcept final;
752 void AddDependency(const Ref& parent, const Ref& child) noexcept final;
753 void SetTransactionFee(const Ref&, int64_t
fee) noexcept final;
755 bool DoWork(uint64_t iters) noexcept final;
757 void StartStaging() noexcept final;
758 void CommitStaging() noexcept final;
759 void AbortStaging() noexcept final;
760 bool HaveStaging() const noexcept final {
return m_staging_clusterset.has_value(); }
762 bool Exists(
const Ref& arg,
Level level)
noexcept final;
763 FeePerWeight GetMainChunkFeerate(
const Ref& arg)
noexcept final;
764 FeePerWeight GetIndividualFeerate(
const Ref& arg)
noexcept final;
765 std::vector<Ref*> GetCluster(
const Ref& arg,
Level level)
noexcept final;
766 std::vector<Ref*> GetAncestors(
const Ref& arg,
Level level)
noexcept final;
767 std::vector<Ref*> GetDescendants(
const Ref& arg,
Level level)
noexcept final;
768 std::vector<Ref*> GetAncestorsUnion(std::span<const Ref* const>
args,
Level level)
noexcept final;
769 std::vector<Ref*> GetDescendantsUnion(std::span<const Ref* const>
args,
Level level)
noexcept final;
770 GraphIndex GetTransactionCount(
Level level)
noexcept final;
771 bool IsOversized(
Level level)
noexcept final;
772 std::strong_ordering CompareMainOrder(
const Ref& a,
const Ref& b)
noexcept final;
773 GraphIndex CountDistinctClusters(std::span<const Ref* const> refs,
Level level)
noexcept final;
774 std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>> GetMainStagingDiagrams() noexcept final;
775 std::vector<Ref*> Trim() noexcept final;
777 std::unique_ptr<BlockBuilder> GetBlockBuilder() noexcept final;
780 size_t GetMainMemoryUsage() noexcept final;
782 void SanityCheck() const final;
785TxGraphImpl::ClusterSet& TxGraphImpl::GetClusterSet(
int level) noexcept
787 if (level == 0)
return m_main_clusterset;
789 Assume(m_staging_clusterset.has_value());
790 return *m_staging_clusterset;
793const TxGraphImpl::ClusterSet& TxGraphImpl::GetClusterSet(
int level)
const noexcept
795 if (level == 0)
return m_main_clusterset;
797 Assume(m_staging_clusterset.has_value());
798 return *m_staging_clusterset;
806 TxGraphImpl*
const m_graph;
808 std::unordered_set<uint64_t> m_excluded_clusters;
810 TxGraphImpl::ChunkIndex::const_iterator m_cur_iter;
813 Cluster* m_cur_cluster;
815 bool m_known_end_of_cluster;
818 void Next() noexcept;
822 BlockBuilderImpl(TxGraphImpl& graph) noexcept;
825 ~BlockBuilderImpl() final;
827 void Include() noexcept final;
828 void Skip() noexcept final;
831void TxGraphImpl::ClearChunkData(Entry& entry) noexcept
833 if (entry.m_main_chunkindex_iterator != m_main_chunkindex.end()) {
834 Assume(m_main_chunkindex_observers == 0);
837 m_main_chunkindex_discarded.emplace_back(m_main_chunkindex.extract(entry.m_main_chunkindex_iterator));
838 entry.m_main_chunkindex_iterator = m_main_chunkindex.end();
842void TxGraphImpl::CreateChunkData(GraphIndex idx, LinearizationIndex chunk_count)
noexcept
844 auto& entry = m_entries[idx];
845 if (!m_main_chunkindex_discarded.empty()) {
847 auto&
node = m_main_chunkindex_discarded.back().value();
848 node.m_graph_index = idx;
849 node.m_chunk_count = chunk_count;
850 auto insert_result = m_main_chunkindex.insert(std::move(m_main_chunkindex_discarded.back()));
851 Assume(insert_result.inserted);
852 entry.m_main_chunkindex_iterator = insert_result.position;
853 m_main_chunkindex_discarded.pop_back();
856 auto emplace_result = m_main_chunkindex.emplace(idx, chunk_count);
857 Assume(emplace_result.second);
858 entry.m_main_chunkindex_iterator = emplace_result.first;
862size_t GenericClusterImpl::TotalMemoryUsage() const noexcept
871 sizeof(std::unique_ptr<Cluster>);
874size_t SingletonClusterImpl::TotalMemoryUsage() const noexcept
879 sizeof(std::unique_ptr<Cluster>);
882uint64_t GenericClusterImpl::GetTotalTxSize() const noexcept
885 for (
auto i : m_linearization) {
893 Assume(graph_idx != GraphIndex(-1));
895 m_mapping.push_back(graph_idx);
896 m_linearization.push_back(
ret);
903 m_graph_index = graph_idx;
908void GenericClusterImpl::AddDependencies(SetType parents,
DepGraphIndex child)
noexcept
913void SingletonClusterImpl::AddDependencies(SetType parents,
DepGraphIndex child)
noexcept
917 Assume(parents == SetType{} || parents == SetType::Fill(0));
920void GenericClusterImpl::ExtractTransactions(
const std::function<
void (
DepGraphIndex, GraphIndex,
FeePerWeight, SetType)>& visit_fn)
noexcept
922 for (
auto pos : m_linearization) {
927 m_linearization.clear();
931void SingletonClusterImpl::ExtractTransactions(
const std::function<
void (
DepGraphIndex, GraphIndex,
FeePerWeight, SetType)>& visit_fn)
noexcept
934 visit_fn(0, m_graph_index, m_feerate, SetType{});
935 m_graph_index = NO_GRAPH_INDEX;
939int GenericClusterImpl::GetLevel(
const TxGraphImpl& graph)
const noexcept
942 if (!
Assume(!m_linearization.empty()))
return -1;
945 const auto& entry = graph.m_entries[m_mapping[m_linearization.front()]];
947 for (
int level = 0; level < MAX_LEVELS; ++level) {
948 if (entry.m_locator[level].cluster ==
this)
return level;
956int SingletonClusterImpl::GetLevel(
const TxGraphImpl& graph)
const noexcept
959 if (!
Assume(GetTxCount()))
return -1;
962 const auto& entry = graph.m_entries[m_graph_index];
964 for (
int level = 0; level < MAX_LEVELS; ++level) {
965 if (entry.m_locator[level].cluster ==
this)
return level;
973void TxGraphImpl::ClearLocator(
int level, GraphIndex idx,
bool oversized_tx)
noexcept
975 auto& entry = m_entries[idx];
976 auto& clusterset = GetClusterSet(level);
977 Assume(entry.m_locator[level].IsPresent());
979 if (level == 0 || !entry.m_locator[level - 1].IsPresent()) {
980 entry.m_locator[level].SetMissing();
982 entry.m_locator[level].SetRemoved();
983 clusterset.m_removed.push_back(idx);
986 --clusterset.m_txcount;
987 clusterset.m_txcount_oversized -= oversized_tx;
989 if (level == 0 && GetTopLevel() == 1) {
990 if (entry.m_locator[1].IsRemoved()) {
991 entry.m_locator[1].SetMissing();
992 }
else if (!entry.m_locator[1].IsPresent()) {
993 --m_staging_clusterset->m_txcount;
994 m_staging_clusterset->m_txcount_oversized -= oversized_tx;
997 if (level == 0) ClearChunkData(entry);
1000void GenericClusterImpl::Updated(TxGraphImpl& graph,
int level)
noexcept
1004 auto& entry = graph.m_entries[m_mapping[idx]];
1007 if (level == 0) graph.ClearChunkData(entry);
1008 entry.m_locator[level].SetPresent(
this, idx);
1015 if (level == 0 && IsAcceptable()) {
1017 LinearizationIndex lin_idx{0};
1019 for (
unsigned chunk_idx = 0; chunk_idx < chunking.NumChunksLeft(); ++chunk_idx) {
1020 auto chunk = chunking.GetChunk(chunk_idx);
1021 auto chunk_count = chunk.transactions.Count();
1026 GraphIndex graph_idx = m_mapping[idx];
1027 auto& entry = graph.m_entries[graph_idx];
1028 entry.m_main_lin_index = lin_idx++;
1030 Assume(chunk.transactions[idx]);
1031 chunk.transactions.Reset(idx);
1032 if (chunk.transactions.None()) {
1034 if (chunk_count == 1 && chunk_idx + 1 == chunking.NumChunksLeft()) {
1038 chunk_count = LinearizationIndex(-1);
1040 graph.CreateChunkData(graph_idx, chunk_count);
1048void SingletonClusterImpl::Updated(TxGraphImpl& graph,
int level)
noexcept
1051 if (GetTxCount() == 0)
return;
1053 auto& entry = graph.m_entries[m_graph_index];
1056 if (level == 0) graph.ClearChunkData(entry);
1057 entry.m_locator[level].SetPresent(
this, 0);
1060 if (level == 0 && IsAcceptable()) {
1061 entry.m_main_lin_index = 0;
1062 entry.m_main_chunk_feerate = m_feerate;
1065 graph.CreateChunkData(m_graph_index, LinearizationIndex(-1));
1069void GenericClusterImpl::GetConflicts(
const TxGraphImpl& graph, std::vector<Cluster*>&
out)
const noexcept
1071 for (
auto i : m_linearization) {
1072 auto& entry = graph.m_entries[m_mapping[i]];
1075 if (entry.m_locator[0].IsPresent()) {
1076 out.push_back(entry.m_locator[0].cluster);
1081void SingletonClusterImpl::GetConflicts(
const TxGraphImpl& graph, std::vector<Cluster*>&
out)
const noexcept
1084 if (GetTxCount() == 0)
return;
1086 auto& entry = graph.m_entries[m_graph_index];
1089 if (entry.m_locator[0].IsPresent()) {
1090 out.push_back(entry.m_locator[0].cluster);
1094std::vector<Cluster*> TxGraphImpl::GetConflicts() const noexcept
1096 Assume(GetTopLevel() == 1);
1097 auto& clusterset = GetClusterSet(1);
1098 std::vector<Cluster*>
ret;
1100 for (
auto i : clusterset.m_removed) {
1101 auto& entry = m_entries[i];
1102 if (entry.m_locator[0].IsPresent()) {
1103 ret.push_back(entry.m_locator[0].cluster);
1108 auto& clusters = clusterset.m_clusters[quality];
1109 for (
const auto& cluster : clusters) {
1110 cluster->GetConflicts(*
this,
ret);
1114 std::sort(
ret.begin(),
ret.end(), [](Cluster* a, Cluster* b)
noexcept { return CompareClusters(a, b) < 0; });
1115 ret.erase(std::unique(
ret.begin(),
ret.end()),
ret.end());
1119Cluster* GenericClusterImpl::CopyToStaging(TxGraphImpl& graph)
const noexcept
1122 auto ret = graph.CreateEmptyGenericCluster();
1123 auto ptr =
ret.get();
1125 ptr->m_depgraph = m_depgraph;
1126 ptr->m_mapping = m_mapping;
1127 ptr->m_linearization = m_linearization;
1129 graph.InsertCluster(1, std::move(
ret), m_quality);
1131 ptr->Updated(graph, 1);
1133 graph.GetClusterSet(1).m_cluster_usage += ptr->TotalMemoryUsage();
1137Cluster* SingletonClusterImpl::CopyToStaging(TxGraphImpl& graph)
const noexcept
1140 auto ret = graph.CreateEmptySingletonCluster();
1141 auto ptr =
ret.get();
1143 ptr->m_graph_index = m_graph_index;
1144 ptr->m_feerate = m_feerate;
1146 graph.InsertCluster(1, std::move(
ret), m_quality);
1148 ptr->Updated(graph, 1);
1150 graph.GetClusterSet(1).m_cluster_usage += ptr->TotalMemoryUsage();
1154void GenericClusterImpl::ApplyRemovals(TxGraphImpl& graph,
int level, std::span<GraphIndex>& to_remove)
noexcept
1157 Assume(!to_remove.empty());
1159 graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
1161 GraphIndex idx = to_remove.front();
1162 Assume(idx < graph.m_entries.size());
1163 auto& entry = graph.m_entries[idx];
1164 auto& locator = entry.m_locator[level];
1166 if (locator.cluster !=
this)
break;
1168 todo.Set(locator.index);
1172 m_mapping[locator.index] = GraphIndex(-1);
1175 entry.m_main_lin_index = LinearizationIndex(-1);
1178 graph.ClearLocator(level, idx, m_quality == QualityLevel::OVERSIZED_SINGLETON);
1179 to_remove = to_remove.subspan(1);
1180 }
while(!to_remove.empty());
1182 auto quality = m_quality;
1190 while (!m_linearization.empty() && todo[m_linearization.back()]) {
1191 todo.Reset(m_linearization.back());
1192 m_linearization.pop_back();
1197 if (IsAcceptable(
true)) {
1198 quality = QualityLevel::NEEDS_SPLIT_ACCEPTABLE;
1200 quality = QualityLevel::NEEDS_SPLIT;
1204 m_linearization.erase(std::remove_if(
1205 m_linearization.begin(),
1206 m_linearization.end(),
1207 [&](
auto pos) { return todo[pos]; }), m_linearization.end());
1208 quality = QualityLevel::NEEDS_SPLIT;
1211 graph.GetClusterSet(level).m_cluster_usage += TotalMemoryUsage();
1212 graph.SetClusterQuality(level, m_quality, m_setindex, quality);
1213 Updated(graph, level);
1216void SingletonClusterImpl::ApplyRemovals(TxGraphImpl& graph,
int level, std::span<GraphIndex>& to_remove)
noexcept
1219 Assume(!to_remove.empty());
1221 Assume(to_remove.front() == m_graph_index);
1225 to_remove = to_remove.subspan(1);
1226 }
while (!to_remove.empty() && to_remove.front() == m_graph_index);
1228 graph.ClearLocator(level, m_graph_index, m_quality == QualityLevel::OVERSIZED_SINGLETON);
1229 m_graph_index = NO_GRAPH_INDEX;
1230 graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::NEEDS_SPLIT);
1235void GenericClusterImpl::Clear(TxGraphImpl& graph,
int level)
noexcept
1238 graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
1239 for (
auto i : m_linearization) {
1240 graph.ClearLocator(level, m_mapping[i], m_quality == QualityLevel::OVERSIZED_SINGLETON);
1243 m_linearization.clear();
1247void SingletonClusterImpl::Clear(TxGraphImpl& graph,
int level)
noexcept
1250 graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
1251 graph.ClearLocator(level, m_graph_index, m_quality == QualityLevel::OVERSIZED_SINGLETON);
1252 m_graph_index = NO_GRAPH_INDEX;
1255void GenericClusterImpl::MoveToMain(TxGraphImpl& graph)
noexcept
1257 for (
auto i : m_linearization) {
1258 GraphIndex idx = m_mapping[i];
1259 auto& entry = graph.m_entries[idx];
1260 entry.m_locator[1].SetMissing();
1262 auto quality = m_quality;
1264 graph.GetClusterSet(1).m_cluster_usage -= TotalMemoryUsage();
1265 graph.GetClusterSet(0).m_cluster_usage += TotalMemoryUsage();
1267 auto cluster = graph.ExtractCluster(1, quality, m_setindex);
1268 graph.InsertCluster(0, std::move(cluster), quality);
1272void SingletonClusterImpl::MoveToMain(TxGraphImpl& graph)
noexcept
1275 auto& entry = graph.m_entries[m_graph_index];
1276 entry.m_locator[1].SetMissing();
1278 auto quality = m_quality;
1279 graph.GetClusterSet(1).m_cluster_usage -= TotalMemoryUsage();
1280 auto cluster = graph.ExtractCluster(1, quality, m_setindex);
1281 graph.InsertCluster(0, std::move(cluster), quality);
1282 graph.GetClusterSet(0).m_cluster_usage += TotalMemoryUsage();
1286void GenericClusterImpl::Compact() noexcept
1288 m_linearization.shrink_to_fit();
1289 m_mapping.shrink_to_fit();
1293void SingletonClusterImpl::Compact() noexcept
1298void GenericClusterImpl::AppendChunkFeerates(std::vector<FeeFrac>&
ret)
const noexcept
1301 ret.reserve(
ret.size() + chunk_feerates.size());
1302 ret.insert(
ret.end(), chunk_feerates.begin(), chunk_feerates.end());
1305void SingletonClusterImpl::AppendChunkFeerates(std::vector<FeeFrac>&
ret)
const noexcept
1308 ret.push_back(m_feerate);
1312uint64_t GenericClusterImpl::AppendTrimData(std::vector<TrimTxData>&
ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps)
const noexcept
1315 LinearizationIndex pos{0};
1317 auto prev_index = GraphIndex(-1);
1319 for (
unsigned i = 0; i < linchunking.NumChunksLeft(); ++i) {
1320 const auto& [chunk, chunk_feerate] = linchunking.GetChunk(i);
1322 auto chunk_tx_count = chunk.Count();
1323 for (
unsigned j = 0; j < chunk_tx_count; ++j) {
1324 auto cluster_idx = m_linearization[pos];
1326 Assume(chunk[cluster_idx]);
1328 auto& entry =
ret.emplace_back();
1330 entry.m_index = m_mapping[cluster_idx];
1333 if (pos != 0) deps.emplace_back(prev_index, entry.m_index);
1334 prev_index = entry.m_index;
1335 entry.m_tx_size = m_depgraph.
FeeRate(cluster_idx).
size;
1336 size += entry.m_tx_size;
1343uint64_t SingletonClusterImpl::AppendTrimData(std::vector<TrimTxData>&
ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps)
const noexcept
1345 if (!GetTxCount())
return 0;
1346 auto& entry =
ret.emplace_back();
1347 entry.m_chunk_feerate = m_feerate;
1348 entry.m_index = m_graph_index;
1349 entry.m_tx_size = m_feerate.
size;
1350 return m_feerate.
size;
1356 Assume(NeedsSplitting());
1358 QualityLevel new_quality = IsAcceptable(
true) ? QualityLevel::ACCEPTABLE
1359 : QualityLevel::NEEDS_RELINEARIZE;
1366 if (new_quality == QualityLevel::ACCEPTABLE) {
1373 std::vector<std::pair<Cluster*, DepGraphIndex>> remap(m_depgraph.
PositionRange());
1374 std::vector<Cluster*> new_clusters;
1377 while (todo.Any()) {
1379 auto component_size = component.Count();
1380 auto split_quality = component_size <= 2 ? QualityLevel::OPTIMAL : new_quality;
1381 if (first && component == todo && SetType::Fill(component_size) == component && component_size >= MIN_INTENDED_TX_COUNT) {
1388 graph.SetClusterQuality(level, m_quality, m_setindex, split_quality);
1391 Updated(graph, level);
1396 auto new_cluster = graph.CreateEmptyCluster(component_size);
1397 new_clusters.push_back(new_cluster.get());
1400 for (
auto i : component) {
1403 graph.InsertCluster(level, std::move(new_cluster), split_quality);
1407 graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
1409 for (
auto i : m_linearization) {
1411 Cluster* new_cluster = remap[i].first;
1416 for (
auto i : m_linearization) {
1418 Cluster* new_cluster = remap[i].first;
1420 SetType new_parents;
1421 for (
auto par : m_depgraph.
GetReducedParents(i)) new_parents.Set(remap[par].second);
1422 new_cluster->AddDependencies(new_parents, remap[i].second);
1425 for (Cluster* new_cluster : new_clusters) {
1426 new_cluster->Updated(graph, level);
1427 new_cluster->Compact();
1428 graph.GetClusterSet(level).m_cluster_usage += new_cluster->TotalMemoryUsage();
1433 m_linearization.clear();
1439 Assume(NeedsSplitting());
1440 if (GetTxCount() == 0) {
1442 graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
1446 graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::OPTIMAL);
1447 Updated(graph, level);
1452void GenericClusterImpl::Merge(TxGraphImpl& graph,
int level, Cluster& other)
noexcept
1455 std::vector<DepGraphIndex> remap(other.GetDepGraphIndexRange());
1457 other.ExtractTransactions([&](
DepGraphIndex pos, GraphIndex idx,
FeePerWeight feerate, SetType other_parents)
noexcept {
1462 Assume(new_pos == m_mapping.size());
1463 remap[pos] = new_pos;
1464 m_mapping.push_back(idx);
1465 m_linearization.push_back(new_pos);
1470 for (
auto par : other_parents) {
1471 parents.Set(remap[par]);
1477 auto& entry = graph.m_entries[idx];
1480 if (level == 0) graph.ClearChunkData(entry);
1481 entry.m_locator[level].SetPresent(
this, new_pos);
1485void SingletonClusterImpl::Merge(TxGraphImpl& graph,
int level, Cluster& other_abstract)
noexcept
1492void GenericClusterImpl::ApplyDependencies(TxGraphImpl& graph,
int level, std::span<std::pair<GraphIndex, GraphIndex>> to_apply)
noexcept
1503 std::sort(to_apply.begin(), to_apply.end(), [](
auto& a,
auto& b) { return a.second < b.second; });
1505 auto it = to_apply.begin();
1506 while (it != to_apply.end()) {
1507 auto& first_child = graph.m_entries[it->second].m_locator[level];
1508 const auto child_idx = first_child.index;
1512 while (it != to_apply.end()) {
1513 auto& child = graph.m_entries[it->second].m_locator[level];
1514 auto& parent = graph.m_entries[it->first].m_locator[level];
1515 Assume(child.cluster ==
this && parent.cluster ==
this);
1516 if (child.index != child_idx)
break;
1517 parents.Set(parent.index);
1530 Assume(!NeedsSplitting());
1532 if (IsAcceptable()) {
1533 graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::NEEDS_RELINEARIZE);
1537 Updated(graph, level);
1540void SingletonClusterImpl::ApplyDependencies(TxGraphImpl& graph,
int level, std::span<std::pair<GraphIndex, GraphIndex>> to_apply)
noexcept
1543 for (
auto& [par, chl] : to_apply) {
1544 Assume(par == m_graph_index);
1545 Assume(chl == m_graph_index);
1549TxGraphImpl::~TxGraphImpl() noexcept
1553 for (
auto& entry : m_entries) {
1554 if (entry.m_ref !=
nullptr) {
1555 GetRefGraph(*entry.m_ref) =
nullptr;
1560std::unique_ptr<Cluster> TxGraphImpl::ExtractCluster(
int level, QualityLevel quality, ClusterSetIndex setindex)
noexcept
1564 auto& clusterset = GetClusterSet(level);
1565 auto& quality_clusters = clusterset.m_clusters[int(quality)];
1566 Assume(setindex < quality_clusters.size());
1569 std::unique_ptr<Cluster>
ret = std::move(quality_clusters[setindex]);
1571 ret->m_setindex = ClusterSetIndex(-1);
1574 auto max_setindex = quality_clusters.size() - 1;
1575 if (setindex != max_setindex) {
1577 quality_clusters.back()->m_setindex = setindex;
1578 quality_clusters[setindex] = std::move(quality_clusters.back());
1581 quality_clusters.pop_back();
1586ClusterSetIndex TxGraphImpl::InsertCluster(
int level, std::unique_ptr<Cluster>&& cluster, QualityLevel quality)
noexcept
1594 auto& clusterset = GetClusterSet(level);
1595 auto& quality_clusters = clusterset.m_clusters[int(quality)];
1596 ClusterSetIndex
ret = quality_clusters.size();
1597 cluster->m_quality = quality;
1598 cluster->m_setindex =
ret;
1599 quality_clusters.push_back(std::move(cluster));
1603void TxGraphImpl::SetClusterQuality(
int level, QualityLevel old_quality, ClusterSetIndex old_index, QualityLevel new_quality)
noexcept
1608 if (old_quality == new_quality)
return;
1610 auto cluster_ptr = ExtractCluster(level, old_quality, old_index);
1612 InsertCluster(level, std::move(cluster_ptr), new_quality);
1615void TxGraphImpl::DeleteCluster(Cluster& cluster,
int level)
noexcept
1618 auto cluster_ptr = ExtractCluster(level, cluster.m_quality, cluster.m_setindex);
1620 cluster_ptr.reset();
1623std::pair<Cluster*, int> TxGraphImpl::FindClusterAndLevel(GraphIndex idx,
int level)
const noexcept
1625 Assume(level >= 0 && level <= GetTopLevel());
1626 auto& entry = m_entries[idx];
1628 for (
int l = level; l >= 0; --l) {
1631 if (entry.m_locator[l].IsMissing())
continue;
1633 if (entry.m_locator[l].IsRemoved())
break;
1635 return {entry.m_locator[l].cluster, l};
1638 return {
nullptr, -1};
1641Cluster* TxGraphImpl::PullIn(Cluster* cluster,
int level)
noexcept
1643 int to_level = GetTopLevel();
1645 Assume(level <= to_level);
1650 MakeAcceptable(*cluster, level);
1651 cluster = cluster->CopyToStaging(*
this);
1656void TxGraphImpl::ApplyRemovals(
int up_to_level)
noexcept
1658 Assume(up_to_level >= 0 && up_to_level <= GetTopLevel());
1659 for (
int level = 0; level <= up_to_level; ++level) {
1660 auto& clusterset = GetClusterSet(level);
1661 auto& to_remove = clusterset.m_to_remove;
1663 if (to_remove.empty())
continue;
1666 for (GraphIndex index : to_remove) {
1667 auto [cluster, cluster_level] = FindClusterAndLevel(index, level);
1668 if (cluster !=
nullptr) PullIn(cluster, cluster_level);
1672 std::sort(to_remove.begin(), to_remove.end(), [&](GraphIndex a, GraphIndex b)
noexcept {
1673 Cluster* cluster_a = m_entries[a].m_locator[level].cluster;
1674 Cluster* cluster_b = m_entries[b].m_locator[level].cluster;
1675 return CompareClusters(cluster_a, cluster_b) < 0;
1678 std::span to_remove_span{to_remove};
1679 while (!to_remove_span.empty()) {
1680 Cluster* cluster = m_entries[to_remove_span.front()].m_locator[level].cluster;
1681 if (cluster !=
nullptr) {
1684 cluster->ApplyRemovals(*
this, level, to_remove_span);
1688 to_remove_span = to_remove_span.subspan(1);
1696void TxGraphImpl::SwapIndexes(GraphIndex a, GraphIndex b)
noexcept
1698 Assume(a < m_entries.size());
1699 Assume(b < m_entries.size());
1701 std::swap(m_entries[a], m_entries[b]);
1703 for (
int i = 0; i < 2; ++i) {
1704 GraphIndex idx = i ? b : a;
1705 Entry& entry = m_entries[idx];
1707 if (entry.m_ref) GetRefIndex(*entry.m_ref) = idx;
1709 if (entry.m_main_chunkindex_iterator != m_main_chunkindex.end()) {
1710 entry.m_main_chunkindex_iterator->m_graph_index = idx;
1714 for (
int level = 0; level < MAX_LEVELS; ++level) {
1715 Locator& locator = entry.m_locator[level];
1716 if (locator.IsPresent()) {
1717 locator.cluster->UpdateMapping(locator.index, idx);
1723void TxGraphImpl::Compact() noexcept
1727 if (!m_main_clusterset.m_deps_to_add.empty())
return;
1728 if (!m_main_clusterset.m_to_remove.empty())
return;
1729 Assume(m_main_clusterset.m_removed.empty());
1730 if (m_staging_clusterset.has_value()) {
1731 if (!m_staging_clusterset->m_deps_to_add.empty())
return;
1732 if (!m_staging_clusterset->m_to_remove.empty())
return;
1733 if (!m_staging_clusterset->m_removed.empty())
return;
1743 std::sort(m_unlinked.begin(), m_unlinked.end(), std::greater{});
1745 auto last = GraphIndex(-1);
1746 for (GraphIndex idx : m_unlinked) {
1753 Entry& entry = m_entries[idx];
1754 Assume(entry.m_ref ==
nullptr);
1756 for (
int level = 0; level < MAX_LEVELS; ++level) {
1757 Assume(!entry.m_locator[level].IsPresent());
1761 if (idx != m_entries.size() - 1) SwapIndexes(idx, m_entries.size() - 1);
1763 m_entries.pop_back();
1772 ApplyRemovals(level);
1773 bool del = cluster.Split(*
this, level);
1776 DeleteCluster(cluster, level);
1780void TxGraphImpl::SplitAll(
int up_to_level)
noexcept
1782 Assume(up_to_level >= 0 && up_to_level <= GetTopLevel());
1784 ApplyRemovals(up_to_level);
1785 for (
int level = 0; level <= up_to_level; ++level) {
1786 for (
auto quality : {QualityLevel::NEEDS_SPLIT, QualityLevel::NEEDS_SPLIT_ACCEPTABLE}) {
1787 auto& queue = GetClusterSet(level).m_clusters[int(quality)];
1788 while (!queue.empty()) {
1789 Split(*queue.back().get(), level);
1795void TxGraphImpl::GroupClusters(
int level)
noexcept
1797 auto& clusterset = GetClusterSet(level);
1799 if (clusterset.m_group_data.has_value())
return;
1809 std::vector<std::pair<Cluster*, uint64_t>> an_clusters;
1814 std::vector<std::pair<std::pair<GraphIndex, GraphIndex>, uint64_t>> an_deps;
1818 for (
int level_iter = 0; level_iter <= level; ++level_iter) {
1819 for (
auto& cluster : GetClusterSet(level_iter).m_clusters[
int(QualityLevel::OVERSIZED_SINGLETON)]) {
1820 auto graph_idx = cluster->GetClusterEntry(0);
1821 auto cur_cluster = FindCluster(graph_idx, level);
1822 if (cur_cluster ==
nullptr)
continue;
1823 an_clusters.emplace_back(cur_cluster, cur_cluster->m_sequence);
1829 an_deps.reserve(clusterset.m_deps_to_add.size());
1830 for (
const auto& [par, chl] : clusterset.m_deps_to_add) {
1831 auto par_cluster = FindCluster(par, level);
1832 auto chl_cluster = FindCluster(chl, level);
1834 if (par_cluster ==
nullptr || chl_cluster ==
nullptr)
continue;
1835 an_clusters.emplace_back(par_cluster, par_cluster->m_sequence);
1838 if (chl_cluster != par_cluster) an_clusters.emplace_back(chl_cluster, chl_cluster->m_sequence);
1840 an_deps.emplace_back(std::pair{par, chl}, chl_cluster->m_sequence);
1844 std::sort(an_clusters.begin(), an_clusters.end(), [](
auto& a,
auto& b)
noexcept { return a.second < b.second; });
1845 an_clusters.erase(std::unique(an_clusters.begin(), an_clusters.end()), an_clusters.end());
1847 std::sort(an_deps.begin(), an_deps.end(), [&](
auto& a,
auto& b)
noexcept { return a.second < b.second; });
1853 struct PartitionData
1861 PartitionData* parent;
1867 std::vector<PartitionData> partition_data;
1870 auto locate_fn = [&](uint64_t
sequence)
noexcept -> PartitionData* {
1871 auto it = std::lower_bound(partition_data.begin(), partition_data.end(),
sequence,
1872 [](
auto& a, uint64_t seq)
noexcept { return a.sequence < seq; });
1873 Assume(it != partition_data.end());
1879 static constexpr auto find_root_fn = [](PartitionData*
data)
noexcept -> PartitionData* {
1883 auto par =
data->parent;
1884 data->parent = par->parent;
1892 static constexpr auto union_fn = [](PartitionData* arg1, PartitionData* arg2)
noexcept {
1895 auto rep1 = find_root_fn(arg1);
1896 auto rep2 = find_root_fn(arg2);
1897 if (rep1 == rep2)
return rep1;
1900 if (rep1->rank < rep2->rank) std::swap(rep1, rep2);
1901 rep2->parent = rep1;
1902 rep1->rank += (rep1->rank == rep2->rank);
1907 partition_data.resize(an_clusters.size());
1908 for (
size_t i = 0; i < an_clusters.size(); ++i) {
1909 partition_data[i].sequence = an_clusters[i].first->m_sequence;
1910 partition_data[i].parent = &partition_data[i];
1911 partition_data[i].rank = 0;
1916 Cluster* last_chl_cluster{
nullptr};
1917 PartitionData* last_partition{
nullptr};
1918 for (
const auto& [dep,
_] : an_deps) {
1919 auto [par, chl] = dep;
1920 auto par_cluster = FindCluster(par, level);
1921 auto chl_cluster = FindCluster(chl, level);
1922 Assume(chl_cluster !=
nullptr && par_cluster !=
nullptr);
1924 if (par_cluster == chl_cluster)
continue;
1926 if (chl_cluster == last_chl_cluster) {
1930 last_partition = union_fn(locate_fn(par_cluster->m_sequence), last_partition);
1932 last_chl_cluster = chl_cluster;
1933 last_partition = union_fn(locate_fn(par_cluster->m_sequence), locate_fn(chl_cluster->m_sequence));
1939 auto deps_it = an_deps.begin();
1940 for (
size_t i = 0; i < partition_data.size(); ++i) {
1941 auto&
data = partition_data[i];
1944 auto rep_seq = find_root_fn(&
data)->sequence;
1945 an_clusters[i].second = rep_seq;
1947 while (deps_it != an_deps.end()) {
1948 auto [par, chl] = deps_it->first;
1949 auto chl_cluster = FindCluster(chl, level);
1950 Assume(chl_cluster !=
nullptr);
1951 if (chl_cluster->m_sequence >
data.sequence)
break;
1952 deps_it->second = rep_seq;
1960 std::sort(an_deps.begin(), an_deps.end(), [](
auto& a,
auto& b)
noexcept { return a.second < b.second; });
1961 std::sort(an_clusters.begin(), an_clusters.end(), [](
auto& a,
auto& b)
noexcept { return a.second < b.second; });
1965 clusterset.m_group_data = GroupData{};
1966 clusterset.m_group_data->m_group_clusters.reserve(an_clusters.size());
1967 clusterset.m_deps_to_add.clear();
1968 clusterset.m_deps_to_add.reserve(an_deps.size());
1969 clusterset.m_oversized =
false;
1970 auto an_deps_it = an_deps.begin();
1971 auto an_clusters_it = an_clusters.begin();
1972 while (an_clusters_it != an_clusters.end()) {
1974 auto rep = an_clusters_it->second;
1976 auto& new_entry = clusterset.m_group_data->m_groups.emplace_back();
1977 new_entry.m_cluster_offset = clusterset.m_group_data->m_group_clusters.size();
1978 new_entry.m_cluster_count = 0;
1979 new_entry.m_deps_offset = clusterset.m_deps_to_add.size();
1980 new_entry.m_deps_count = 0;
1981 uint32_t total_count{0};
1982 uint64_t total_size{0};
1984 while (an_clusters_it != an_clusters.end() && an_clusters_it->second == rep) {
1985 clusterset.m_group_data->m_group_clusters.push_back(an_clusters_it->first);
1986 total_count += an_clusters_it->first->GetTxCount();
1987 total_size += an_clusters_it->first->GetTotalTxSize();
1989 ++new_entry.m_cluster_count;
1992 while (an_deps_it != an_deps.end() && an_deps_it->second == rep) {
1993 clusterset.m_deps_to_add.push_back(an_deps_it->first);
1995 ++new_entry.m_deps_count;
1998 if (total_count > m_max_cluster_count || total_size > m_max_cluster_size) {
1999 clusterset.m_oversized =
true;
2002 Assume(an_deps_it == an_deps.end());
2003 Assume(an_clusters_it == an_clusters.end());
2007void TxGraphImpl::Merge(std::span<Cluster*> to_merge,
int level)
noexcept
2009 Assume(!to_merge.empty());
2011 if (to_merge.size() == 1)
return;
2016 size_t max_size_pos{0};
2017 DepGraphIndex max_size = to_merge[max_size_pos]->GetTxCount();
2018 GetClusterSet(level).m_cluster_usage -= to_merge[max_size_pos]->TotalMemoryUsage();
2020 for (
size_t i = 1; i < to_merge.size(); ++i) {
2021 GetClusterSet(level).m_cluster_usage -= to_merge[i]->TotalMemoryUsage();
2024 if (size > max_size) {
2029 if (max_size_pos != 0) std::swap(to_merge[0], to_merge[max_size_pos]);
2031 size_t start_idx = 1;
2032 Cluster* into_cluster = to_merge[0];
2033 if (total_size > into_cluster->GetMaxTxCount()) {
2037 auto new_cluster = CreateEmptyCluster(total_size);
2038 into_cluster = new_cluster.get();
2039 InsertCluster(level, std::move(new_cluster), QualityLevel::OPTIMAL);
2045 for (
size_t i = start_idx; i < to_merge.size(); ++i) {
2046 into_cluster->Merge(*
this, level, *to_merge[i]);
2047 DeleteCluster(*to_merge[i], level);
2049 into_cluster->Compact();
2050 GetClusterSet(level).m_cluster_usage += into_cluster->TotalMemoryUsage();
2053void TxGraphImpl::ApplyDependencies(
int level)
noexcept
2055 auto& clusterset = GetClusterSet(level);
2057 if (clusterset.m_oversized ==
true)
return;
2059 GroupClusters(level);
2060 Assume(clusterset.m_group_data.has_value());
2062 if (clusterset.m_deps_to_add.empty())
return;
2064 if (clusterset.m_oversized ==
true)
return;
2067 for (
const auto& group_entry : clusterset.m_group_data->m_groups) {
2068 auto cluster_span = std::span{clusterset.m_group_data->m_group_clusters}
2069 .subspan(group_entry.m_cluster_offset, group_entry.m_cluster_count);
2072 for (Cluster*& cluster : cluster_span) {
2073 cluster = PullIn(cluster, cluster->GetLevel(*
this));
2077 Merge(cluster_span, level);
2080 auto deps_span = std::span{clusterset.m_deps_to_add}
2081 .subspan(group_entry.m_deps_offset, group_entry.m_deps_count);
2082 Assume(!deps_span.empty());
2083 const auto& loc = m_entries[deps_span[0].second].m_locator[level];
2085 loc.cluster->ApplyDependencies(*
this, level, deps_span);
2089 clusterset.m_deps_to_add.clear();
2093 clusterset.m_group_data = GroupData{};
2096std::pair<uint64_t, bool> GenericClusterImpl::Relinearize(TxGraphImpl& graph,
int level, uint64_t max_iters)
noexcept
2099 Assume(!NeedsSplitting());
2101 if (IsOptimal())
return {0,
false};
2103 uint64_t rng_seed = graph.m_rng.rand64();
2104 auto [linearization, optimal, cost] =
Linearize(m_depgraph, max_iters, rng_seed, m_linearization);
2109 m_linearization = std::move(linearization);
2111 bool improved =
false;
2113 graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::OPTIMAL);
2115 }
else if (max_iters >= graph.m_acceptable_iters && !IsAcceptable()) {
2116 graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::ACCEPTABLE);
2120 Updated(graph, level);
2121 return {cost, improved};
2124std::pair<uint64_t, bool> SingletonClusterImpl::Relinearize(TxGraphImpl& graph,
int level, uint64_t max_iters)
noexcept
2132void TxGraphImpl::MakeAcceptable(Cluster& cluster,
int level)
noexcept
2135 if (!cluster.NeedsSplitting() && !cluster.IsAcceptable() && !cluster.IsOversized()) {
2136 cluster.Relinearize(*
this, level, m_acceptable_iters);
2140void TxGraphImpl::MakeAllAcceptable(
int level)
noexcept
2142 ApplyDependencies(level);
2143 auto& clusterset = GetClusterSet(level);
2144 if (clusterset.m_oversized ==
true)
return;
2145 auto& queue = clusterset.m_clusters[int(QualityLevel::NEEDS_RELINEARIZE)];
2146 while (!queue.empty()) {
2147 MakeAcceptable(*queue.back().get(), level);
2151GenericClusterImpl::GenericClusterImpl(uint64_t
sequence) noexcept : Cluster{
sequence} {}
2155 Assume(m_main_chunkindex_observers == 0 || GetTopLevel() != 0);
2160 auto idx = m_entries.size();
2161 m_entries.emplace_back();
2162 auto& entry = m_entries.back();
2163 entry.m_main_chunkindex_iterator = m_main_chunkindex.end();
2165 GetRefGraph(
ret) =
this;
2166 GetRefIndex(
ret) = idx;
2168 bool oversized = uint64_t(feerate.
size) > m_max_cluster_size;
2169 auto cluster = CreateEmptyCluster(1);
2170 cluster->AppendTransaction(idx, feerate);
2171 auto cluster_ptr = cluster.get();
2172 int level = GetTopLevel();
2173 auto& clusterset = GetClusterSet(level);
2174 InsertCluster(level, std::move(cluster), oversized ? QualityLevel::OVERSIZED_SINGLETON : QualityLevel::OPTIMAL);
2175 cluster_ptr->Updated(*
this, level);
2176 clusterset.m_cluster_usage += cluster_ptr->TotalMemoryUsage();
2177 ++clusterset.m_txcount;
2180 ++clusterset.m_txcount_oversized;
2181 clusterset.m_oversized =
true;
2182 clusterset.m_group_data = std::nullopt;
2188void TxGraphImpl::RemoveTransaction(
const Ref& arg)
noexcept
2192 if (GetRefGraph(arg) ==
nullptr)
return;
2193 Assume(GetRefGraph(arg) ==
this);
2194 Assume(m_main_chunkindex_observers == 0 || GetTopLevel() != 0);
2196 int level = GetTopLevel();
2197 auto cluster = FindCluster(GetRefIndex(arg), level);
2198 if (cluster ==
nullptr)
return;
2200 auto& clusterset = GetClusterSet(level);
2201 clusterset.m_to_remove.push_back(GetRefIndex(arg));
2203 clusterset.m_group_data.reset();
2204 if (clusterset.m_oversized ==
true) clusterset.m_oversized = std::nullopt;
2207void TxGraphImpl::AddDependency(
const Ref& parent,
const Ref& child)
noexcept
2211 if (GetRefGraph(parent) ==
nullptr || GetRefGraph(child) ==
nullptr)
return;
2212 Assume(GetRefGraph(parent) ==
this && GetRefGraph(child) ==
this);
2213 Assume(m_main_chunkindex_observers == 0 || GetTopLevel() != 0);
2215 if (GetRefIndex(parent) == GetRefIndex(child))
return;
2218 int level = GetTopLevel();
2219 auto par_cluster = FindCluster(GetRefIndex(parent), level);
2220 if (par_cluster ==
nullptr)
return;
2221 auto chl_cluster = FindCluster(GetRefIndex(child), level);
2222 if (chl_cluster ==
nullptr)
return;
2224 auto& clusterset = GetClusterSet(level);
2225 clusterset.m_deps_to_add.emplace_back(GetRefIndex(parent), GetRefIndex(child));
2227 clusterset.m_group_data.reset();
2228 if (clusterset.m_oversized ==
false) clusterset.m_oversized = std::nullopt;
2231bool TxGraphImpl::Exists(
const Ref& arg,
Level level_select)
noexcept
2233 if (GetRefGraph(arg) ==
nullptr)
return false;
2234 Assume(GetRefGraph(arg) ==
this);
2235 size_t level = GetSpecifiedLevel(level_select);
2237 ApplyRemovals(level);
2238 auto cluster = FindCluster(GetRefIndex(arg), level);
2239 return cluster !=
nullptr;
2242void GenericClusterImpl::GetAncestorRefs(
const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>&
args, std::vector<TxGraph::Ref*>& output)
noexcept
2245 SetType ancestors_union;
2247 while (!
args.empty()) {
2248 if (
args.front().first !=
this)
break;
2249 ancestors_union |= m_depgraph.
Ancestors(
args.front().second);
2252 Assume(ancestors_union.Any());
2254 for (
auto idx : ancestors_union) {
2255 const auto& entry = graph.m_entries[m_mapping[idx]];
2256 Assume(entry.m_ref !=
nullptr);
2257 output.push_back(entry.m_ref);
2261void SingletonClusterImpl::GetAncestorRefs(
const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>&
args, std::vector<TxGraph::Ref*>& output)
noexcept
2264 while (!
args.empty()) {
2265 if (
args.front().first !=
this)
break;
2268 const auto& entry = graph.m_entries[m_graph_index];
2269 Assume(entry.m_ref !=
nullptr);
2270 output.push_back(entry.m_ref);
2273void GenericClusterImpl::GetDescendantRefs(
const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>&
args, std::vector<TxGraph::Ref*>& output)
noexcept
2276 SetType descendants_union;
2278 while (!
args.empty()) {
2279 if (
args.front().first !=
this)
break;
2283 Assume(descendants_union.Any());
2285 for (
auto idx : descendants_union) {
2286 const auto& entry = graph.m_entries[m_mapping[idx]];
2287 Assume(entry.m_ref !=
nullptr);
2288 output.push_back(entry.m_ref);
2292void SingletonClusterImpl::GetDescendantRefs(
const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>&
args, std::vector<TxGraph::Ref*>& output)
noexcept
2295 GetAncestorRefs(graph,
args, output);
2298bool GenericClusterImpl::GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos)
noexcept
2302 for (
auto& ref : range) {
2303 Assume(start_pos < m_linearization.size());
2304 const auto& entry = graph.m_entries[m_mapping[m_linearization[start_pos++]]];
2305 Assume(entry.m_ref !=
nullptr);
2309 return start_pos == m_linearization.size();
2312bool SingletonClusterImpl::GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos)
noexcept
2317 const auto& entry = graph.m_entries[m_graph_index];
2318 Assume(entry.m_ref !=
nullptr);
2319 range[0] = entry.m_ref;
2335void GenericClusterImpl::MakeStagingTransactionsMissing(TxGraphImpl& graph)
noexcept
2339 for (
auto ci : m_linearization) {
2340 GraphIndex idx = m_mapping[ci];
2341 auto& entry = graph.m_entries[idx];
2342 entry.m_locator[1].SetMissing();
2346void SingletonClusterImpl::MakeStagingTransactionsMissing(TxGraphImpl& graph)
noexcept
2349 auto& entry = graph.m_entries[m_graph_index];
2350 entry.m_locator[1].SetMissing();
2354std::vector<TxGraph::Ref*> TxGraphImpl::GetAncestors(
const Ref& arg,
Level level_select)
noexcept
2357 if (GetRefGraph(arg) ==
nullptr)
return {};
2358 Assume(GetRefGraph(arg) ==
this);
2360 size_t level = GetSpecifiedLevel(level_select);
2361 ApplyDependencies(level);
2363 Assume(GetClusterSet(level).m_deps_to_add.empty());
2365 auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(arg), level);
2366 if (cluster ==
nullptr)
return {};
2368 std::pair<Cluster*, DepGraphIndex> match = {cluster, m_entries[GetRefIndex(arg)].m_locator[cluster_level].index};
2369 auto matches = std::span(&match, 1);
2370 std::vector<TxGraph::Ref*>
ret;
2371 cluster->GetAncestorRefs(*
this, matches,
ret);
2375std::vector<TxGraph::Ref*> TxGraphImpl::GetDescendants(
const Ref& arg,
Level level_select)
noexcept
2378 if (GetRefGraph(arg) ==
nullptr)
return {};
2379 Assume(GetRefGraph(arg) ==
this);
2381 size_t level = GetSpecifiedLevel(level_select);
2382 ApplyDependencies(level);
2384 Assume(GetClusterSet(level).m_deps_to_add.empty());
2386 auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(arg), level);
2387 if (cluster ==
nullptr)
return {};
2389 std::pair<Cluster*, DepGraphIndex> match = {cluster, m_entries[GetRefIndex(arg)].m_locator[cluster_level].index};
2390 auto matches = std::span(&match, 1);
2391 std::vector<TxGraph::Ref*>
ret;
2392 cluster->GetDescendantRefs(*
this, matches,
ret);
2396std::vector<TxGraph::Ref*> TxGraphImpl::GetAncestorsUnion(std::span<const Ref* const>
args,
Level level_select)
noexcept
2399 size_t level = GetSpecifiedLevel(level_select);
2400 ApplyDependencies(level);
2402 Assume(GetClusterSet(level).m_deps_to_add.empty());
2405 std::vector<std::pair<Cluster*, DepGraphIndex>> matches;
2406 matches.reserve(
args.size());
2407 for (
auto arg :
args) {
2410 if (GetRefGraph(*arg) ==
nullptr)
continue;
2411 Assume(GetRefGraph(*arg) ==
this);
2413 auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(*arg), level);
2414 if (cluster ==
nullptr)
continue;
2416 matches.emplace_back(cluster, m_entries[GetRefIndex(*arg)].m_locator[cluster_level].index);
2419 std::sort(matches.begin(), matches.end(), [](
auto& a,
auto& b)
noexcept { return CompareClusters(a.first, b.first) < 0; });
2421 std::span match_span(matches);
2422 std::vector<TxGraph::Ref*>
ret;
2423 while (!match_span.empty()) {
2424 match_span.front().first->GetAncestorRefs(*
this, match_span,
ret);
2429std::vector<TxGraph::Ref*> TxGraphImpl::GetDescendantsUnion(std::span<const Ref* const>
args,
Level level_select)
noexcept
2432 size_t level = GetSpecifiedLevel(level_select);
2433 ApplyDependencies(level);
2435 Assume(GetClusterSet(level).m_deps_to_add.empty());
2438 std::vector<std::pair<Cluster*, DepGraphIndex>> matches;
2439 matches.reserve(
args.size());
2440 for (
auto arg :
args) {
2443 if (GetRefGraph(*arg) ==
nullptr)
continue;
2444 Assume(GetRefGraph(*arg) ==
this);
2446 auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(*arg), level);
2447 if (cluster ==
nullptr)
continue;
2449 matches.emplace_back(cluster, m_entries[GetRefIndex(*arg)].m_locator[cluster_level].index);
2452 std::sort(matches.begin(), matches.end(), [](
auto& a,
auto& b)
noexcept { return CompareClusters(a.first, b.first) < 0; });
2454 std::span match_span(matches);
2455 std::vector<TxGraph::Ref*>
ret;
2456 while (!match_span.empty()) {
2457 match_span.front().first->GetDescendantRefs(*
this, match_span,
ret);
2462std::vector<TxGraph::Ref*> TxGraphImpl::GetCluster(
const Ref& arg,
Level level_select)
noexcept
2466 if (GetRefGraph(arg) ==
nullptr)
return {};
2467 Assume(GetRefGraph(arg) ==
this);
2469 size_t level = GetSpecifiedLevel(level_select);
2470 ApplyDependencies(level);
2472 Assume(GetClusterSet(level).m_deps_to_add.empty());
2474 auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(arg), level);
2475 if (cluster ==
nullptr)
return {};
2477 MakeAcceptable(*cluster, cluster_level);
2478 std::vector<TxGraph::Ref*>
ret(cluster->GetTxCount());
2479 cluster->GetClusterRefs(*
this,
ret, 0);
2485 size_t level = GetSpecifiedLevel(level_select);
2486 ApplyRemovals(level);
2487 return GetClusterSet(level).m_txcount;
2490FeePerWeight TxGraphImpl::GetIndividualFeerate(
const Ref& arg)
noexcept
2493 if (GetRefGraph(arg) ==
nullptr)
return {};
2494 Assume(GetRefGraph(arg) ==
this);
2497 Cluster* cluster{
nullptr};
2499 for (level = 0; level <= GetTopLevel(); ++level) {
2502 ApplyRemovals(level);
2503 if (m_entries[GetRefIndex(arg)].m_locator[level].IsPresent()) {
2504 cluster = m_entries[GetRefIndex(arg)].m_locator[level].cluster;
2508 if (cluster ==
nullptr)
return {};
2510 return cluster->GetIndividualFeerate(m_entries[GetRefIndex(arg)].m_locator[level].index);
2513FeePerWeight TxGraphImpl::GetMainChunkFeerate(
const Ref& arg)
noexcept
2516 if (GetRefGraph(arg) ==
nullptr)
return {};
2517 Assume(GetRefGraph(arg) ==
this);
2519 ApplyDependencies(0);
2521 Assume(m_main_clusterset.m_deps_to_add.empty());
2523 auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(arg), 0);
2524 if (cluster ==
nullptr)
return {};
2527 MakeAcceptable(*cluster, cluster_level);
2528 const auto& entry = m_entries[GetRefIndex(arg)];
2529 return entry.m_main_chunk_feerate;
2532bool TxGraphImpl::IsOversized(
Level level_select)
noexcept
2534 size_t level = GetSpecifiedLevel(level_select);
2535 auto& clusterset = GetClusterSet(level);
2536 if (clusterset.m_oversized.has_value()) {
2538 return *clusterset.m_oversized;
2540 ApplyRemovals(level);
2541 if (clusterset.m_txcount_oversized > 0) {
2542 clusterset.m_oversized =
true;
2546 GroupClusters(level);
2548 Assume(clusterset.m_oversized.has_value());
2549 return *clusterset.m_oversized;
2552void TxGraphImpl::StartStaging() noexcept
2555 Assume(!m_staging_clusterset.has_value());
2562 ApplyDependencies(0);
2564 m_staging_clusterset.emplace();
2567 m_staging_clusterset->m_txcount = m_main_clusterset.m_txcount;
2568 m_staging_clusterset->m_txcount_oversized = m_main_clusterset.m_txcount_oversized;
2569 m_staging_clusterset->m_deps_to_add = m_main_clusterset.m_deps_to_add;
2570 m_staging_clusterset->m_group_data = m_main_clusterset.m_group_data;
2571 m_staging_clusterset->m_oversized = m_main_clusterset.m_oversized;
2572 Assume(m_staging_clusterset->m_oversized.has_value());
2573 m_staging_clusterset->m_cluster_usage = 0;
2576void TxGraphImpl::AbortStaging() noexcept
2579 Assume(m_staging_clusterset.has_value());
2582 for (
auto idx : m_staging_clusterset->m_removed) {
2583 m_entries[idx].m_locator[1].SetMissing();
2587 for (
auto& cluster : m_staging_clusterset->m_clusters[quality]) {
2588 cluster->MakeStagingTransactionsMissing(*
this);
2592 m_staging_clusterset.reset();
2594 if (!m_main_clusterset.m_group_data.has_value()) {
2597 if (m_main_clusterset.m_to_remove.empty() && m_main_clusterset.m_txcount_oversized > 0) {
2600 m_main_clusterset.m_oversized =
true;
2602 m_main_clusterset.m_oversized = std::nullopt;
2607void TxGraphImpl::CommitStaging() noexcept
2610 Assume(m_staging_clusterset.has_value());
2611 Assume(m_main_chunkindex_observers == 0);
2614 auto conflicts = GetConflicts();
2615 for (Cluster* conflict : conflicts) {
2616 conflict->Clear(*
this, 0);
2617 DeleteCluster(*conflict, 0);
2621 for (
auto idx : m_staging_clusterset->m_removed) {
2622 m_entries[idx].m_locator[1].SetMissing();
2626 auto& stage_sets = m_staging_clusterset->m_clusters[quality];
2627 while (!stage_sets.empty()) {
2628 stage_sets.back()->MoveToMain(*
this);
2632 m_main_clusterset.m_deps_to_add = std::move(m_staging_clusterset->m_deps_to_add);
2633 m_main_clusterset.m_to_remove = std::move(m_staging_clusterset->m_to_remove);
2634 m_main_clusterset.m_group_data = std::move(m_staging_clusterset->m_group_data);
2635 m_main_clusterset.m_oversized = std::move(m_staging_clusterset->m_oversized);
2636 m_main_clusterset.m_txcount = std::move(m_staging_clusterset->m_txcount);
2637 m_main_clusterset.m_txcount_oversized = std::move(m_staging_clusterset->m_txcount_oversized);
2639 m_staging_clusterset.reset();
2643void GenericClusterImpl::SetFee(TxGraphImpl& graph,
int level,
DepGraphIndex idx, int64_t
fee)
noexcept
2652 if (m_quality == QualityLevel::OVERSIZED_SINGLETON) {
2654 }
else if (!NeedsSplitting()) {
2655 graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::NEEDS_RELINEARIZE);
2657 graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::NEEDS_SPLIT);
2659 Updated(graph, level);
2662void SingletonClusterImpl::SetFee(TxGraphImpl& graph,
int level,
DepGraphIndex idx, int64_t
fee)
noexcept
2667 Updated(graph, level);
2670void TxGraphImpl::SetTransactionFee(
const Ref& ref, int64_t
fee)
noexcept
2673 if (GetRefGraph(ref) ==
nullptr)
return;
2674 Assume(GetRefGraph(ref) ==
this);
2675 Assume(m_main_chunkindex_observers == 0);
2677 auto& entry = m_entries[GetRefIndex(ref)];
2678 for (
int level = 0; level < MAX_LEVELS; ++level) {
2679 auto& locator = entry.m_locator[level];
2680 if (locator.IsPresent()) {
2681 locator.cluster->SetFee(*
this, level, locator.index,
fee);
2686std::strong_ordering TxGraphImpl::CompareMainOrder(
const Ref& a,
const Ref& b)
noexcept
2689 Assume(GetRefGraph(a) ==
this);
2690 Assume(GetRefGraph(b) ==
this);
2692 ApplyDependencies(0);
2693 Assume(m_main_clusterset.m_deps_to_add.empty());
2695 const auto& entry_a = m_entries[GetRefIndex(a)];
2696 const auto& entry_b = m_entries[GetRefIndex(b)];
2697 const auto& locator_a = entry_a.m_locator[0];
2698 const auto& locator_b = entry_b.m_locator[0];
2699 Assume(locator_a.IsPresent());
2700 Assume(locator_b.IsPresent());
2701 MakeAcceptable(*locator_a.cluster, 0);
2702 MakeAcceptable(*locator_b.cluster, 0);
2704 return CompareMainTransactions(GetRefIndex(a), GetRefIndex(b));
2707TxGraph::GraphIndex TxGraphImpl::CountDistinctClusters(std::span<const Ref* const> refs,
Level level_select)
noexcept
2709 size_t level = GetSpecifiedLevel(level_select);
2710 ApplyDependencies(level);
2711 auto& clusterset = GetClusterSet(level);
2712 Assume(clusterset.m_deps_to_add.empty());
2714 std::vector<Cluster*> clusters;
2715 clusters.reserve(refs.size());
2716 for (
const Ref* ref : refs) {
2718 if (GetRefGraph(*ref) ==
nullptr)
continue;
2719 Assume(GetRefGraph(*ref) ==
this);
2720 auto cluster = FindCluster(GetRefIndex(*ref), level);
2721 if (cluster !=
nullptr) clusters.push_back(cluster);
2724 std::sort(clusters.begin(), clusters.end(), [](Cluster* a, Cluster* b)
noexcept { return CompareClusters(a, b) < 0; });
2725 Cluster* last{
nullptr};
2727 for (Cluster* cluster : clusters) {
2728 ret += (cluster != last);
2734std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>> TxGraphImpl::GetMainStagingDiagrams() noexcept
2736 Assume(m_staging_clusterset.has_value());
2737 MakeAllAcceptable(0);
2738 Assume(m_main_clusterset.m_deps_to_add.empty());
2739 MakeAllAcceptable(1);
2740 Assume(m_staging_clusterset->m_deps_to_add.empty());
2743 auto main_clusters = GetConflicts();
2744 std::vector<FeeFrac> main_feerates, staging_feerates;
2745 for (Cluster* cluster : main_clusters) {
2746 cluster->AppendChunkFeerates(main_feerates);
2750 for (
const auto& cluster : m_staging_clusterset->m_clusters[quality]) {
2751 cluster->AppendChunkFeerates(staging_feerates);
2755 std::sort(main_feerates.begin(), main_feerates.end(), [](
auto& a,
auto& b) { return a > b; });
2756 std::sort(staging_feerates.begin(), staging_feerates.end(), [](
auto& a,
auto& b) { return a > b; });
2757 return std::make_pair(std::move(main_feerates), std::move(staging_feerates));
2760void GenericClusterImpl::SanityCheck(
const TxGraphImpl& graph,
int level)
const
2767 if (!NeedsSplitting()) {
2776 LinearizationIndex linindex{0};
2779 for (
auto lin_pos : m_linearization) {
2780 assert(lin_pos < m_mapping.size());
2781 const auto& entry = graph.m_entries[m_mapping[lin_pos]];
2783 m_done.Set(lin_pos);
2786 assert(entry.m_locator[level].cluster ==
this);
2787 assert(entry.m_locator[level].index == lin_pos);
2789 if (level == 0 && IsAcceptable()) {
2790 assert(entry.m_main_lin_index == linindex);
2792 if (!linchunking.GetChunk(0).transactions[lin_pos]) {
2793 linchunking.MarkDone(linchunking.GetChunk(0).transactions);
2796 assert(entry.m_main_chunk_feerate == linchunking.GetChunk(0).feerate);
2799 bool is_chunk_end = (chunk_pos == linchunking.GetChunk(0).transactions.Count());
2800 assert((entry.m_main_chunkindex_iterator != graph.m_main_chunkindex.end()) == is_chunk_end);
2802 auto& chunk_data = *entry.m_main_chunkindex_iterator;
2803 if (m_done == m_depgraph.
Positions() && chunk_pos == 1) {
2804 assert(chunk_data.m_chunk_count == LinearizationIndex(-1));
2806 assert(chunk_data.m_chunk_count == chunk_pos);
2817void SingletonClusterImpl::SanityCheck(
const TxGraphImpl& graph,
int level)
const
2820 Assume(IsOptimal() || IsOversized() || NeedsSplitting());
2822 const auto& entry = graph.m_entries[m_graph_index];
2824 assert(entry.m_locator[level].cluster ==
this);
2825 assert(entry.m_locator[level].index == 0);
2827 if (level == 0 && IsAcceptable()) {
2828 assert(entry.m_main_lin_index == 0);
2829 assert(entry.m_main_chunk_feerate == m_feerate);
2830 assert(entry.m_main_chunkindex_iterator != graph.m_main_chunkindex.end());
2831 auto& chunk_data = *entry.m_main_chunkindex_iterator;
2832 assert(chunk_data.m_chunk_count == LinearizationIndex(-1));
2837void TxGraphImpl::SanityCheck()
const
2840 std::set<GraphIndex> expected_unlinked;
2842 std::set<const Cluster*> expected_clusters[MAX_LEVELS];
2844 std::set<GraphIndex> expected_removed[MAX_LEVELS];
2846 std::set<uint64_t> sequences;
2848 std::set<GraphIndex> expected_chunkindex;
2850 bool compact_possible{
true};
2853 for (GraphIndex idx = 0; idx < m_entries.size(); ++idx) {
2854 const auto& entry = m_entries[idx];
2855 if (entry.m_ref ==
nullptr) {
2857 expected_unlinked.insert(idx);
2860 assert(GetRefGraph(*entry.m_ref) ==
this);
2861 assert(GetRefIndex(*entry.m_ref) == idx);
2863 if (entry.m_main_chunkindex_iterator != m_main_chunkindex.end()) {
2865 assert(entry.m_locator[0].IsPresent());
2866 expected_chunkindex.insert(idx);
2869 bool was_present{
false}, was_removed{
false};
2870 for (
int level = 0; level < MAX_LEVELS; ++level) {
2871 const auto& locator = entry.m_locator[level];
2873 assert(locator.IsMissing() + locator.IsRemoved() + locator.IsPresent() == 1);
2874 if (locator.IsPresent()) {
2878 assert(locator.cluster->GetClusterEntry(locator.index) == idx);
2880 expected_clusters[level].insert(locator.cluster);
2882 }
else if (locator.IsRemoved()) {
2886 assert(was_present && !was_removed);
2888 expected_removed[level].insert(idx);
2895 for (
int level = 0; level <= GetTopLevel(); ++level) {
2896 assert(level < MAX_LEVELS);
2897 auto& clusterset = GetClusterSet(level);
2898 std::set<const Cluster*> actual_clusters;
2899 size_t recomputed_cluster_usage{0};
2903 QualityLevel quality{qual};
2904 const auto& quality_clusters = clusterset.m_clusters[qual];
2906 for (ClusterSetIndex setindex = 0; setindex < quality_clusters.size(); ++setindex) {
2907 const auto& cluster = *quality_clusters[setindex];
2909 assert(cluster.GetTxCount() <= m_max_cluster_count);
2912 assert(cluster.GetTxCount() == 0 || level == cluster.GetLevel(*
this));
2917 assert(cluster.IsOversized() || cluster.GetTotalTxSize() <= m_max_cluster_size);
2919 assert(!cluster.IsOversized() || cluster.GetTxCount() == 1);
2922 assert(cluster.GetTxCount() <= cluster.GetMaxTxCount());
2925 if (!cluster.NeedsSplitting()) {
2926 assert(cluster.GetTxCount() >= cluster.GetMinIntendedTxCount());
2930 assert(cluster.m_sequence < m_next_sequence_counter);
2931 assert(sequences.count(cluster.m_sequence) == 0);
2932 sequences.insert(cluster.m_sequence);
2935 if (cluster.GetTxCount() != 0) {
2936 actual_clusters.insert(&cluster);
2939 cluster.SanityCheck(*
this, level);
2941 assert(cluster.m_quality == quality);
2942 assert(cluster.m_setindex == setindex);
2944 recomputed_cluster_usage += cluster.TotalMemoryUsage();
2949 assert(clusterset.m_cluster_usage == recomputed_cluster_usage);
2952 for (GraphIndex idx : clusterset.m_to_remove) {
2953 assert(idx < m_entries.size());
2961 for (
auto [par_idx, chl_idx] : clusterset.m_deps_to_add) {
2962 assert(par_idx != chl_idx);
2963 assert(par_idx < m_entries.size());
2964 assert(chl_idx < m_entries.size());
2968 assert(actual_clusters == expected_clusters[level]);
2971 std::set<GraphIndex> actual_removed(clusterset.m_removed.begin(), clusterset.m_removed.end());
2972 for (
auto i : expected_unlinked) {
2977 actual_removed.erase(i);
2978 expected_removed[level].erase(i);
2981 assert(actual_removed == expected_removed[level]);
2984 if (!clusterset.m_deps_to_add.empty()) compact_possible =
false;
2985 if (!clusterset.m_to_remove.empty()) compact_possible =
false;
2986 if (!clusterset.m_removed.empty()) compact_possible =
false;
2990 if (level < GetTopLevel())
assert(clusterset.m_oversized.has_value());
2994 std::set<GraphIndex> actual_unlinked(m_unlinked.begin(), m_unlinked.end());
2995 assert(actual_unlinked == expected_unlinked);
2999 if (compact_possible) {
3000 assert(actual_unlinked.empty());
3004 std::set<GraphIndex> actual_chunkindex;
3006 for (
const auto& chunk : m_main_chunkindex) {
3007 GraphIndex idx = chunk.m_graph_index;
3008 actual_chunkindex.insert(idx);
3009 auto chunk_feerate = m_entries[idx].m_main_chunk_feerate;
3010 if (!last_chunk_feerate.
IsEmpty()) {
3011 assert(FeeRateCompare(last_chunk_feerate, chunk_feerate) >= 0);
3013 last_chunk_feerate = chunk_feerate;
3015 assert(actual_chunkindex == expected_chunkindex);
3018bool TxGraphImpl::DoWork(uint64_t iters)
noexcept
3020 uint64_t iters_done{0};
3023 for (QualityLevel quality : {QualityLevel::NEEDS_RELINEARIZE, QualityLevel::ACCEPTABLE}) {
3025 for (
int level = GetTopLevel(); level >= 0; --level) {
3027 if (level == 0 && m_main_chunkindex_observers != 0)
continue;
3028 ApplyDependencies(level);
3029 auto& clusterset = GetClusterSet(level);
3031 if (clusterset.m_oversized ==
true)
continue;
3032 auto& queue = clusterset.m_clusters[int(quality)];
3033 while (!queue.empty()) {
3034 if (iters_done >= iters)
return false;
3038 auto pos = m_rng.
randrange<
size_t>(queue.size());
3039 auto iters_now = iters - iters_done;
3040 if (quality == QualityLevel::NEEDS_RELINEARIZE) {
3045 iters_now = std::min(iters_now, m_acceptable_iters);
3047 auto [cost, improved] = queue[pos].get()->Relinearize(*
this, level, iters_now);
3054 if (!improved)
return false;
3064void BlockBuilderImpl::Next() noexcept
3067 if (m_cur_iter == m_graph->m_main_chunkindex.end())
return;
3071 m_cur_cluster =
nullptr;
3072 if (m_cur_iter == m_graph->m_main_chunkindex.end())
break;
3074 const auto& chunk_data = *m_cur_iter;
3075 const auto& chunk_end_entry = m_graph->m_entries[chunk_data.m_graph_index];
3076 m_cur_cluster = chunk_end_entry.m_locator[0].cluster;
3077 m_known_end_of_cluster =
false;
3079 if (!m_excluded_clusters.contains(m_cur_cluster->m_sequence))
break;
3083std::optional<std::pair<std::vector<TxGraph::Ref*>,
FeePerWeight>> BlockBuilderImpl::GetCurrentChunk() noexcept
3085 std::optional<std::pair<std::vector<TxGraph::Ref*>,
FeePerWeight>>
ret;
3087 if (m_cur_iter != m_graph->m_main_chunkindex.end()) {
3089 const auto& chunk_data = *m_cur_iter;
3090 const auto& chunk_end_entry = m_graph->m_entries[chunk_data.m_graph_index];
3091 if (chunk_data.m_chunk_count == LinearizationIndex(-1)) {
3094 ret->first.resize(1);
3095 Assume(chunk_end_entry.m_ref !=
nullptr);
3096 ret->first[0] = chunk_end_entry.m_ref;
3097 m_known_end_of_cluster =
true;
3100 ret->first.resize(chunk_data.m_chunk_count);
3101 auto start_pos = chunk_end_entry.m_main_lin_index + 1 - chunk_data.m_chunk_count;
3102 m_known_end_of_cluster = m_cur_cluster->GetClusterRefs(*m_graph,
ret->first, start_pos);
3105 Assume(!m_known_end_of_cluster || chunk_data.m_chunk_count > 1);
3107 ret->second = chunk_end_entry.m_main_chunk_feerate;
3112BlockBuilderImpl::BlockBuilderImpl(TxGraphImpl& graph) noexcept : m_graph(&graph)
3115 m_graph->MakeAllAcceptable(0);
3117 Assume(m_graph->m_main_clusterset.m_deps_to_add.empty());
3120 ++m_graph->m_main_chunkindex_observers;
3122 m_cur_iter = m_graph->m_main_chunkindex.begin();
3123 m_cur_cluster =
nullptr;
3124 if (m_cur_iter != m_graph->m_main_chunkindex.end()) {
3126 const auto& chunk_data = *m_cur_iter;
3127 const auto& chunk_end_entry = m_graph->m_entries[chunk_data.m_graph_index];
3128 m_cur_cluster = chunk_end_entry.m_locator[0].cluster;
3132BlockBuilderImpl::~BlockBuilderImpl()
3134 Assume(m_graph->m_main_chunkindex_observers > 0);
3136 --m_graph->m_main_chunkindex_observers;
3139void BlockBuilderImpl::Include() noexcept
3146void BlockBuilderImpl::Skip() noexcept
3152 if (m_cur_cluster !=
nullptr && !m_known_end_of_cluster) {
3153 m_excluded_clusters.insert(m_cur_cluster->m_sequence);
3158std::unique_ptr<TxGraph::BlockBuilder> TxGraphImpl::GetBlockBuilder() noexcept
3160 return std::make_unique<BlockBuilderImpl>(*
this);
3163std::pair<std::vector<TxGraph::Ref*>,
FeePerWeight> TxGraphImpl::GetWorstMainChunk() noexcept
3167 MakeAllAcceptable(0);
3168 Assume(m_main_clusterset.m_deps_to_add.empty());
3170 if (!m_main_chunkindex.empty()) {
3171 const auto& chunk_data = *m_main_chunkindex.rbegin();
3172 const auto& chunk_end_entry = m_entries[chunk_data.m_graph_index];
3173 Cluster* cluster = chunk_end_entry.m_locator[0].cluster;
3174 if (chunk_data.m_chunk_count == LinearizationIndex(-1) || chunk_data.m_chunk_count == 1) {
3176 ret.first.resize(1);
3177 Assume(chunk_end_entry.m_ref !=
nullptr);
3178 ret.first[0] = chunk_end_entry.m_ref;
3180 ret.first.resize(chunk_data.m_chunk_count);
3181 auto start_pos = chunk_end_entry.m_main_lin_index + 1 - chunk_data.m_chunk_count;
3182 cluster->GetClusterRefs(*
this,
ret.first, start_pos);
3183 std::reverse(
ret.first.begin(),
ret.first.end());
3185 ret.second = chunk_end_entry.m_main_chunk_feerate;
3190std::vector<TxGraph::Ref*> TxGraphImpl::Trim() noexcept
3192 int level = GetTopLevel();
3193 Assume(m_main_chunkindex_observers == 0 || level != 0);
3194 std::vector<TxGraph::Ref*>
ret;
3197 auto& clusterset = GetClusterSet(level);
3198 if (clusterset.m_oversized ==
false)
return ret;
3199 GroupClusters(level);
3200 Assume(clusterset.m_group_data.has_value());
3202 Assume(clusterset.m_oversized.has_value());
3203 if (clusterset.m_oversized ==
false)
return ret;
3227 std::vector<std::pair<GraphIndex, GraphIndex>> deps_by_parent;
3229 std::vector<std::pair<GraphIndex, GraphIndex>> deps_by_child;
3233 std::vector<TrimTxData> trim_data;
3236 std::vector<std::vector<TrimTxData>::iterator> trim_heap;
3238 std::vector<TrimTxData*> current_deps;
3241 static constexpr auto cmp_fn = [](
auto a,
auto b)
noexcept {
3246 return a->m_chunk_feerate < b->m_chunk_feerate;
3250 static constexpr auto find_fn = [](TrimTxData* arg)
noexcept {
3251 while (arg != arg->m_uf_parent) {
3254 auto par = arg->m_uf_parent;
3255 arg->m_uf_parent = par->m_uf_parent;
3263 static constexpr auto union_fn = [](TrimTxData* arg1, TrimTxData* arg2)
noexcept {
3265 auto rep1 = find_fn(arg1);
3266 auto rep2 = find_fn(arg2);
3269 if (rep1 == rep2)
return rep1;
3272 if (rep1->m_uf_count < rep2->m_uf_count) std::swap(rep1, rep2);
3273 rep2->m_uf_parent = rep1;
3276 rep1->m_uf_size += rep2->m_uf_size;
3277 rep1->m_uf_count += rep2->m_uf_count;
3282 auto locate_fn = [&](GraphIndex index)
noexcept {
3283 auto it = std::lower_bound(trim_data.begin(), trim_data.end(), index, [](TrimTxData& elem, GraphIndex idx)
noexcept {
3284 return elem.m_index < idx;
3286 Assume(it != trim_data.end() && it->m_index == index);
3291 for (
const auto& group_data : clusterset.m_group_data->m_groups) {
3294 deps_by_child.clear();
3295 deps_by_parent.clear();
3298 auto cluster_span = std::span{clusterset.m_group_data->m_group_clusters}
3299 .subspan(group_data.m_cluster_offset, group_data.m_cluster_count);
3301 for (Cluster* cluster : cluster_span) {
3302 size += cluster->AppendTrimData(trim_data, deps_by_child);
3305 if (trim_data.size() <= m_max_cluster_count && size <= m_max_cluster_size)
continue;
3309 std::sort(trim_data.begin(), trim_data.end(), [](
auto& a,
auto& b)
noexcept { return a.m_index < b.m_index; });
3312 deps_by_child.insert(deps_by_child.end(),
3313 clusterset.m_deps_to_add.begin() + group_data.m_deps_offset,
3314 clusterset.m_deps_to_add.begin() + group_data.m_deps_offset + group_data.m_deps_count);
3318 std::sort(deps_by_child.begin(), deps_by_child.end(), [](
auto& a,
auto& b)
noexcept { return a.second < b.second; });
3322 auto deps_it = deps_by_child.begin();
3323 for (
auto trim_it = trim_data.begin(); trim_it != trim_data.end(); ++trim_it) {
3324 trim_it->m_parent_offset = deps_it - deps_by_child.begin();
3325 trim_it->m_deps_left = 0;
3326 while (deps_it != deps_by_child.end() && deps_it->second == trim_it->m_index) {
3327 ++trim_it->m_deps_left;
3330 trim_it->m_parent_count = trim_it->m_deps_left;
3333 if (trim_it->m_deps_left == 0 && trim_it->m_tx_size <= m_max_cluster_size) {
3334 trim_heap.push_back(trim_it);
3337 Assume(deps_it == deps_by_child.end());
3341 deps_by_parent = deps_by_child;
3342 std::sort(deps_by_parent.begin(), deps_by_parent.end(), [](
auto& a,
auto& b)
noexcept { return a.first < b.first; });
3346 deps_it = deps_by_parent.begin();
3347 for (
auto& trim_entry : trim_data) {
3348 trim_entry.m_children_count = 0;
3349 trim_entry.m_children_offset = deps_it - deps_by_parent.begin();
3350 while (deps_it != deps_by_parent.end() && deps_it->first == trim_entry.m_index) {
3351 ++trim_entry.m_children_count;
3355 Assume(deps_it == deps_by_parent.end());
3358 std::make_heap(trim_heap.begin(), trim_heap.end(), cmp_fn);
3372 while (!trim_heap.empty()) {
3374 std::pop_heap(trim_heap.begin(), trim_heap.end(), cmp_fn);
3376 auto& entry = *trim_heap.back();
3377 trim_heap.pop_back();
3380 entry.m_uf_parent = &entry;
3381 entry.m_uf_count = 1;
3382 entry.m_uf_size = entry.m_tx_size;
3385 current_deps.clear();
3386 for (
auto& [par, chl] : std::span{deps_by_child}.subspan(entry.m_parent_offset, entry.m_parent_count)) {
3387 Assume(chl == entry.m_index);
3388 current_deps.push_back(find_fn(&*locate_fn(par)));
3390 std::sort(current_deps.begin(), current_deps.end());
3391 current_deps.erase(std::unique(current_deps.begin(), current_deps.end()), current_deps.end());
3394 uint32_t new_count = 1;
3395 uint64_t new_size = entry.m_tx_size;
3396 for (TrimTxData* ptr : current_deps) {
3397 new_count += ptr->m_uf_count;
3398 new_size += ptr->m_uf_size;
3401 if (new_count > m_max_cluster_count || new_size > m_max_cluster_size)
continue;
3405 for (TrimTxData* ptr : current_deps) rep = union_fn(ptr, rep);
3407 entry.m_deps_left = uint32_t(-1);
3409 for (
auto& [par, chl] : std::span{deps_by_parent}.subspan(entry.m_children_offset, entry.m_children_count)) {
3410 Assume(par == entry.m_index);
3411 auto chl_it = locate_fn(chl);
3414 Assume(chl_it->m_deps_left > 0);
3415 if (--chl_it->m_deps_left == 0) {
3416 trim_heap.push_back(chl_it);
3417 std::push_heap(trim_heap.begin(), trim_heap.end(), cmp_fn);
3426 for (
const auto& trim_entry : trim_data) {
3427 if (trim_entry.m_deps_left != uint32_t(-1)) {
3428 ret.push_back(m_entries[trim_entry.m_index].m_ref);
3429 clusterset.m_to_remove.push_back(trim_entry.m_index);
3433 clusterset.m_group_data.reset();
3434 clusterset.m_oversized =
false;
3439size_t TxGraphImpl::GetMainMemoryUsage() noexcept
3443 ApplyDependencies(0);
3446 m_main_clusterset.m_cluster_usage +
3448 sizeof(Entry) * m_main_clusterset.m_txcount +
3460 m_graph->UnlinkRef(m_index);
3468 if (m_graph) m_graph->UnlinkRef(m_index);
3472 m_graph = other.m_graph;
3473 m_index = other.m_index;
3474 other.m_graph =
nullptr;
3482 if (other.m_graph) other.m_graph->UpdateRef(other.m_index, *
this);
3484 std::swap(m_graph, other.m_graph);
3485 std::swap(m_index, other.m_index);
3488std::unique_ptr<TxGraph>
MakeTxGraph(
unsigned max_cluster_count, uint64_t max_cluster_size, uint64_t acceptable_iters)
noexcept
3490 return std::make_unique<TxGraphImpl>(max_cluster_count, max_cluster_size, acceptable_iters);
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.
I randrange(I range) noexcept
Generate a random integer in the range [0..range), with range > 0.
Interface returned by GetBlockBuilder.
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.
size_t DynamicMemoryUsage() const noexcept
const SetType & Positions() const noexcept
Get the set of transactions positions in use.
void Compact() noexcept
Reduce memory usage if possible.
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::vector< FeeFrac > ChunkLinearization(const DepGraph< SetType > &depgraph, std::span< const DepGraphIndex > linearization) noexcept
Compute the feerates of the chunks of linearization.
std::tuple< std::vector< DepGraphIndex >, bool, uint64_t > 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.
static size_t DynamicUsage(const int8_t &v)
Dynamic memory usage for built-in types is zero.
static size_t MallocUsage(size_t alloc)
Compute the total memory used by allocating alloc bytes.
std::vector< T > Split(const std::span< const char > &sp, std::string_view separators, bool include_sep=false)
Split a string on any char found in separators, returning a vector.
Data structure storing a fee and size, ordered by increasing fee/size.
bool IsEmpty() const noexcept
Check if this is empty (size and fee are 0).
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, uint64_t max_cluster_size, uint64_t acceptable_iters) noexcept
Construct a new TxGraph with the specified limit on the number of transactions within a cluster,...
static constexpr unsigned MAX_CLUSTER_COUNT_LIMIT
void ClearShrink(V &v) noexcept
Clear a vector (or std::deque) and release its allocated memory.