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                 :             : #include <util/feefrac.h>
       6                 :             : 
       7                 :             : #include <util/check.h>
       8                 :             : 
       9                 :             : #include <array>
      10                 :             : #include <cstddef>
      11                 :             : 
      12                 :        1303 : std::partial_ordering CompareChunks(std::span<const FeeFrac> chunks0, std::span<const FeeFrac> chunks1)
      13                 :             : {
      14                 :             :     /** Array to allow indexed access to input diagrams. */
      15                 :        1303 :     const std::array<std::span<const FeeFrac>, 2> chunk = {chunks0, chunks1};
      16                 :             :     /** How many elements we have processed in each input. */
      17                 :        1303 :     size_t next_index[2] = {0, 0};
      18                 :             :     /** Accumulated fee/sizes in diagrams, up to next_index[i] - 1. */
      19                 :        1303 :     FeeFrac accum[2];
      20                 :             :     /** Whether the corresponding input is strictly better than the other at least in one place. */
      21                 :        1303 :     bool better_somewhere[2] = {false, false};
      22                 :             :     /** Get the first unprocessed point in diagram number dia. */
      23                 :        9689 :     const auto next_point = [&](int dia) { return chunk[dia][next_index[dia]] + accum[dia]; };
      24                 :             :     /** Get the last processed point in diagram number dia. */
      25                 :        3938 :     const auto prev_point = [&](int dia) { return accum[dia]; };
      26                 :             :     /** Move to the next point in diagram number dia. */
      27                 :        1303 :     const auto advance = [&](int dia) { accum[dia] += chunk[dia][next_index[dia]++]; };
      28                 :             : 
      29                 :        3928 :     do {
      30         [ +  + ]:        3928 :         bool done_0 = next_index[0] == chunk[0].size();
      31                 :        3928 :         bool done_1 = next_index[1] == chunk[1].size();
      32         [ +  + ]:        3928 :         if (done_0 && done_1) break;
      33                 :             : 
      34                 :             :         // Determine which diagram has the first unprocessed point. If a single side is finished, use the
      35                 :             :         // other one. Only up to one can be done due to check above.
      36         [ +  + ]:        2635 :         const int unproc_side = (done_0 || done_1) ? done_0 : next_point(0).size > next_point(1).size;
      37                 :             : 
      38                 :             :         // Let `P` be the next point on diagram unproc_side, and `A` and `B` the previous and next points
      39                 :             :         // on the other diagram. We want to know if P lies above or below the line AB. To determine this, we
      40                 :             :         // compute the slopes of line AB and of line AP, and compare them. These slopes are fee per size,
      41                 :             :         // and can thus be expressed as FeeFracs.
      42                 :        2635 :         const FeeFrac& point_p = next_point(unproc_side);
      43                 :        2635 :         const FeeFrac& point_a = prev_point(!unproc_side);
      44                 :             : 
      45         [ +  + ]:        2635 :         const auto slope_ap = point_p - point_a;
      46         [ +  + ]:        2635 :         Assume(slope_ap.size > 0);
      47                 :        2635 :         std::weak_ordering cmp = std::weak_ordering::equivalent;
      48         [ +  + ]:        2635 :         if (done_0 || done_1) {
      49                 :             :             // If a single side has no points left, act as if AB has slope tail_feerate(of 0).
      50                 :         718 :             Assume(!(done_0 && done_1));
      51                 :         718 :             cmp = FeeRateCompare(slope_ap, FeeFrac(0, 1));
      52                 :             :         } else {
      53                 :             :             // If both sides have points left, compute B, and the slope of AB explicitly.
      54                 :        1917 :             const FeeFrac& point_b = next_point(!unproc_side);
      55         [ +  + ]:        1917 :             const auto slope_ab = point_b - point_a;
      56         [ +  + ]:        1917 :             Assume(slope_ab.size >= slope_ap.size);
      57                 :        1917 :             cmp = FeeRateCompare(slope_ap, slope_ab);
      58                 :             : 
      59                 :             :             // If B and P have the same size, B can be marked as processed (in addition to P, see
      60                 :             :             // below), as we've already performed a comparison at this size.
      61         [ +  + ]:        1917 :             if (point_b.size == point_p.size) advance(!unproc_side);
      62                 :             :         }
      63                 :             :         // If P lies above AB, unproc_side is better in P. If P lies below AB, then !unproc_side is
      64                 :             :         // better in P.
      65         [ +  + ]:        2635 :         if (std::is_gt(cmp)) better_somewhere[unproc_side] = true;
      66         [ +  + ]:        2635 :         if (std::is_lt(cmp)) better_somewhere[!unproc_side] = true;
      67                 :        2635 :         advance(unproc_side);
      68                 :             : 
      69                 :             :         // If both diagrams are better somewhere, they are incomparable.
      70   [ +  +  +  + ]:        2635 :         if (better_somewhere[0] && better_somewhere[1]) return std::partial_ordering::unordered;
      71                 :             :     } while(true);
      72                 :             : 
      73                 :             :     // Otherwise compare the better_somewhere values.
      74   [ +  +  +  + ]:        1293 :     return better_somewhere[0] <=> better_somewhere[1];
      75                 :             : }