aboutsummaryrefslogtreecommitdiff
path: root/src/wallet/coinselection.cpp
AgeCommit message (Collapse)Author
2023-09-13Amend bumpfee for inputs with overlapping ancestryMurch
At the end of coin selection reduce the fees by the difference between the individual bump fee estimates and the collective bump fee estimate.
2023-09-13Bump unconfirmed parent txs to target feerateMurch
When a transaction uses an unconfirmed input, preceding this commit it would not consider the feerate of the parent transaction. Given a parent transaction with a lower ancestor feerate, this resulted in the new transaction's ancestor feerate undershooting the target feerate. This commit changes how we calculate the effective value of unconfirmed UTXOs. The effective value of unconfirmed UTXOs is decreased by the fee necessary to bump its ancestry to the target feerate. This also impacts the calculation of the waste metric: since the estimate for the current fee is increased by the bump fees, unconfirmed UTXOs current fees appear less favorable compared to their unchanged long term fees. This has one caveat: if multiple UTXOs have overlapping ancestries, each of their individual estimates will account for bumping all ancestors.
2023-09-13coinselection: Move GetSelectionWaste into SelectionResultAndrew Chow
GetSelectionWaste will need to access more context within a selection result, and so should be a private member function rather than a static function. It's only use outside of SelectionResult was for tests which have now been updated to just make a SelectionResult. Co-authored-by: Murch <murch@murch.one>
2023-06-21[bug] Increase SRD target by change_feeMurch
I discovered via fuzzing of another coin selection approach that at extremely high feerates SRD may find input sets that lead to transactions without change outputs. This is an unintended outcome since SRD is meant to always produce a transaction with a change output—we use other algorithms to specifically search for changeless solutions. The issue occures when the flat allowance of 50,000 ṩ for change is insufficient to pay for the creation of a change output with a non-dust amount, at and above 1,613 ṩ/vB. Increasing the change budget by change_fees makes SRD behave as expected at any feerates.
2023-05-20refactor: Move system from util to common libraryTheCharlatan
Since the kernel library no longer depends on the system file, move it to the common library instead in accordance to the diagram in doc/design/libraries.md.
2023-04-21Merge bitcoin/bitcoin#27419: move-only: Extract common/args from util/systemfanquake
be55f545d53d44fdcf2d8ae802e9eae551d120c6 move-only: Extract common/args and common/config.cpp from util/system (TheCharlatan) Pull request description: This pull request is part of the `libbitcoinkernel` project https://github.com/bitcoin/bitcoin/issues/24303 https://github.com/bitcoin/bitcoin/projects/18 and more specifically its "Step 2: Decouple most non-consensus code from libbitcoinkernel". It is part of a series of patches splitting up the `util/system` files. Its preceding pull request is https://github.com/bitcoin/bitcoin/pull/27254. The pull request contains an extraction of ArgsManager related functions from util/system into their own common/ file. The background of this commit is an ongoing effort to decouple the libbitcoinkernel library from the ArgsManager. The ArgsManager belongs into the common library, since the kernel library should not depend on it. See [doc/design/libraries.md](https://github.com/bitcoin/bitcoin/blob/master/doc/design/libraries.md) for more information on this rationale. ACKs for top commit: MarcoFalke: re-ACK be55f545d53d44fdcf2d8ae802e9eae551d120c6 🚲 ryanofsky: Code review ACK be55f545d53d44fdcf2d8ae802e9eae551d120c6. Just small cleanups since the last review. hebasto: ACK be55f545d53d44fdcf2d8ae802e9eae551d120c6, I have reviewed the code and it looks OK, I agree it can be merged. Tree-SHA512: 90eb03334af0155b823030b4f2ecf286d35058d700ee2ddbbaa445be19e31eb0fe982656f35bd14ecee3ad2c3d0db3746855cb8f3777eff7253713e42873e111
2023-04-20Merge bitcoin/bitcoin#26720: wallet: coin selection, don't return results ↵Andrew Chow
that exceed the max allowed weight 25ab14712b9d80276016f9fc9bff7fb9c1d09635 refactor: coinselector_tests, unify wallet creation code (furszy) ba9431c505e1590db6103b9632134985cd4704dc test: coverage for bnb max weight (furszy) 5a2bc45ee0b123e461c5191322ed0b43524c3d82 wallet: clean post coin selection max weight filter (furszy) 2d112584e384de10021c64e4700455d71326824e coin selection: BnB, don't return selection if exceeds max allowed tx weight (furszy) d3a1c098e4b5df2ebbae20c6e390c3d783950e93 test: coin selection, add coverage for SRD (furszy) 9d9689e5a657956db8a30829c994600ec7d3098b coin selection: heap-ify SRD, don't return selection if exceeds max tx weight (furszy) 6107ec2229c5f5b4e944a6b10d38010c850094ac coin selection: knapsack, select closest UTXO above target if result exceeds max tx size (furszy) 1284223691127e76135a46d251c52416104f0ff1 wallet: refactor coin selection algos to return util::Result (furszy) Pull request description: Coming from the following comment https://github.com/bitcoin/bitcoin/pull/25729#discussion_r1029324367. The reason why we are adding hundreds of UTXO from different sources when the target amount is covered only by one of them is because only SRD returns a usable result. Context: In the test, we create 1515 UTXOs with 0.033 BTC each, and 1 UTXO with 50 BTC. Then perform Coin Selection to fund 49.5 BTC. As the selection of the 1515 small UTXOs exceeds the max allowed tx size, the expectation here is to receive a selection result that only contain the big UTXO. Which is not happening for the following reason: Knapsack returns a result that exceeds the max allowed transaction size, when it should return the closest utxo above the target, so we fallback to SRD who selects coins randomly up until the target is met. So we end up with a selection result with lot more coins than what is needed. ACKs for top commit: S3RK: ACK 25ab14712b9d80276016f9fc9bff7fb9c1d09635 achow101: ACK 25ab14712b9d80276016f9fc9bff7fb9c1d09635 Xekyo: reACK 25ab14712b9d80276016f9fc9bff7fb9c1d09635 theStack: Code-review ACK 25ab14712b9d80276016f9fc9bff7fb9c1d09635 Tree-SHA512: 2425de4cc479b4db999b3b2e02eb522a2130a06379cca0418672a51c4076971a1d427191173820db76a0f85a8edfff100114e1c38fb3b5dc51598d07cabe1a60
2023-04-19move-only: Extract common/args and common/config.cpp from util/systemTheCharlatan
This is an extraction of ArgsManager related functions from util/system into their own common file. Config file related functions are moved to common/config.cpp. The background of this commit is an ongoing effort to decouple the libbitcoinkernel library from the ArgsManager. The ArgsManager belongs into the common library, since the kernel library should not depend on it. See doc/design/libraries.md for more information on this rationale.
2023-04-05coin selection: BnB, don't return selection if exceeds max allowed tx weightfurszy
2023-04-05coin selection: heap-ify SRD, don't return selection if exceeds max tx weightfurszy
Uses a min-effective-value heap, so we can remove the least valuable input/s while the selected weight exceeds the maximum allowed weight. Co-authored-by: Murch <murch@murch.one>
2023-04-05coin selection: knapsack, select closest UTXO above target if result exceeds ↵furszy
max tx size The simplest scenario where this is useful is on the 'check_max_weight' unit test already: We create 1515 UTXOs with 0.033 BTC each, and 1 UTXO with 50 BTC. Then perform Coin Selection. As the selection of the 1515 small UTXOs exceeds the max allowed tx size, the expectation here is to receive a selection result that only contain the big UTXO (which is not happening for the reasons stated below). As knapsack returns a result that exceeds the max allowed transaction size, we fallback to SRD, which selects coins randomly up until the target is met. So we end up with a selection result with lot more coins than what is needed.
2023-03-08wallet: remove unused methodsfurszy
CWallet::DummySignTx, OutputGroupTypeMap::find
2023-03-07wallet: refactor coin selection algos to return util::Resultfurszy
so the selection processes can retrieve different errors and not uninformative std::nullopt
2023-03-06wallet: unify outputs grouping processfurszy
The 'GroupOutputs()' function performs the same calculations for only-positive and mixed groups, the only difference is that when we look for only-positive groups, we discard negative utxos. So, instead of wasting resources calling GroupOutputs() for positive-only first, then call it again to include the negative ones in the result, we can execute GroupOutputs() only once, including in the response both group types (positive-only and mixed).
2023-03-06refactor: make OutputGroup::m_outputs field a vector of shared_ptrfurszy
Initial steps towards sharing COutput instances across all possible OutputGroups (instead of copying them time after time).
2023-03-03wallet: make OutputGroup "positive_only" filter explicitfurszy
And not hide it inside the `OutputGroup::Insert` method. This method does not return anything if insertion fails. We can know before calling `Insert` whether the coin will be accepted or not.
2023-01-03Merge bitcoin/bitcoin#26661: wallet: Coin Selection, return accurate error ↵Andrew Chow
messages 76dc547ee7b05864e7b1b6c55fc0301d47aa3a15 gui: create tx, launch error dialog if backend throws runtime_error (furszy) f4d79477ff0946b0bd340ade9251fa38e3b95dd7 wallet: coin selection, add duplicated inputs checks (furszy) 0aa065b14e67592d5be8f46ebbe5d59a083ff0a5 wallet: return accurate error messages from Coin Selection (furszy) 7e8340ab1a970a14e180b1fcf420b46a5657b062 wallet: make SelectCoins flow return util::Result (furszy) e5e147fe97f706e82bc51358f8bdc355f355be57 wallet: refactor eight consecutive 'AttemptSelection' calls into a loop (furszy) Pull request description: Work decoupled from #25806, which cleanup and improves the Coin Selection flow further. Adding the capability to propagate specific error messages from the Coin Selection process to the user. Instead of always returning the general "Insufficient funds" message which is not always accurate to what happened internally. Letting us instruct the user how to proceed under certain circumstances. The following error messages were added: 1) If the selection result exceeds the maximum transaction weight, we now will return: -> "The inputs size exceeds the maximum weight. Please try sending a smaller amount or manually consolidating your wallet's UTXOs". 2) If the user pre-selected inputs and disallowed the automatic coin selection process (no other inputs are allowed), we now will return: -> "The preselected coins total amount does not cover the transaction target. Please allow other inputs to be automatically selected or include more coins manually". 3) The double-counted preset inputs during Coin Selection error will now throw an "internal bug detected" message instead of crashing the node. The essence of this work comes from several comments: 1. https://github.com/bitcoin/bitcoin/pull/26560#discussion_r1037395665 2. https://github.com/bitcoin/bitcoin/pull/25729#discussion_r940619491 3. https://github.com/bitcoin/bitcoin/pull/25269#pullrequestreview-1135240825 4. https://github.com/bitcoin/bitcoin/issues/23144 (which is connected to #24845) ACKs for top commit: ishaanam: crACK 76dc547ee7b05864e7b1b6c55fc0301d47aa3a15 achow101: ACK 76dc547ee7b05864e7b1b6c55fc0301d47aa3a15 aureleoules: ACK 76dc547ee7b05864e7b1b6c55fc0301d47aa3a15 theStack: ACK 76dc547ee7b05864e7b1b6c55fc0301d47aa3a15 :city_sunrise: Tree-SHA512: 9de30792d7a5849cae77747aa978e70390b66ee9d082779a56088a024f82e725b0af050e6603aece0ac8229f6d73bc471ba97b4ab69dc7eddf419f5f56ae89a5
2023-01-03Merge bitcoin/bitcoin#25932: refactor: Simplify backtrack logicAndrew Chow
81d4a2b14ff65fe07085ef2a967a466015370ce3 refactor: Move feerate comparison invariant outside of the loop (yancy) 365aca40453995163bbd17231251512f9f9a103b refactor: Simplify feerate comparison statement (yancy) Pull request description: This is a small nit, however I think it's more understandable to write: `utxo_pool.at(0).fee > utxo_pool.at(0).long_term_fee` vs `(utxo_pool.at(0).fee - utxo_pool.at(0).long_term_fee) > 0` ACKs for top commit: Xekyo: ACK 81d4a2b14ff65fe07085ef2a967a466015370ce3 achow101: ACK 81d4a2b14ff65fe07085ef2a967a466015370ce3 aureleoules: ACK 81d4a2b14ff65fe07085ef2a967a466015370ce3 Tree-SHA512: 3e89377989c36716b53114fe40178261671dde5688075fab1c21ec173ac310f8c84ed6af90354d7c329176cb7262dfcaa7191fd19847d3b7147a9a10c3e31176
2022-12-24scripted-diff: Bump copyright headersHennadii Stepanov
-BEGIN VERIFY SCRIPT- ./contrib/devtools/copyright_header.py update ./ -END VERIFY SCRIPT- Commits of previous years: - 2021: f47dda2c58b5d8d623e0e7ff4e74bc352dfa83d7 - 2020: fa0074e2d82928016a43ca408717154a1c70a4db - 2019: aaaaad6ac95b402fe18d019d67897ced6b316ee0
2022-12-21wallet: coin selection, add duplicated inputs checksfurszy
As no process should be able to trigger this error using the regular transaction creation process, throw a runtime_error if happens to tell users/devs to report the bug if happens.
2022-12-05wallet: Check max tx weight in coin selectorAurèle Oulès
Co-authored-by: Andrew Chow <github@achow101.com>
2022-12-02wallet: add assert to SelectionResult::Merge for safetyS3RK
2022-10-26wallet: encapsulate pre-selected-inputs lookup into its own functionfurszy
First step towards decoupling the pre-selected-inputs fetching functionality from `SelectCoins`. Which, will let us not waste resources calculating the available coins if one of the pre-set inputs has an error. (right now, if one of the pre-set inputs is invalid, we first walk through the entire wallet txes map just to end up failing right after it finish)
2022-09-17refactor: Move feerate comparison invariant outside of the loopyancy
2022-09-16refactor: Simplify feerate comparison statementyancy
2022-08-15wallet: use GetChange() when computing wasteS3RK
2022-08-15wallet: add SelectionResult::GetChangeS3RK
2022-08-15wallet: add SelectionResult::MergeS3RK
2022-08-15wallet: accurate SelectionResult::m_targetS3RK
SelectionResult::m_target should be equal to actual selection target. Selection target is the sum of all recipient amounts plus non input fees. So we need to remove change_fee from the m_target. It's safe because change target is always greater than the change fee, so we can always cover fees if change output is created.
2022-08-15wallet: ensure m_min_change_target always covers change feeS3RK
2022-06-28Revert "bnb: exit selection when best_waste is 0"Murch
This reverts commit 9b5950db8683f9b4be03f79ee0aae8a780b01a4b. Waste can be negative. At feerates lower than long_term_feerate this means that a waste of 0 may be a suboptimal solution and this causes the search to exit prematurely. Only when the feerate is equal to the long_term_feerate would achieving a waste of 0 indicate that we have achieved an optimal solution, because it would mean that the excess is 0. It seems unlikely that this would ever occur outside of test cases, and even then we should prefer solutions with more inputs over solutions with fewer according to previous decisions—but solutions with more inputs are found later in the branch exploration. The "optimization" described in #18257 and implemented in #18262 is therefore a premature exit on a suboptimal solution and should be reverted.
2022-05-25logging: Unconditionally log levels >= WARNlaanwj
Messages with level `WARN` or higher should be logged even when the category is not provided with `-debug=`, to make sure important warnings are not lost.
2022-05-21Set effective_value when initializing a COutputishaanam
Previously in COutput, effective_value was initialized as the absolute value of the txout, and fee as 0. effective_value along with fee were calculated outside of the COutput constructor and set after the object had been initialized. These changes will allow either the fee or the feerate to be passed in a COutput constructor. If either are provided, fee and effective_value are calculated and set in the constructor. As a result, AvailableCoins also needs to be passed the feerate when utxos are being spent. When balance is calculated or the coins are being listed and feerate is neither available nor required, AvailableCoinsListUnspent is used instead, which runs AvailableCoins while providing the default value for feerate. Unit tests for the calculation of effective value have also been added.
2022-04-14wallet: track which coin selection algorithm produced a SelectionResultAndrew Chow
2022-03-25[wallet] randomly generate change targetsglozow
If the wallet always chooses 1 million sats as its change target, it is easier to fingerprint transactions created by the Core wallet.
2022-03-25refactor coin selection for parameterizable change targetglozow
no behavior changes, since the target is always MIN_CHANGE
2022-03-24Merge bitcoin/bitcoin#24091: wallet: Consolidate CInputCoin and COutputfanquake
049003fe68a4183f6f20da16f58f10079d1e02df coinselection: Remove COutput operators == and != (Andrew Chow) f6c39c6adb6cbf9c87f04d3d667701905ef5c0a0 coinselection: Remove CInputCoin (Andrew Chow) 70f31f1a81710aa59e95770de9a84bf58cbce1e8 coinselection: Use COutput instead of CInputCoin (Andrew Chow) 14fbb57b79c664090f6a4e60d7bdfc9759ff4307 coinselection: Add effective value and fees to COutput (Andrew Chow) f0821230b8de2eec21a869d1edf9e2b9f502de25 moveonly: move COutput to coinselection.h (Andrew Chow) 42e974e15c6deba1d9395a4da9341c9ebec6e8e5 wallet: Remove CWallet and CWalletTx from COutput's constructor (Andrew Chow) 14d04d5ad15ae56df56edee7ca9a202b52037889 wallet: Replace CWalletTx in COutput with COutPoint and CTxOut (Andrew Chow) 0ba4d1916e26e2a5d603edcdb7625463989d25b6 wallet: Provide input bytes to COutput (Andrew Chow) d51f27d3bb0d6e3ca55bcd23ce53e4fe413a9360 wallet: Store whether a COutput is from the wallet (Andrew Chow) b799814bbd53736b79495072f3c9e05989a465e8 wallet: Store tx time in COutput (Andrew Chow) 46022953ee2e8113167bafd1fd48a383a578b13c wallet: Remove use_max_sig default value (Andrew Chow) 10379f007fd2c18f4cd24d0a0783d6d929f45556 scripted-diff: Rename COutput member variables (Andrew Chow) c7c64db41e1718584aa2f30ff27f60ab0966de62 wallet: cleanup COutput constructor (Andrew Chow) Pull request description: While working on coin selection code, it occurred to me that `CInputCoin` is really a subset of `COutput` and the conversion of a `COutput` to a `CInputCoin` does not appear to be all that useful. So this PR adds fields that are present in `CInputCoin` to `COutput` and replaces the usage of `CInputCoin` with `COutput`. `COutput` is also moved to coinselection.h. As part of this move, the usage of `CWalletTx` is removed from `COutput`. It is instead replaced by storing a `COutPoint` and the `CTxOut` rather than the entire `CWalletTx` as coin selection does not really need the full `CWalletTx`. The `CWalletTx` was only used for figuring out whether the transaction containing the output was from the current wallet, and for the transaction's time. These are now parameters to `COutput`'s constructor. ACKs for top commit: ryanofsky: Code review ACK 049003fe68a4183f6f20da16f58f10079d1e02df, just adding comments and removing == operators since last review w0xlt: reACK 049003f Xekyo: reACK 049003fe68a4183f6f20da16f58f10079d1e02df Tree-SHA512: 048b4cd620a0415e1d9fe8597257ee4bc64656566e1d28a9bdd147d6d72dc87c3f34a3339fa9ab6acf42c388df7901fc4ee900ccaabc3de790ffad162b544c15
2022-03-23coinselection: Use COutput instead of CInputCoinAndrew Chow
Also rename setPresetCoins to preset_coins
2022-03-23moveonly: move COutput to coinselection.hAndrew Chow
2022-03-23Merge bitcoin/bitcoin#24560: wallet: Use single FastRandomContext when ↵Andrew Chow
creating a wallet tx fa7deaa0464576a229b5a6ab13ad033c16d0dada wallet: Pass FastRandomContext& to coin selection (MarcoFalke) 77773b061cb13229a8afb46f6f3ab89fc70eabe3 wallet: Pass FastRandomContext& to DiscourageFeeSniping (MarcoFalke) Pull request description: Passing around a single randomness context shouldn't come with any downsides, but documents better where randomness is used and allows the unit test to be deterministic, if they wish to be so. ACKs for top commit: achow101: ACK fa7deaa0464576a229b5a6ab13ad033c16d0dada promag: Code review ACK fa7deaa0464576a229b5a6ab13ad033c16d0dada. glozow: light code review ACK fa7deaa0464576a229b5a6ab13ad033c16d0dada Tree-SHA512: c16287708cc82ce58311710595d0127af42fb156c93fbcaa5bde634ce323d325f4d8c99a74af24423ab22b5ad58163dd771e8b1a0e7d6bff39c9fb2a1cb21bc7
2022-03-21Merge bitcoin/bitcoin#13226: Optimize SelectCoinsBnB by tracking the ↵Andrew Chow
selection by index rather than by position 9d2005285c77f6c4148bccfa0b8b9135abfa021c doc: Revise comments and whitespace to clarify (Ben Woosley) def43a4d888b4a21c082404d1b25707c481d7625 refactor: Rename i to curr_try in SelectCoinsBnB (Ben Woosley) 1dd092367789749527777ac2b256e639f5706584 refactor: Track BnB selection by index (Ben Woosley) Pull request description: This is prompted by #13167 and presented as a friendly alternative to it. IMO you can improve code readability and performance by about 20% by tracking the selected utxos by index, rather than by position. This reduces the storage access complexity from roughly O(utxo_size) to O(selection_size). On my machine (median of 5 trials): ``` BnBExhaustion, 5, 650, 2.2564, 0.000672999, 0.000711565, 0.000693112 - master BnBExhaustion, 5, 650, 1.76232, 0.000528563, 0.000568806, 0.000539147 - this PR ``` ACKs for top commit: achow101: reACK 9d2005285c77f6c4148bccfa0b8b9135abfa021c glozow: code review ACK 9d2005285c77f6c4148bccfa0b8b9135abfa021c Xekyo: reACK 9d2005285c77f6c4148bccfa0b8b9135abfa021c Tree-SHA512: 453ea11ad58c48928dc76956e3e98916f6924e95510eb02fe89a899ff102fe9cc08a04d557f381ad0218a210275e5383101d971c1ffad38b06b1c57d81144315
2022-03-14wallet: Pass FastRandomContext& to coin selectionMarcoFalke
2022-03-14doc: Revise comments and whitespace to clarifyBen Woosley
2022-03-14refactor: Rename i to curr_try in SelectCoinsBnBBen Woosley
Clarifies purpose and removes name collisions with other indicies.
2022-03-14refactor: Track BnB selection by indexBen Woosley
This is a performance optimization - rather than track all visited values in a bool vector, track the selected index in a vector. This results in a complexity reduction of O(utxo_size) to O(selection_size).
2022-03-11[wallet] assert BnB internally calculated waste is the same as ↵glozow
GetSelectionWaste() These two implementations of waste calculation should never deviate. Still keep the SelectCoinsBnB internal calculation because incremental calculate-as-you-go is much more performant than calling GetSelectionWaste() over and over again.
2022-01-06Add src/wallet/* code to wallet:: namespaceRussell Yanofsky
2021-12-30scripted-diff: Bump copyright headersHennadii Stepanov
-BEGIN VERIFY SCRIPT- ./contrib/devtools/copyright_header.py update ./ -END VERIFY SCRIPT- Commits of previous years: * 2020: fa0074e2d82928016a43ca408717154a1c70a4db * 2019: aaaaad6ac95b402fe18d019d67897ced6b316ee0
2021-12-13wallet: Replace Assume with Assert where needed in coinselectionMarcoFalke
2021-12-09Merge bitcoin/bitcoin#22019: wallet: Introduce SelectionResult for ↵W. J. van der Laan
encapsulating a coin selection solution 05300c14392facf38330eb4fcd8e695a838b76f3 Use SelectionResult in SelectCoins (Andrew Chow) 9d9b101d2019d8237546eedd022e74519feb07bb Use SelectionResult in AttemptSelection (Andrew Chow) bb50850a447bdf461ffb76d47d4a4db904fce324 Use SelectionResult for waste calculation (Andrew Chow) e8f7ae5eb3c682d1a80b503f71e06ce76af1b65c Make an OutputGroup for preset inputs (Andrew Chow) 51a9c00b4de707e0a6a1a68ca6f8e38d86c72d94 Return SelectionResult from SelectCoinsSRD (Andrew Chow) 0ef6184575e77b17f5ec6d7ca086900aca79f6d7 Return SelectionResult from KnapsackSolver (Andrew Chow) 60d2ca72e3f4c56433c63b929a88e7a2def06399 Return SelectionResult from SelectCoinsBnB (Andrew Chow) a339add471717623915cd1a846ade4dab2c89deb Make member variables of SelectionResult private (Andrew Chow) cbf0b9f4ff438865a71c7ceb0a543c18a34f41f0 scripted-diff: Use SelectionResult in coin selector tests (Andrew Chow) 9d1d86da04d5d4768975338841285e90b01130b8 Introduce SelectionResult struct (Andrew Chow) 94d851d28cb909a8f1f8ab795f1d9fc74bebfc7f Fix bnb_search_test to use set equivalence for (Andrew Chow) Pull request description: Instead of returning a set of selected coins and their total value as separate items, encapsulate both of these, and other variables, into a new `SelectionResult` struct. This allows us to have all of the things relevant to a coin selection solution be in a single object. `SelectionResult` enables us to implement the waste calculation in a cleaner way. All of the coin selection functions (`SelectCoinsBnB`, `KnapsackSolver`, `AttemptSelection`, and `SelectCoins`) are changed to use a `SelectionResult` as the output parameter. Based on #22009 ACKs for top commit: laanwj: Code review ACK 05300c14392facf38330eb4fcd8e695a838b76f3 Tree-SHA512: e4dbb4d78a6cda9c237d230b19e7265591efac5a101a64e6970f0654e2c4f93d13bb5d07b98e8c7b8d37321753dbfc94c28c3a7810cb1c59b5bc29b08a8493ef
generated by cgit v1.2.3 (git 2.26.2) at 2024-10-16 20:52:38 +0000