Branch data Line data Source code
1 : : // Copyright (c) The Bitcoin Core developers
2 : : // Distributed under the MIT software license, see the accompanying
3 : : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 : :
5 : : #ifndef BITCOIN_CLUSTER_LINEARIZE_H
6 : : #define BITCOIN_CLUSTER_LINEARIZE_H
7 : :
8 : : #include <algorithm>
9 : : #include <cstdint>
10 : : #include <numeric>
11 : : #include <optional>
12 : : #include <utility>
13 : : #include <vector>
14 : :
15 : : #include <memusage.h>
16 : : #include <random.h>
17 : : #include <span.h>
18 : : #include <util/feefrac.h>
19 : : #include <util/vecdeque.h>
20 : :
21 : : namespace cluster_linearize {
22 : :
23 : : /** Data type to represent transaction indices in DepGraphs and the clusters they represent. */
24 : : using DepGraphIndex = uint32_t;
25 : :
26 : : /** Data structure that holds a transaction graph's preprocessed data (fee, size, ancestors,
27 : : * descendants). */
28 : : template<typename SetType>
29 [ # # # # : 14 : class DepGraph
# # ]
30 : : {
31 : : /** Information about a single transaction. */
32 : : struct Entry
33 : : {
34 : : /** Fee and size of transaction itself. */
35 : 20 : FeeFrac feerate;
36 : : /** All ancestors of the transaction (including itself). */
37 : 20 : SetType ancestors;
38 : : /** All descendants of the transaction (including itself). */
39 : 20 : SetType descendants;
40 : :
41 : : /** Equality operator (primarily for for testing purposes). */
42 [ + - + - : 40 : friend bool operator==(const Entry&, const Entry&) noexcept = default;
- + ]
43 : :
44 : : /** Construct an empty entry. */
45 : 29 : Entry() noexcept = default;
46 : : /** Construct an entry with a given feerate, ancestor set, descendant set. */
47 : 49 : Entry(const FeeFrac& f, const SetType& a, const SetType& d) noexcept : feerate(f), ancestors(a), descendants(d) {}
48 : : };
49 : :
50 : : /** Data for each transaction. */
51 : : std::vector<Entry> entries;
52 : :
53 : : /** Which positions are used. */
54 : : SetType m_used;
55 : :
56 : : public:
57 : : /** Equality operator (primarily for testing purposes). */
58 : 7 : friend bool operator==(const DepGraph& a, const DepGraph& b) noexcept
59 : : {
60 [ + - ]: 7 : if (a.m_used != b.m_used) return false;
61 : : // Only compare the used positions within the entries vector.
62 [ + + + + : 54 : for (auto idx : a.m_used) {
+ + ]
63 [ + - ]: 20 : if (a.entries[idx] != b.entries[idx]) return false;
64 : : }
65 : : return true;
66 : : }
67 : :
68 : : // Default constructors.
69 [ # # ]: 0 : DepGraph() noexcept = default;
70 : : DepGraph(const DepGraph&) noexcept = default;
71 : : DepGraph(DepGraph&&) noexcept = default;
72 : 0 : DepGraph& operator=(const DepGraph&) noexcept = default;
73 : 7 : DepGraph& operator=(DepGraph&&) noexcept = default;
74 : :
75 : : /** Construct a DepGraph object given another DepGraph and a mapping from old to new.
76 : : *
77 : : * @param depgraph The original DepGraph that is being remapped.
78 : : *
79 : : * @param mapping A span such that mapping[i] gives the position in the new DepGraph
80 : : * for position i in the old depgraph. Its size must be equal to
81 : : * depgraph.PositionRange(). The value of mapping[i] is ignored if
82 : : * position i is a hole in depgraph (i.e., if !depgraph.Positions()[i]).
83 : : *
84 : : * @param pos_range The PositionRange() for the new DepGraph. It must equal the largest
85 : : * value in mapping for any used position in depgraph plus 1, or 0 if
86 : : * depgraph.TxCount() == 0.
87 : : *
88 : : * Complexity: O(N^2) where N=depgraph.TxCount().
89 : : */
90 [ - + ]: 7 : DepGraph(const DepGraph<SetType>& depgraph, std::span<const DepGraphIndex> mapping, DepGraphIndex pos_range) noexcept : entries(pos_range)
91 : : {
92 : 14 : Assume(mapping.size() == depgraph.PositionRange());
93 : 7 : Assume((pos_range == 0) == (depgraph.TxCount() == 0));
94 [ + + ]: 34 : for (DepGraphIndex i : depgraph.Positions()) {
95 [ + + ]: 20 : auto new_idx = mapping[i];
96 [ + + ]: 20 : Assume(new_idx < pos_range);
97 : : // Add transaction.
98 [ + + ]: 20 : entries[new_idx].ancestors = SetType::Singleton(new_idx);
99 : 20 : entries[new_idx].descendants = SetType::Singleton(new_idx);
100 [ + + ]: 20 : m_used.Set(new_idx);
101 : : // Fill in fee and size.
102 [ + + ]: 20 : entries[new_idx].feerate = depgraph.entries[i].feerate;
103 : : }
104 [ + + + + ]: 48 : for (DepGraphIndex i : depgraph.Positions()) {
105 : : // Fill in dependencies by mapping direct parents.
106 : 20 : SetType parents;
107 [ + + + + : 65 : for (auto j : depgraph.GetReducedParents(i)) parents.Set(mapping[j]);
+ + ]
108 : 20 : AddDependencies(parents, mapping[i]);
109 : : }
110 : : // Verify that the provided pos_range was correct (no unused positions at the end).
111 : 7 : Assume(m_used.None() ? (pos_range == 0) : (pos_range == m_used.Last() + 1));
112 : 7 : }
113 : :
114 : : /** Get the set of transactions positions in use. Complexity: O(1). */
115 [ + + + + ]: 14 : const SetType& Positions() const noexcept { return m_used; }
[ # # ]
116 : : /** Get the range of positions in this DepGraph. All entries in Positions() are in [0, PositionRange() - 1]. */
117 [ - + + + ]: 7 : DepGraphIndex PositionRange() const noexcept { return entries.size(); }
[ # # # #
# # # # #
# # # #
# ]
118 : : /** Get the number of transactions in the graph. Complexity: O(1). */
119 [ + + + - : 34 : auto TxCount() const noexcept { return m_used.Count(); }
+ - ]
120 : : /** Get the feerate of a given transaction i. Complexity: O(1). */
121 [ + - + + ]: 40 : const FeeFrac& FeeRate(DepGraphIndex i) const noexcept { return entries[i].feerate; }
122 : : /** Get the mutable feerate of a given transaction i. Complexity: O(1). */
123 [ # # # # ]: 0 : FeeFrac& FeeRate(DepGraphIndex i) noexcept { return entries[i].feerate; }
124 : : /** Get the ancestors of a given transaction i. Complexity: O(1). */
125 [ + - + + : 89 : const SetType& Ancestors(DepGraphIndex i) const noexcept { return entries[i].ancestors; }
+ + ]
[ # # # # ]
126 : : /** Get the descendants of a given transaction i. Complexity: O(1). */
127 [ + + + - ]: 63 : const SetType& Descendants(DepGraphIndex i) const noexcept { return entries[i].descendants; }
[ # # ]
128 : :
129 : : /** Add a new unconnected transaction to this transaction graph (in the first available
130 : : * position), and return its DepGraphIndex.
131 : : *
132 : : * Complexity: O(1) (amortized, due to resizing of backing vector).
133 : : */
134 : 49 : DepGraphIndex AddTransaction(const FeeFrac& feefrac) noexcept
135 : : {
136 : : static constexpr auto ALL_POSITIONS = SetType::Fill(SetType::Size());
137 [ + - ]: 49 : auto available = ALL_POSITIONS - m_used;
138 [ + - ]: 49 : Assume(available.Any());
139 : 49 : DepGraphIndex new_idx = available.First();
140 [ - + + - ]: 49 : if (new_idx == entries.size()) {
141 : 49 : entries.emplace_back(feefrac, SetType::Singleton(new_idx), SetType::Singleton(new_idx));
142 : : } else {
143 : 0 : entries[new_idx] = Entry(feefrac, SetType::Singleton(new_idx), SetType::Singleton(new_idx));
144 : : }
145 : 49 : m_used.Set(new_idx);
146 : 49 : return new_idx;
147 : : }
148 : :
149 : : /** Remove the specified positions from this DepGraph.
150 : : *
151 : : * The specified positions will no longer be part of Positions(), and dependencies with them are
152 : : * removed. Note that due to DepGraph only tracking ancestors/descendants (and not direct
153 : : * dependencies), if a parent is removed while a grandparent remains, the grandparent will
154 : : * remain an ancestor.
155 : : *
156 : : * Complexity: O(N) where N=TxCount().
157 : : */
158 : 7 : void RemoveTransactions(const SetType& del) noexcept
159 : : {
160 : 7 : m_used -= del;
161 : : // Remove now-unused trailing entries.
162 [ + + - + : 7 : while (!entries.empty() && !m_used[entries.size() - 1]) {
- + ]
163 : 0 : entries.pop_back();
164 : : }
165 : : // Remove the deleted transactions from ancestors/descendants of other transactions. Note
166 : : // that the deleted positions will retain old feerate and dependency information. This does
167 : : // not matter as they will be overwritten by AddTransaction if they get used again.
168 [ + + ]: 36 : for (auto& entry : entries) {
169 : 29 : entry.ancestors &= m_used;
170 : 29 : entry.descendants &= m_used;
171 : : }
172 : 7 : }
173 : :
174 : : /** Modify this transaction graph, adding multiple parents to a specified child.
175 : : *
176 : : * Complexity: O(N) where N=TxCount().
177 : : */
178 : 69 : void AddDependencies(const SetType& parents, DepGraphIndex child) noexcept
179 : : {
180 : 69 : Assume(m_used[child]);
181 : 69 : Assume(parents.IsSubsetOf(m_used));
182 : : // Compute the ancestors of parents that are not already ancestors of child.
183 [ + + ]: 69 : SetType par_anc;
184 [ + + + + : 218 : for (auto par : parents - Ancestors(child)) {
+ + ]
185 [ + + ]: 47 : par_anc |= Ancestors(par);
186 : : }
187 [ + + ]: 69 : par_anc -= Ancestors(child);
188 : : // Bail out if there are no such ancestors.
189 [ + + ]: 69 : if (par_anc.None()) return;
190 : : // To each such ancestor, add as descendants the descendants of the child.
191 : 33 : const auto& chl_des = entries[child].descendants;
192 [ + + ]: 123 : for (auto anc_of_par : par_anc) {
193 [ + + ]: 57 : entries[anc_of_par].descendants |= chl_des;
194 : : }
195 : : // To each descendant of the child, add those ancestors.
196 [ + - + + ]: 132 : for (auto dec_of_chl : Descendants(child)) {
197 [ - + ]: 33 : entries[dec_of_chl].ancestors |= par_anc;
198 : : }
199 : : }
200 : :
201 : : /** Compute the (reduced) set of parents of node i in this graph.
202 : : *
203 : : * This returns the minimal subset of the parents of i whose ancestors together equal all of
204 : : * i's ancestors (unless i is part of a cycle of dependencies). Note that DepGraph does not
205 : : * store the set of parents; this information is inferred from the ancestor sets.
206 : : *
207 : : * Complexity: O(N) where N=Ancestors(i).Count() (which is bounded by TxCount()).
208 : : */
209 [ + + ]: 20 : SetType GetReducedParents(DepGraphIndex i) const noexcept
210 : : {
211 [ + + ]: 20 : SetType parents = Ancestors(i);
212 : 20 : parents.Reset(i);
213 [ + + + - : 78 : for (auto parent : parents) {
+ + + + ]
214 [ + - ]: 19 : if (parents[parent]) {
215 : 19 : parents -= Ancestors(parent);
216 : 19 : parents.Set(parent);
217 : : }
218 : : }
219 : 20 : return parents;
220 : : }
221 : :
222 : : /** Compute the (reduced) set of children of node i in this graph.
223 : : *
224 : : * This returns the minimal subset of the children of i whose descendants together equal all of
225 : : * i's descendants (unless i is part of a cycle of dependencies). Note that DepGraph does not
226 : : * store the set of children; this information is inferred from the descendant sets.
227 : : *
228 : : * Complexity: O(N) where N=Descendants(i).Count() (which is bounded by TxCount()).
229 : : */
230 : : SetType GetReducedChildren(DepGraphIndex i) const noexcept
231 : : {
232 : : SetType children = Descendants(i);
233 : : children.Reset(i);
234 : : for (auto child : children) {
235 : : if (children[child]) {
236 : : children -= Descendants(child);
237 : : children.Set(child);
238 : : }
239 : : }
240 : : return children;
241 : : }
242 : :
243 : : /** Compute the aggregate feerate of a set of nodes in this graph.
244 : : *
245 : : * Complexity: O(N) where N=elems.Count().
246 : : **/
247 : 0 : FeeFrac FeeRate(const SetType& elems) const noexcept
248 : : {
249 : 0 : FeeFrac ret;
250 [ # # # # : 0 : for (auto pos : elems) ret += entries[pos].feerate;
# # ]
251 : 0 : return ret;
252 : : }
253 : :
254 : : /** Get the connected component within the subset "todo" that contains tx (which must be in
255 : : * todo).
256 : : *
257 : : * Two transactions are considered connected if they are both in `todo`, and one is an ancestor
258 : : * of the other in the entire graph (so not just within `todo`), or transitively there is a
259 : : * path of transactions connecting them. This does mean that if `todo` contains a transaction
260 : : * and a grandparent, but misses the parent, they will still be part of the same component.
261 : : *
262 : : * Complexity: O(ret.Count()).
263 : : */
264 : 0 : SetType GetConnectedComponent(const SetType& todo, DepGraphIndex tx) const noexcept
265 : : {
266 : 0 : Assume(todo[tx]);
267 : 0 : Assume(todo.IsSubsetOf(m_used));
268 : 0 : auto to_add = SetType::Singleton(tx);
269 : 0 : SetType ret;
270 : : do {
271 : 0 : SetType old = ret;
272 [ # # # # : 0 : for (auto add : to_add) {
# # ]
273 [ # # ]: 0 : ret |= Descendants(add);
274 [ # # ]: 0 : ret |= Ancestors(add);
275 : : }
276 [ # # ]: 0 : ret &= todo;
277 : 0 : to_add = ret - old;
278 [ # # ]: 0 : } while (to_add.Any());
279 : 0 : return ret;
280 : : }
281 : :
282 : : /** Find some connected component within the subset "todo" of this graph.
283 : : *
284 : : * Specifically, this finds the connected component which contains the first transaction of
285 : : * todo (if any).
286 : : *
287 : : * Complexity: O(ret.Count()).
288 : : */
289 [ # # ]: 0 : SetType FindConnectedComponent(const SetType& todo) const noexcept
290 : : {
291 [ # # ]: 0 : if (todo.None()) return todo;
292 : 0 : return GetConnectedComponent(todo, todo.First());
293 : : }
294 : :
295 : : /** Determine if a subset is connected.
296 : : *
297 : : * Complexity: O(subset.Count()).
298 : : */
299 : 0 : bool IsConnected(const SetType& subset) const noexcept
300 : : {
301 [ # # ]: 0 : return FindConnectedComponent(subset) == subset;
302 : : }
303 : :
304 : : /** Determine if this entire graph is connected.
305 : : *
306 : : * Complexity: O(TxCount()).
307 : : */
308 : : bool IsConnected() const noexcept { return IsConnected(m_used); }
309 : :
310 : : /** Append the entries of select to list in a topologically valid order.
311 : : *
312 : : * Complexity: O(select.Count() * log(select.Count())).
313 : : */
314 [ # # ]: 0 : void AppendTopo(std::vector<DepGraphIndex>& list, const SetType& select) const noexcept
315 : : {
316 : 0 : DepGraphIndex old_len = list.size();
317 [ # # # # : 0 : for (auto i : select) list.push_back(i);
# # ]
318 : 0 : std::sort(list.begin() + old_len, list.end(), [&](DepGraphIndex a, DepGraphIndex b) noexcept {
319 [ # # ]: 0 : const auto a_anc_count = entries[a].ancestors.Count();
320 : 0 : const auto b_anc_count = entries[b].ancestors.Count();
321 [ # # ]: 0 : if (a_anc_count != b_anc_count) return a_anc_count < b_anc_count;
322 : 0 : return a < b;
323 : : });
324 : 0 : }
325 : :
326 : : /** Check if this graph is acyclic. */
327 : 0 : bool IsAcyclic() const noexcept
328 : : {
329 [ # # # # : 0 : for (auto i : Positions()) {
# # ]
330 [ # # # # ]: 0 : if ((Ancestors(i) & Descendants(i)) != SetType::Singleton(i)) {
331 : : return false;
332 : : }
333 : : }
334 : : return true;
335 : : }
336 : :
337 : : /** Reduce memory usage if possible. No observable effect. */
338 : 0 : void Compact() noexcept
339 : : {
340 : 0 : entries.shrink_to_fit();
341 : : }
342 : :
343 : 0 : size_t DynamicMemoryUsage() const noexcept
344 : : {
345 [ # # ]: 0 : return memusage::DynamicUsage(entries);
346 : : }
347 : : };
348 : :
349 : : /** A set of transactions together with their aggregate feerate. */
350 : : template<typename SetType>
351 : : struct SetInfo
352 : : {
353 : : /** The transactions in the set. */
354 : : SetType transactions;
355 : : /** Their combined fee and size. */
356 : : FeeFrac feerate;
357 : :
358 : : /** Construct a SetInfo for the empty set. */
359 : : SetInfo() noexcept = default;
360 : :
361 : : /** Construct a SetInfo for a specified set and feerate. */
362 : 0 : SetInfo(const SetType& txn, const FeeFrac& fr) noexcept : transactions(txn), feerate(fr) {}
363 : :
364 : : /** Construct a SetInfo for a given transaction in a depgraph. */
365 : 0 : explicit SetInfo(const DepGraph<SetType>& depgraph, DepGraphIndex pos) noexcept :
366 : 0 : transactions(SetType::Singleton(pos)), feerate(depgraph.FeeRate(pos)) {}
367 : :
368 : : /** Construct a SetInfo for a set of transactions in a depgraph. */
369 : 0 : explicit SetInfo(const DepGraph<SetType>& depgraph, const SetType& txn) noexcept :
370 : 0 : transactions(txn), feerate(depgraph.FeeRate(txn)) {}
371 : :
372 : : /** Add a transaction to this SetInfo (which must not yet be in it). */
373 : 0 : void Set(const DepGraph<SetType>& depgraph, DepGraphIndex pos) noexcept
374 : : {
375 : 0 : Assume(!transactions[pos]);
376 : 0 : transactions.Set(pos);
377 : 0 : feerate += depgraph.FeeRate(pos);
378 : 0 : }
379 : :
380 : : /** Add the transactions of other to this SetInfo (no overlap allowed). */
381 : 0 : SetInfo& operator|=(const SetInfo& other) noexcept
382 : : {
383 : : Assume(!transactions.Overlaps(other.transactions));
384 : 0 : transactions |= other.transactions;
385 : 0 : feerate += other.feerate;
386 : : return *this;
387 : : }
388 : :
389 : : /** Construct a new SetInfo equal to this, with more transactions added (which may overlap
390 : : * with the existing transactions in the SetInfo). */
391 : 0 : [[nodiscard]] SetInfo Add(const DepGraph<SetType>& depgraph, const SetType& txn) const noexcept
392 : : {
393 : 0 : return {transactions | txn, feerate + depgraph.FeeRate(txn - transactions)};
394 : : }
395 : :
396 : : /** Swap two SetInfo objects. */
397 : 0 : friend void swap(SetInfo& a, SetInfo& b) noexcept
398 : : {
399 : 0 : swap(a.transactions, b.transactions);
400 : 0 : swap(a.feerate, b.feerate);
401 : : }
402 : :
403 : : /** Permit equality testing. */
404 : : friend bool operator==(const SetInfo&, const SetInfo&) noexcept = default;
405 : : };
406 : :
407 : : /** Compute the feerates of the chunks of linearization. */
408 : : template<typename SetType>
409 : 0 : std::vector<FeeFrac> ChunkLinearization(const DepGraph<SetType>& depgraph, std::span<const DepGraphIndex> linearization) noexcept
410 : : {
411 : 0 : std::vector<FeeFrac> ret;
412 [ # # ]: 0 : for (DepGraphIndex i : linearization) {
413 : : /** The new chunk to be added, initially a singleton. */
414 : 0 : auto new_chunk = depgraph.FeeRate(i);
415 : : // As long as the new chunk has a higher feerate than the last chunk so far, absorb it.
416 [ # # # # ]: 0 : while (!ret.empty() && new_chunk >> ret.back()) {
417 : 0 : new_chunk += ret.back();
418 : 0 : ret.pop_back();
419 : : }
420 : : // Actually move that new chunk into the chunking.
421 : 0 : ret.push_back(std::move(new_chunk));
422 : : }
423 : 0 : return ret;
424 : : }
425 : :
426 : : /** Data structure encapsulating the chunking of a linearization, permitting removal of subsets. */
427 : : template<typename SetType>
428 : 0 : class LinearizationChunking
429 : : {
430 : : /** The depgraph this linearization is for. */
431 : : const DepGraph<SetType>& m_depgraph;
432 : :
433 : : /** The linearization we started from, possibly with removed prefix stripped. */
434 : : std::span<const DepGraphIndex> m_linearization;
435 : :
436 : : /** Chunk sets and their feerates, of what remains of the linearization. */
437 : : std::vector<SetInfo<SetType>> m_chunks;
438 : :
439 : : /** How large a prefix of m_chunks corresponds to removed transactions. */
440 : : DepGraphIndex m_chunks_skip{0};
441 : :
442 : : /** Which transactions remain in the linearization. */
443 : : SetType m_todo;
444 : :
445 : : /** Fill the m_chunks variable, and remove the done prefix of m_linearization. */
446 : 0 : void BuildChunks() noexcept
447 : : {
448 : : // Caller must clear m_chunks.
449 : 0 : Assume(m_chunks.empty());
450 : :
451 : : // Chop off the initial part of m_linearization that is already done.
452 [ # # # # ]: 0 : while (!m_linearization.empty() && !m_todo[m_linearization.front()]) {
453 : 0 : m_linearization = m_linearization.subspan(1);
454 : : }
455 : :
456 : : // Iterate over the remaining entries in m_linearization. This is effectively the same
457 : : // algorithm as ChunkLinearization, but supports skipping parts of the linearization and
458 : : // keeps track of the sets themselves instead of just their feerates.
459 [ # # ]: 0 : for (auto idx : m_linearization) {
460 [ # # ]: 0 : if (!m_todo[idx]) continue;
461 : : // Start with an initial chunk containing just element idx.
462 : 0 : SetInfo add(m_depgraph, idx);
463 : : // Absorb existing final chunks into add while they have lower feerate.
464 [ # # # # ]: 0 : while (!m_chunks.empty() && add.feerate >> m_chunks.back().feerate) {
465 : 0 : add |= m_chunks.back();
466 : 0 : m_chunks.pop_back();
467 : : }
468 : : // Remember new chunk.
469 : 0 : m_chunks.push_back(std::move(add));
470 : : }
471 : 0 : }
472 : :
473 : : public:
474 : : /** Initialize a LinearizationSubset object for a given length of linearization. */
475 : 0 : explicit LinearizationChunking(const DepGraph<SetType>& depgraph LIFETIMEBOUND, std::span<const DepGraphIndex> lin LIFETIMEBOUND) noexcept :
476 : 0 : m_depgraph(depgraph), m_linearization(lin)
477 : : {
478 : : // Mark everything in lin as todo still.
479 [ # # ]: 0 : for (auto i : m_linearization) m_todo.Set(i);
480 : : // Compute the initial chunking.
481 : 0 : m_chunks.reserve(depgraph.TxCount());
482 : 0 : BuildChunks();
483 : 0 : }
484 : :
485 : : /** Determine how many chunks remain in the linearization. */
486 [ # # # # : 0 : DepGraphIndex NumChunksLeft() const noexcept { return m_chunks.size() - m_chunks_skip; }
# # # # #
# # # ]
487 : :
488 : : /** Access a chunk. Chunk 0 is the highest-feerate prefix of what remains. */
489 : 0 : const SetInfo<SetType>& GetChunk(DepGraphIndex n) const noexcept
490 : : {
491 [ # # # # : 0 : Assume(n + m_chunks_skip < m_chunks.size());
# # ]
492 [ # # # # : 0 : return m_chunks[n + m_chunks_skip];
# # # # ]
493 : : }
494 : :
495 : : /** Remove some subset of transactions from the linearization. */
496 [ # # ]: 0 : void MarkDone(SetType subset) noexcept
497 : : {
498 : 0 : Assume(subset.Any());
499 : 0 : Assume(subset.IsSubsetOf(m_todo));
500 [ # # ]: 0 : m_todo -= subset;
501 [ # # ]: 0 : if (GetChunk(0).transactions == subset) {
502 : : // If the newly done transactions exactly match the first chunk of the remainder of
503 : : // the linearization, we do not need to rechunk; just remember to skip one
504 : : // additional chunk.
505 : 0 : ++m_chunks_skip;
506 : : // With subset marked done, some prefix of m_linearization will be done now. How long
507 : : // that prefix is depends on how many done elements were interspersed with subset,
508 : : // but at least as many transactions as there are in subset.
509 : 0 : m_linearization = m_linearization.subspan(subset.Count());
510 : : } else {
511 : : // Otherwise rechunk what remains of m_linearization.
512 [ # # ]: 0 : m_chunks.clear();
513 : 0 : m_chunks_skip = 0;
514 : 0 : BuildChunks();
515 : : }
516 : 0 : }
517 : :
518 : : /** Find the shortest intersection between subset and the prefixes of remaining chunks
519 : : * of the linearization that has a feerate not below subset's.
520 : : *
521 : : * This is a crucial operation in guaranteeing improvements to linearizations. If subset has
522 : : * a feerate not below GetChunk(0)'s, then moving IntersectPrefixes(subset) to the front of
523 : : * (what remains of) the linearization is guaranteed not to make it worse at any point.
524 : : *
525 : : * See https://delvingbitcoin.org/t/introduction-to-cluster-linearization/1032 for background.
526 : : */
527 : 0 : SetInfo<SetType> IntersectPrefixes(const SetInfo<SetType>& subset) const noexcept
528 : : {
529 : 0 : Assume(subset.transactions.IsSubsetOf(m_todo));
530 : 0 : SetInfo<SetType> accumulator;
531 : : // Iterate over all chunks of the remaining linearization.
532 [ # # # # ]: 0 : for (DepGraphIndex i = 0; i < NumChunksLeft(); ++i) {
533 : : // Find what (if any) intersection the chunk has with subset.
534 [ # # ]: 0 : const SetType to_add = GetChunk(i).transactions & subset.transactions;
535 [ # # ]: 0 : if (to_add.Any()) {
536 : : // If adding that to accumulator makes us hit all of subset, we are done as no
537 : : // shorter intersection with higher/equal feerate exists.
538 : 0 : accumulator.transactions |= to_add;
539 [ # # ]: 0 : if (accumulator.transactions == subset.transactions) break;
540 : : // Otherwise update the accumulator feerate.
541 [ # # ]: 0 : accumulator.feerate += m_depgraph.FeeRate(to_add);
542 : : // If that does result in something better, or something with the same feerate but
543 : : // smaller, return that. Even if a longer, higher-feerate intersection exists, it
544 : : // does not hurt to return the shorter one (the remainder of the longer intersection
545 : : // will generally be found in the next call to Intersect, but even if not, it is not
546 : : // required for the improvement guarantee this function makes).
547 [ # # ]: 0 : if (!(accumulator.feerate << subset.feerate)) return accumulator;
548 : : }
549 : : }
550 : 0 : return subset;
551 : : }
552 : : };
553 : :
554 : : /** Class encapsulating the state needed to find the best remaining ancestor set.
555 : : *
556 : : * It is initialized for an entire DepGraph, and parts of the graph can be dropped by calling
557 : : * MarkDone.
558 : : *
559 : : * As long as any part of the graph remains, FindCandidateSet() can be called which will return a
560 : : * SetInfo with the highest-feerate ancestor set that remains (an ancestor set is a single
561 : : * transaction together with all its remaining ancestors).
562 : : */
563 : : template<typename SetType>
564 : 0 : class AncestorCandidateFinder
565 : : {
566 : : /** Internal dependency graph. */
567 : : const DepGraph<SetType>& m_depgraph;
568 : : /** Which transaction are left to include. */
569 : : SetType m_todo;
570 : : /** Precomputed ancestor-set feerates (only kept up-to-date for indices in m_todo). */
571 : : std::vector<FeeFrac> m_ancestor_set_feerates;
572 : :
573 : : public:
574 : : /** Construct an AncestorCandidateFinder for a given cluster.
575 : : *
576 : : * Complexity: O(N^2) where N=depgraph.TxCount().
577 : : */
578 : 0 : AncestorCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept :
579 : 0 : m_depgraph(depgraph),
580 : 0 : m_todo{depgraph.Positions()},
581 [ # # # # ]: 0 : m_ancestor_set_feerates(depgraph.PositionRange())
582 : : {
583 : : // Precompute ancestor-set feerates.
584 [ # # # # : 0 : for (DepGraphIndex i : m_depgraph.Positions()) {
# # ]
585 : : /** The remaining ancestors for transaction i. */
586 [ # # ]: 0 : SetType anc_to_add = m_depgraph.Ancestors(i);
587 [ # # ]: 0 : FeeFrac anc_feerate;
588 : : // Reuse accumulated feerate from first ancestor, if usable.
589 [ # # ]: 0 : Assume(anc_to_add.Any());
590 : 0 : DepGraphIndex first = anc_to_add.First();
591 [ # # ]: 0 : if (first < i) {
592 : 0 : anc_feerate = m_ancestor_set_feerates[first];
593 : 0 : Assume(!anc_feerate.IsEmpty());
594 : 0 : anc_to_add -= m_depgraph.Ancestors(first);
595 : : }
596 : : // Add in other ancestors (which necessarily include i itself).
597 : 0 : Assume(anc_to_add[i]);
598 [ # # ]: 0 : anc_feerate += m_depgraph.FeeRate(anc_to_add);
599 : : // Store the result.
600 [ # # ]: 0 : m_ancestor_set_feerates[i] = anc_feerate;
601 : : }
602 : 0 : }
603 : :
604 : : /** Remove a set of transactions from the set of to-be-linearized ones.
605 : : *
606 : : * The same transaction may not be MarkDone()'d twice.
607 : : *
608 : : * Complexity: O(N*M) where N=depgraph.TxCount(), M=select.Count().
609 : : */
610 [ # # ]: 0 : void MarkDone(SetType select) noexcept
611 : : {
612 : 0 : Assume(select.Any());
613 : 0 : Assume(select.IsSubsetOf(m_todo));
614 [ # # ]: 0 : m_todo -= select;
615 [ # # # # : 0 : for (auto i : select) {
# # ]
616 [ # # ]: 0 : auto feerate = m_depgraph.FeeRate(i);
617 [ # # # # ]: 0 : for (auto j : m_depgraph.Descendants(i) & m_todo) {
618 [ # # ]: 0 : m_ancestor_set_feerates[j] -= feerate;
619 : : }
620 : : }
621 : 0 : }
622 : :
623 : : /** Check whether any unlinearized transactions remain. */
624 : 0 : bool AllDone() const noexcept
625 : : {
626 : 0 : return m_todo.None();
627 : : }
628 : :
629 : : /** Count the number of remaining unlinearized transactions. */
630 : 0 : DepGraphIndex NumRemaining() const noexcept
631 : : {
632 [ # # ]: 0 : return m_todo.Count();
633 : : }
634 : :
635 : : /** Find the best (highest-feerate, smallest among those in case of a tie) ancestor set
636 : : * among the remaining transactions. Requires !AllDone().
637 : : *
638 : : * Complexity: O(N) where N=depgraph.TxCount();
639 : : */
640 : 0 : SetInfo<SetType> FindCandidateSet() const noexcept
641 : : {
642 : 0 : Assume(!AllDone());
643 : 0 : std::optional<DepGraphIndex> best;
644 [ # # # # : 0 : for (auto i : m_todo) {
# # # # ]
645 [ # # ]: 0 : if (best.has_value()) {
646 [ # # ]: 0 : Assume(!m_ancestor_set_feerates[i].IsEmpty());
647 [ # # ]: 0 : if (!(m_ancestor_set_feerates[i] > m_ancestor_set_feerates[*best])) continue;
648 : : }
649 : 0 : best = i;
650 : : }
651 : 0 : Assume(best.has_value());
652 : 0 : return {m_depgraph.Ancestors(*best) & m_todo, m_ancestor_set_feerates[*best]};
653 : : }
654 : : };
655 : :
656 : : /** Class encapsulating the state needed to perform search for good candidate sets.
657 : : *
658 : : * It is initialized for an entire DepGraph, and parts of the graph can be dropped by calling
659 : : * MarkDone().
660 : : *
661 : : * As long as any part of the graph remains, FindCandidateSet() can be called to perform a search
662 : : * over the set of topologically-valid subsets of that remainder, with a limit on how many
663 : : * combinations are tried.
664 : : */
665 : : template<typename SetType>
666 : : class SearchCandidateFinder
667 : : {
668 : : /** Internal RNG. */
669 : : InsecureRandomContext m_rng;
670 : : /** m_sorted_to_original[i] is the original position that sorted transaction position i had. */
671 : : std::vector<DepGraphIndex> m_sorted_to_original;
672 : : /** m_original_to_sorted[i] is the sorted position original transaction position i has. */
673 : : std::vector<DepGraphIndex> m_original_to_sorted;
674 : : /** Internal dependency graph for the cluster (with transactions in decreasing individual
675 : : * feerate order). */
676 : : DepGraph<SetType> m_sorted_depgraph;
677 : : /** Which transactions are left to do (indices in m_sorted_depgraph's order). */
678 : : SetType m_todo;
679 : :
680 : : /** Given a set of transactions with sorted indices, get their original indices. */
681 : 0 : SetType SortedToOriginal(const SetType& arg) const noexcept
682 : : {
683 : 0 : SetType ret;
684 [ # # # # : 0 : for (auto pos : arg) ret.Set(m_sorted_to_original[pos]);
# # ]
685 : 0 : return ret;
686 : : }
687 : :
688 : : /** Given a set of transactions with original indices, get their sorted indices. */
689 : 0 : SetType OriginalToSorted(const SetType& arg) const noexcept
690 : : {
691 : 0 : SetType ret;
692 [ # # # # : 0 : for (auto pos : arg) ret.Set(m_original_to_sorted[pos]);
# # ]
693 : 0 : return ret;
694 : : }
695 : :
696 : : public:
697 : : /** Construct a candidate finder for a graph.
698 : : *
699 : : * @param[in] depgraph Dependency graph for the to-be-linearized cluster.
700 : : * @param[in] rng_seed A random seed to control the search order.
701 : : *
702 : : * Complexity: O(N^2) where N=depgraph.Count().
703 : : */
704 : 0 : SearchCandidateFinder(const DepGraph<SetType>& depgraph, uint64_t rng_seed) noexcept :
705 : 0 : m_rng(rng_seed),
706 [ # # ]: 0 : m_sorted_to_original(depgraph.TxCount()),
707 [ # # # # ]: 0 : m_original_to_sorted(depgraph.PositionRange())
708 : : {
709 : : // Determine reordering mapping, by sorting by decreasing feerate. Unused positions are
710 : : // not included, as they will never be looked up anyway.
711 : 0 : DepGraphIndex sorted_pos{0};
712 [ # # # # ]: 0 : for (auto i : depgraph.Positions()) {
713 [ # # ]: 0 : m_sorted_to_original[sorted_pos++] = i;
714 : : }
715 : 0 : std::sort(m_sorted_to_original.begin(), m_sorted_to_original.end(), [&](auto a, auto b) {
716 [ # # ]: 0 : auto feerate_cmp = depgraph.FeeRate(a) <=> depgraph.FeeRate(b);
717 [ # # ]: 0 : if (feerate_cmp == 0) return a < b;
718 : 0 : return feerate_cmp > 0;
719 : : });
720 : : // Compute reverse mapping.
721 [ # # # # ]: 0 : for (DepGraphIndex i = 0; i < m_sorted_to_original.size(); ++i) {
722 : 0 : m_original_to_sorted[m_sorted_to_original[i]] = i;
723 : : }
724 : : // Compute reordered dependency graph.
725 [ # # ]: 0 : m_sorted_depgraph = DepGraph(depgraph, m_original_to_sorted, m_sorted_to_original.size());
726 : 0 : m_todo = m_sorted_depgraph.Positions();
727 : 0 : }
728 : :
729 : : /** Check whether any unlinearized transactions remain. */
730 : : bool AllDone() const noexcept
731 : : {
732 : 0 : return m_todo.None();
733 : : }
734 : :
735 : : /** Find a high-feerate topologically-valid subset of what remains of the cluster.
736 : : * Requires !AllDone().
737 : : *
738 : : * @param[in] max_iterations The maximum number of optimization steps that will be performed.
739 : : * @param[in] best A set/feerate pair with an already-known good candidate. This may
740 : : * be empty.
741 : : * @return A pair of:
742 : : * - The best (highest feerate, smallest size as tiebreaker)
743 : : * topologically valid subset (and its feerate) that was
744 : : * encountered during search. It will be at least as good as the
745 : : * best passed in (if not empty).
746 : : * - The number of optimization steps that were performed. This will
747 : : * be <= max_iterations. If strictly < max_iterations, the
748 : : * returned subset is optimal.
749 : : *
750 : : * Complexity: possibly O(N * min(max_iterations, sqrt(2^N))) where N=depgraph.TxCount().
751 : : */
752 : 0 : std::pair<SetInfo<SetType>, uint64_t> FindCandidateSet(uint64_t max_iterations, SetInfo<SetType> best) noexcept
753 : : {
754 : 0 : Assume(!AllDone());
755 : :
756 : : // Convert the provided best to internal sorted indices.
757 : 0 : best.transactions = OriginalToSorted(best.transactions);
758 : :
759 : : /** Type for work queue items. */
760 : : struct WorkItem
761 : : {
762 : : /** Set of transactions definitely included (and its feerate). This must be a subset
763 : : * of m_todo, and be topologically valid (includes all in-m_todo ancestors of
764 : : * itself). */
765 : : SetInfo<SetType> inc;
766 : : /** Set of undecided transactions. This must be a subset of m_todo, and have no overlap
767 : : * with inc. The set (inc | und) must be topologically valid. */
768 : : SetType und;
769 : : /** (Only when inc is not empty) The best feerate of any superset of inc that is also a
770 : : * subset of (inc | und), without requiring it to be topologically valid. It forms a
771 : : * conservative upper bound on how good a set this work item can give rise to.
772 : : * Transactions whose feerate is below best's are ignored when determining this value,
773 : : * which means it may technically be an underestimate, but if so, this work item
774 : : * cannot result in something that beats best anyway. */
775 : : FeeFrac pot_feerate;
776 : :
777 : : /** Construct a new work item. */
778 : 0 : WorkItem(SetInfo<SetType>&& i, SetType&& u, FeeFrac&& p_f) noexcept :
779 : 0 : inc(std::move(i)), und(std::move(u)), pot_feerate(std::move(p_f))
780 : : {
781 : 0 : Assume(pot_feerate.IsEmpty() == inc.feerate.IsEmpty());
782 : : }
783 : :
784 : : /** Swap two WorkItems. */
785 : 0 : void Swap(WorkItem& other) noexcept
786 : : {
787 : 0 : swap(inc, other.inc);
788 : 0 : swap(und, other.und);
789 : 0 : swap(pot_feerate, other.pot_feerate);
790 : 0 : }
791 : : };
792 : :
793 : : /** The queue of work items. */
794 : 0 : VecDeque<WorkItem> queue;
795 [ # # # # ]: 0 : queue.reserve(std::max<size_t>(256, 2 * m_todo.Count()));
796 : :
797 : : // Create initial entries per connected component of m_todo. While clusters themselves are
798 : : // generally connected, this is not necessarily true after some parts have already been
799 : : // removed from m_todo. Without this, effort can be wasted on searching "inc" sets that
800 : : // span multiple components.
801 : 0 : auto to_cover = m_todo;
802 : : do {
803 [ # # ]: 0 : auto component = m_sorted_depgraph.FindConnectedComponent(to_cover);
804 [ # # ]: 0 : to_cover -= component;
805 : : // If best is not provided, set it to the first component, so that during the work
806 : : // processing loop below, and during the add_fn/split_fn calls, we do not need to deal
807 : : // with the best=empty case.
808 [ # # ]: 0 : if (best.feerate.IsEmpty()) best = SetInfo(m_sorted_depgraph, component);
809 : 0 : queue.emplace_back(/*inc=*/SetInfo<SetType>{},
810 : : /*und=*/std::move(component),
811 : 0 : /*pot_feerate=*/FeeFrac{});
812 [ # # ]: 0 : } while (to_cover.Any());
813 : :
814 : : /** Local copy of the iteration limit. */
815 : 0 : uint64_t iterations_left = max_iterations;
816 : :
817 : : /** The set of transactions in m_todo which have feerate > best's. */
818 : 0 : SetType imp = m_todo;
819 [ # # ]: 0 : while (imp.Any()) {
820 : 0 : DepGraphIndex check = imp.Last();
821 [ # # ]: 0 : if (m_sorted_depgraph.FeeRate(check) >> best.feerate) break;
822 : 0 : imp.Reset(check);
823 : : }
824 : :
825 : : /** Internal function to add an item to the queue of elements to explore if there are any
826 : : * transactions left to split on, possibly improving it before doing so, and to update
827 : : * best/imp.
828 : : *
829 : : * - inc: the "inc" value for the new work item (must be topological).
830 : : * - und: the "und" value for the new work item ((inc | und) must be topological).
831 : : */
832 : 0 : auto add_fn = [&](SetInfo<SetType> inc, SetType und) noexcept {
833 : : /** SetInfo object with the set whose feerate will become the new work item's
834 : : * pot_feerate. It starts off equal to inc. */
835 [ # # ]: 0 : auto pot = inc;
836 [ # # ]: 0 : if (!inc.feerate.IsEmpty()) {
837 : : // Add entries to pot. We iterate over all undecided transactions whose feerate is
838 : : // higher than best. While undecided transactions of lower feerate may improve pot,
839 : : // the resulting pot feerate cannot possibly exceed best's (and this item will be
840 : : // skipped in split_fn anyway).
841 [ # # # # : 0 : for (auto pos : imp & und) {
# # ]
842 : : // Determine if adding transaction pos to pot (ignoring topology) would improve
843 : : // it. If not, we're done updating pot. This relies on the fact that
844 : : // m_sorted_depgraph, and thus the transactions iterated over, are in decreasing
845 : : // individual feerate order.
846 [ # # ]: 0 : if (!(m_sorted_depgraph.FeeRate(pos) >> pot.feerate)) break;
847 : 0 : pot.Set(m_sorted_depgraph, pos);
848 : : }
849 : :
850 : : // The "jump ahead" optimization: whenever pot has a topologically-valid subset,
851 : : // that subset can be added to inc. Any subset of (pot - inc) has the property that
852 : : // its feerate exceeds that of any set compatible with this work item (superset of
853 : : // inc, subset of (inc | und)). Thus, if T is a topological subset of pot, and B is
854 : : // the best topologically-valid set compatible with this work item, and (T - B) is
855 : : // non-empty, then (T | B) is better than B and also topological. This is in
856 : : // contradiction with the assumption that B is best. Thus, (T - B) must be empty,
857 : : // or T must be a subset of B.
858 : : //
859 : : // See https://delvingbitcoin.org/t/how-to-linearize-your-cluster/303 section 2.4.
860 [ # # ]: 0 : const auto init_inc = inc.transactions;
861 [ # # # # : 0 : for (auto pos : pot.transactions - inc.transactions) {
# # ]
862 : : // If the transaction's ancestors are a subset of pot, we can add it together
863 : : // with its ancestors to inc. Just update the transactions here; the feerate
864 : : // update happens below.
865 [ # # ]: 0 : auto anc_todo = m_sorted_depgraph.Ancestors(pos) & m_todo;
866 [ # # ]: 0 : if (anc_todo.IsSubsetOf(pot.transactions)) inc.transactions |= anc_todo;
867 : : }
868 : : // Finally update und and inc's feerate to account for the added transactions.
869 : 0 : und -= inc.transactions;
870 [ # # ]: 0 : inc.feerate += m_sorted_depgraph.FeeRate(inc.transactions - init_inc);
871 : :
872 : : // If inc's feerate is better than best's, remember it as our new best.
873 [ # # ]: 0 : if (inc.feerate > best.feerate) {
874 : 0 : best = inc;
875 : : // See if we can remove any entries from imp now.
876 [ # # ]: 0 : while (imp.Any()) {
877 [ # # ]: 0 : DepGraphIndex check = imp.Last();
878 [ # # ]: 0 : if (m_sorted_depgraph.FeeRate(check) >> best.feerate) break;
879 : 0 : imp.Reset(check);
880 : : }
881 : : }
882 : :
883 : : // If no potential transactions exist beyond the already included ones, no
884 : : // improvement is possible anymore.
885 [ # # ]: 0 : if (pot.feerate.size == inc.feerate.size) return;
886 : : // At this point und must be non-empty. If it were empty then pot would equal inc.
887 : : Assume(und.Any());
888 : : } else {
889 [ # # ]: 0 : Assume(inc.transactions.None());
890 : : // If inc is empty, we just make sure there are undecided transactions left to
891 : : // split on.
892 [ # # ]: 0 : if (und.None()) return;
893 : : }
894 : :
895 : : // Actually construct a new work item on the queue. Due to the switch to DFS when queue
896 : : // space runs out (see below), we know that no reallocation of the queue should ever
897 : : // occur.
898 : 0 : Assume(queue.size() < queue.capacity());
899 : 0 : queue.emplace_back(/*inc=*/std::move(inc),
900 : : /*und=*/std::move(und),
901 : : /*pot_feerate=*/std::move(pot.feerate));
902 : : };
903 : :
904 : : /** Internal process function. It takes an existing work item, and splits it in two: one
905 : : * with a particular transaction (and its ancestors) included, and one with that
906 : : * transaction (and its descendants) excluded. */
907 : 0 : auto split_fn = [&](WorkItem&& elem) noexcept {
908 : : // Any queue element must have undecided transactions left, otherwise there is nothing
909 : : // to explore anymore.
910 [ # # ]: 0 : Assume(elem.und.Any());
911 : : // The included and undecided set are all subsets of m_todo.
912 [ # # ]: 0 : Assume(elem.inc.transactions.IsSubsetOf(m_todo) && elem.und.IsSubsetOf(m_todo));
913 : : // Included transactions cannot be undecided.
914 : 0 : Assume(!elem.inc.transactions.Overlaps(elem.und));
915 : : // If pot is empty, then so is inc.
916 : 0 : Assume(elem.inc.feerate.IsEmpty() == elem.pot_feerate.IsEmpty());
917 : :
918 [ # # ]: 0 : const DepGraphIndex first = elem.und.First();
919 [ # # ]: 0 : if (!elem.inc.feerate.IsEmpty()) {
920 : : // If no undecided transactions remain with feerate higher than best, this entry
921 : : // cannot be improved beyond best.
922 [ # # ]: 0 : if (!elem.und.Overlaps(imp)) return;
923 : : // We can ignore any queue item whose potential feerate isn't better than the best
924 : : // seen so far.
925 [ # # ]: 0 : if (elem.pot_feerate <= best.feerate) return;
926 : : } else {
927 : : // In case inc is empty use a simpler alternative check.
928 [ # # ]: 0 : if (m_sorted_depgraph.FeeRate(first) <= best.feerate) return;
929 : : }
930 : :
931 : : // Decide which transaction to split on. Splitting is how new work items are added, and
932 : : // how progress is made. One split transaction is chosen among the queue item's
933 : : // undecided ones, and:
934 : : // - A work item is (potentially) added with that transaction plus its remaining
935 : : // descendants excluded (removed from the und set).
936 : : // - A work item is (potentially) added with that transaction plus its remaining
937 : : // ancestors included (added to the inc set).
938 : : //
939 : : // To decide what to split on, consider the undecided ancestors of the highest
940 : : // individual feerate undecided transaction. Pick the one which reduces the search space
941 : : // most. Let I(t) be the size of the undecided set after including t, and E(t) the size
942 : : // of the undecided set after excluding t. Then choose the split transaction t such
943 : : // that 2^I(t) + 2^E(t) is minimal, tie-breaking by highest individual feerate for t.
944 : 0 : DepGraphIndex split = 0;
945 [ # # ]: 0 : const auto select = elem.und & m_sorted_depgraph.Ancestors(first);
946 : 0 : Assume(select.Any());
947 : 0 : std::optional<std::pair<DepGraphIndex, DepGraphIndex>> split_counts;
948 [ # # # # ]: 0 : for (auto t : select) {
949 : : // Call max = max(I(t), E(t)) and min = min(I(t), E(t)). Let counts = {max,min}.
950 : : // Sorting by the tuple counts is equivalent to sorting by 2^I(t) + 2^E(t). This
951 : : // expression is equal to 2^max + 2^min = 2^max * (1 + 1/2^(max - min)). The second
952 : : // factor (1 + 1/2^(max - min)) there is in (1,2]. Thus increasing max will always
953 : : // increase it, even when min decreases. Because of this, we can first sort by max.
954 : 0 : std::pair<DepGraphIndex, DepGraphIndex> counts{
955 [ # # ]: 0 : (elem.und - m_sorted_depgraph.Ancestors(t)).Count(),
956 [ # # ]: 0 : (elem.und - m_sorted_depgraph.Descendants(t)).Count()};
957 [ # # ]: 0 : if (counts.first < counts.second) std::swap(counts.first, counts.second);
958 : : // Remember the t with the lowest counts.
959 [ # # # # ]: 0 : if (!split_counts.has_value() || counts < *split_counts) {
960 [ # # ]: 0 : split = t;
961 [ # # ]: 0 : split_counts = counts;
962 : : }
963 : : }
964 : : // Since there was at least one transaction in select, we must always find one.
965 : 0 : Assume(split_counts.has_value());
966 : :
967 : : // Add a work item corresponding to exclusion of the split transaction.
968 : 0 : const auto& desc = m_sorted_depgraph.Descendants(split);
969 : 0 : add_fn(/*inc=*/elem.inc,
970 : 0 : /*und=*/elem.und - desc);
971 : :
972 : : // Add a work item corresponding to inclusion of the split transaction.
973 : 0 : const auto anc = m_sorted_depgraph.Ancestors(split) & m_todo;
974 : 0 : add_fn(/*inc=*/elem.inc.Add(m_sorted_depgraph, anc),
975 : 0 : /*und=*/elem.und - anc);
976 : :
977 : : // Account for the performed split.
978 : 0 : --iterations_left;
979 : : };
980 : :
981 : : // Work processing loop.
982 : : //
983 : : // New work items are always added at the back of the queue, but items to process use a
984 : : // hybrid approach where they can be taken from the front or the back.
985 : : //
986 : : // Depth-first search (DFS) corresponds to always taking from the back of the queue. This
987 : : // is very memory-efficient (linear in the number of transactions). Breadth-first search
988 : : // (BFS) corresponds to always taking from the front, which potentially uses more memory
989 : : // (up to exponential in the transaction count), but seems to work better in practice.
990 : : //
991 : : // The approach here combines the two: use BFS (plus random swapping) until the queue grows
992 : : // too large, at which point we temporarily switch to DFS until the size shrinks again.
993 [ # # ]: 0 : while (!queue.empty()) {
994 : : // Randomly swap the first two items to randomize the search order.
995 [ # # # # ]: 0 : if (queue.size() > 1 && m_rng.randbool()) {
996 [ # # ]: 0 : queue[0].Swap(queue[1]);
997 : : }
998 : :
999 : : // Processing the first queue item, and then using DFS for everything it gives rise to,
1000 : : // may increase the queue size by the number of undecided elements in there, minus 1
1001 : : // for the first queue item being removed. Thus, only when that pushes the queue over
1002 : : // its capacity can we not process from the front (BFS), and should we use DFS.
1003 [ # # ]: 0 : while (queue.size() - 1 + queue.front().und.Count() > queue.capacity()) {
1004 [ # # ]: 0 : if (!iterations_left) break;
1005 : 0 : auto elem = queue.back();
1006 : 0 : queue.pop_back();
1007 : 0 : split_fn(std::move(elem));
1008 : : }
1009 : :
1010 : : // Process one entry from the front of the queue (BFS exploration)
1011 [ # # ]: 0 : if (!iterations_left) break;
1012 [ # # ]: 0 : auto elem = queue.front();
1013 : 0 : queue.pop_front();
1014 : 0 : split_fn(std::move(elem));
1015 : : }
1016 : :
1017 : : // Return the found best set (converted to the original transaction indices), and the
1018 : : // number of iterations performed.
1019 : 0 : best.transactions = SortedToOriginal(best.transactions);
1020 : 0 : return {std::move(best), max_iterations - iterations_left};
1021 : 0 : }
1022 : :
1023 : : /** Remove a subset of transactions from the cluster being linearized.
1024 : : *
1025 : : * Complexity: O(N) where N=done.Count().
1026 : : */
1027 : 0 : void MarkDone(const SetType& done) noexcept
1028 : : {
1029 : 0 : const auto done_sorted = OriginalToSorted(done);
1030 : 0 : Assume(done_sorted.Any());
1031 : 0 : Assume(done_sorted.IsSubsetOf(m_todo));
1032 : 0 : m_todo -= done_sorted;
1033 : 0 : }
1034 : : };
1035 : :
1036 : : /** Find or improve a linearization for a cluster.
1037 : : *
1038 : : * @param[in] depgraph Dependency graph of the cluster to be linearized.
1039 : : * @param[in] max_iterations Upper bound on the number of optimization steps that will be done.
1040 : : * @param[in] rng_seed A random number seed to control search order. This prevents peers
1041 : : * from predicting exactly which clusters would be hard for us to
1042 : : * linearize.
1043 : : * @param[in] old_linearization An existing linearization for the cluster (which must be
1044 : : * topologically valid), or empty.
1045 : : * @return A tuple of:
1046 : : * - The resulting linearization. It is guaranteed to be at least as
1047 : : * good (in the feerate diagram sense) as old_linearization.
1048 : : * - A boolean indicating whether the result is guaranteed to be
1049 : : * optimal.
1050 : : * - How many optimization steps were actually performed.
1051 : : *
1052 : : * Complexity: possibly O(N * min(max_iterations + N, sqrt(2^N))) where N=depgraph.TxCount().
1053 : : */
1054 : : template<typename SetType>
1055 [ # # ]: 0 : 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
1056 : : {
1057 [ # # # # ]: 0 : Assume(old_linearization.empty() || old_linearization.size() == depgraph.TxCount());
1058 [ # # ]: 0 : if (depgraph.TxCount() == 0) return {{}, true, 0};
1059 : :
1060 : 0 : uint64_t iterations_left = max_iterations;
1061 : 0 : std::vector<DepGraphIndex> linearization;
1062 : :
1063 : 0 : AncestorCandidateFinder anc_finder(depgraph);
1064 : 0 : std::optional<SearchCandidateFinder<SetType>> src_finder;
1065 : 0 : linearization.reserve(depgraph.TxCount());
1066 [ # # ]: 0 : bool optimal = true;
1067 : :
1068 : : // Treat the initialization of SearchCandidateFinder as taking N^2/64 (rounded up) iterations
1069 : : // (largely due to the cost of constructing the internal sorted-by-feerate DepGraph inside
1070 : : // SearchCandidateFinder), a rough approximation based on benchmark. If we don't have that
1071 : : // many, don't start it.
1072 : 0 : uint64_t start_iterations = (uint64_t{depgraph.TxCount()} * depgraph.TxCount() + 63) / 64;
1073 [ # # ]: 0 : if (iterations_left > start_iterations) {
1074 : 0 : iterations_left -= start_iterations;
1075 : 0 : src_finder.emplace(depgraph, rng_seed);
1076 : : }
1077 : :
1078 : : /** Chunking of what remains of the old linearization. */
1079 : 0 : LinearizationChunking old_chunking(depgraph, old_linearization);
1080 : :
1081 : : while (true) {
1082 : : // Find the highest-feerate prefix of the remainder of old_linearization.
1083 [ # # ]: 0 : SetInfo<SetType> best_prefix;
1084 [ # # ]: 0 : if (old_chunking.NumChunksLeft()) best_prefix = old_chunking.GetChunk(0);
1085 : :
1086 : : // Then initialize best to be either the best remaining ancestor set, or the first chunk.
1087 [ # # ]: 0 : auto best = anc_finder.FindCandidateSet();
1088 [ # # # # ]: 0 : if (!best_prefix.feerate.IsEmpty() && best_prefix.feerate >= best.feerate) best = best_prefix;
1089 : :
1090 : 0 : uint64_t iterations_done_now = 0;
1091 [ # # ]: 0 : uint64_t max_iterations_now = 0;
1092 [ # # ]: 0 : if (src_finder) {
1093 : : // Treat the invocation of SearchCandidateFinder::FindCandidateSet() as costing N/4
1094 : : // up-front (rounded up) iterations (largely due to the cost of connected-component
1095 : : // splitting), a rough approximation based on benchmarks.
1096 : 0 : uint64_t base_iterations = (anc_finder.NumRemaining() + 3) / 4;
1097 [ # # ]: 0 : if (iterations_left > base_iterations) {
1098 : : // Invoke bounded search to update best, with up to half of our remaining
1099 : : // iterations as limit.
1100 : 0 : iterations_left -= base_iterations;
1101 : 0 : max_iterations_now = (iterations_left + 1) / 2;
1102 : 0 : std::tie(best, iterations_done_now) = src_finder->FindCandidateSet(max_iterations_now, best);
1103 : 0 : iterations_left -= iterations_done_now;
1104 : : }
1105 : : }
1106 : :
1107 [ # # ]: 0 : if (iterations_done_now == max_iterations_now) {
1108 [ # # ]: 0 : optimal = false;
1109 : : // If the search result is not (guaranteed to be) optimal, run intersections to make
1110 : : // sure we don't pick something that makes us unable to reach further diagram points
1111 : : // of the old linearization.
1112 [ # # ]: 0 : if (old_chunking.NumChunksLeft() > 0) {
1113 : 0 : best = old_chunking.IntersectPrefixes(best);
1114 : : }
1115 : : }
1116 : :
1117 : : // Add to output in topological order.
1118 : 0 : depgraph.AppendTopo(linearization, best.transactions);
1119 : :
1120 : : // Update state to reflect best is no longer to be linearized.
1121 [ # # ]: 0 : anc_finder.MarkDone(best.transactions);
1122 [ # # ]: 0 : if (anc_finder.AllDone()) break;
1123 [ # # ]: 0 : if (src_finder) src_finder->MarkDone(best.transactions);
1124 [ # # ]: 0 : if (old_chunking.NumChunksLeft() > 0) {
1125 : 0 : old_chunking.MarkDone(best.transactions);
1126 : : }
1127 : : }
1128 : :
1129 : 0 : return {std::move(linearization), optimal, max_iterations - iterations_left};
1130 : 0 : }
1131 : :
1132 : : /** Improve a given linearization.
1133 : : *
1134 : : * @param[in] depgraph Dependency graph of the cluster being linearized.
1135 : : * @param[in,out] linearization On input, an existing linearization for depgraph. On output, a
1136 : : * potentially better linearization for the same graph.
1137 : : *
1138 : : * Postlinearization guarantees:
1139 : : * - The resulting chunks are connected.
1140 : : * - If the input has a tree shape (either all transactions have at most one child, or all
1141 : : * transactions have at most one parent), the result is optimal.
1142 : : * - Given a linearization L1 and a leaf transaction T in it. Let L2 be L1 with T moved to the end,
1143 : : * optionally with its fee increased. Let L3 be the postlinearization of L2. L3 will be at least
1144 : : * as good as L1. This means that replacing transactions with same-size higher-fee transactions
1145 : : * will not worsen linearizations through a "drop conflicts, append new transactions,
1146 : : * postlinearize" process.
1147 : : */
1148 : : template<typename SetType>
1149 [ # # ]: 0 : void PostLinearize(const DepGraph<SetType>& depgraph, std::span<DepGraphIndex> linearization)
1150 : : {
1151 : : // This algorithm performs a number of passes (currently 2); the even ones operate from back to
1152 : : // front, the odd ones from front to back. Each results in an equal-or-better linearization
1153 : : // than the one started from.
1154 : : // - One pass in either direction guarantees that the resulting chunks are connected.
1155 : : // - Each direction corresponds to one shape of tree being linearized optimally (forward passes
1156 : : // guarantee this for graphs where each transaction has at most one child; backward passes
1157 : : // guarantee this for graphs where each transaction has at most one parent).
1158 : : // - Starting with a backward pass guarantees the moved-tree property.
1159 : : //
1160 : : // During an odd (forward) pass, the high-level operation is:
1161 : : // - Start with an empty list of groups L=[].
1162 : : // - For every transaction i in the old linearization, from front to back:
1163 : : // - Append a new group C=[i], containing just i, to the back of L.
1164 : : // - While L has at least one group before C, and the group immediately before C has feerate
1165 : : // lower than C:
1166 : : // - If C depends on P:
1167 : : // - Merge P into C, making C the concatenation of P+C, continuing with the combined C.
1168 : : // - Otherwise:
1169 : : // - Swap P with C, continuing with the now-moved C.
1170 : : // - The output linearization is the concatenation of the groups in L.
1171 : : //
1172 : : // During even (backward) passes, i iterates from the back to the front of the existing
1173 : : // linearization, and new groups are prepended instead of appended to the list L. To enable
1174 : : // more code reuse, both passes append groups, but during even passes the meanings of
1175 : : // parent/child, and of high/low feerate are reversed, and the final concatenation is reversed
1176 : : // on output.
1177 : : //
1178 : : // In the implementation below, the groups are represented by singly-linked lists (pointing
1179 : : // from the back to the front), which are themselves organized in a singly-linked circular
1180 : : // list (each group pointing to its predecessor, with a special sentinel group at the front
1181 : : // that points back to the last group).
1182 : : //
1183 : : // Information about transaction t is stored in entries[t + 1], while the sentinel is in
1184 : : // entries[0].
1185 : :
1186 : : /** Index of the sentinel in the entries array below. */
1187 : : static constexpr DepGraphIndex SENTINEL{0};
1188 : : /** Indicator that a group has no previous transaction. */
1189 : : static constexpr DepGraphIndex NO_PREV_TX{0};
1190 : :
1191 : :
1192 : : /** Data structure per transaction entry. */
1193 : 0 : struct TxEntry
1194 : : {
1195 : : /** The index of the previous transaction in this group; NO_PREV_TX if this is the first
1196 : : * entry of a group. */
1197 : : DepGraphIndex prev_tx;
1198 : :
1199 : : // The fields below are only used for transactions that are the last one in a group
1200 : : // (referred to as tail transactions below).
1201 : :
1202 : : /** Index of the first transaction in this group, possibly itself. */
1203 : : DepGraphIndex first_tx;
1204 : : /** Index of the last transaction in the previous group. The first group (the sentinel)
1205 : : * points back to the last group here, making it a singly-linked circular list. */
1206 : : DepGraphIndex prev_group;
1207 : : /** All transactions in the group. Empty for the sentinel. */
1208 : : SetType group;
1209 : : /** All dependencies of the group (descendants in even passes; ancestors in odd ones). */
1210 : : SetType deps;
1211 : : /** The combined fee/size of transactions in the group. Fee is negated in even passes. */
1212 : : FeeFrac feerate;
1213 : : };
1214 : :
1215 : : // As an example, consider the state corresponding to the linearization [1,0,3,2], with
1216 : : // groups [1,0,3] and [2], in an odd pass. The linked lists would be:
1217 : : //
1218 : : // +-----+
1219 : : // 0<-P-- | 0 S | ---\ Legend:
1220 : : // +-----+ |
1221 : : // ^ | - digit in box: entries index
1222 : : // /--------------F---------+ G | (note: one more than tx value)
1223 : : // v \ | | - S: sentinel group
1224 : : // +-----+ +-----+ +-----+ | (empty feerate)
1225 : : // 0<-P-- | 2 | <--P-- | 1 | <--P-- | 4 T | | - T: tail transaction, contains
1226 : : // +-----+ +-----+ +-----+ | fields beyond prev_tv.
1227 : : // ^ | - P: prev_tx reference
1228 : : // G G - F: first_tx reference
1229 : : // | | - G: prev_group reference
1230 : : // +-----+ |
1231 : : // 0<-P-- | 3 T | <--/
1232 : : // +-----+
1233 : : // ^ |
1234 : : // \-F-/
1235 : : //
1236 : : // During an even pass, the diagram above would correspond to linearization [2,3,0,1], with
1237 : : // groups [2] and [3,0,1].
1238 : :
1239 : 0 : std::vector<TxEntry> entries(depgraph.PositionRange() + 1);
1240 : :
1241 : : // Perform two passes over the linearization.
1242 [ # # ]: 0 : for (int pass = 0; pass < 2; ++pass) {
1243 : 0 : int rev = !(pass & 1);
1244 : : // Construct a sentinel group, identifying the start of the list.
1245 : 0 : entries[SENTINEL].prev_group = SENTINEL;
1246 : 0 : Assume(entries[SENTINEL].feerate.IsEmpty());
1247 : :
1248 : : // Iterate over all elements in the existing linearization.
1249 [ # # ]: 0 : for (DepGraphIndex i = 0; i < linearization.size(); ++i) {
1250 : : // Even passes are from back to front; odd passes from front to back.
1251 [ # # ]: 0 : DepGraphIndex idx = linearization[rev ? linearization.size() - 1 - i : i];
1252 : : // Construct a new group containing just idx. In even passes, the meaning of
1253 : : // parent/child and high/low feerate are swapped.
1254 [ # # ]: 0 : DepGraphIndex cur_group = idx + 1;
1255 [ # # ]: 0 : entries[cur_group].group = SetType::Singleton(idx);
1256 [ # # # # ]: 0 : entries[cur_group].deps = rev ? depgraph.Descendants(idx): depgraph.Ancestors(idx);
1257 : 0 : entries[cur_group].feerate = depgraph.FeeRate(idx);
1258 [ # # ]: 0 : if (rev) entries[cur_group].feerate.fee = -entries[cur_group].feerate.fee;
1259 : 0 : entries[cur_group].prev_tx = NO_PREV_TX; // No previous transaction in group.
1260 : 0 : entries[cur_group].first_tx = cur_group; // Transaction itself is first of group.
1261 : : // Insert the new group at the back of the groups linked list.
1262 : 0 : entries[cur_group].prev_group = entries[SENTINEL].prev_group;
1263 : 0 : entries[SENTINEL].prev_group = cur_group;
1264 : :
1265 : : // Start merge/swap cycle.
1266 : 0 : DepGraphIndex next_group = SENTINEL; // We inserted at the end, so next group is sentinel.
1267 : 0 : DepGraphIndex prev_group = entries[cur_group].prev_group;
1268 : : // Continue as long as the current group has higher feerate than the previous one.
1269 [ # # ]: 0 : while (entries[cur_group].feerate >> entries[prev_group].feerate) {
1270 : : // prev_group/cur_group/next_group refer to (the last transactions of) 3
1271 : : // consecutive entries in groups list.
1272 : 0 : Assume(cur_group == entries[next_group].prev_group);
1273 : 0 : Assume(prev_group == entries[cur_group].prev_group);
1274 : : // The sentinel has empty feerate, which is neither higher or lower than other
1275 : : // feerates. Thus, the while loop we are in here guarantees that cur_group and
1276 : : // prev_group are not the sentinel.
1277 : : Assume(cur_group != SENTINEL);
1278 : : Assume(prev_group != SENTINEL);
1279 [ # # ]: 0 : if (entries[cur_group].deps.Overlaps(entries[prev_group].group)) {
1280 : : // There is a dependency between cur_group and prev_group; merge prev_group
1281 : : // into cur_group. The group/deps/feerate fields of prev_group remain unchanged
1282 : : // but become unused.
1283 : 0 : entries[cur_group].group |= entries[prev_group].group;
1284 : 0 : entries[cur_group].deps |= entries[prev_group].deps;
1285 : 0 : entries[cur_group].feerate += entries[prev_group].feerate;
1286 : : // Make the first of the current group point to the tail of the previous group.
1287 : 0 : entries[entries[cur_group].first_tx].prev_tx = prev_group;
1288 : : // The first of the previous group becomes the first of the newly-merged group.
1289 : 0 : entries[cur_group].first_tx = entries[prev_group].first_tx;
1290 : : // The previous group becomes whatever group was before the former one.
1291 : 0 : prev_group = entries[prev_group].prev_group;
1292 : 0 : entries[cur_group].prev_group = prev_group;
1293 : : } else {
1294 : : // There is no dependency between cur_group and prev_group; swap them.
1295 : 0 : DepGraphIndex preprev_group = entries[prev_group].prev_group;
1296 : : // If PP, P, C, N were the old preprev, prev, cur, next groups, then the new
1297 : : // layout becomes [PP, C, P, N]. Update prev_groups to reflect that order.
1298 : 0 : entries[next_group].prev_group = prev_group;
1299 : 0 : entries[prev_group].prev_group = cur_group;
1300 : 0 : entries[cur_group].prev_group = preprev_group;
1301 : : // The current group remains the same, but the groups before/after it have
1302 : : // changed.
1303 : 0 : next_group = prev_group;
1304 : 0 : prev_group = preprev_group;
1305 : : }
1306 : : }
1307 : : }
1308 : :
1309 : : // Convert the entries back to linearization (overwriting the existing one).
1310 : 0 : DepGraphIndex cur_group = entries[0].prev_group;
1311 : 0 : DepGraphIndex done = 0;
1312 [ # # ]: 0 : while (cur_group != SENTINEL) {
1313 : 0 : DepGraphIndex cur_tx = cur_group;
1314 : : // Traverse the transactions of cur_group (from back to front), and write them in the
1315 : : // same order during odd passes, and reversed (front to back) in even passes.
1316 [ # # ]: 0 : if (rev) {
1317 : : do {
1318 [ # # ]: 0 : *(linearization.begin() + (done++)) = cur_tx - 1;
1319 [ # # ]: 0 : cur_tx = entries[cur_tx].prev_tx;
1320 [ # # ]: 0 : } while (cur_tx != NO_PREV_TX);
1321 : : } else {
1322 : : do {
1323 [ # # ]: 0 : *(linearization.end() - (++done)) = cur_tx - 1;
1324 [ # # ]: 0 : cur_tx = entries[cur_tx].prev_tx;
1325 [ # # ]: 0 : } while (cur_tx != NO_PREV_TX);
1326 : : }
1327 : 0 : cur_group = entries[cur_group].prev_group;
1328 : : }
1329 : 0 : Assume(done == linearization.size());
1330 : : }
1331 : 0 : }
1332 : :
1333 : : /** Merge two linearizations for the same cluster into one that is as good as both.
1334 : : *
1335 : : * Complexity: O(N^2) where N=depgraph.TxCount(); O(N) if both inputs are identical.
1336 : : */
1337 : : template<typename SetType>
1338 : : std::vector<DepGraphIndex> MergeLinearizations(const DepGraph<SetType>& depgraph, std::span<const DepGraphIndex> lin1, std::span<const DepGraphIndex> lin2)
1339 : : {
1340 : : Assume(lin1.size() == depgraph.TxCount());
1341 : : Assume(lin2.size() == depgraph.TxCount());
1342 : :
1343 : : /** Chunkings of what remains of both input linearizations. */
1344 : : LinearizationChunking chunking1(depgraph, lin1), chunking2(depgraph, lin2);
1345 : : /** Output linearization. */
1346 : : std::vector<DepGraphIndex> ret;
1347 : : if (depgraph.TxCount() == 0) return ret;
1348 : : ret.reserve(depgraph.TxCount());
1349 : :
1350 : : while (true) {
1351 : : // As long as we are not done, both linearizations must have chunks left.
1352 : : Assume(chunking1.NumChunksLeft() > 0);
1353 : : Assume(chunking2.NumChunksLeft() > 0);
1354 : : // Find the set to output by taking the best remaining chunk, and then intersecting it with
1355 : : // prefixes of remaining chunks of the other linearization.
1356 : : SetInfo<SetType> best;
1357 : : const auto& lin1_firstchunk = chunking1.GetChunk(0);
1358 : : const auto& lin2_firstchunk = chunking2.GetChunk(0);
1359 : : if (lin2_firstchunk.feerate >> lin1_firstchunk.feerate) {
1360 : : best = chunking1.IntersectPrefixes(lin2_firstchunk);
1361 : : } else {
1362 : : best = chunking2.IntersectPrefixes(lin1_firstchunk);
1363 : : }
1364 : : // Append the result to the output and mark it as done.
1365 : : depgraph.AppendTopo(ret, best.transactions);
1366 : : chunking1.MarkDone(best.transactions);
1367 : : if (chunking1.NumChunksLeft() == 0) break;
1368 : : chunking2.MarkDone(best.transactions);
1369 : : }
1370 : :
1371 : : Assume(ret.size() == depgraph.TxCount());
1372 : : return ret;
1373 : : }
1374 : :
1375 : : /** Make linearization topological, retaining its ordering where possible. */
1376 : : template<typename SetType>
1377 : 0 : void FixLinearization(const DepGraph<SetType>& depgraph, std::span<DepGraphIndex> linearization) noexcept
1378 : : {
1379 : : // This algorithm can be summarized as moving every element in the linearization backwards
1380 : : // until it is placed after all its ancestors.
1381 : 0 : SetType done;
1382 : 0 : const auto len = linearization.size();
1383 : : // Iterate over the elements of linearization from back to front (i is distance from back).
1384 [ # # ]: 0 : for (DepGraphIndex i = 0; i < len; ++i) {
1385 : : /** The element at that position. */
1386 : 0 : DepGraphIndex elem = linearization[len - 1 - i];
1387 : : /** j represents how far from the back of the linearization elem should be placed. */
1388 : 0 : DepGraphIndex j = i;
1389 : : // Figure out which elements need to be moved before elem.
1390 : 0 : SetType place_before = done & depgraph.Ancestors(elem);
1391 : : // Find which position to place elem in (updating j), continuously moving the elements
1392 : : // in between forward.
1393 [ # # ]: 0 : while (place_before.Any()) {
1394 : : // j cannot be 0 here; if it was, then there was necessarily nothing earlier which
1395 : : // elem needs to be placed before anymore, and place_before would be empty.
1396 : : Assume(j > 0);
1397 : 0 : auto to_swap = linearization[len - 1 - (j - 1)];
1398 : 0 : place_before.Reset(to_swap);
1399 : 0 : linearization[len - 1 - (j--)] = to_swap;
1400 : : }
1401 : : // Put elem in its final position and mark it as done.
1402 : 0 : linearization[len - 1 - j] = elem;
1403 : 0 : done.Set(elem);
1404 : : }
1405 : 0 : }
1406 : :
1407 : : } // namespace cluster_linearize
1408 : :
1409 : : #endif // BITCOIN_CLUSTER_LINEARIZE_H
|
