Bitcoin Core  27.99.0
P2P Digital Currency
feefrac.h
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 #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 
38 struct FeeFrac
39 {
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 
67  inline FeeFrac() noexcept : fee{0}, size{0} {}
68 
70  inline FeeFrac(int64_t f, int32_t s) noexcept : fee{f}, size{s} {}
71 
72  inline FeeFrac(const FeeFrac&) noexcept = default;
73  inline FeeFrac& operator=(const FeeFrac&) noexcept = default;
74 
76  bool inline IsEmpty() const noexcept {
77  return size == 0;
78  }
79 
81  void inline operator+=(const FeeFrac& other) noexcept
82  {
83  fee += other.fee;
84  size += other.size;
85  }
86 
88  void inline operator-=(const FeeFrac& other) noexcept
89  {
90  fee -= other.fee;
91  size -= other.size;
92  }
93 
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 
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 
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 
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 
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 
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 
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 
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 
150 std::vector<FeeFrac> BuildDiagramFromChunks(Span<const FeeFrac> chunks);
151 
158 std::partial_ordering CompareFeerateDiagram(Span<const FeeFrac> dia0, Span<const FeeFrac> dia1);
159 
160 #endif // BITCOIN_UTIL_FEEFRAC_H
A Span is an object that can refer to a contiguous sequence of objects.
Definition: span.h:98
std::partial_ordering CompareFeerateDiagram(Span< const FeeFrac > dia0, Span< const FeeFrac > dia1)
Compares two feerate diagrams.
Definition: feefrac.cpp:22
std::vector< FeeFrac > BuildDiagramFromChunks(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
Data structure storing a fee and size, ordered by increasing fee/size.
Definition: feefrac.h:39
friend std::weak_ordering FeeRateCompare(const FeeFrac &a, const FeeFrac &b) noexcept
Compare two FeeFracs just by feerate.
Definition: feefrac.h:113
friend FeeFrac operator-(const FeeFrac &a, const FeeFrac &b) noexcept
Subtract both fee and size.
Definition: feefrac.h:101
friend bool operator>>(const FeeFrac &a, const FeeFrac &b) noexcept
Check if a FeeFrac object has strictly higher feerate than another.
Definition: feefrac.h:127
friend void swap(FeeFrac &a, FeeFrac &b) noexcept
Swap two FeeFracs.
Definition: feefrac.h:142
FeeFrac(const FeeFrac &) noexcept=default
int64_t fee
Definition: feefrac.h:63
friend std::strong_ordering operator<=>(const FeeFrac &a, const FeeFrac &b) noexcept
Compare two FeeFracs.
Definition: feefrac.h:134
FeeFrac & operator=(const FeeFrac &) noexcept=default
static constexpr auto Mul
Definition: feefrac.h:60
friend bool operator<<(const FeeFrac &a, const FeeFrac &b) noexcept
Check if a FeeFrac object has strictly lower feerate than another.
Definition: feefrac.h:120
FeeFrac() noexcept
Construct an IsEmpty() FeeFrac.
Definition: feefrac.h:67
void operator-=(const FeeFrac &other) noexcept
Subtract fee and size of another FeeFrac from this one.
Definition: feefrac.h:88
int32_t size
Definition: feefrac.h:64
FeeFrac(int64_t f, int32_t s) noexcept
Construct a FeeFrac with specified fee and size.
Definition: feefrac.h:70
static std::pair< int64_t, uint32_t > MulFallback(int64_t a, int32_t b) noexcept
Fallback version for Mul (see below).
Definition: feefrac.h:44
void operator+=(const FeeFrac &other) noexcept
Add fee and size of another FeeFrac to this one.
Definition: feefrac.h:81
bool IsEmpty() const noexcept
Check if this is empty (size and fee are 0).
Definition: feefrac.h:76
friend FeeFrac operator+(const FeeFrac &a, const FeeFrac &b) noexcept
Sum fee and size.
Definition: feefrac.h:95
friend bool operator==(const FeeFrac &a, const FeeFrac &b) noexcept
Check if two FeeFrac objects are equal (both same fee and same size).
Definition: feefrac.h:107