6#include <cluster_linearize.h>
38 static constexpr auto MISSING = Pos(-1);
46 std::array<std::shared_ptr<TxGraph::Ref>, MAX_TRANSACTIONS> simmap;
48 std::map<const TxGraph::Ref*, Pos> simrevmap;
50 std::vector<std::shared_ptr<TxGraph::Ref>> removed;
52 std::optional<bool> oversized;
57 explicit SimTxGraph(
DepGraphIndex max_cluster) : max_cluster_count(max_cluster) {}
60 SimTxGraph(
const SimTxGraph&)
noexcept =
default;
61 SimTxGraph& operator=(
const SimTxGraph&)
noexcept =
default;
62 SimTxGraph(SimTxGraph&&) noexcept = default;
63 SimTxGraph& operator=(SimTxGraph&&) noexcept = default;
69 if (!oversized.has_value()) {
76 if (component.Count() > max_cluster_count) oversized =
true;
89 auto it = simrevmap.find(ref);
90 if (it != simrevmap.end())
return it->second;
99 return simmap[pos].get();
108 simmap[simpos] = std::make_shared<TxGraph::Ref>();
109 auto ptr = simmap[simpos].get();
110 simrevmap[ptr] = simpos;
117 auto par_pos =
Find(parent);
118 if (par_pos ==
MISSING)
return;
119 auto chl_pos =
Find(child);
120 if (chl_pos ==
MISSING)
return;
123 if (oversized.has_value() && !*oversized) oversized = std::nullopt;
129 auto pos =
Find(ref);
137 auto pos =
Find(ref);
140 simrevmap.erase(simmap[pos].get());
143 removed.push_back(std::move(simmap[pos]));
146 if (oversized.has_value() && *oversized) oversized = std::nullopt;
153 void DestroyTransaction(
TxGraph::Ref* ref,
bool reset_oversize)
155 auto pos =
Find(ref);
160 auto remove = std::partition(removed.begin(), removed.end(), [&](
auto& arg) { return arg.get() != ref; });
161 removed.erase(remove, removed.end());
164 simrevmap.erase(simmap[pos].get());
167 if (reset_oversize && oversized.has_value() && *oversized) {
168 oversized = std::nullopt;
175 SetType MakeSet(std::span<TxGraph::Ref* const> arg)
179 auto pos =
Find(ptr);
189 auto pos =
Find(arg);
196 void IncludeAncDesc(std::vector<TxGraph::Ref*>& arg,
bool desc)
198 std::vector<TxGraph::Ref*>
ret;
199 for (
auto ptr : arg) {
200 auto simpos =
Find(ptr);
203 ret.push_back(simmap[i].get());
212 for (
auto ptr :
ret) {
213 if (std::find(arg.begin(), arg.end(), ptr) == arg.end()) {
244 std::vector<SimTxGraph> sims;
246 sims.emplace_back(max_count);
251 size_t tx_count[2] = {sims[0].GetTransactionCount(), 0};
253 size_t choices = tx_count[0] + sims[0].removed.size() + 1;
254 if (sims.size() == 2) {
255 tx_count[1] = sims[1].GetTransactionCount();
256 choices += tx_count[1] + sims[1].removed.size();
261 for (
size_t level = 0; level < sims.size(); ++level) {
262 auto& sim = sims[level];
263 if (choice < tx_count[level]) {
265 for (
auto i : sim.graph.Positions()) {
266 if (choice == 0)
return sim.GetRef(i);
271 choice -= tx_count[level];
273 if (choice < sim.removed.size()) {
275 return sim.removed[choice].get();
277 choice -= sim.removed.size();
298 auto& top_sim = sims.back();
299 auto& sel_sim = use_main ? sims[0] : top_sim;
300 auto& main_sim = sims[0];
305 if (top_sim.GetTransactionCount() < SimTxGraph::MAX_TRANSACTIONS &&
command-- == 0) {
321 auto ref = real->AddTransaction(feerate);
323 auto ref_loc = top_sim.AddTransaction(feerate);
325 *ref_loc = std::move(ref);
327 }
else if (top_sim.GetTransactionCount() + top_sim.removed.size() > 1 &&
command-- == 0) {
329 auto par = pick_fn();
330 auto chl = pick_fn();
331 auto pos_par = top_sim.Find(par);
332 auto pos_chl = top_sim.Find(chl);
336 if (top_sim.graph.Ancestors(pos_par)[pos_chl])
break;
338 top_sim.AddDependency(par, chl);
339 real->AddDependency(*par, *chl);
341 }
else if (top_sim.removed.size() < 100 &&
command-- == 0) {
345 std::vector<TxGraph::Ref*> to_remove;
346 to_remove.push_back(pick_fn());
347 top_sim.IncludeAncDesc(to_remove, alt);
350 std::shuffle(to_remove.begin(), to_remove.end(), rng);
352 real->RemoveTransaction(*ptr);
353 top_sim.RemoveTransaction(ptr);
356 }
else if (sel_sim.removed.size() > 0 &&
command-- == 0) {
366 if (removed_pos != sel_sim.removed.size() - 1) {
367 std::swap(sel_sim.removed[removed_pos], sel_sim.removed.back());
369 sel_sim.removed.pop_back();
373 std::vector<TxGraph::Ref*> to_destroy;
374 to_destroy.push_back(pick_fn());
380 auto old_size = to_destroy.size();
381 for (
auto& sim : sims) sim.IncludeAncDesc(to_destroy, alt);
382 if (to_destroy.size() == old_size)
break;
386 std::shuffle(to_destroy.begin(), to_destroy.end(), rng);
388 for (
size_t level = 0; level < sims.size(); ++level) {
389 sims[level].DestroyTransaction(ptr, level == sims.size() - 1);
401 auto ref = pick_fn();
402 real->SetTransactionFee(*ref,
fee);
403 for (
auto& sim : sims) {
404 sim.SetTransactionFee(ref,
fee);
409 assert(real->GetTransactionCount(use_main) == sel_sim.GetTransactionCount());
413 auto ref = pick_fn();
414 bool exists = real->Exists(*ref, use_main);
416 assert(exists == should_exist);
420 assert(sel_sim.IsOversized() == real->IsOversized(use_main));
424 auto ref = pick_fn();
425 auto feerate = real->GetIndividualFeerate(*ref);
427 for (
auto& sim : sims) {
428 auto simpos = sim.Find(ref);
431 assert(feerate == sim.graph.FeeRate(simpos));
436 }
else if (!main_sim.IsOversized() &&
command-- == 0) {
438 auto ref = pick_fn();
439 auto feerate = real->GetMainChunkFeerate(*ref);
440 auto simpos = main_sim.Find(ref);
446 assert(feerate.
size >= main_sim.graph.FeeRate(simpos).size);
449 }
else if (!sel_sim.IsOversized() &&
command-- == 0) {
451 auto ref = pick_fn();
452 auto result = alt ? real->GetDescendants(*ref, use_main)
453 : real->GetAncestors(*ref, use_main);
454 assert(result.size() <= max_count);
455 auto result_set = sel_sim.MakeSet(result);
456 assert(result.size() == result_set.Count());
457 auto expect_set = sel_sim.GetAncDesc(ref, alt);
458 assert(result_set == expect_set);
460 }
else if (!sel_sim.IsOversized() &&
command-- == 0) {
462 std::vector<TxGraph::Ref*> refs;
466 for (
size_t i = 0; i <
count; ++i) {
470 std::shuffle(refs.begin(), refs.end(), rng);
472 auto result = alt ? real->GetDescendantsUnion(refs, use_main)
473 : real->GetAncestorsUnion(refs, use_main);
474 auto result_set = sel_sim.MakeSet(result);
475 assert(result.size() == result_set.Count());
477 SimTxGraph::SetType expect_set;
478 for (
TxGraph::Ref* ref : refs) expect_set |= sel_sim.GetAncDesc(ref, alt);
480 assert(result_set == expect_set);
482 }
else if (!sel_sim.IsOversized() &&
command-- == 0) {
484 auto ref = pick_fn();
485 auto result = real->GetCluster(*ref, use_main);
487 assert(result.size() <= max_count);
489 auto left = sel_sim.graph.Positions();
490 for (
auto refptr : result) {
491 auto simpos = sel_sim.Find(refptr);
495 assert(!sel_sim.graph.Ancestors(simpos).Overlaps(left));
498 auto result_set = sel_sim.MakeSet(result);
499 assert(sel_sim.graph.IsConnected(result_set));
501 auto simpos = sel_sim.Find(ref);
503 assert(result_set[simpos]);
505 assert(result_set.None());
508 for (
auto i : result_set) {
509 assert(sel_sim.graph.Ancestors(i).IsSubsetOf(result_set));
510 assert(sel_sim.graph.Descendants(i).IsSubsetOf(result_set));
515 assert((sims.size() == 2) == real->HaveStaging());
517 }
else if (sims.size() < 2 &&
command-- == 0) {
519 sims.emplace_back(sims.back());
520 real->StartStaging();
522 }
else if (sims.size() > 1 &&
command-- == 0) {
524 real->CommitStaging();
525 sims.erase(sims.begin());
527 }
else if (sims.size() > 1 &&
command-- == 0) {
529 real->AbortStaging();
534 sims.back().oversized = std::nullopt;
536 }
else if (!main_sim.IsOversized() &&
command-- == 0) {
538 auto ref_a = pick_fn();
539 auto ref_b = pick_fn();
540 auto sim_a = main_sim.Find(ref_a);
541 auto sim_b = main_sim.Find(ref_b);
544 auto cmp = real->CompareMainOrder(*ref_a, *ref_b);
546 if (sim_a != sim_b)
assert(cmp != 0);
548 if (main_sim.graph.Ancestors(sim_a)[sim_b])
assert(cmp >= 0);
549 if (main_sim.graph.Descendants(sim_a)[sim_b])
assert(cmp <= 0);
554 }
else if (!sel_sim.IsOversized() &&
command-- == 0) {
556 std::vector<TxGraph::Ref*> refs;
560 for (
size_t i = 0; i <
count; ++i) {
564 std::shuffle(refs.begin(), refs.end(), rng);
566 auto result = real->CountDistinctClusters(refs, use_main);
570 SimTxGraph::SetType sim_reps;
571 for (
auto ref : refs) {
573 auto simpos = sel_sim.Find(ref);
576 auto component = sel_sim.graph.GetConnectedComponent(sel_sim.graph.Positions(), simpos);
579 sim_reps.Set(component.First());
583 assert(result == sim_reps.Count());
597 if (!sims[0].IsOversized()) {
601 std::vector<SimTxGraph::Pos> vec1;
602 for (
auto i : sims[0].graph.
Positions()) vec1.push_back(i);
603 std::shuffle(vec1.begin(), vec1.end(), rng);
605 std::shuffle(vec2.begin(), vec2.end(), rng);
606 if (vec1 == vec2) std::next_permutation(vec2.begin(), vec2.end());
609 auto cmp = [&](SimTxGraph::Pos a, SimTxGraph::Pos b)
noexcept {
610 return real->CompareMainOrder(*sims[0].GetRef(a), *sims[0].GetRef(b)) < 0;
612 std::sort(vec1.begin(), vec1.end(), cmp);
613 std::sort(vec2.begin(), vec2.end(), cmp);
620 auto todo = sims[0].graph.Positions();
621 for (
auto i : vec1) {
629 for (
size_t pos = 0; pos < vec1.size(); ++pos) {
630 auto pos_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[pos]));
632 size_t before = rng.
randrange<
size_t>(pos);
633 auto before_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[before]));
634 assert(FeeRateCompare(before_feerate, pos_feerate) >= 0);
636 if (pos + 1 < vec1.size()) {
637 size_t after = pos + 1 + rng.
randrange<
size_t>(vec1.size() - 1 - pos);
638 auto after_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[after]));
639 assert(FeeRateCompare(after_feerate, pos_feerate) <= 0);
644 assert(real->HaveStaging() == (sims.size() > 1));
648 for (
int main_only = 0; main_only < 2; ++main_only) {
649 auto& sim = main_only ? sims[0] : sims.back();
651 assert(real->IsOversized(main_only) == sim.IsOversized());
652 assert(real->GetTransactionCount(main_only) == sim.GetTransactionCount());
654 if (!sim.IsOversized()) {
655 auto todo = sim.graph.Positions();
659 auto component = sim.graph.FindConnectedComponent(todo);
662 for (
auto i : component) {
664 assert(sim.graph.FeeRate(i) == real->GetIndividualFeerate(*sim.GetRef(i)));
666 auto expect_anc = sim.graph.Ancestors(i);
667 auto anc = sim.MakeSet(real->GetAncestors(*sim.GetRef(i), main_only));
668 assert(anc.Count() <= max_count);
669 assert(anc == expect_anc);
671 auto expect_desc = sim.graph.Descendants(i);
672 auto desc = sim.MakeSet(real->GetDescendants(*sim.GetRef(i), main_only));
673 assert(desc.Count() <= max_count);
674 assert(desc == expect_desc);
676 auto cluster = real->GetCluster(*sim.GetRef(i), main_only);
677 assert(cluster.size() <= max_count);
678 assert(sim.MakeSet(cluster) == component);
681 std::vector<DepGraphIndex> simlin;
682 SimTxGraph::SetType done;
684 auto simpos = sim.Find(ptr);
685 assert(sim.graph.Descendants(simpos).IsSubsetOf(component - done));
687 assert(sim.graph.Ancestors(simpos).IsSubsetOf(done));
688 simlin.push_back(simpos);
692 if (sims.size() == 1 || main_only) {
695 for (
unsigned chunknum = 0; chunknum < simlinchunk.
NumChunksLeft(); ++chunknum) {
696 auto chunk = simlinchunk.
GetChunk(chunknum);
699 assert(sim.graph.IsConnected(chunk.transactions));
701 while (chunk.transactions.Any()) {
702 assert(chunk.transactions[simlin[idx]]);
703 chunk.transactions.Reset(simlin[idx]);
704 assert(chunk.feerate == real->GetMainChunkFeerate(*cluster[idx]));
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
T ConsumeIntegralInRange(T min, T max)
I randrange(I range) noexcept
Generate a random integer in the range [0..range), with range > 0.
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.
const FeeFrac & FeeRate(DepGraphIndex i) const noexcept
Get the feerate of a given transaction i.
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.
Data structure encapsulating the chunking of a linearization, permitting removal of subsets.
DepGraphIndex NumChunksLeft() const noexcept
Determine how many chunks remain in the linearization.
const SetInfo< SetType > & GetChunk(DepGraphIndex n) const noexcept
Access a chunk.
constexpr MaybeCoin MISSING
#define LIMITED_WHILE(condition, limit)
Can be used to limit a theoretically unbounded loop.
Value Find(const std::map< Key, Value > &map, const Key &key)
uint32_t DepGraphIndex
Data type to represent transaction indices in DepGraphs and the clusters they represent.
bool IsEmpty() const noexcept
Check if this is empty (size and fee are 0).
Tagged wrapper around FeeFrac to avoid unit confusion.
void SeedRandomStateForTest(SeedRand seedtype)
Seed the global RNG state for testing and log the seed value.
@ ZEROS
Seed with a compile time constant of zeros.
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