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());
210 std::sort(
ret.begin(),
ret.end());
211 ret.erase(std::unique(
ret.begin(),
ret.end()),
ret.end());
213 arg = std::move(
ret);
241 std::vector<SimTxGraph> sims;
243 sims.emplace_back(max_count);
248 size_t tx_count[2] = {sims[0].GetTransactionCount(), 0};
250 size_t choices = tx_count[0] + sims[0].removed.size() + 1;
251 if (sims.size() == 2) {
252 tx_count[1] = sims[1].GetTransactionCount();
253 choices += tx_count[1] + sims[1].removed.size();
258 for (
size_t level = 0; level < sims.size(); ++level) {
259 auto& sim = sims[level];
260 if (choice < tx_count[level]) {
262 for (
auto i : sim.graph.Positions()) {
263 if (choice == 0)
return sim.GetRef(i);
268 choice -= tx_count[level];
270 if (choice < sim.removed.size()) {
272 return sim.removed[choice].get();
274 choice -= sim.removed.size();
295 auto& top_sim = sims.back();
296 auto& sel_sim = use_main ? sims[0] : top_sim;
297 auto& main_sim = sims[0];
302 if (top_sim.GetTransactionCount() < SimTxGraph::MAX_TRANSACTIONS &&
command-- == 0) {
318 auto ref = real->AddTransaction(feerate);
320 auto ref_loc = top_sim.AddTransaction(feerate);
322 *ref_loc = std::move(ref);
324 }
else if (top_sim.GetTransactionCount() + top_sim.removed.size() > 1 &&
command-- == 0) {
326 auto par = pick_fn();
327 auto chl = pick_fn();
328 auto pos_par = top_sim.Find(par);
329 auto pos_chl = top_sim.Find(chl);
333 if (top_sim.graph.Ancestors(pos_par)[pos_chl])
break;
335 top_sim.AddDependency(par, chl);
336 real->AddDependency(*par, *chl);
338 }
else if (top_sim.removed.size() < 100 &&
command-- == 0) {
342 std::vector<TxGraph::Ref*> to_remove;
343 to_remove.push_back(pick_fn());
344 top_sim.IncludeAncDesc(to_remove, alt);
347 std::shuffle(to_remove.begin(), to_remove.end(), rng);
349 real->RemoveTransaction(*ptr);
350 top_sim.RemoveTransaction(ptr);
353 }
else if (sel_sim.removed.size() > 0 &&
command-- == 0) {
363 if (removed_pos != sel_sim.removed.size() - 1) {
364 std::swap(sel_sim.removed[removed_pos], sel_sim.removed.back());
366 sel_sim.removed.pop_back();
370 std::vector<TxGraph::Ref*> to_destroy;
371 to_destroy.push_back(pick_fn());
377 auto old_size = to_destroy.size();
378 for (
auto& sim : sims) sim.IncludeAncDesc(to_destroy, alt);
379 if (to_destroy.size() == old_size)
break;
383 std::shuffle(to_destroy.begin(), to_destroy.end(), rng);
385 for (
size_t level = 0; level < sims.size(); ++level) {
386 sims[level].DestroyTransaction(ptr, level == sims.size() - 1);
398 auto ref = pick_fn();
399 real->SetTransactionFee(*ref,
fee);
400 for (
auto& sim : sims) {
401 sim.SetTransactionFee(ref,
fee);
406 assert(real->GetTransactionCount(use_main) == sel_sim.GetTransactionCount());
410 auto ref = pick_fn();
411 bool exists = real->Exists(*ref, use_main);
417 assert(sel_sim.IsOversized() == real->IsOversized(use_main));
421 auto ref = pick_fn();
422 auto feerate = real->GetIndividualFeerate(*ref);
424 for (
auto& sim : sims) {
425 auto simpos = sim.Find(ref);
428 assert(feerate == sim.graph.FeeRate(simpos));
433 }
else if (!main_sim.IsOversized() &&
command-- == 0) {
435 auto ref = pick_fn();
436 auto feerate = real->GetMainChunkFeerate(*ref);
437 auto simpos = main_sim.Find(ref);
443 assert(feerate.
size >= main_sim.graph.FeeRate(simpos).size);
446 }
else if (!sel_sim.IsOversized() &&
command-- == 0) {
448 auto ref = pick_fn();
449 auto result = alt ? real->GetDescendants(*ref, use_main)
450 : real->GetAncestors(*ref, use_main);
451 assert(result.size() <= max_count);
452 auto result_set = sel_sim.MakeSet(result);
453 assert(result.size() == result_set.Count());
454 auto expect_set = sel_sim.GetAncDesc(ref, alt);
455 assert(result_set == expect_set);
457 }
else if (!sel_sim.IsOversized() &&
command-- == 0) {
459 std::vector<TxGraph::Ref*> refs;
463 for (
size_t i = 0; i <
count; ++i) {
467 std::shuffle(refs.begin(), refs.end(), rng);
469 auto result = alt ? real->GetDescendantsUnion(refs, use_main)
470 : real->GetAncestorsUnion(refs, use_main);
471 auto result_set = sel_sim.MakeSet(result);
472 assert(result.size() == result_set.Count());
474 SimTxGraph::SetType expect_set;
475 for (
TxGraph::Ref* ref : refs) expect_set |= sel_sim.GetAncDesc(ref, alt);
477 assert(result_set == expect_set);
479 }
else if (!sel_sim.IsOversized() &&
command-- == 0) {
481 auto ref = pick_fn();
482 auto result = real->GetCluster(*ref, use_main);
484 assert(result.size() <= max_count);
486 auto left = sel_sim.graph.Positions();
487 for (
auto refptr : result) {
488 auto simpos = sel_sim.Find(refptr);
492 assert(!sel_sim.graph.Ancestors(simpos).Overlaps(left));
495 auto result_set = sel_sim.MakeSet(result);
496 assert(sel_sim.graph.IsConnected(result_set));
498 auto simpos = sel_sim.Find(ref);
500 assert(result_set[simpos]);
502 assert(result_set.None());
505 for (
auto i : result_set) {
506 assert(sel_sim.graph.Ancestors(i).IsSubsetOf(result_set));
507 assert(sel_sim.graph.Descendants(i).IsSubsetOf(result_set));
512 assert((sims.size() == 2) == real->HaveStaging());
514 }
else if (sims.size() < 2 &&
command-- == 0) {
516 sims.emplace_back(sims.back());
517 real->StartStaging();
519 }
else if (sims.size() > 1 &&
command-- == 0) {
521 real->CommitStaging();
522 sims.erase(sims.begin());
524 }
else if (sims.size() > 1 &&
command-- == 0) {
526 real->AbortStaging();
531 sims.back().oversized = std::nullopt;
533 }
else if (!main_sim.IsOversized() &&
command-- == 0) {
535 auto ref_a = pick_fn();
536 auto ref_b = pick_fn();
537 auto sim_a = main_sim.Find(ref_a);
538 auto sim_b = main_sim.Find(ref_b);
541 auto cmp = real->CompareMainOrder(*ref_a, *ref_b);
543 if (sim_a != sim_b)
assert(cmp != 0);
545 if (main_sim.graph.Ancestors(sim_a)[sim_b])
assert(cmp >= 0);
546 if (main_sim.graph.Descendants(sim_a)[sim_b])
assert(cmp <= 0);
551 }
else if (!sel_sim.IsOversized() &&
command-- == 0) {
553 std::vector<TxGraph::Ref*> refs;
557 for (
size_t i = 0; i <
count; ++i) {
561 std::shuffle(refs.begin(), refs.end(), rng);
563 auto result = real->CountDistinctClusters(refs, use_main);
567 SimTxGraph::SetType sim_reps;
568 for (
auto ref : refs) {
570 auto simpos = sel_sim.Find(ref);
573 auto component = sel_sim.graph.GetConnectedComponent(sel_sim.graph.Positions(), simpos);
576 sim_reps.Set(component.First());
580 assert(result == sim_reps.Count());
594 if (!sims[0].IsOversized()) {
598 std::vector<SimTxGraph::Pos> vec1;
599 for (
auto i : sims[0].graph.
Positions()) vec1.push_back(i);
600 std::shuffle(vec1.begin(), vec1.end(), rng);
602 std::shuffle(vec2.begin(), vec2.end(), rng);
603 if (vec1 == vec2) std::next_permutation(vec2.begin(), vec2.end());
606 auto cmp = [&](SimTxGraph::Pos a, SimTxGraph::Pos b)
noexcept {
607 return real->CompareMainOrder(*sims[0].GetRef(a), *sims[0].GetRef(b)) < 0;
609 std::sort(vec1.begin(), vec1.end(), cmp);
610 std::sort(vec2.begin(), vec2.end(), cmp);
617 auto todo = sims[0].graph.Positions();
618 for (
auto i : vec1) {
626 for (
size_t pos = 0; pos < vec1.size(); ++pos) {
627 auto pos_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[pos]));
629 size_t before = rng.
randrange<
size_t>(pos);
630 auto before_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[before]));
631 assert(FeeRateCompare(before_feerate, pos_feerate) >= 0);
633 if (pos + 1 < vec1.size()) {
634 size_t after = pos + 1 + rng.
randrange<
size_t>(vec1.size() - 1 - pos);
635 auto after_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[after]));
636 assert(FeeRateCompare(after_feerate, pos_feerate) <= 0);
641 assert(real->HaveStaging() == (sims.size() > 1));
645 for (
int main_only = 0; main_only < 2; ++main_only) {
646 auto& sim = main_only ? sims[0] : sims.back();
648 assert(real->IsOversized(main_only) == sim.IsOversized());
649 assert(real->GetTransactionCount(main_only) == sim.GetTransactionCount());
651 if (!sim.IsOversized()) {
652 auto todo = sim.graph.Positions();
656 auto component = sim.graph.FindConnectedComponent(todo);
659 for (
auto i : component) {
661 assert(sim.graph.FeeRate(i) == real->GetIndividualFeerate(*sim.GetRef(i)));
663 auto expect_anc = sim.graph.Ancestors(i);
664 auto anc = sim.MakeSet(real->GetAncestors(*sim.GetRef(i), main_only));
665 assert(anc.Count() <= max_count);
666 assert(anc == expect_anc);
668 auto expect_desc = sim.graph.Descendants(i);
669 auto desc = sim.MakeSet(real->GetDescendants(*sim.GetRef(i), main_only));
670 assert(desc.Count() <= max_count);
671 assert(desc == expect_desc);
673 auto cluster = real->GetCluster(*sim.GetRef(i), main_only);
674 assert(cluster.size() <= max_count);
675 assert(sim.MakeSet(cluster) == component);
678 std::vector<DepGraphIndex> simlin;
679 SimTxGraph::SetType done;
681 auto simpos = sim.Find(ptr);
682 assert(sim.graph.Descendants(simpos).IsSubsetOf(component - done));
684 assert(sim.graph.Ancestors(simpos).IsSubsetOf(done));
685 simlin.push_back(simpos);
689 if (sims.size() == 1 || main_only) {
692 for (
unsigned chunknum = 0; chunknum < simlinchunk.
NumChunksLeft(); ++chunknum) {
693 auto chunk = simlinchunk.
GetChunk(chunknum);
696 assert(sim.graph.IsConnected(chunk.transactions));
698 while (chunk.transactions.Any()) {
699 assert(chunk.transactions[simlin[idx]]);
700 chunk.transactions.Reset(simlin[idx]);
701 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.
static bool exists(const path &p)
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