25static constexpr int MAX_LEVELS{2};
31using LinearizationIndex = uint32_t;
33using ClusterSetIndex = uint32_t;
36enum class QualityLevel
41 NEEDS_SPLIT_ACCEPTABLE,
56 friend class TxGraphImpl;
64 std::vector<GraphIndex> m_mapping;
67 std::vector<DepGraphIndex> m_linearization;
71 ClusterSetIndex m_setindex{ClusterSetIndex(-1)};
79 Cluster() noexcept = delete;
81 explicit Cluster(uint64_t
sequence) noexcept;
83 explicit Cluster(uint64_t
sequence, TxGraphImpl& graph, const
FeePerWeight& feerate, GraphIndex graph_index) noexcept;
86 Cluster(const Cluster&) = delete;
87 Cluster& operator=(const Cluster&) = delete;
88 Cluster(Cluster&&) = delete;
89 Cluster& operator=(Cluster&&) = delete;
94 bool IsAcceptable(
bool after_split = false) const noexcept
96 return m_quality == QualityLevel::ACCEPTABLE || m_quality == QualityLevel::OPTIMAL ||
97 (after_split && m_quality == QualityLevel::NEEDS_SPLIT_ACCEPTABLE);
100 bool IsOptimal() const noexcept
102 return m_quality == QualityLevel::OPTIMAL;
105 bool NeedsSplitting() const noexcept
107 return m_quality == QualityLevel::NEEDS_SPLIT ||
108 m_quality == QualityLevel::NEEDS_SPLIT_ACCEPTABLE;
111 LinearizationIndex GetTxCount() const noexcept {
return m_linearization.size(); }
113 GraphIndex GetClusterEntry(
DepGraphIndex index)
const noexcept {
return m_mapping[index]; }
115 void UpdateMapping(
DepGraphIndex cluster_idx, GraphIndex graph_idx)
noexcept { m_mapping[cluster_idx] = graph_idx; }
117 void Updated(TxGraphImpl& graph)
noexcept;
119 Cluster* CopyToStaging(TxGraphImpl& graph)
const noexcept;
121 void GetConflicts(
const TxGraphImpl& graph, std::vector<Cluster*>&
out)
const noexcept;
124 void MakeStagingTransactionsMissing(TxGraphImpl& graph)
noexcept;
126 void Clear(TxGraphImpl& graph)
noexcept;
128 void MoveToMain(TxGraphImpl& graph)
noexcept;
134 void ApplyRemovals(TxGraphImpl& graph, std::span<GraphIndex>& to_remove)
noexcept;
137 [[nodiscard]]
bool Split(TxGraphImpl& graph)
noexcept;
139 void Merge(TxGraphImpl& graph, Cluster& cluster)
noexcept;
141 void ApplyDependencies(TxGraphImpl& graph, std::span<std::pair<GraphIndex, GraphIndex>> to_apply)
noexcept;
143 void Relinearize(TxGraphImpl& graph, uint64_t max_iters)
noexcept;
145 void AppendChunkFeerates(std::vector<FeeFrac>&
ret)
const noexcept;
151 void GetAncestorRefs(
const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>&
args, std::vector<TxGraph::Ref*>& output)
noexcept;
154 void GetDescendantRefs(
const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>&
args, std::vector<TxGraph::Ref*>& output)
noexcept;
158 bool GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos)
noexcept;
166 void SanityCheck(
const TxGraphImpl& graph,
int level)
const;
193class TxGraphImpl final :
public TxGraph
195 friend class Cluster;
196 friend class BlockBuilderImpl;
207 uint32_t m_cluster_offset;
209 uint32_t m_cluster_count;
211 uint32_t m_deps_offset;
213 uint32_t m_deps_count;
220 std::vector<GroupEntry> m_groups;
222 std::vector<Cluster*> m_group_clusters;
225 bool m_group_oversized;
232 std::array<std::vector<std::unique_ptr<Cluster>>, int(
QualityLevel::NONE)> m_clusters;
234 std::vector<GraphIndex> m_to_remove;
237 std::vector<std::pair<GraphIndex, GraphIndex>> m_deps_to_add;
239 std::optional<GroupData> m_group_data = GroupData{};
243 std::vector<GraphIndex> m_removed;
246 GraphIndex m_txcount{0};
249 std::optional<bool> m_oversized{
false};
251 ClusterSet() noexcept = default;
255 ClusterSet m_main_clusterset;
257 std::optional<ClusterSet> m_staging_clusterset;
259 uint64_t m_next_sequence_counter{0};
265 mutable GraphIndex m_graph_index;
267 LinearizationIndex m_chunk_count;
269 ChunkData(GraphIndex graph_index, LinearizationIndex chunk_count) noexcept :
270 m_graph_index{graph_index}, m_chunk_count{chunk_count} {}
274 static std::strong_ordering CompareClusters(Cluster* a, Cluster* b)
noexcept
277 if (a ==
nullptr || b ==
nullptr) {
278 return (a !=
nullptr) <=> (b !=
nullptr);
281 Assume(a == b || a->m_sequence != b->m_sequence);
282 return a->m_sequence <=> b->m_sequence;
286 std::strong_ordering CompareMainTransactions(GraphIndex a, GraphIndex b)
const noexcept
288 Assume(a < m_entries.size() && b < m_entries.size());
289 const auto& entry_a = m_entries[a];
290 const auto& entry_b = m_entries[b];
292 auto feerate_cmp = FeeRateCompare(entry_b.m_main_chunk_feerate, entry_a.m_main_chunk_feerate);
293 if (feerate_cmp < 0)
return std::strong_ordering::less;
294 if (feerate_cmp > 0)
return std::strong_ordering::greater;
296 const auto& locator_a = entry_a.m_locator[0];
297 const auto& locator_b = entry_b.m_locator[0];
298 Assume(locator_a.IsPresent() && locator_b.IsPresent());
299 if (locator_a.cluster != locator_b.cluster) {
300 return CompareClusters(locator_a.cluster, locator_b.cluster);
303 return entry_a.m_main_lin_index <=> entry_b.m_main_lin_index;
309 const TxGraphImpl*
const m_graph;
311 explicit ChunkOrder(
const TxGraphImpl* graph) : m_graph(graph) {}
313 bool operator()(
const ChunkData& a,
const ChunkData& b)
const noexcept
315 return m_graph->CompareMainTransactions(a.m_graph_index, b.m_graph_index) < 0;
320 using ChunkIndex = std::set<ChunkData, ChunkOrder>;
324 ChunkIndex m_main_chunkindex;
326 size_t m_main_chunkindex_observers{0};
328 std::vector<ChunkIndex::node_type> m_main_chunkindex_discarded;
363 Cluster* cluster{
nullptr};
368 void SetMissing() noexcept { cluster =
nullptr; index = 0; }
370 void SetRemoved() noexcept { cluster =
nullptr; index =
DepGraphIndex(-1); }
372 void SetPresent(Cluster* c,
DepGraphIndex i)
noexcept { cluster = c; index = i; }
374 bool IsMissing() const noexcept {
return cluster ==
nullptr && index == 0; }
376 bool IsRemoved() const noexcept {
return cluster ==
nullptr && index ==
DepGraphIndex(-1); }
378 bool IsPresent() const noexcept {
return cluster !=
nullptr; }
388 ChunkIndex::iterator m_main_chunkindex_iterator;
390 Locator m_locator[MAX_LEVELS];
394 LinearizationIndex m_main_lin_index;
398 std::vector<Entry> m_entries;
401 std::vector<GraphIndex> m_unlinked;
405 explicit TxGraphImpl(
DepGraphIndex max_cluster_count) noexcept :
406 m_max_cluster_count(max_cluster_count),
407 m_main_chunkindex(ChunkOrder(
this))
409 Assume(max_cluster_count >= 1);
414 ~TxGraphImpl() noexcept;
417 TxGraphImpl(const TxGraphImpl&) = delete;
418 TxGraphImpl& operator=(const TxGraphImpl&) = delete;
419 TxGraphImpl(TxGraphImpl&&) = delete;
420 TxGraphImpl& operator=(TxGraphImpl&&) = delete;
425 void SwapIndexes(GraphIndex a, GraphIndex b) noexcept;
428 Cluster* FindCluster(GraphIndex idx,
int level) const noexcept;
430 std::unique_ptr<Cluster> ExtractCluster(
int level, QualityLevel quality, ClusterSetIndex setindex) noexcept;
432 void DeleteCluster(Cluster& cluster) noexcept;
434 ClusterSetIndex InsertCluster(
int level,
std::unique_ptr<Cluster>&& cluster, QualityLevel quality) noexcept;
436 void SetClusterQuality(
int level, QualityLevel old_quality, ClusterSetIndex old_index, QualityLevel new_quality) noexcept;
438 int GetTopLevel() const noexcept {
return m_staging_clusterset.has_value(); }
440 int GetSpecifiedLevel(
bool main_only)
const noexcept {
return m_staging_clusterset.has_value() && !main_only; }
442 ClusterSet& GetClusterSet(
int level)
noexcept;
443 const ClusterSet& GetClusterSet(
int level)
const noexcept;
445 void ClearLocator(
int level, GraphIndex index)
noexcept;
447 std::vector<Cluster*> GetConflicts() const noexcept;
449 void ClearChunkData(Entry& entry) noexcept;
451 void CreateChunkData(GraphIndex idx, LinearizationIndex chunk_count) noexcept;
456 void UpdateRef(GraphIndex idx, Ref& new_location) noexcept final
458 auto& entry = m_entries[idx];
459 Assume(entry.m_ref !=
nullptr);
460 entry.m_ref = &new_location;
464 void UnlinkRef(GraphIndex idx)
noexcept final
466 auto& entry = m_entries[idx];
467 Assume(entry.m_ref !=
nullptr);
468 Assume(m_main_chunkindex_observers == 0 || !entry.m_locator[0].IsPresent());
469 entry.m_ref =
nullptr;
472 bool exists_anywhere{
false};
474 for (
int level = 0; level <= GetTopLevel(); ++level) {
475 if (entry.m_locator[level].IsPresent()) {
476 exists_anywhere =
true;
478 }
else if (entry.m_locator[level].IsRemoved()) {
482 auto& clusterset = GetClusterSet(level);
483 clusterset.m_to_remove.push_back(idx);
485 clusterset.m_group_data = std::nullopt;
491 if (level == GetTopLevel() && clusterset.m_oversized ==
true) {
492 clusterset.m_oversized = std::nullopt;
496 m_unlinked.push_back(idx);
497 if (!exists_anywhere) Compact();
504 void Compact() noexcept;
508 Cluster* PullIn(Cluster* cluster) noexcept;
511 void ApplyRemovals(
int up_to_level) noexcept;
513 void Split(Cluster& cluster) noexcept;
515 void SplitAll(
int up_to_level) noexcept;
517 void GroupClusters(
int level) noexcept;
519 void Merge(
std::span<Cluster*> to_merge) noexcept;
521 void ApplyDependencies(
int level) noexcept;
523 void MakeAcceptable(Cluster& cluster) noexcept;
525 void MakeAllAcceptable(
int level) noexcept;
529 Ref AddTransaction(const
FeePerWeight& feerate) noexcept final;
530 void RemoveTransaction(const Ref& arg) noexcept final;
531 void AddDependency(const Ref& parent, const Ref& child) noexcept final;
532 void SetTransactionFee(const Ref&, int64_t
fee) noexcept final;
534 void DoWork() noexcept final;
536 void StartStaging() noexcept final;
537 void CommitStaging() noexcept final;
538 void AbortStaging() noexcept final;
539 bool HaveStaging() const noexcept final {
return m_staging_clusterset.has_value(); }
541 bool Exists(
const Ref& arg,
bool main_only =
false) noexcept final;
542 FeePerWeight GetMainChunkFeerate(const Ref& arg) noexcept final;
543 FeePerWeight GetIndividualFeerate(const Ref& arg) noexcept final;
544 std::vector<Ref*> GetCluster(const Ref& arg,
bool main_only = false) noexcept final;
545 std::vector<Ref*> GetAncestors(const Ref& arg,
bool main_only = false) noexcept final;
546 std::vector<Ref*> GetDescendants(const Ref& arg,
bool main_only = false) noexcept final;
547 std::vector<Ref*> GetAncestorsUnion(
std::span<const Ref* const>
args,
bool main_only = false) noexcept final;
548 std::vector<Ref*> GetDescendantsUnion(
std::span<const Ref* const>
args,
bool main_only = false) noexcept final;
549 GraphIndex GetTransactionCount(
bool main_only = false) noexcept final;
550 bool IsOversized(
bool main_only = false) noexcept final;
551 std::strong_ordering CompareMainOrder(const Ref& a, const Ref& b) noexcept final;
552 GraphIndex CountDistinctClusters(
std::span<const Ref* const> refs,
bool main_only = false) noexcept final;
555 std::unique_ptr<BlockBuilder> GetBlockBuilder() noexcept final;
558 void SanityCheck() const final;
561TxGraphImpl::ClusterSet& TxGraphImpl::GetClusterSet(
int level) noexcept
563 if (level == 0)
return m_main_clusterset;
565 Assume(m_staging_clusterset.has_value());
566 return *m_staging_clusterset;
569const TxGraphImpl::ClusterSet& TxGraphImpl::GetClusterSet(
int level)
const noexcept
571 if (level == 0)
return m_main_clusterset;
573 Assume(m_staging_clusterset.has_value());
574 return *m_staging_clusterset;
582 TxGraphImpl*
const m_graph;
584 std::set<Cluster*> m_excluded_clusters;
586 TxGraphImpl::ChunkIndex::const_iterator m_cur_iter;
589 Cluster* m_cur_cluster;
591 bool m_known_end_of_cluster;
594 void Next() noexcept;
598 BlockBuilderImpl(TxGraphImpl& graph) noexcept;
601 ~BlockBuilderImpl() final;
603 void Include() noexcept final;
604 void Skip() noexcept final;
607void TxGraphImpl::ClearChunkData(Entry& entry) noexcept
609 if (entry.m_main_chunkindex_iterator != m_main_chunkindex.end()) {
610 Assume(m_main_chunkindex_observers == 0);
613 m_main_chunkindex_discarded.emplace_back(m_main_chunkindex.extract(entry.m_main_chunkindex_iterator));
614 entry.m_main_chunkindex_iterator = m_main_chunkindex.end();
618void TxGraphImpl::CreateChunkData(GraphIndex idx, LinearizationIndex chunk_count)
noexcept
620 auto& entry = m_entries[idx];
621 if (!m_main_chunkindex_discarded.empty()) {
623 auto&
node = m_main_chunkindex_discarded.back().value();
624 node.m_graph_index = idx;
625 node.m_chunk_count = chunk_count;
626 auto insert_result = m_main_chunkindex.insert(std::move(m_main_chunkindex_discarded.back()));
627 Assume(insert_result.inserted);
628 entry.m_main_chunkindex_iterator = insert_result.position;
629 m_main_chunkindex_discarded.pop_back();
632 auto emplace_result = m_main_chunkindex.emplace(idx, chunk_count);
633 Assume(emplace_result.second);
634 entry.m_main_chunkindex_iterator = emplace_result.first;
638void TxGraphImpl::ClearLocator(
int level, GraphIndex idx)
noexcept
640 auto& entry = m_entries[idx];
641 auto& clusterset = GetClusterSet(level);
642 Assume(entry.m_locator[level].IsPresent());
644 if (level == 0 || !entry.m_locator[level - 1].IsPresent()) {
645 entry.m_locator[level].SetMissing();
647 entry.m_locator[level].SetRemoved();
648 clusterset.m_removed.push_back(idx);
651 --clusterset.m_txcount;
653 if (level == 0 && GetTopLevel() == 1) {
654 if (entry.m_locator[1].IsRemoved()) {
655 entry.m_locator[1].SetMissing();
656 }
else if (!entry.m_locator[1].IsPresent()) {
657 --m_staging_clusterset->m_txcount;
660 if (level == 0) ClearChunkData(entry);
663void Cluster::Updated(TxGraphImpl& graph)
noexcept
667 auto& entry = graph.m_entries[m_mapping[idx]];
670 if (m_level == 0) graph.ClearChunkData(entry);
671 entry.m_locator[m_level].SetPresent(
this, idx);
678 if (m_level == 0 && IsAcceptable()) {
680 LinearizationIndex lin_idx{0};
682 for (
unsigned chunk_idx = 0; chunk_idx < chunking.NumChunksLeft(); ++chunk_idx) {
683 auto chunk = chunking.GetChunk(chunk_idx);
684 auto chunk_count = chunk.transactions.Count();
689 GraphIndex graph_idx = m_mapping[idx];
690 auto& entry = graph.m_entries[graph_idx];
691 entry.m_main_lin_index = lin_idx++;
693 Assume(chunk.transactions[idx]);
694 chunk.transactions.Reset(idx);
695 if (chunk.transactions.None()) {
697 if (chunk_count == 1 && chunk_idx + 1 == chunking.NumChunksLeft()) {
701 chunk_count = LinearizationIndex(-1);
703 graph.CreateChunkData(graph_idx, chunk_count);
711void Cluster::GetConflicts(
const TxGraphImpl& graph, std::vector<Cluster*>&
out)
const noexcept
714 for (
auto i : m_linearization) {
715 auto& entry = graph.m_entries[m_mapping[i]];
718 if (entry.m_locator[0].IsPresent()) {
719 out.push_back(entry.m_locator[0].cluster);
724std::vector<Cluster*> TxGraphImpl::GetConflicts() const noexcept
726 Assume(GetTopLevel() == 1);
727 auto& clusterset = GetClusterSet(1);
728 std::vector<Cluster*>
ret;
730 for (
auto i : clusterset.m_removed) {
731 auto& entry = m_entries[i];
732 if (entry.m_locator[0].IsPresent()) {
733 ret.push_back(entry.m_locator[0].cluster);
738 auto& clusters = clusterset.m_clusters[quality];
739 for (
const auto& cluster : clusters) {
740 cluster->GetConflicts(*
this,
ret);
744 std::sort(
ret.begin(),
ret.end(), [](Cluster* a, Cluster* b)
noexcept { return CompareClusters(a, b) < 0; });
745 ret.erase(std::unique(
ret.begin(),
ret.end()),
ret.end());
749Cluster* Cluster::CopyToStaging(TxGraphImpl& graph)
const noexcept
752 auto ret = std::make_unique<Cluster>(graph.m_next_sequence_counter++);
753 auto ptr =
ret.get();
755 ptr->m_depgraph = m_depgraph;
756 ptr->m_mapping = m_mapping;
757 ptr->m_linearization = m_linearization;
759 graph.InsertCluster(1, std::move(
ret), m_quality);
765void Cluster::ApplyRemovals(TxGraphImpl& graph, std::span<GraphIndex>& to_remove)
noexcept
768 Assume(!to_remove.empty());
771 GraphIndex idx = to_remove.front();
772 Assume(idx < graph.m_entries.size());
773 auto& entry = graph.m_entries[idx];
774 auto& locator = entry.m_locator[m_level];
776 if (locator.cluster !=
this)
break;
778 todo.Set(locator.index);
782 m_mapping[locator.index] = GraphIndex(-1);
785 entry.m_main_lin_index = LinearizationIndex(-1);
788 graph.ClearLocator(m_level, idx);
789 to_remove = to_remove.subspan(1);
790 }
while(!to_remove.empty());
792 auto quality = m_quality;
800 while (!m_linearization.empty() && todo[m_linearization.back()]) {
801 todo.Reset(m_linearization.back());
802 m_linearization.pop_back();
807 if (IsAcceptable(
true)) {
808 quality = QualityLevel::NEEDS_SPLIT_ACCEPTABLE;
810 quality = QualityLevel::NEEDS_SPLIT;
814 m_linearization.erase(std::remove_if(
815 m_linearization.begin(),
816 m_linearization.end(),
817 [&](
auto pos) { return todo[pos]; }), m_linearization.end());
818 quality = QualityLevel::NEEDS_SPLIT;
820 graph.SetClusterQuality(m_level, m_quality, m_setindex, quality);
824void Cluster::Clear(TxGraphImpl& graph)
noexcept
826 for (
auto i : m_linearization) {
827 graph.ClearLocator(m_level, m_mapping[i]);
830 m_linearization.clear();
834void Cluster::MoveToMain(TxGraphImpl& graph)
noexcept
837 for (
auto i : m_linearization) {
838 GraphIndex idx = m_mapping[i];
839 auto& entry = graph.m_entries[idx];
840 entry.m_locator[1].SetMissing();
842 auto quality = m_quality;
843 auto cluster = graph.ExtractCluster(1, quality, m_setindex);
844 graph.InsertCluster(0, std::move(cluster), quality);
848void Cluster::AppendChunkFeerates(std::vector<FeeFrac>&
ret)
const noexcept
851 ret.reserve(
ret.size() + chunk_feerates.size());
852 ret.insert(
ret.end(), chunk_feerates.begin(), chunk_feerates.end());
860 QualityLevel new_quality = IsAcceptable(
true) ? QualityLevel::ACCEPTABLE
861 : QualityLevel::NEEDS_RELINEARIZE;
868 if (new_quality == QualityLevel::ACCEPTABLE) {
875 std::vector<std::pair<Cluster*, DepGraphIndex>> remap(m_depgraph.
PositionRange());
876 std::vector<Cluster*> new_clusters;
881 if (first && component == todo) {
884 graph.SetClusterQuality(m_level, m_quality, m_setindex, new_quality);
892 auto new_cluster = std::make_unique<Cluster>(graph.m_next_sequence_counter++);
893 new_clusters.push_back(new_cluster.get());
896 for (
auto i : component) {
899 graph.InsertCluster(m_level, std::move(new_cluster), new_quality);
903 for (
auto i : m_linearization) {
905 Cluster* new_cluster = remap[i].first;
907 remap[i].second = new_cluster->m_depgraph.AddTransaction(m_depgraph.
FeeRate(i));
909 new_cluster->m_mapping.push_back(m_mapping[i]);
912 new_cluster->m_linearization.push_back(remap[i].second);
915 for (
auto i : m_linearization) {
917 Cluster* new_cluster = remap[i].first;
920 for (
auto par : m_depgraph.
GetReducedParents(i)) new_parents.Set(remap[par].second);
921 new_cluster->m_depgraph.AddDependencies(new_parents, remap[i].second);
924 for (Cluster* new_cluster : new_clusters) {
925 new_cluster->Updated(graph);
930 m_linearization.clear();
934void Cluster::Merge(TxGraphImpl& graph, Cluster& other)
noexcept
937 std::vector<DepGraphIndex> remap(other.m_depgraph.PositionRange());
939 for (
auto pos : other.m_linearization) {
940 auto idx = other.m_mapping[pos];
942 auto new_pos = m_depgraph.
AddTransaction(other.m_depgraph.FeeRate(pos));
943 remap[pos] = new_pos;
944 if (new_pos == m_mapping.size()) {
945 m_mapping.push_back(idx);
947 m_mapping[new_pos] = idx;
949 m_linearization.push_back(new_pos);
954 for (
auto par : other.m_depgraph.GetReducedParents(pos)) {
955 parents.Set(remap[par]);
961 auto& entry = graph.m_entries[idx];
964 if (m_level == 0) graph.ClearChunkData(entry);
965 entry.m_locator[m_level].SetPresent(
this, new_pos);
969 other.m_linearization.clear();
970 other.m_mapping.clear();
973void Cluster::ApplyDependencies(TxGraphImpl& graph, std::span<std::pair<GraphIndex, GraphIndex>> to_apply)
noexcept
984 std::sort(to_apply.begin(), to_apply.end(), [](
auto& a,
auto& b) { return a.second < b.second; });
986 auto it = to_apply.begin();
987 while (it != to_apply.end()) {
988 auto& first_child = graph.m_entries[it->second].m_locator[m_level];
989 const auto child_idx = first_child.index;
993 while (it != to_apply.end()) {
994 auto& child = graph.m_entries[it->second].m_locator[m_level];
995 auto& parent = graph.m_entries[it->first].m_locator[m_level];
996 Assume(child.cluster ==
this && parent.cluster ==
this);
997 if (child.index != child_idx)
break;
998 parents.Set(parent.index);
1016TxGraphImpl::~TxGraphImpl() noexcept
1020 for (
auto& entry : m_entries) {
1021 if (entry.m_ref !=
nullptr) {
1022 GetRefGraph(*entry.m_ref) =
nullptr;
1027std::unique_ptr<Cluster> TxGraphImpl::ExtractCluster(
int level, QualityLevel quality, ClusterSetIndex setindex)
noexcept
1031 auto& clusterset = GetClusterSet(level);
1032 auto& quality_clusters = clusterset.m_clusters[int(quality)];
1033 Assume(setindex < quality_clusters.size());
1036 std::unique_ptr<Cluster>
ret = std::move(quality_clusters[setindex]);
1038 ret->m_setindex = ClusterSetIndex(-1);
1042 auto max_setindex = quality_clusters.size() - 1;
1043 if (setindex != max_setindex) {
1045 quality_clusters.back()->m_setindex = setindex;
1046 quality_clusters.back()->m_level = level;
1047 quality_clusters[setindex] = std::move(quality_clusters.back());
1050 quality_clusters.pop_back();
1055ClusterSetIndex TxGraphImpl::InsertCluster(
int level, std::unique_ptr<Cluster>&& cluster, QualityLevel quality)
noexcept
1063 auto& clusterset = GetClusterSet(level);
1064 auto& quality_clusters = clusterset.m_clusters[int(quality)];
1065 ClusterSetIndex
ret = quality_clusters.size();
1066 cluster->m_quality = quality;
1067 cluster->m_setindex =
ret;
1068 cluster->m_level = level;
1069 quality_clusters.push_back(std::move(cluster));
1073void TxGraphImpl::SetClusterQuality(
int level, QualityLevel old_quality, ClusterSetIndex old_index, QualityLevel new_quality)
noexcept
1078 if (old_quality == new_quality)
return;
1080 auto cluster_ptr = ExtractCluster(level, old_quality, old_index);
1082 InsertCluster(level, std::move(cluster_ptr), new_quality);
1085void TxGraphImpl::DeleteCluster(Cluster& cluster)
noexcept
1088 auto cluster_ptr = ExtractCluster(cluster.m_level, cluster.m_quality, cluster.m_setindex);
1090 cluster_ptr.reset();
1093Cluster* TxGraphImpl::FindCluster(GraphIndex idx,
int level)
const noexcept
1095 Assume(level >= 0 && level <= GetTopLevel());
1096 auto& entry = m_entries[idx];
1098 for (
int l = level; l >= 0; --l) {
1101 if (entry.m_locator[l].IsMissing())
continue;
1103 if (entry.m_locator[l].IsRemoved())
break;
1105 return entry.m_locator[l].cluster;
1111Cluster* TxGraphImpl::PullIn(Cluster* cluster)
noexcept
1113 int to_level = GetTopLevel();
1115 int level = cluster->m_level;
1116 Assume(level <= to_level);
1121 MakeAcceptable(*cluster);
1122 cluster = cluster->CopyToStaging(*
this);
1127void TxGraphImpl::ApplyRemovals(
int up_to_level)
noexcept
1129 Assume(up_to_level >= 0 && up_to_level <= GetTopLevel());
1130 for (
int level = 0; level <= up_to_level; ++level) {
1131 auto& clusterset = GetClusterSet(level);
1132 auto& to_remove = clusterset.m_to_remove;
1134 if (to_remove.empty())
continue;
1137 for (GraphIndex index : to_remove) {
1138 auto cluster = FindCluster(index, level);
1139 if (cluster !=
nullptr) PullIn(cluster);
1143 std::sort(to_remove.begin(), to_remove.end(), [&](GraphIndex a, GraphIndex b)
noexcept {
1144 Cluster* cluster_a = m_entries[a].m_locator[level].cluster;
1145 Cluster* cluster_b = m_entries[b].m_locator[level].cluster;
1146 return CompareClusters(cluster_a, cluster_b) < 0;
1149 std::span to_remove_span{to_remove};
1150 while (!to_remove_span.empty()) {
1151 Cluster* cluster = m_entries[to_remove_span.front()].m_locator[level].cluster;
1152 if (cluster !=
nullptr) {
1155 cluster->ApplyRemovals(*
this, to_remove_span);
1159 to_remove_span = to_remove_span.subspan(1);
1167void TxGraphImpl::SwapIndexes(GraphIndex a, GraphIndex b)
noexcept
1169 Assume(a < m_entries.size());
1170 Assume(b < m_entries.size());
1172 std::swap(m_entries[a], m_entries[b]);
1174 for (
int i = 0; i < 2; ++i) {
1175 GraphIndex idx = i ? b : a;
1176 Entry& entry = m_entries[idx];
1178 if (entry.m_ref) GetRefIndex(*entry.m_ref) = idx;
1180 if (entry.m_main_chunkindex_iterator != m_main_chunkindex.end()) {
1181 entry.m_main_chunkindex_iterator->m_graph_index = idx;
1185 for (
int level = 0; level < MAX_LEVELS; ++level) {
1186 Locator& locator = entry.m_locator[level];
1187 if (locator.IsPresent()) {
1188 locator.cluster->UpdateMapping(locator.index, idx);
1194void TxGraphImpl::Compact() noexcept
1198 if (!m_main_clusterset.m_deps_to_add.empty())
return;
1199 if (!m_main_clusterset.m_to_remove.empty())
return;
1200 Assume(m_main_clusterset.m_removed.empty());
1201 if (m_staging_clusterset.has_value()) {
1202 if (!m_staging_clusterset->m_deps_to_add.empty())
return;
1203 if (!m_staging_clusterset->m_to_remove.empty())
return;
1204 if (!m_staging_clusterset->m_removed.empty())
return;
1214 std::sort(m_unlinked.begin(), m_unlinked.end(), std::greater{});
1216 auto last = GraphIndex(-1);
1217 for (GraphIndex idx : m_unlinked) {
1224 Entry& entry = m_entries[idx];
1225 Assume(entry.m_ref ==
nullptr);
1227 for (
int level = 0; level < MAX_LEVELS; ++level) {
1228 Assume(!entry.m_locator[level].IsPresent());
1232 if (idx != m_entries.size() - 1) SwapIndexes(idx, m_entries.size() - 1);
1234 m_entries.pop_back();
1243 ApplyRemovals(cluster.m_level);
1244 bool del = cluster.Split(*
this);
1247 DeleteCluster(cluster);
1251void TxGraphImpl::SplitAll(
int up_to_level)
noexcept
1253 Assume(up_to_level >= 0 && up_to_level <= GetTopLevel());
1255 ApplyRemovals(up_to_level);
1256 for (
int level = 0; level <= up_to_level; ++level) {
1257 for (
auto quality : {QualityLevel::NEEDS_SPLIT, QualityLevel::NEEDS_SPLIT_ACCEPTABLE}) {
1258 auto& queue = GetClusterSet(level).m_clusters[int(quality)];
1259 while (!queue.empty()) {
1260 Split(*queue.back().get());
1266void TxGraphImpl::GroupClusters(
int level)
noexcept
1268 auto& clusterset = GetClusterSet(level);
1270 if (clusterset.m_group_data.has_value())
return;
1280 std::vector<std::pair<Cluster*, uint64_t>> an_clusters;
1285 std::vector<std::pair<std::pair<GraphIndex, GraphIndex>, uint64_t>> an_deps;
1289 an_deps.reserve(clusterset.m_deps_to_add.size());
1290 for (
const auto& [par, chl] : clusterset.m_deps_to_add) {
1291 auto par_cluster = FindCluster(par, level);
1292 auto chl_cluster = FindCluster(chl, level);
1294 if (par_cluster ==
nullptr || chl_cluster ==
nullptr)
continue;
1295 an_clusters.emplace_back(par_cluster, par_cluster->m_sequence);
1298 if (chl_cluster != par_cluster) an_clusters.emplace_back(chl_cluster, chl_cluster->m_sequence);
1300 an_deps.emplace_back(std::pair{par, chl}, chl_cluster->m_sequence);
1304 std::sort(an_clusters.begin(), an_clusters.end(), [](
auto& a,
auto& b)
noexcept { return a.second < b.second; });
1305 an_clusters.erase(std::unique(an_clusters.begin(), an_clusters.end()), an_clusters.end());
1307 std::sort(an_deps.begin(), an_deps.end(), [&](
auto& a,
auto& b)
noexcept { return a.second < b.second; });
1313 struct PartitionData
1321 PartitionData* parent;
1327 std::vector<PartitionData> partition_data;
1330 auto locate_fn = [&](uint64_t
sequence)
noexcept -> PartitionData* {
1331 auto it = std::lower_bound(partition_data.begin(), partition_data.end(),
sequence,
1332 [](
auto& a, uint64_t seq)
noexcept { return a.sequence < seq; });
1333 Assume(it != partition_data.end());
1339 static constexpr auto find_root_fn = [](PartitionData*
data)
noexcept -> PartitionData* {
1343 auto par =
data->parent;
1344 data->parent = par->parent;
1352 static constexpr auto union_fn = [](PartitionData* arg1, PartitionData* arg2)
noexcept {
1355 auto rep1 = find_root_fn(arg1);
1356 auto rep2 = find_root_fn(arg2);
1357 if (rep1 == rep2)
return rep1;
1360 if (rep1->rank < rep2->rank) std::swap(rep1, rep2);
1361 rep2->parent = rep1;
1362 rep1->rank += (rep1->rank == rep2->rank);
1367 partition_data.resize(an_clusters.size());
1368 for (
size_t i = 0; i < an_clusters.size(); ++i) {
1369 partition_data[i].sequence = an_clusters[i].first->m_sequence;
1370 partition_data[i].parent = &partition_data[i];
1371 partition_data[i].rank = 0;
1376 Cluster* last_chl_cluster{
nullptr};
1377 PartitionData* last_partition{
nullptr};
1378 for (
const auto& [dep,
_] : an_deps) {
1379 auto [par, chl] = dep;
1380 auto par_cluster = FindCluster(par, level);
1381 auto chl_cluster = FindCluster(chl, level);
1382 Assume(chl_cluster !=
nullptr && par_cluster !=
nullptr);
1384 if (par_cluster == chl_cluster)
continue;
1386 if (chl_cluster == last_chl_cluster) {
1390 last_partition = union_fn(locate_fn(par_cluster->m_sequence), last_partition);
1392 last_chl_cluster = chl_cluster;
1393 last_partition = union_fn(locate_fn(par_cluster->m_sequence), locate_fn(chl_cluster->m_sequence));
1399 auto deps_it = an_deps.begin();
1400 for (
size_t i = 0; i < partition_data.size(); ++i) {
1401 auto&
data = partition_data[i];
1404 auto rep_seq = find_root_fn(&
data)->sequence;
1405 an_clusters[i].second = rep_seq;
1407 while (deps_it != an_deps.end()) {
1408 auto [par, chl] = deps_it->first;
1409 auto chl_cluster = FindCluster(chl, level);
1410 Assume(chl_cluster !=
nullptr);
1411 if (chl_cluster->m_sequence >
data.sequence)
break;
1412 deps_it->second = rep_seq;
1420 std::sort(an_deps.begin(), an_deps.end(), [](
auto& a,
auto& b)
noexcept { return a.second < b.second; });
1421 std::sort(an_clusters.begin(), an_clusters.end(), [](
auto& a,
auto& b)
noexcept { return a.second < b.second; });
1425 clusterset.m_group_data = GroupData{};
1426 clusterset.m_group_data->m_group_clusters.reserve(an_clusters.size());
1427 clusterset.m_group_data->m_group_oversized =
false;
1428 clusterset.m_deps_to_add.clear();
1429 clusterset.m_deps_to_add.reserve(an_deps.size());
1430 auto an_deps_it = an_deps.begin();
1431 auto an_clusters_it = an_clusters.begin();
1432 while (an_clusters_it != an_clusters.end()) {
1434 auto rep = an_clusters_it->second;
1436 auto& new_entry = clusterset.m_group_data->m_groups.emplace_back();
1437 new_entry.m_cluster_offset = clusterset.m_group_data->m_group_clusters.size();
1438 new_entry.m_cluster_count = 0;
1439 new_entry.m_deps_offset = clusterset.m_deps_to_add.size();
1440 new_entry.m_deps_count = 0;
1441 uint32_t total_count{0};
1443 while (an_clusters_it != an_clusters.end() && an_clusters_it->second == rep) {
1444 clusterset.m_group_data->m_group_clusters.push_back(an_clusters_it->first);
1445 total_count += an_clusters_it->first->GetTxCount();
1447 ++new_entry.m_cluster_count;
1450 while (an_deps_it != an_deps.end() && an_deps_it->second == rep) {
1451 clusterset.m_deps_to_add.push_back(an_deps_it->first);
1453 ++new_entry.m_deps_count;
1456 if (total_count > m_max_cluster_count) {
1457 clusterset.m_group_data->m_group_oversized =
true;
1460 Assume(an_deps_it == an_deps.end());
1461 Assume(an_clusters_it == an_clusters.end());
1462 clusterset.m_oversized = clusterset.m_group_data->m_group_oversized;
1466void TxGraphImpl::Merge(std::span<Cluster*> to_merge)
noexcept
1468 Assume(!to_merge.empty());
1470 if (to_merge.size() == 1)
return;
1475 size_t max_size_pos{0};
1476 DepGraphIndex max_size = to_merge[max_size_pos]->GetTxCount();
1477 for (
size_t i = 1; i < to_merge.size(); ++i) {
1479 if (size > max_size) {
1484 if (max_size_pos != 0) std::swap(to_merge[0], to_merge[max_size_pos]);
1487 for (
size_t i = 1; i < to_merge.size(); ++i) {
1488 to_merge[0]->Merge(*
this, *to_merge[i]);
1489 DeleteCluster(*to_merge[i]);
1493void TxGraphImpl::ApplyDependencies(
int level)
noexcept
1495 auto& clusterset = GetClusterSet(level);
1497 if (clusterset.m_oversized ==
true)
return;
1499 GroupClusters(level);
1500 Assume(clusterset.m_group_data.has_value());
1502 if (clusterset.m_deps_to_add.empty())
return;
1504 if (clusterset.m_group_data->m_group_oversized)
return;
1507 for (
const auto& group_entry : clusterset.m_group_data->m_groups) {
1508 auto cluster_span = std::span{clusterset.m_group_data->m_group_clusters}
1509 .subspan(group_entry.m_cluster_offset, group_entry.m_cluster_count);
1512 for (Cluster*& cluster : cluster_span) {
1513 cluster = PullIn(cluster);
1517 Merge(cluster_span);
1520 auto deps_span = std::span{clusterset.m_deps_to_add}
1521 .subspan(group_entry.m_deps_offset, group_entry.m_deps_count);
1522 Assume(!deps_span.empty());
1523 const auto& loc = m_entries[deps_span[0].second].m_locator[level];
1525 loc.cluster->ApplyDependencies(*
this, deps_span);
1529 clusterset.m_deps_to_add.clear();
1533 clusterset.m_group_data = GroupData{};
1536void Cluster::Relinearize(TxGraphImpl& graph, uint64_t max_iters)
noexcept
1539 Assume(!NeedsSplitting());
1541 if (IsOptimal())
return;
1543 uint64_t rng_seed = graph.m_rng.rand64();
1544 auto [linearization, optimal] =
Linearize(m_depgraph, max_iters, rng_seed, m_linearization);
1549 m_linearization = std::move(linearization);
1551 auto new_quality = optimal ? QualityLevel::OPTIMAL : QualityLevel::ACCEPTABLE;
1552 graph.SetClusterQuality(m_level, m_quality, m_setindex, new_quality);
1557void TxGraphImpl::MakeAcceptable(Cluster& cluster)
noexcept
1560 if (!cluster.NeedsSplitting() && !cluster.IsAcceptable()) {
1561 cluster.Relinearize(*
this, 10000);
1565void TxGraphImpl::MakeAllAcceptable(
int level)
noexcept
1567 ApplyDependencies(level);
1568 auto& clusterset = GetClusterSet(level);
1569 if (clusterset.m_oversized ==
true)
return;
1570 auto& queue = clusterset.m_clusters[int(QualityLevel::NEEDS_RELINEARIZE)];
1571 while (!queue.empty()) {
1572 MakeAcceptable(*queue.back().get());
1578Cluster::Cluster(uint64_t
sequence, TxGraphImpl& graph,
const FeePerWeight& feerate, GraphIndex graph_index) noexcept :
1583 m_mapping.push_back(graph_index);
1584 m_linearization.push_back(cluster_idx);
1589 Assume(m_main_chunkindex_observers == 0 || GetTopLevel() != 0);
1593 auto idx = m_entries.size();
1594 m_entries.emplace_back();
1595 auto& entry = m_entries.back();
1596 entry.m_main_chunkindex_iterator = m_main_chunkindex.end();
1598 GetRefGraph(
ret) =
this;
1599 GetRefIndex(
ret) = idx;
1601 auto cluster = std::make_unique<Cluster>(m_next_sequence_counter++, *
this, feerate, idx);
1602 auto cluster_ptr = cluster.get();
1603 int level = GetTopLevel();
1604 auto& clusterset = GetClusterSet(level);
1605 InsertCluster(level, std::move(cluster), QualityLevel::OPTIMAL);
1606 cluster_ptr->Updated(*
this);
1607 ++clusterset.m_txcount;
1612void TxGraphImpl::RemoveTransaction(
const Ref& arg)
noexcept
1616 if (GetRefGraph(arg) ==
nullptr)
return;
1617 Assume(GetRefGraph(arg) ==
this);
1618 Assume(m_main_chunkindex_observers == 0 || GetTopLevel() != 0);
1620 int level = GetTopLevel();
1621 auto cluster = FindCluster(GetRefIndex(arg), level);
1622 if (cluster ==
nullptr)
return;
1624 auto& clusterset = GetClusterSet(level);
1625 clusterset.m_to_remove.push_back(GetRefIndex(arg));
1627 clusterset.m_group_data.reset();
1628 if (clusterset.m_oversized ==
true) clusterset.m_oversized = std::nullopt;
1631void TxGraphImpl::AddDependency(
const Ref& parent,
const Ref& child)
noexcept
1635 if (GetRefGraph(parent) ==
nullptr || GetRefGraph(child) ==
nullptr)
return;
1636 Assume(GetRefGraph(parent) ==
this && GetRefGraph(child) ==
this);
1637 Assume(m_main_chunkindex_observers == 0 || GetTopLevel() != 0);
1639 if (GetRefIndex(parent) == GetRefIndex(child))
return;
1642 int level = GetTopLevel();
1643 auto par_cluster = FindCluster(GetRefIndex(parent), level);
1644 if (par_cluster ==
nullptr)
return;
1645 auto chl_cluster = FindCluster(GetRefIndex(child), level);
1646 if (chl_cluster ==
nullptr)
return;
1648 auto& clusterset = GetClusterSet(level);
1649 clusterset.m_deps_to_add.emplace_back(GetRefIndex(parent), GetRefIndex(child));
1651 clusterset.m_group_data.reset();
1652 if (clusterset.m_oversized ==
false) clusterset.m_oversized = std::nullopt;
1655bool TxGraphImpl::Exists(
const Ref& arg,
bool main_only)
noexcept
1657 if (GetRefGraph(arg) ==
nullptr)
return false;
1658 Assume(GetRefGraph(arg) ==
this);
1659 size_t level = GetSpecifiedLevel(main_only);
1661 ApplyRemovals(level);
1662 auto cluster = FindCluster(GetRefIndex(arg), level);
1663 return cluster !=
nullptr;
1666void Cluster::GetAncestorRefs(
const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>&
args, std::vector<TxGraph::Ref*>& output)
noexcept
1669 SetType ancestors_union;
1671 while (!
args.empty()) {
1672 if (
args.front().first !=
this)
break;
1673 ancestors_union |= m_depgraph.
Ancestors(
args.front().second);
1676 Assume(ancestors_union.Any());
1678 for (
auto idx : ancestors_union) {
1679 const auto& entry = graph.m_entries[m_mapping[idx]];
1680 Assume(entry.m_ref !=
nullptr);
1681 output.push_back(entry.m_ref);
1685void Cluster::GetDescendantRefs(
const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>&
args, std::vector<TxGraph::Ref*>& output)
noexcept
1688 SetType descendants_union;
1690 while (!
args.empty()) {
1691 if (
args.front().first !=
this)
break;
1695 Assume(descendants_union.Any());
1697 for (
auto idx : descendants_union) {
1698 const auto& entry = graph.m_entries[m_mapping[idx]];
1699 Assume(entry.m_ref !=
nullptr);
1700 output.push_back(entry.m_ref);
1704bool Cluster::GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos)
noexcept
1708 for (
auto& ref : range) {
1709 Assume(start_pos < m_linearization.size());
1710 const auto& entry = graph.m_entries[m_mapping[m_linearization[start_pos++]]];
1711 Assume(entry.m_ref !=
nullptr);
1715 return start_pos == m_linearization.size();
1723void Cluster::MakeStagingTransactionsMissing(TxGraphImpl& graph)
noexcept
1728 for (
auto ci : m_linearization) {
1729 GraphIndex idx = m_mapping[ci];
1730 auto& entry = graph.m_entries[idx];
1731 entry.m_locator[1].SetMissing();
1735std::vector<TxGraph::Ref*> TxGraphImpl::GetAncestors(
const Ref& arg,
bool main_only)
noexcept
1738 if (GetRefGraph(arg) ==
nullptr)
return {};
1739 Assume(GetRefGraph(arg) ==
this);
1741 size_t level = GetSpecifiedLevel(main_only);
1742 ApplyDependencies(level);
1744 Assume(GetClusterSet(level).m_deps_to_add.empty());
1746 auto cluster = FindCluster(GetRefIndex(arg), level);
1747 if (cluster ==
nullptr)
return {};
1749 std::pair<Cluster*, DepGraphIndex> match = {cluster, m_entries[GetRefIndex(arg)].m_locator[cluster->m_level].index};
1750 auto matches = std::span(&match, 1);
1751 std::vector<TxGraph::Ref*>
ret;
1752 cluster->GetAncestorRefs(*
this, matches,
ret);
1756std::vector<TxGraph::Ref*> TxGraphImpl::GetDescendants(
const Ref& arg,
bool main_only)
noexcept
1759 if (GetRefGraph(arg) ==
nullptr)
return {};
1760 Assume(GetRefGraph(arg) ==
this);
1762 size_t level = GetSpecifiedLevel(main_only);
1763 ApplyDependencies(level);
1765 Assume(GetClusterSet(level).m_deps_to_add.empty());
1767 auto cluster = FindCluster(GetRefIndex(arg), level);
1768 if (cluster ==
nullptr)
return {};
1770 std::pair<Cluster*, DepGraphIndex> match = {cluster, m_entries[GetRefIndex(arg)].m_locator[cluster->m_level].index};
1771 auto matches = std::span(&match, 1);
1772 std::vector<TxGraph::Ref*>
ret;
1773 cluster->GetDescendantRefs(*
this, matches,
ret);
1777std::vector<TxGraph::Ref*> TxGraphImpl::GetAncestorsUnion(std::span<const Ref* const>
args,
bool main_only)
noexcept
1780 size_t level = GetSpecifiedLevel(main_only);
1781 ApplyDependencies(level);
1783 Assume(GetClusterSet(level).m_deps_to_add.empty());
1786 std::vector<std::pair<Cluster*, DepGraphIndex>> matches;
1787 matches.reserve(
args.size());
1788 for (
auto arg :
args) {
1791 if (GetRefGraph(*arg) ==
nullptr)
continue;
1792 Assume(GetRefGraph(*arg) ==
this);
1794 auto cluster = FindCluster(GetRefIndex(*arg), level);
1795 if (cluster ==
nullptr)
continue;
1797 matches.emplace_back(cluster, m_entries[GetRefIndex(*arg)].m_locator[cluster->m_level].index);
1800 std::sort(matches.begin(), matches.end(), [](
auto& a,
auto& b)
noexcept { return CompareClusters(a.first, b.first) < 0; });
1802 std::span match_span(matches);
1803 std::vector<TxGraph::Ref*>
ret;
1804 while (!match_span.empty()) {
1805 match_span.front().first->GetAncestorRefs(*
this, match_span,
ret);
1810std::vector<TxGraph::Ref*> TxGraphImpl::GetDescendantsUnion(std::span<const Ref* const>
args,
bool main_only)
noexcept
1813 size_t level = GetSpecifiedLevel(main_only);
1814 ApplyDependencies(level);
1816 Assume(GetClusterSet(level).m_deps_to_add.empty());
1819 std::vector<std::pair<Cluster*, DepGraphIndex>> matches;
1820 matches.reserve(
args.size());
1821 for (
auto arg :
args) {
1824 if (GetRefGraph(*arg) ==
nullptr)
continue;
1825 Assume(GetRefGraph(*arg) ==
this);
1827 auto cluster = FindCluster(GetRefIndex(*arg), level);
1828 if (cluster ==
nullptr)
continue;
1830 matches.emplace_back(cluster, m_entries[GetRefIndex(*arg)].m_locator[cluster->m_level].index);
1833 std::sort(matches.begin(), matches.end(), [](
auto& a,
auto& b)
noexcept { return CompareClusters(a.first, b.first) < 0; });
1835 std::span match_span(matches);
1836 std::vector<TxGraph::Ref*>
ret;
1837 while (!match_span.empty()) {
1838 match_span.front().first->GetDescendantRefs(*
this, match_span,
ret);
1843std::vector<TxGraph::Ref*> TxGraphImpl::GetCluster(
const Ref& arg,
bool main_only)
noexcept
1847 if (GetRefGraph(arg) ==
nullptr)
return {};
1848 Assume(GetRefGraph(arg) ==
this);
1850 size_t level = GetSpecifiedLevel(main_only);
1851 ApplyDependencies(level);
1853 Assume(GetClusterSet(level).m_deps_to_add.empty());
1855 auto cluster = FindCluster(GetRefIndex(arg), level);
1856 if (cluster ==
nullptr)
return {};
1858 MakeAcceptable(*cluster);
1859 std::vector<TxGraph::Ref*>
ret(cluster->GetTxCount());
1860 cluster->GetClusterRefs(*
this,
ret, 0);
1866 size_t level = GetSpecifiedLevel(main_only);
1867 ApplyRemovals(level);
1868 return GetClusterSet(level).m_txcount;
1871FeePerWeight TxGraphImpl::GetIndividualFeerate(
const Ref& arg)
noexcept
1874 if (GetRefGraph(arg) ==
nullptr)
return {};
1875 Assume(GetRefGraph(arg) ==
this);
1878 Cluster* cluster{
nullptr};
1879 for (
int level = 0; level <= GetTopLevel(); ++level) {
1882 ApplyRemovals(level);
1883 if (m_entries[GetRefIndex(arg)].m_locator[level].IsPresent()) {
1884 cluster = m_entries[GetRefIndex(arg)].m_locator[level].cluster;
1888 if (cluster ==
nullptr)
return {};
1890 return cluster->GetIndividualFeerate(m_entries[GetRefIndex(arg)].m_locator[cluster->m_level].index);
1893FeePerWeight TxGraphImpl::GetMainChunkFeerate(
const Ref& arg)
noexcept
1896 if (GetRefGraph(arg) ==
nullptr)
return {};
1897 Assume(GetRefGraph(arg) ==
this);
1899 ApplyDependencies(0);
1901 Assume(m_main_clusterset.m_deps_to_add.empty());
1903 auto cluster = FindCluster(GetRefIndex(arg), 0);
1904 if (cluster ==
nullptr)
return {};
1907 MakeAcceptable(*cluster);
1908 const auto& entry = m_entries[GetRefIndex(arg)];
1909 return entry.m_main_chunk_feerate;
1912bool TxGraphImpl::IsOversized(
bool main_only)
noexcept
1914 size_t level = GetSpecifiedLevel(main_only);
1915 auto& clusterset = GetClusterSet(level);
1916 if (clusterset.m_oversized.has_value()) {
1918 return *clusterset.m_oversized;
1922 GroupClusters(level);
1923 Assume(clusterset.m_group_data.has_value());
1924 clusterset.m_oversized = clusterset.m_group_data->m_group_oversized;
1925 return *clusterset.m_oversized;
1928void TxGraphImpl::StartStaging() noexcept
1931 Assume(!m_staging_clusterset.has_value());
1938 ApplyDependencies(0);
1940 m_staging_clusterset.emplace();
1943 m_staging_clusterset->m_txcount = m_main_clusterset.m_txcount;
1944 m_staging_clusterset->m_deps_to_add = m_main_clusterset.m_deps_to_add;
1945 m_staging_clusterset->m_group_data = m_main_clusterset.m_group_data;
1946 m_staging_clusterset->m_oversized = m_main_clusterset.m_oversized;
1947 Assume(m_staging_clusterset->m_oversized.has_value());
1950void TxGraphImpl::AbortStaging() noexcept
1953 Assume(m_staging_clusterset.has_value());
1956 for (
auto idx : m_staging_clusterset->m_removed) {
1957 m_entries[idx].m_locator[1].SetMissing();
1961 for (
auto& cluster : m_staging_clusterset->m_clusters[quality]) {
1962 cluster->MakeStagingTransactionsMissing(*
this);
1966 m_staging_clusterset.reset();
1968 if (!m_main_clusterset.m_group_data.has_value()) {
1971 m_main_clusterset.m_oversized = std::nullopt;
1975void TxGraphImpl::CommitStaging() noexcept
1978 Assume(m_staging_clusterset.has_value());
1979 Assume(m_main_chunkindex_observers == 0);
1982 auto conflicts = GetConflicts();
1983 for (Cluster* conflict : conflicts) {
1984 conflict->Clear(*
this);
1985 DeleteCluster(*conflict);
1989 for (
auto idx : m_staging_clusterset->m_removed) {
1990 m_entries[idx].m_locator[1].SetMissing();
1994 auto& stage_sets = m_staging_clusterset->m_clusters[quality];
1995 while (!stage_sets.empty()) {
1996 stage_sets.back()->MoveToMain(*
this);
2000 m_main_clusterset.m_deps_to_add = std::move(m_staging_clusterset->m_deps_to_add);
2001 m_main_clusterset.m_to_remove = std::move(m_staging_clusterset->m_to_remove);
2002 m_main_clusterset.m_group_data = std::move(m_staging_clusterset->m_group_data);
2003 m_main_clusterset.m_oversized = std::move(m_staging_clusterset->m_oversized);
2004 m_main_clusterset.m_txcount = std::move(m_staging_clusterset->m_txcount);
2006 m_staging_clusterset.reset();
2010void Cluster::SetFee(TxGraphImpl& graph,
DepGraphIndex idx, int64_t
fee)
noexcept
2019 if (!NeedsSplitting()) {
2020 graph.SetClusterQuality(m_level, m_quality, m_setindex, QualityLevel::NEEDS_RELINEARIZE);
2022 graph.SetClusterQuality(m_level, m_quality, m_setindex, QualityLevel::NEEDS_SPLIT);
2027void TxGraphImpl::SetTransactionFee(
const Ref& ref, int64_t
fee)
noexcept
2030 if (GetRefGraph(ref) ==
nullptr)
return;
2031 Assume(GetRefGraph(ref) ==
this);
2032 Assume(m_main_chunkindex_observers == 0);
2034 auto& entry = m_entries[GetRefIndex(ref)];
2035 for (
int level = 0; level < MAX_LEVELS; ++level) {
2036 auto& locator = entry.m_locator[level];
2037 if (locator.IsPresent()) {
2038 locator.cluster->SetFee(*
this, locator.index,
fee);
2043std::strong_ordering TxGraphImpl::CompareMainOrder(
const Ref& a,
const Ref& b)
noexcept
2046 Assume(GetRefGraph(a) ==
this);
2047 Assume(GetRefGraph(b) ==
this);
2049 ApplyDependencies(0);
2050 Assume(m_main_clusterset.m_deps_to_add.empty());
2052 const auto& entry_a = m_entries[GetRefIndex(a)];
2053 const auto& entry_b = m_entries[GetRefIndex(b)];
2054 const auto& locator_a = entry_a.m_locator[0];
2055 const auto& locator_b = entry_b.m_locator[0];
2056 Assume(locator_a.IsPresent());
2057 Assume(locator_b.IsPresent());
2058 MakeAcceptable(*locator_a.cluster);
2059 MakeAcceptable(*locator_b.cluster);
2061 return CompareMainTransactions(GetRefIndex(a), GetRefIndex(b));
2064TxGraph::GraphIndex TxGraphImpl::CountDistinctClusters(std::span<const Ref* const> refs,
bool main_only)
noexcept
2066 size_t level = GetSpecifiedLevel(main_only);
2067 ApplyDependencies(level);
2068 auto& clusterset = GetClusterSet(level);
2069 Assume(clusterset.m_deps_to_add.empty());
2071 std::vector<Cluster*> clusters;
2072 clusters.reserve(refs.size());
2073 for (
const Ref* ref : refs) {
2075 if (GetRefGraph(*ref) ==
nullptr)
continue;
2076 Assume(GetRefGraph(*ref) ==
this);
2077 auto cluster = FindCluster(GetRefIndex(*ref), level);
2078 if (cluster !=
nullptr) clusters.push_back(cluster);
2081 std::sort(clusters.begin(), clusters.end(), [](Cluster* a, Cluster* b)
noexcept { return CompareClusters(a, b) < 0; });
2082 Cluster* last{
nullptr};
2084 for (Cluster* cluster : clusters) {
2085 ret += (cluster != last);
2091std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>> TxGraphImpl::GetMainStagingDiagrams() noexcept
2093 Assume(m_staging_clusterset.has_value());
2094 MakeAllAcceptable(0);
2095 Assume(m_main_clusterset.m_deps_to_add.empty());
2096 MakeAllAcceptable(1);
2097 Assume(m_staging_clusterset->m_deps_to_add.empty());
2100 auto main_clusters = GetConflicts();
2101 std::vector<FeeFrac> main_feerates, staging_feerates;
2102 for (Cluster* cluster : main_clusters) {
2103 cluster->AppendChunkFeerates(main_feerates);
2107 for (
const auto& cluster : m_staging_clusterset->m_clusters[quality]) {
2108 cluster->AppendChunkFeerates(staging_feerates);
2112 std::sort(main_feerates.begin(), main_feerates.end(), [](
auto& a,
auto& b) { return a > b; });
2113 std::sort(staging_feerates.begin(), staging_feerates.end(), [](
auto& a,
auto& b) { return a > b; });
2114 return std::make_pair(std::move(main_feerates), std::move(staging_feerates));
2117void Cluster::SanityCheck(
const TxGraphImpl& graph,
int level)
const
2124 assert(m_linearization.size() <= graph.m_max_cluster_count);
2126 assert(m_level == level);
2134 LinearizationIndex linindex{0};
2137 for (
auto lin_pos : m_linearization) {
2138 assert(lin_pos < m_mapping.size());
2139 const auto& entry = graph.m_entries[m_mapping[lin_pos]];
2141 m_done.Set(lin_pos);
2144 assert(entry.m_locator[level].cluster ==
this);
2145 assert(entry.m_locator[level].index == lin_pos);
2147 if (level == 0 && IsAcceptable()) {
2148 assert(entry.m_main_lin_index == linindex);
2150 if (!linchunking.GetChunk(0).transactions[lin_pos]) {
2151 linchunking.MarkDone(linchunking.GetChunk(0).transactions);
2154 assert(entry.m_main_chunk_feerate == linchunking.GetChunk(0).feerate);
2157 bool is_chunk_end = (chunk_pos == linchunking.GetChunk(0).transactions.Count());
2158 assert((entry.m_main_chunkindex_iterator != graph.m_main_chunkindex.end()) == is_chunk_end);
2160 auto& chunk_data = *entry.m_main_chunkindex_iterator;
2161 if (m_done == m_depgraph.
Positions() && chunk_pos == 1) {
2162 assert(chunk_data.m_chunk_count == LinearizationIndex(-1));
2164 assert(chunk_data.m_chunk_count == chunk_pos);
2175void TxGraphImpl::SanityCheck()
const
2178 std::set<GraphIndex> expected_unlinked;
2180 std::set<const Cluster*> expected_clusters[MAX_LEVELS];
2182 std::set<GraphIndex> expected_removed[MAX_LEVELS];
2184 std::set<uint64_t> sequences;
2186 std::set<GraphIndex> expected_chunkindex;
2188 bool compact_possible{
true};
2191 for (GraphIndex idx = 0; idx < m_entries.size(); ++idx) {
2192 const auto& entry = m_entries[idx];
2193 if (entry.m_ref ==
nullptr) {
2195 expected_unlinked.insert(idx);
2198 assert(GetRefGraph(*entry.m_ref) ==
this);
2199 assert(GetRefIndex(*entry.m_ref) == idx);
2201 if (entry.m_main_chunkindex_iterator != m_main_chunkindex.end()) {
2203 assert(entry.m_locator[0].IsPresent());
2204 expected_chunkindex.insert(idx);
2207 bool was_present{
false}, was_removed{
false};
2208 for (
int level = 0; level < MAX_LEVELS; ++level) {
2209 const auto& locator = entry.m_locator[level];
2211 assert(locator.IsMissing() + locator.IsRemoved() + locator.IsPresent() == 1);
2212 if (locator.IsPresent()) {
2216 assert(locator.cluster->GetClusterEntry(locator.index) == idx);
2218 expected_clusters[level].insert(locator.cluster);
2220 }
else if (locator.IsRemoved()) {
2224 assert(was_present && !was_removed);
2226 expected_removed[level].insert(idx);
2233 for (
int level = 0; level <= GetTopLevel(); ++level) {
2234 assert(level < MAX_LEVELS);
2235 auto& clusterset = GetClusterSet(level);
2236 std::set<const Cluster*> actual_clusters;
2240 QualityLevel quality{qual};
2241 const auto& quality_clusters = clusterset.m_clusters[qual];
2243 for (ClusterSetIndex setindex = 0; setindex < quality_clusters.size(); ++setindex) {
2244 const auto& cluster = *quality_clusters[setindex];
2246 assert(cluster.m_sequence < m_next_sequence_counter);
2247 assert(sequences.count(cluster.m_sequence) == 0);
2248 sequences.insert(cluster.m_sequence);
2251 if (cluster.GetTxCount() != 0) {
2252 actual_clusters.insert(&cluster);
2255 cluster.SanityCheck(*
this, level);
2257 assert(cluster.m_quality == quality);
2258 assert(cluster.m_setindex == setindex);
2263 for (GraphIndex idx : clusterset.m_to_remove) {
2264 assert(idx < m_entries.size());
2272 for (
auto [par_idx, chl_idx] : clusterset.m_deps_to_add) {
2273 assert(par_idx != chl_idx);
2274 assert(par_idx < m_entries.size());
2275 assert(chl_idx < m_entries.size());
2279 assert(actual_clusters == expected_clusters[level]);
2282 std::set<GraphIndex> actual_removed(clusterset.m_removed.begin(), clusterset.m_removed.end());
2283 for (
auto i : expected_unlinked) {
2288 actual_removed.erase(i);
2289 expected_removed[level].erase(i);
2292 assert(actual_removed == expected_removed[level]);
2295 if (!clusterset.m_deps_to_add.empty()) compact_possible =
false;
2296 if (!clusterset.m_to_remove.empty()) compact_possible =
false;
2297 if (!clusterset.m_removed.empty()) compact_possible =
false;
2300 if (clusterset.m_group_data.has_value()) {
2301 assert(clusterset.m_oversized == clusterset.m_group_data->m_group_oversized);
2306 if (level < GetTopLevel())
assert(clusterset.m_oversized.has_value());
2310 std::set<GraphIndex> actual_unlinked(m_unlinked.begin(), m_unlinked.end());
2311 assert(actual_unlinked == expected_unlinked);
2315 if (compact_possible) {
2316 assert(actual_unlinked.empty());
2320 std::set<GraphIndex> actual_chunkindex;
2322 for (
const auto& chunk : m_main_chunkindex) {
2323 GraphIndex idx = chunk.m_graph_index;
2324 actual_chunkindex.insert(idx);
2325 auto chunk_feerate = m_entries[idx].m_main_chunk_feerate;
2326 if (!last_chunk_feerate.
IsEmpty()) {
2327 assert(FeeRateCompare(last_chunk_feerate, chunk_feerate) >= 0);
2329 last_chunk_feerate = chunk_feerate;
2331 assert(actual_chunkindex == expected_chunkindex);
2334void TxGraphImpl::DoWork() noexcept
2336 for (
int level = 0; level <= GetTopLevel(); ++level) {
2337 if (level > 0 || m_main_chunkindex_observers == 0) {
2338 MakeAllAcceptable(level);
2343void BlockBuilderImpl::Next() noexcept
2346 if (m_cur_iter == m_graph->m_main_chunkindex.end())
return;
2350 m_cur_cluster =
nullptr;
2351 if (m_cur_iter == m_graph->m_main_chunkindex.end())
break;
2353 const auto& chunk_data = *m_cur_iter;
2354 const auto& chunk_end_entry = m_graph->m_entries[chunk_data.m_graph_index];
2355 m_cur_cluster = chunk_end_entry.m_locator[0].cluster;
2356 m_known_end_of_cluster =
false;
2358 if (!m_excluded_clusters.contains(m_cur_cluster))
break;
2362std::optional<std::pair<std::vector<TxGraph::Ref*>,
FeePerWeight>> BlockBuilderImpl::GetCurrentChunk() noexcept
2364 std::optional<std::pair<std::vector<TxGraph::Ref*>,
FeePerWeight>>
ret;
2366 if (m_cur_iter != m_graph->m_main_chunkindex.end()) {
2368 const auto& chunk_data = *m_cur_iter;
2369 const auto& chunk_end_entry = m_graph->m_entries[chunk_data.m_graph_index];
2370 if (chunk_data.m_chunk_count == LinearizationIndex(-1)) {
2373 ret->first.resize(1);
2374 Assume(chunk_end_entry.m_ref !=
nullptr);
2375 ret->first[0] = chunk_end_entry.m_ref;
2376 m_known_end_of_cluster =
true;
2379 ret->first.resize(chunk_data.m_chunk_count);
2380 auto start_pos = chunk_end_entry.m_main_lin_index + 1 - chunk_data.m_chunk_count;
2381 m_known_end_of_cluster = m_cur_cluster->GetClusterRefs(*m_graph,
ret->first, start_pos);
2384 Assume(!m_known_end_of_cluster || chunk_data.m_chunk_count > 1);
2386 ret->second = chunk_end_entry.m_main_chunk_feerate;
2391BlockBuilderImpl::BlockBuilderImpl(TxGraphImpl& graph) noexcept : m_graph(&graph)
2394 m_graph->MakeAllAcceptable(0);
2396 Assume(m_graph->m_main_clusterset.m_deps_to_add.empty());
2399 ++m_graph->m_main_chunkindex_observers;
2401 m_cur_iter = m_graph->m_main_chunkindex.begin();
2402 m_cur_cluster =
nullptr;
2403 if (m_cur_iter != m_graph->m_main_chunkindex.end()) {
2405 const auto& chunk_data = *m_cur_iter;
2406 const auto& chunk_end_entry = m_graph->m_entries[chunk_data.m_graph_index];
2407 m_cur_cluster = chunk_end_entry.m_locator[0].cluster;
2411BlockBuilderImpl::~BlockBuilderImpl()
2413 Assume(m_graph->m_main_chunkindex_observers > 0);
2415 --m_graph->m_main_chunkindex_observers;
2418void BlockBuilderImpl::Include() noexcept
2425void BlockBuilderImpl::Skip() noexcept
2431 if (m_cur_cluster !=
nullptr && !m_known_end_of_cluster) {
2432 m_excluded_clusters.insert(m_cur_cluster);
2437std::unique_ptr<TxGraph::BlockBuilder> TxGraphImpl::GetBlockBuilder() noexcept
2439 return std::make_unique<BlockBuilderImpl>(*
this);
2442std::pair<std::vector<TxGraph::Ref*>,
FeePerWeight> TxGraphImpl::GetWorstMainChunk() noexcept
2446 MakeAllAcceptable(0);
2447 Assume(m_main_clusterset.m_deps_to_add.empty());
2449 if (!m_main_chunkindex.empty()) {
2450 const auto& chunk_data = *m_main_chunkindex.rbegin();
2451 const auto& chunk_end_entry = m_entries[chunk_data.m_graph_index];
2452 Cluster* cluster = chunk_end_entry.m_locator[0].cluster;
2453 if (chunk_data.m_chunk_count == LinearizationIndex(-1) || chunk_data.m_chunk_count == 1) {
2455 ret.first.resize(1);
2456 Assume(chunk_end_entry.m_ref !=
nullptr);
2457 ret.first[0] = chunk_end_entry.m_ref;
2459 ret.first.resize(chunk_data.m_chunk_count);
2460 auto start_pos = chunk_end_entry.m_main_lin_index + 1 - chunk_data.m_chunk_count;
2461 cluster->GetClusterRefs(*
this,
ret.first, start_pos);
2462 std::reverse(
ret.first.begin(),
ret.first.end());
2464 ret.second = chunk_end_entry.m_main_chunk_feerate;
2475 m_graph->UnlinkRef(m_index);
2483 if (m_graph) m_graph->UnlinkRef(m_index);
2487 m_graph = other.m_graph;
2488 m_index = other.m_index;
2489 other.m_graph =
nullptr;
2497 if (other.m_graph) other.m_graph->UpdateRef(other.m_index, *
this);
2499 std::swap(m_graph, other.m_graph);
2500 std::swap(m_index, other.m_index);
2503std::unique_ptr<TxGraph>
MakeTxGraph(
unsigned max_cluster_count)
noexcept
2505 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.
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.
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::vector< FeeFrac > ChunkLinearization(const DepGraph< SetType > &depgraph, std::span< const DepGraphIndex > linearization) noexcept
Compute the feerates of the chunks of linearization.
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.
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) noexcept
Construct a new TxGraph with the specified limit on 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.