1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
|
// Copyright (c) The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
#ifndef BITCOIN_CLUSTER_LINEARIZE_H
#define BITCOIN_CLUSTER_LINEARIZE_H
#include <stdint.h>
#include <vector>
#include <utility>
#include <util/feefrac.h>
namespace cluster_linearize {
/** Data type to represent cluster input.
*
* cluster[i].first is tx_i's fee and size.
* cluster[i].second[j] is true iff tx_i spends one or more of tx_j's outputs.
*/
template<typename SetType>
using Cluster = std::vector<std::pair<FeeFrac, SetType>>;
/** Data type to represent transaction indices in clusters. */
using ClusterIndex = uint32_t;
/** Data structure that holds a transaction graph's preprocessed data (fee, size, ancestors,
* descendants). */
template<typename SetType>
class DepGraph
{
/** Information about a single transaction. */
struct Entry
{
/** Fee and size of transaction itself. */
FeeFrac feerate;
/** All ancestors of the transaction (including itself). */
SetType ancestors;
/** All descendants of the transaction (including itself). */
SetType descendants;
/** Equality operator (primarily for for testing purposes). */
friend bool operator==(const Entry&, const Entry&) noexcept = default;
/** Construct an empty entry. */
Entry() noexcept = default;
/** Construct an entry with a given feerate, ancestor set, descendant set. */
Entry(const FeeFrac& f, const SetType& a, const SetType& d) noexcept : feerate(f), ancestors(a), descendants(d) {}
};
/** Data for each transaction, in the same order as the Cluster it was constructed from. */
std::vector<Entry> entries;
public:
/** Equality operator (primarily for testing purposes). */
friend bool operator==(const DepGraph&, const DepGraph&) noexcept = default;
// Default constructors.
DepGraph() noexcept = default;
DepGraph(const DepGraph&) noexcept = default;
DepGraph(DepGraph&&) noexcept = default;
DepGraph& operator=(const DepGraph&) noexcept = default;
DepGraph& operator=(DepGraph&&) noexcept = default;
/** Construct a DepGraph object for ntx transactions, with no dependencies.
*
* Complexity: O(N) where N=ntx.
**/
explicit DepGraph(ClusterIndex ntx) noexcept
{
Assume(ntx <= SetType::Size());
entries.resize(ntx);
for (ClusterIndex i = 0; i < ntx; ++i) {
entries[i].ancestors = SetType::Singleton(i);
entries[i].descendants = SetType::Singleton(i);
}
}
/** Construct a DepGraph object given a cluster.
*
* Complexity: O(N^2) where N=cluster.size().
*/
explicit DepGraph(const Cluster<SetType>& cluster) noexcept : entries(cluster.size())
{
for (ClusterIndex i = 0; i < cluster.size(); ++i) {
// Fill in fee and size.
entries[i].feerate = cluster[i].first;
// Fill in direct parents as ancestors.
entries[i].ancestors = cluster[i].second;
// Make sure transactions are ancestors of themselves.
entries[i].ancestors.Set(i);
}
// Propagate ancestor information.
for (ClusterIndex i = 0; i < entries.size(); ++i) {
// At this point, entries[a].ancestors[b] is true iff b is an ancestor of a and there
// is a path from a to b through the subgraph consisting of {a, b} union
// {0, 1, ..., (i-1)}.
SetType to_merge = entries[i].ancestors;
for (ClusterIndex j = 0; j < entries.size(); ++j) {
if (entries[j].ancestors[i]) {
entries[j].ancestors |= to_merge;
}
}
}
// Fill in descendant information by transposing the ancestor information.
for (ClusterIndex i = 0; i < entries.size(); ++i) {
for (auto j : entries[i].ancestors) {
entries[j].descendants.Set(i);
}
}
}
/** Get the number of transactions in the graph. Complexity: O(1). */
auto TxCount() const noexcept { return entries.size(); }
/** Get the feerate of a given transaction i. Complexity: O(1). */
const FeeFrac& FeeRate(ClusterIndex i) const noexcept { return entries[i].feerate; }
/** Get the ancestors of a given transaction i. Complexity: O(1). */
const SetType& Ancestors(ClusterIndex i) const noexcept { return entries[i].ancestors; }
/** Get the descendants of a given transaction i. Complexity: O(1). */
const SetType& Descendants(ClusterIndex i) const noexcept { return entries[i].descendants; }
/** Add a new unconnected transaction to this transaction graph (at the end), and return its
* ClusterIndex.
*
* Complexity: O(1) (amortized, due to resizing of backing vector).
*/
ClusterIndex AddTransaction(const FeeFrac& feefrac) noexcept
{
Assume(TxCount() < SetType::Size());
ClusterIndex new_idx = TxCount();
entries.emplace_back(feefrac, SetType::Singleton(new_idx), SetType::Singleton(new_idx));
return new_idx;
}
/** Modify this transaction graph, adding a dependency between a specified parent and child.
*
* Complexity: O(N) where N=TxCount().
**/
void AddDependency(ClusterIndex parent, ClusterIndex child) noexcept
{
// Bail out if dependency is already implied.
if (entries[child].ancestors[parent]) return;
// To each ancestor of the parent, add as descendants the descendants of the child.
const auto& chl_des = entries[child].descendants;
for (auto anc_of_par : Ancestors(parent)) {
entries[anc_of_par].descendants |= chl_des;
}
// To each descendant of the child, add as ancestors the ancestors of the parent.
const auto& par_anc = entries[parent].ancestors;
for (auto dec_of_chl : Descendants(child)) {
entries[dec_of_chl].ancestors |= par_anc;
}
}
/** Compute the aggregate feerate of a set of nodes in this graph.
*
* Complexity: O(N) where N=elems.Count().
**/
FeeFrac FeeRate(const SetType& elems) const noexcept
{
FeeFrac ret;
for (auto pos : elems) ret += entries[pos].feerate;
return ret;
}
};
} // namespace cluster_linearize
#endif // BITCOIN_CLUSTER_LINEARIZE_H
|
