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_UTIL_FEEFRAC_H
6 : : #define BITCOIN_UTIL_FEEFRAC_H
7 : :
8 : : #include <stdint.h>
9 : : #include <compare>
10 : : #include <vector>
11 : : #include <span.h>
12 : : #include <util/check.h>
13 : :
14 : : /** Data structure storing a fee and size, ordered by increasing fee/size.
15 : : *
16 : : * The size of a FeeFrac cannot be zero unless the fee is also zero.
17 : : *
18 : : * FeeFracs have a total ordering, first by increasing feerate (ratio of fee over size), and then
19 : : * by decreasing size. The empty FeeFrac (fee and size both 0) sorts last. So for example, the
20 : : * following FeeFracs are in sorted order:
21 : : *
22 : : * - fee=0 size=1 (feerate 0)
23 : : * - fee=1 size=2 (feerate 0.5)
24 : : * - fee=2 size=3 (feerate 0.667...)
25 : : * - fee=2 size=2 (feerate 1)
26 : : * - fee=1 size=1 (feerate 1)
27 : : * - fee=3 size=2 (feerate 1.5)
28 : : * - fee=2 size=1 (feerate 2)
29 : : * - fee=0 size=0 (undefined feerate)
30 : : *
31 : : * A FeeFrac is considered "better" if it sorts after another, by this ordering. All standard
32 : : * comparison operators (<=>, ==, !=, >, <, >=, <=) respect this ordering.
33 : : *
34 : : * The FeeRateCompare, and >> and << operators only compare feerate and treat equal feerate but
35 : : * different size as equivalent. The empty FeeFrac is neither lower or higher in feerate than any
36 : : * other.
37 : : */
38 : : struct FeeFrac
39 : : {
40 : : /** Fallback version for Mul (see below).
41 : : *
42 : : * Separate to permit testing on platforms where it isn't actually needed.
43 : : */
44 : 43 : static inline std::pair<int64_t, uint32_t> MulFallback(int64_t a, int32_t b) noexcept
45 : : {
46 : : // Otherwise, emulate 96-bit multiplication using two 64-bit multiplies.
47 : 43 : int64_t low = int64_t{static_cast<uint32_t>(a)} * b;
48 : 43 : int64_t high = (a >> 32) * b;
49 [ - + ]: 43 : return {high + (low >> 32), static_cast<uint32_t>(low)};
50 : : }
51 : :
52 : : // Compute a * b, returning an unspecified but totally ordered type.
53 : : #ifdef __SIZEOF_INT128__
54 : 166231629 : static inline __int128 Mul(int64_t a, int32_t b) noexcept
55 : : {
56 : : // If __int128 is available, use 128-bit wide multiply.
57 [ + + ]: 166121699 : return __int128{a} * b;
58 : : }
59 : : #else
60 : : static constexpr auto Mul = MulFallback;
61 : : #endif
62 : :
63 : : int64_t fee;
64 : : int32_t size;
65 : :
66 : : /** Construct an IsEmpty() FeeFrac. */
67 : 245362 : constexpr inline FeeFrac() noexcept : fee{0}, size{0} {}
68 : :
69 : : /** Construct a FeeFrac with specified fee and size. */
70 [ + + ]: 133851905 : constexpr inline FeeFrac(int64_t f, int32_t s) noexcept : fee{f}, size{s} {}
[ + + + + ]
71 : :
72 : : constexpr inline FeeFrac(const FeeFrac&) noexcept = default;
73 : : constexpr inline FeeFrac& operator=(const FeeFrac&) noexcept = default;
74 : :
75 : : /** Check if this is empty (size and fee are 0). */
76 : 1505086 : bool inline IsEmpty() const noexcept {
77 [ + + + - : 1505086 : return size == 0;
+ + + + +
+ + + + +
+ + + + +
+ ]
78 : : }
79 : :
80 : : /** Add fee and size of another FeeFrac to this one. */
81 : 86909675 : void inline operator+=(const FeeFrac& other) noexcept
82 : : {
83 : 86909675 : fee += other.fee;
84 [ + + + + ]: 86259925 : size += other.size;
85 : : }
86 : :
87 : : /** Subtract fee and size of another FeeFrac from this one. */
88 : 65852 : void inline operator-=(const FeeFrac& other) noexcept
89 : : {
90 : 65852 : fee -= other.fee;
91 : 65852 : size -= other.size;
92 : : }
93 : :
94 : : /** Sum fee and size. */
95 : 577432 : friend inline FeeFrac operator+(const FeeFrac& a, const FeeFrac& b) noexcept
96 : : {
97 [ + - ]: 577432 : return {a.fee + b.fee, a.size + b.size};
98 : : }
99 : :
100 : : /** Subtract both fee and size. */
101 : 219318 : friend inline FeeFrac operator-(const FeeFrac& a, const FeeFrac& b) noexcept
102 : : {
103 [ + + ]: 219318 : return {a.fee - b.fee, a.size - b.size};
104 : : }
105 : :
106 : : /** Check if two FeeFrac objects are equal (both same fee and same size). */
107 : 66679092 : friend inline bool operator==(const FeeFrac& a, const FeeFrac& b) noexcept
108 : : {
109 [ + + + - : 66678993 : return a.fee == b.fee && a.size == b.size;
+ + + + ]
[ + - + -
+ - + - +
- - + + -
- + + - +
- + - - +
+ - - + +
- - + + -
- + + - -
+ + - + -
+ - + - +
- - + + -
+ - ][ + +
+ + # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
110 : : }
111 : :
112 : : /** Compare two FeeFracs just by feerate. */
113 : 109887 : friend inline std::weak_ordering FeeRateCompare(const FeeFrac& a, const FeeFrac& b) noexcept
114 : : {
115 : 109887 : auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
116 [ + + + + ]: 109887 : return cross_a <=> cross_b;
117 : : }
118 : :
119 : : /** Check if a FeeFrac object has strictly lower feerate than another. */
120 : 170147 : friend inline bool operator<<(const FeeFrac& a, const FeeFrac& b) noexcept
121 : : {
122 : 170147 : auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
123 [ + + ]: 170147 : return cross_a < cross_b;
[ - + - + ]
124 : : }
125 : :
126 : : /** Check if a FeeFrac object has strictly higher feerate than another. */
127 : 1300660 : friend inline bool operator>>(const FeeFrac& a, const FeeFrac& b) noexcept
128 : : {
129 : 1300660 : auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
130 [ + + + + : 1300660 : return cross_a > cross_b;
+ + + + +
+ + + + +
- + - + +
+ ][ + + #
# # # # #
# # # # #
# # # # #
# # ]
131 : : }
132 : :
133 : : /** Compare two FeeFracs. <, >, <=, and >= are auto-generated from this. */
134 : 164650935 : friend inline std::strong_ordering operator<=>(const FeeFrac& a, const FeeFrac& b) noexcept
135 : : {
136 : 164650935 : auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
137 [ + + + + : 164650935 : if (cross_a == cross_b) return b.size <=> a.size;
+ + ]
138 [ + + ]: 75730669 : return cross_a <=> cross_b;
139 : : }
140 : :
141 : : /** Swap two FeeFracs. */
142 : 1109402 : friend inline void swap(FeeFrac& a, FeeFrac& b) noexcept
143 : : {
144 : 130940 : std::swap(a.fee, b.fee);
145 : 130940 : std::swap(a.size, b.size);
146 : : }
147 : : };
148 : :
149 : : /** Compare the feerate diagrams implied by the provided sorted chunks data.
150 : : *
151 : : * The implied diagram for each starts at (0, 0), then contains for each chunk the cumulative fee
152 : : * and size up to that chunk, and then extends infinitely to the right with a horizontal line.
153 : : *
154 : : * The caller must guarantee that the sum of the FeeFracs in either of the chunks' data set do not
155 : : * overflow (so sum fees < 2^63, and sum sizes < 2^31).
156 : : */
157 : : std::partial_ordering CompareChunks(Span<const FeeFrac> chunks0, Span<const FeeFrac> chunks1);
158 : :
159 : : #endif // BITCOIN_UTIL_FEEFRAC_H
|
