It reduces the amount of the flows and/or removes some flows in order to * deliver no more than max_deliver. It will leave at least one flow. * Returns the total delivery amount. */
| 373 | * deliver no more than max_deliver. It will leave at least one flow. |
| 374 | * Returns the total delivery amount. */ |
| 375 | static struct amount_msat remove_excess(struct flow ***flows, |
| 376 | struct amount_msat max_deliver) |
| 377 | { |
| 378 | if (tal_count(*flows) == 0) |
| 379 | return AMOUNT_MSAT(0); |
| 380 | |
| 381 | struct amount_msat all_deliver, excess; |
| 382 | all_deliver = sum_all_deliver(*flows); |
| 383 | |
| 384 | /* early exit: there is no excess */ |
| 385 | if (!amount_msat_sub(&excess, all_deliver, max_deliver) || |
| 386 | amount_msat_is_zero(excess)) |
| 387 | return all_deliver; |
| 388 | |
| 389 | asort(*flows, tal_count(*flows), revcmp_flows, NULL); |
| 390 | |
| 391 | /* Remove the smaller parts if they deliver less than the |
| 392 | * excess. */ |
| 393 | for (int i = tal_count(*flows) - 1; i >= 0; i--) { |
| 394 | if (!amount_msat_deduct(&excess, |
| 395 | (*flows)[i]->delivers)) |
| 396 | break; |
| 397 | if (!amount_msat_deduct(&all_deliver, |
| 398 | (*flows)[i]->delivers)) |
| 399 | abort(); |
| 400 | del_flow_from_arr(flows, i); |
| 401 | } |
| 402 | |
| 403 | /* If we still have some excess, remove it from the |
| 404 | * current flows in the same proportion every flow contributes to the |
| 405 | * total. */ |
| 406 | struct amount_msat old_excess = excess; |
| 407 | struct amount_msat old_deliver = all_deliver; |
| 408 | for (size_t i = 0; i < tal_count(*flows); i++) { |
| 409 | double fraction = amount_msat_ratio( |
| 410 | (*flows)[i]->delivers, old_deliver); |
| 411 | struct amount_msat remove; |
| 412 | |
| 413 | if (!amount_msat_scale(&remove, old_excess, fraction)) |
| 414 | abort(); |
| 415 | |
| 416 | /* rounding errors: don't remove more than excess */ |
| 417 | remove = amount_msat_min(remove, excess); |
| 418 | |
| 419 | if (!amount_msat_deduct(&excess, remove)) |
| 420 | abort(); |
| 421 | |
| 422 | if (!amount_msat_deduct(&all_deliver, remove) || |
| 423 | !amount_msat_deduct(&(*flows)[i]->delivers, remove)) |
| 424 | abort(); |
| 425 | } |
| 426 | |
| 427 | /* any rounding error left, take it from the first */ |
| 428 | assert(tal_count(*flows) > 0); |
| 429 | if (!amount_msat_deduct(&all_deliver, excess) || |
| 430 | !amount_msat_deduct(&(*flows)[0]->delivers, excess)) |
| 431 | abort(); |
| 432 | return all_deliver; |
no test coverage detected