Bitcoin Core  27.99.0
P2P Digital Currency
feefrac.cpp
Go to the documentation of this file.
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 #include <util/feefrac.h>
6 #include <algorithm>
7 #include <array>
8 #include <vector>
9 
10 std::vector<FeeFrac> BuildDiagramFromChunks(const Span<const FeeFrac> chunks)
11 {
12  std::vector<FeeFrac> diagram;
13  diagram.reserve(chunks.size() + 1);
14 
15  diagram.emplace_back(0, 0);
16  for (auto& chunk : chunks) {
17  diagram.emplace_back(diagram.back() + chunk);
18  }
19  return diagram;
20 }
21 
23 {
25  const std::array<Span<const FeeFrac>, 2> dias = {dia0, dia1};
27  size_t next_index[2] = {1, 1};
29  bool better_somewhere[2] = {false, false};
31  const auto next_point = [&](int dia) { return dias[dia][next_index[dia]]; };
33  const auto prev_point = [&](int dia) { return dias[dia][next_index[dia] - 1]; };
34 
35  // Diagrams should be non-empty, and first elements zero in size and fee
36  Assert(!dia0.empty() && !dia1.empty());
37  Assert(prev_point(0).IsEmpty());
38  Assert(prev_point(1).IsEmpty());
39 
40  do {
41  bool done_0 = next_index[0] == dias[0].size();
42  bool done_1 = next_index[1] == dias[1].size();
43  if (done_0 && done_1) break;
44 
45  // Determine which diagram has the first unprocessed point. If a single side is finished, use the
46  // other one. Only up to one can be done due to check above.
47  const int unproc_side = (done_0 || done_1) ? done_0 : next_point(0).size > next_point(1).size;
48 
49  // Let `P` be the next point on diagram unproc_side, and `A` and `B` the previous and next points
50  // on the other diagram. We want to know if P lies above or below the line AB. To determine this, we
51  // compute the slopes of line AB and of line AP, and compare them. These slopes are fee per size,
52  // and can thus be expressed as FeeFracs.
53  const FeeFrac& point_p = next_point(unproc_side);
54  const FeeFrac& point_a = prev_point(!unproc_side);
55 
56  const auto slope_ap = point_p - point_a;
57  Assume(slope_ap.size > 0);
58  std::weak_ordering cmp = std::weak_ordering::equivalent;
59  if (done_0 || done_1) {
60  // If a single side has no points left, act as if AB has slope tail_feerate(of 0).
61  Assume(!(done_0 && done_1));
62  cmp = FeeRateCompare(slope_ap, FeeFrac(0, 1));
63  } else {
64  // If both sides have points left, compute B, and the slope of AB explicitly.
65  const FeeFrac& point_b = next_point(!unproc_side);
66  const auto slope_ab = point_b - point_a;
67  Assume(slope_ab.size >= slope_ap.size);
68  cmp = FeeRateCompare(slope_ap, slope_ab);
69 
70  // If B and P have the same size, B can be marked as processed (in addition to P, see
71  // below), as we've already performed a comparison at this size.
72  if (point_b.size == point_p.size) ++next_index[!unproc_side];
73  }
74  // If P lies above AB, unproc_side is better in P. If P lies below AB, then !unproc_side is
75  // better in P.
76  if (std::is_gt(cmp)) better_somewhere[unproc_side] = true;
77  if (std::is_lt(cmp)) better_somewhere[!unproc_side] = true;
78  ++next_index[unproc_side];
79 
80  // If both diagrams are better somewhere, they are incomparable.
81  if (better_somewhere[0] && better_somewhere[1]) return std::partial_ordering::unordered;
82 
83  } while(true);
84 
85  // Otherwise compare the better_somewhere values.
86  return better_somewhere[0] <=> better_somewhere[1];
87 }
#define Assert(val)
Identity function.
Definition: check.h:77
#define Assume(val)
Assume is the identity function.
Definition: check.h:89
A Span is an object that can refer to a contiguous sequence of objects.
Definition: span.h:98
constexpr std::size_t size() const noexcept
Definition: span.h:187
constexpr bool empty() const noexcept
Definition: span.h:189
Data structure storing a fee and size, ordered by increasing fee/size.
Definition: feefrac.h:39
int32_t size
Definition: feefrac.h:64
std::partial_ordering CompareFeerateDiagram(Span< const FeeFrac > dia0, Span< const FeeFrac > dia1)
Compares two feerate diagrams.
Definition: feefrac.cpp:22
std::vector< FeeFrac > BuildDiagramFromChunks(const Span< const FeeFrac > chunks)
Takes the pre-computed and topologically-valid chunks and generates a fee diagram which starts at Fee...
Definition: feefrac.cpp:10