1 // Copyright (c) The Limenka 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 LIMENKA_UTIL_FEEFRAC_H
6 #define LIMENKA_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 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 int64_t low = int64_t{static_cast<uint32_t>(a)} * b;
48 int64_t high = (a >> 32) * b;
49 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 static inline __int128 Mul(int64_t a, int32_t b) noexcept
55 {
56 // If __int128 is available, use 128-bit wide multiply.
57 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 constexpr inline FeeFrac() noexcept : fee{0}, size{0} {}
68 69 /** Construct a FeeFrac with specified fee and size. */
70 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 bool inline IsEmpty() const noexcept {
77 return size == 0;
78 }
79 80 /** Add fee and size of another FeeFrac to this one. */
81 void inline operator+=(const FeeFrac& other) noexcept
82 {
83 fee += other.fee;
84 size += other.size;
85 }
86 87 /** Subtract fee and size of another FeeFrac from this one. */
88 void inline operator-=(const FeeFrac& other) noexcept
89 {
90 fee -= other.fee;
91 size -= other.size;
92 }
93 94 /** Sum fee and size. */
95 friend inline FeeFrac operator+(const FeeFrac& a, const FeeFrac& b) noexcept
96 {
97 return {a.fee + b.fee, a.size + b.size};
98 }
99 100 /** Subtract both fee and size. */
101 friend inline FeeFrac operator-(const FeeFrac& a, const FeeFrac& b) noexcept
102 {
103 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 friend inline bool operator==(const FeeFrac& a, const FeeFrac& b) noexcept
108 {
109 return a.fee == b.fee && a.size == b.size;
110 }
111 112 /** Compare two FeeFracs just by feerate. */
113 friend inline std::weak_ordering FeeRateCompare(const FeeFrac& a, const FeeFrac& b) noexcept
114 {
115 auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
116 return cross_a <=> cross_b;
117 }
118 119 /** Check if a FeeFrac object has strictly lower feerate than another. */
120 friend inline bool operator<<(const FeeFrac& a, const FeeFrac& b) noexcept
121 {
122 auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
123 return cross_a < cross_b;
124 }
125 126 /** Check if a FeeFrac object has strictly higher feerate than another. */
127 friend inline bool operator>>(const FeeFrac& a, const FeeFrac& b) noexcept
128 {
129 auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
130 return cross_a > cross_b;
131 }
132 133 /** Compare two FeeFracs. <, >, <=, and >= are auto-generated from this. */
134 friend inline std::strong_ordering operator<=>(const FeeFrac& a, const FeeFrac& b) noexcept
135 {
136 auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
137 if (cross_a == cross_b) return b.size <=> a.size;
138 return cross_a <=> cross_b;
139 }
140 141 /** Swap two FeeFracs. */
142 friend inline void swap(FeeFrac& a, FeeFrac& b) noexcept
143 {
144 std::swap(a.fee, b.fee);
145 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 // LIMENKA_UTIL_FEEFRAC_H
160