_ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEC2Ev:
   68|  1.66k|    DepGraph() noexcept = default;
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE7TxCountEv:
  118|  9.24k|    auto TxCount() const noexcept { return m_used.Count(); }
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE9PositionsEv:
  114|  17.2k|    const SetType& Positions() const noexcept { return m_used; }
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE9AncestorsEj:
  124|   120k|    const SetType& Ancestors(ClusterIndex i) const noexcept { return entries[i].ancestors; }
_ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE14AddTransactionERK7FeeFrac:
  134|  4.91k|    {
  135|  4.91k|        static constexpr auto ALL_POSITIONS = SetType::Fill(SetType::Size());
  136|  4.91k|        auto available = ALL_POSITIONS - m_used;
  137|  4.91k|        Assume(available.Any());
  ------------------
  |  |   97|  4.91k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  138|  4.91k|        ClusterIndex new_idx = available.First();
  139|  4.91k|        if (new_idx == entries.size()) {
  ------------------
  |  Branch (139:13): [True: 4.91k, False: 0]
  ------------------
  140|  4.91k|            entries.emplace_back(feefrac, SetType::Singleton(new_idx), SetType::Singleton(new_idx));
  141|  4.91k|        } else {
  142|      0|            entries[new_idx] = Entry(feefrac, SetType::Singleton(new_idx), SetType::Singleton(new_idx));
  143|      0|        }
  144|  4.91k|        m_used.Set(new_idx);
  145|  4.91k|        return new_idx;
  146|  4.91k|    }
_ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE5EntryC2ERK7FeeFracRKS3_SA_:
   46|  4.91k|        Entry(const FeeFrac& f, const SetType& a, const SetType& d) noexcept : feerate(f), ancestors(a), descendants(d) {}
_ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE15AddDependenciesERKS3_j:
  178|  9.83k|    {
  179|  9.83k|        Assume(m_used[child]);
  ------------------
  |  |   97|  9.83k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  180|  9.83k|        Assume(parents.IsSubsetOf(m_used));
  ------------------
  |  |   97|  9.83k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  181|       |        // Compute the ancestors of parents that are not already ancestors of child.
  182|  9.83k|        SetType par_anc;
  183|  9.83k|        for (auto par : parents - Ancestors(child)) {
  ------------------
  |  Branch (183:23): [True: 8.57k, False: 9.83k]
  ------------------
  184|  8.57k|            par_anc |= Ancestors(par);
  185|  8.57k|        }
  186|  9.83k|        par_anc -= Ancestors(child);
  187|       |        // Bail out if there are no such ancestors.
  188|  9.83k|        if (par_anc.None()) return;
  ------------------
  |  Branch (188:13): [True: 8.35k, False: 1.47k]
  ------------------
  189|       |        // To each such ancestor, add as descendants the descendants of the child.
  190|  1.47k|        const auto& chl_des = entries[child].descendants;
  191|  12.9k|        for (auto anc_of_par : par_anc) {
  ------------------
  |  Branch (191:30): [True: 12.9k, False: 1.47k]
  ------------------
  192|  12.9k|            entries[anc_of_par].descendants |= chl_des;
  193|  12.9k|        }
  194|       |        // To each descendant of the child, add those ancestors.
  195|  1.47k|        for (auto dec_of_chl : Descendants(child)) {
  ------------------
  |  Branch (195:30): [True: 1.47k, False: 1.47k]
  ------------------
  196|  1.47k|            entries[dec_of_chl].ancestors |= par_anc;
  197|  1.47k|        }
  198|  1.47k|    }
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE7FeeRateEj:
  120|  39.3k|    const FeeFrac& FeeRate(ClusterIndex i) const noexcept { return entries[i].feerate; }
_ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEaSEOS4_:
   72|    831|    DepGraph& operator=(DepGraph&&) noexcept = default;
_ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEC2ERKS4_4SpanIKjEj:
   89|    831|    DepGraph(const DepGraph<SetType>& depgraph, Span<const ClusterIndex> mapping, ClusterIndex pos_range) noexcept : entries(pos_range)
   90|    831|    {
   91|    831|        Assume(mapping.size() == depgraph.PositionRange());
  ------------------
  |  |   97|    831|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
   92|    831|        Assume((pos_range == 0) == (depgraph.TxCount() == 0));
  ------------------
  |  |   97|    831|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
   93|  4.91k|        for (ClusterIndex i : depgraph.Positions()) {
  ------------------
  |  Branch (93:29): [True: 4.91k, False: 831]
  ------------------
   94|  4.91k|            auto new_idx = mapping[i];
   95|  4.91k|            Assume(new_idx < pos_range);
  ------------------
  |  |   97|  4.91k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
   96|       |            // Add transaction.
   97|  4.91k|            entries[new_idx].ancestors = SetType::Singleton(new_idx);
   98|  4.91k|            entries[new_idx].descendants = SetType::Singleton(new_idx);
   99|  4.91k|            m_used.Set(new_idx);
  100|       |            // Fill in fee and size.
  101|  4.91k|            entries[new_idx].feerate = depgraph.entries[i].feerate;
  102|  4.91k|        }
  103|  4.91k|        for (ClusterIndex i : depgraph.Positions()) {
  ------------------
  |  Branch (103:29): [True: 4.91k, False: 831]
  ------------------
  104|       |            // Fill in dependencies by mapping direct parents.
  105|  4.91k|            SetType parents;
  106|  4.91k|            for (auto j : depgraph.GetReducedParents(i)) parents.Set(mapping[j]);
  ------------------
  |  Branch (106:25): [True: 2.08k, False: 4.91k]
  ------------------
  107|  4.91k|            AddDependencies(parents, mapping[i]);
  108|  4.91k|        }
  109|       |        // Verify that the provided pos_range was correct (no unused positions at the end).
  110|    831|        Assume(m_used.None() ? (pos_range == 0) : (pos_range == m_used.Last() + 1));
  ------------------
  |  |   97|  1.66k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  |  |  ------------------
  |  |  |  Branch (97:51): [True: 229, False: 602]
  |  |  ------------------
  ------------------
  111|    831|    }
_ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE5EntryC2Ev:
   44|  15.3k|        Entry() noexcept = default;
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE22FindConnectedComponentERKS3_:
  266|  3.26k|    {
  267|  3.26k|        if (todo.None()) return todo;
  ------------------
  |  Branch (267:13): [True: 0, False: 3.26k]
  ------------------
  268|  3.26k|        auto to_add = SetType::Singleton(todo.First());
  269|  3.26k|        SetType ret;
  270|  6.56k|        do {
  271|  6.56k|            SetType old = ret;
  272|  8.18k|            for (auto add : to_add) {
  ------------------
  |  Branch (272:27): [True: 8.18k, False: 6.56k]
  ------------------
  273|  8.18k|                ret |= Descendants(add);
  274|  8.18k|                ret |= Ancestors(add);
  275|  8.18k|            }
  276|  6.56k|            ret &= todo;
  277|  6.56k|            to_add = ret - old;
  278|  6.56k|        } while (to_add.Any());
  ------------------
  |  Branch (278:18): [True: 3.30k, False: 3.26k]
  ------------------
  279|  3.26k|        return ret;
  280|  3.26k|    }
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE11IsConnectedERKS3_:
  287|  3.26k|    {
  288|  3.26k|        return FindConnectedComponent(subset) == subset;
  289|  3.26k|    }
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE11DescendantsEj:
  126|  19.4k|    const SetType& Descendants(ClusterIndex i) const noexcept { return entries[i].descendants; }
_ZN17cluster_linearize18ChunkLinearizationIN13bitset_detail9IntBitSetIjEEEENSt3__16vectorI7FeeFracNS4_9allocatorIS6_EEEERKNS_8DepGraphIT_EE4SpanIKjE:
  375|  2.49k|{
  376|  2.49k|    std::vector<FeeFrac> ret;
  377|  14.7k|    for (ClusterIndex i : linearization) {
  ------------------
  |  Branch (377:25): [True: 14.7k, False: 2.49k]
  ------------------
  378|       |        /** The new chunk to be added, initially a singleton. */
  379|  14.7k|        auto new_chunk = depgraph.FeeRate(i);
  380|       |        // As long as the new chunk has a higher feerate than the last chunk so far, absorb it.
  381|  21.5k|        while (!ret.empty() && new_chunk >> ret.back()) {
  ------------------
  |  Branch (381:16): [True: 17.7k, False: 3.85k]
  |  Branch (381:32): [True: 6.84k, False: 10.8k]
  ------------------
  382|  6.84k|            new_chunk += ret.back();
  383|  6.84k|            ret.pop_back();
  384|  6.84k|        }
  385|       |        // Actually move that new chunk into the chunking.
  386|  14.7k|        ret.push_back(std::move(new_chunk));
  387|  14.7k|    }
  388|  2.49k|    return ret;
  389|  2.49k|}
_ZN17cluster_linearize21LinearizationChunkingIN13bitset_detail9IntBitSetIjEEEC2ERKNS_8DepGraphIS3_EE4SpanIKjE:
  441|    831|        m_depgraph(depgraph), m_linearization(lin)
  442|    831|    {
  443|       |        // Mark everything in lin as todo still.
  444|  4.91k|        for (auto i : m_linearization) m_todo.Set(i);
  ------------------
  |  Branch (444:21): [True: 4.91k, False: 831]
  ------------------
  445|       |        // Compute the initial chunking.
  446|    831|        m_chunks.reserve(depgraph.TxCount());
  447|    831|        BuildChunks();
  448|    831|    }
_ZN17cluster_linearize21LinearizationChunkingIN13bitset_detail9IntBitSetIjEEE11BuildChunksEv:
  412|    831|    {
  413|       |        // Caller must clear m_chunks.
  414|    831|        Assume(m_chunks.empty());
  ------------------
  |  |   97|    831|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  415|       |
  416|       |        // Chop off the initial part of m_linearization that is already done.
  417|    831|        while (!m_linearization.empty() && !m_todo[m_linearization.front()]) {
  ------------------
  |  Branch (417:16): [True: 602, False: 229]
  |  Branch (417:44): [True: 0, False: 602]
  ------------------
  418|      0|            m_linearization = m_linearization.subspan(1);
  419|      0|        }
  420|       |
  421|       |        // Iterate over the remaining entries in m_linearization. This is effectively the same
  422|       |        // algorithm as ChunkLinearization, but supports skipping parts of the linearization and
  423|       |        // keeps track of the sets themselves instead of just their feerates.
  424|  4.91k|        for (auto idx : m_linearization) {
  ------------------
  |  Branch (424:23): [True: 4.91k, False: 831]
  ------------------
  425|  4.91k|            if (!m_todo[idx]) continue;
  ------------------
  |  Branch (425:17): [True: 0, False: 4.91k]
  ------------------
  426|       |            // Start with an initial chunk containing just element idx.
  427|  4.91k|            SetInfo add(m_depgraph, idx);
  428|       |            // Absorb existing final chunks into add while they have lower feerate.
  429|  6.56k|            while (!m_chunks.empty() && add.feerate >> m_chunks.back().feerate) {
  ------------------
  |  Branch (429:20): [True: 5.48k, False: 1.08k]
  |  Branch (429:41): [True: 1.64k, False: 3.83k]
  ------------------
  430|  1.64k|                add |= m_chunks.back();
  431|  1.64k|                m_chunks.pop_back();
  432|  1.64k|            }
  433|       |            // Remember new chunk.
  434|  4.91k|            m_chunks.push_back(std::move(add));
  435|  4.91k|        }
  436|    831|    }
_ZN17cluster_linearize7SetInfoIN13bitset_detail9IntBitSetIjEEEC2ERKNS_8DepGraphIS3_EEj:
  331|  4.91k|        transactions(SetType::Singleton(pos)), feerate(depgraph.FeeRate(pos)) {}
_ZN17cluster_linearize7SetInfoIN13bitset_detail9IntBitSetIjEEEoRERKS4_:
  347|  1.64k|    {
  348|  1.64k|        Assume(!transactions.Overlaps(other.transactions));
  ------------------
  |  |   97|  1.64k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  349|  1.64k|        transactions |= other.transactions;
  350|  1.64k|        feerate += other.feerate;
  351|  1.64k|        return *this;
  352|  1.64k|    }
_ZNK17cluster_linearize21LinearizationChunkingIN13bitset_detail9IntBitSetIjEEE13NumChunksLeftEv:
  451|  4.09k|    ClusterIndex NumChunksLeft() const noexcept { return m_chunks.size() - m_chunks_skip; }
_ZNK17cluster_linearize21LinearizationChunkingIN13bitset_detail9IntBitSetIjEEE8GetChunkEj:
  455|  9.79k|    {
  456|  9.79k|        Assume(n + m_chunks_skip < m_chunks.size());
  ------------------
  |  |   97|  9.79k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  457|  9.79k|        return m_chunks[n + m_chunks_skip];
  458|  9.79k|    }
_ZN17cluster_linearize21LinearizationChunkingIN13bitset_detail9IntBitSetIjEEE8MarkDoneES3_:
  462|  3.26k|    {
  463|  3.26k|        Assume(subset.Any());
  ------------------
  |  |   97|  3.26k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  464|  3.26k|        Assume(subset.IsSubsetOf(m_todo));
  ------------------
  |  |   97|  3.26k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  465|  3.26k|        m_todo -= subset;
  466|  3.26k|        if (GetChunk(0).transactions == subset) {
  ------------------
  |  Branch (466:13): [True: 3.26k, False: 0]
  ------------------
  467|       |            // If the newly done transactions exactly match the first chunk of the remainder of
  468|       |            // the linearization, we do not need to rechunk; just remember to skip one
  469|       |            // additional chunk.
  470|  3.26k|            ++m_chunks_skip;
  471|       |            // With subset marked done, some prefix of m_linearization will be done now. How long
  472|       |            // that prefix is depends on how many done elements were interspersed with subset,
  473|       |            // but at least as many transactions as there are in subset.
  474|  3.26k|            m_linearization = m_linearization.subspan(subset.Count());
  475|  3.26k|        } else {
  476|       |            // Otherwise rechunk what remains of m_linearization.
  477|      0|            m_chunks.clear();
  478|      0|            m_chunks_skip = 0;
  479|      0|            BuildChunks();
  480|      0|        }
  481|  3.26k|    }
_ZN17cluster_linearize13PostLinearizeIN13bitset_detail9IntBitSetIjEEEEvRKNS_8DepGraphIT_EE4SpanIjE:
 1114|  1.66k|{
 1115|       |    // This algorithm performs a number of passes (currently 2); the even ones operate from back to
 1116|       |    // front, the odd ones from front to back. Each results in an equal-or-better linearization
 1117|       |    // than the one started from.
 1118|       |    // - One pass in either direction guarantees that the resulting chunks are connected.
 1119|       |    // - Each direction corresponds to one shape of tree being linearized optimally (forward passes
 1120|       |    //   guarantee this for graphs where each transaction has at most one child; backward passes
 1121|       |    //   guarantee this for graphs where each transaction has at most one parent).
 1122|       |    // - Starting with a backward pass guarantees the moved-tree property.
 1123|       |    //
 1124|       |    // During an odd (forward) pass, the high-level operation is:
 1125|       |    // - Start with an empty list of groups L=[].
 1126|       |    // - For every transaction i in the old linearization, from front to back:
 1127|       |    //   - Append a new group C=[i], containing just i, to the back of L.
 1128|       |    //   - While L has at least one group before C, and the group immediately before C has feerate
 1129|       |    //     lower than C:
 1130|       |    //     - If C depends on P:
 1131|       |    //       - Merge P into C, making C the concatenation of P+C, continuing with the combined C.
 1132|       |    //     - Otherwise:
 1133|       |    //       - Swap P with C, continuing with the now-moved C.
 1134|       |    // - The output linearization is the concatenation of the groups in L.
 1135|       |    //
 1136|       |    // During even (backward) passes, i iterates from the back to the front of the existing
 1137|       |    // linearization, and new groups are prepended instead of appended to the list L. To enable
 1138|       |    // more code reuse, both passes append groups, but during even passes the meanings of
 1139|       |    // parent/child, and of high/low feerate are reversed, and the final concatenation is reversed
 1140|       |    // on output.
 1141|       |    //
 1142|       |    // In the implementation below, the groups are represented by singly-linked lists (pointing
 1143|       |    // from the back to the front), which are themselves organized in a singly-linked circular
 1144|       |    // list (each group pointing to its predecessor, with a special sentinel group at the front
 1145|       |    // that points back to the last group).
 1146|       |    //
 1147|       |    // Information about transaction t is stored in entries[t + 1], while the sentinel is in
 1148|       |    // entries[0].
 1149|       |
 1150|       |    /** Index of the sentinel in the entries array below. */
 1151|  1.66k|    static constexpr ClusterIndex SENTINEL{0};
 1152|       |    /** Indicator that a group has no previous transaction. */
 1153|  1.66k|    static constexpr ClusterIndex NO_PREV_TX{0};
 1154|       |
 1155|       |
 1156|       |    /** Data structure per transaction entry. */
 1157|  1.66k|    struct TxEntry
 1158|  1.66k|    {
 1159|       |        /** The index of the previous transaction in this group; NO_PREV_TX if this is the first
 1160|       |         *  entry of a group. */
 1161|  1.66k|        ClusterIndex prev_tx;
 1162|       |
 1163|       |        // The fields below are only used for transactions that are the last one in a group
 1164|       |        // (referred to as tail transactions below).
 1165|       |
 1166|       |        /** Index of the first transaction in this group, possibly itself. */
 1167|  1.66k|        ClusterIndex first_tx;
 1168|       |        /** Index of the last transaction in the previous group. The first group (the sentinel)
 1169|       |         *  points back to the last group here, making it a singly-linked circular list. */
 1170|  1.66k|        ClusterIndex prev_group;
 1171|       |        /** All transactions in the group. Empty for the sentinel. */
 1172|  1.66k|        SetType group;
 1173|       |        /** All dependencies of the group (descendants in even passes; ancestors in odd ones). */
 1174|  1.66k|        SetType deps;
 1175|       |        /** The combined fee/size of transactions in the group. Fee is negated in even passes. */
 1176|  1.66k|        FeeFrac feerate;
 1177|  1.66k|    };
 1178|       |
 1179|       |    // As an example, consider the state corresponding to the linearization [1,0,3,2], with
 1180|       |    // groups [1,0,3] and [2], in an odd pass. The linked lists would be:
 1181|       |    //
 1182|       |    //                                        +-----+
 1183|       |    //                                 0<-P-- | 0 S | ---\     Legend:
 1184|       |    //                                        +-----+    |
 1185|       |    //                                           ^       |     - digit in box: entries index
 1186|       |    //             /--------------F---------+    G       |       (note: one more than tx value)
 1187|       |    //             v                         \   |       |     - S: sentinel group
 1188|       |    //          +-----+        +-----+        +-----+    |          (empty feerate)
 1189|       |    //   0<-P-- | 2   | <--P-- | 1   | <--P-- | 4 T |    |     - T: tail transaction, contains
 1190|       |    //          +-----+        +-----+        +-----+    |          fields beyond prev_tv.
 1191|       |    //                                           ^       |     - P: prev_tx reference
 1192|       |    //                                           G       G     - F: first_tx reference
 1193|       |    //                                           |       |     - G: prev_group reference
 1194|       |    //                                        +-----+    |
 1195|       |    //                                 0<-P-- | 3 T | <--/
 1196|       |    //                                        +-----+
 1197|       |    //                                         ^   |
 1198|       |    //                                         \-F-/
 1199|       |    //
 1200|       |    // During an even pass, the diagram above would correspond to linearization [2,3,0,1], with
 1201|       |    // groups [2] and [3,0,1].
 1202|       |
 1203|  1.66k|    std::vector<TxEntry> entries(depgraph.PositionRange() + 1);
 1204|       |
 1205|       |    // Perform two passes over the linearization.
 1206|  4.98k|    for (int pass = 0; pass < 2; ++pass) {
  ------------------
  |  Branch (1206:24): [True: 3.32k, False: 1.66k]
  ------------------
 1207|  3.32k|        int rev = !(pass & 1);
 1208|       |        // Construct a sentinel group, identifying the start of the list.
 1209|  3.32k|        entries[SENTINEL].prev_group = SENTINEL;
 1210|  3.32k|        Assume(entries[SENTINEL].feerate.IsEmpty());
  ------------------
  |  |   97|  3.32k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
 1211|       |
 1212|       |        // Iterate over all elements in the existing linearization.
 1213|  22.9k|        for (ClusterIndex i = 0; i < linearization.size(); ++i) {
  ------------------
  |  Branch (1213:34): [True: 19.6k, False: 3.32k]
  ------------------
 1214|       |            // Even passes are from back to front; odd passes from front to back.
 1215|  19.6k|            ClusterIndex idx = linearization[rev ? linearization.size() - 1 - i : i];
  ------------------
  |  Branch (1215:46): [True: 9.83k, False: 9.83k]
  ------------------
 1216|       |            // Construct a new group containing just idx. In even passes, the meaning of
 1217|       |            // parent/child and high/low feerate are swapped.
 1218|  19.6k|            ClusterIndex cur_group = idx + 1;
 1219|  19.6k|            entries[cur_group].group = SetType::Singleton(idx);
 1220|  19.6k|            entries[cur_group].deps = rev ? depgraph.Descendants(idx): depgraph.Ancestors(idx);
  ------------------
  |  Branch (1220:39): [True: 9.83k, False: 9.83k]
  ------------------
 1221|  19.6k|            entries[cur_group].feerate = depgraph.FeeRate(idx);
 1222|  19.6k|            if (rev) entries[cur_group].feerate.fee = -entries[cur_group].feerate.fee;
  ------------------
  |  Branch (1222:17): [True: 9.83k, False: 9.83k]
  ------------------
 1223|  19.6k|            entries[cur_group].prev_tx = NO_PREV_TX; // No previous transaction in group.
 1224|  19.6k|            entries[cur_group].first_tx = cur_group; // Transaction itself is first of group.
 1225|       |            // Insert the new group at the back of the groups linked list.
 1226|  19.6k|            entries[cur_group].prev_group = entries[SENTINEL].prev_group;
 1227|  19.6k|            entries[SENTINEL].prev_group = cur_group;
 1228|       |
 1229|       |            // Start merge/swap cycle.
 1230|  19.6k|            ClusterIndex next_group = SENTINEL; // We inserted at the end, so next group is sentinel.
 1231|  19.6k|            ClusterIndex prev_group = entries[cur_group].prev_group;
 1232|       |            // Continue as long as the current group has higher feerate than the previous one.
 1233|  34.5k|            while (entries[cur_group].feerate >> entries[prev_group].feerate) {
  ------------------
  |  Branch (1233:20): [True: 14.8k, False: 19.6k]
  ------------------
 1234|       |                // prev_group/cur_group/next_group refer to (the last transactions of) 3
 1235|       |                // consecutive entries in groups list.
 1236|  14.8k|                Assume(cur_group == entries[next_group].prev_group);
  ------------------
  |  |   97|  14.8k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
 1237|  14.8k|                Assume(prev_group == entries[cur_group].prev_group);
  ------------------
  |  |   97|  14.8k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
 1238|       |                // The sentinel has empty feerate, which is neither higher or lower than other
 1239|       |                // feerates. Thus, the while loop we are in here guarantees that cur_group and
 1240|       |                // prev_group are not the sentinel.
 1241|  14.8k|                Assume(cur_group != SENTINEL);
  ------------------
  |  |   97|  14.8k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
 1242|  14.8k|                Assume(prev_group != SENTINEL);
  ------------------
  |  |   97|  14.8k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
 1243|  14.8k|                if (entries[cur_group].deps.Overlaps(entries[prev_group].group)) {
  ------------------
  |  Branch (1243:21): [True: 6.69k, False: 8.16k]
  ------------------
 1244|       |                    // There is a dependency between cur_group and prev_group; merge prev_group
 1245|       |                    // into cur_group. The group/deps/feerate fields of prev_group remain unchanged
 1246|       |                    // but become unused.
 1247|  6.69k|                    entries[cur_group].group |= entries[prev_group].group;
 1248|  6.69k|                    entries[cur_group].deps |= entries[prev_group].deps;
 1249|  6.69k|                    entries[cur_group].feerate += entries[prev_group].feerate;
 1250|       |                    // Make the first of the current group point to the tail of the previous group.
 1251|  6.69k|                    entries[entries[cur_group].first_tx].prev_tx = prev_group;
 1252|       |                    // The first of the previous group becomes the first of the newly-merged group.
 1253|  6.69k|                    entries[cur_group].first_tx = entries[prev_group].first_tx;
 1254|       |                    // The previous group becomes whatever group was before the former one.
 1255|  6.69k|                    prev_group = entries[prev_group].prev_group;
 1256|  6.69k|                    entries[cur_group].prev_group = prev_group;
 1257|  8.16k|                } else {
 1258|       |                    // There is no dependency between cur_group and prev_group; swap them.
 1259|  8.16k|                    ClusterIndex preprev_group = entries[prev_group].prev_group;
 1260|       |                    // If PP, P, C, N were the old preprev, prev, cur, next groups, then the new
 1261|       |                    // layout becomes [PP, C, P, N]. Update prev_groups to reflect that order.
 1262|  8.16k|                    entries[next_group].prev_group = prev_group;
 1263|  8.16k|                    entries[prev_group].prev_group = cur_group;
 1264|  8.16k|                    entries[cur_group].prev_group = preprev_group;
 1265|       |                    // The current group remains the same, but the groups before/after it have
 1266|       |                    // changed.
 1267|  8.16k|                    next_group = prev_group;
 1268|  8.16k|                    prev_group = preprev_group;
 1269|  8.16k|                }
 1270|  14.8k|            }
 1271|  19.6k|        }
 1272|       |
 1273|       |        // Convert the entries back to linearization (overwriting the existing one).
 1274|  3.32k|        ClusterIndex cur_group = entries[0].prev_group;
 1275|  3.32k|        ClusterIndex done = 0;
 1276|  16.2k|        while (cur_group != SENTINEL) {
  ------------------
  |  Branch (1276:16): [True: 12.9k, False: 3.32k]
  ------------------
 1277|  12.9k|            ClusterIndex cur_tx = cur_group;
 1278|       |            // Traverse the transactions of cur_group (from back to front), and write them in the
 1279|       |            // same order during odd passes, and reversed (front to back) in even passes.
 1280|  12.9k|            if (rev) {
  ------------------
  |  Branch (1280:17): [True: 6.43k, False: 6.53k]
  ------------------
 1281|  9.83k|                do {
 1282|  9.83k|                    *(linearization.begin() + (done++)) = cur_tx - 1;
 1283|  9.83k|                    cur_tx = entries[cur_tx].prev_tx;
 1284|  9.83k|                } while (cur_tx != NO_PREV_TX);
  ------------------
  |  Branch (1284:26): [True: 3.39k, False: 6.43k]
  ------------------
 1285|  6.53k|            } else {
 1286|  9.83k|                do {
 1287|  9.83k|                    *(linearization.end() - (++done)) = cur_tx - 1;
 1288|  9.83k|                    cur_tx = entries[cur_tx].prev_tx;
 1289|  9.83k|                } while (cur_tx != NO_PREV_TX);
  ------------------
  |  Branch (1289:26): [True: 3.29k, False: 6.53k]
  ------------------
 1290|  6.53k|            }
 1291|  12.9k|            cur_group = entries[cur_group].prev_group;
 1292|  12.9k|        }
 1293|  3.32k|        Assume(done == linearization.size());
  ------------------
  |  |   97|  3.32k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
 1294|  3.32k|    }
 1295|  1.66k|}
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE13PositionRangeEv:
  116|  2.49k|    ClusterIndex PositionRange() const noexcept { return entries.size(); }
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE17GetReducedParentsEj:
  209|  4.91k|    {
  210|  4.91k|        SetType parents = Ancestors(i);
  211|  4.91k|        parents.Reset(i);
  212|  6.49k|        for (auto parent : parents) {
  ------------------
  |  Branch (212:26): [True: 6.49k, False: 4.91k]
  ------------------
  213|  6.49k|            if (parents[parent]) {
  ------------------
  |  Branch (213:17): [True: 6.49k, False: 0]
  ------------------
  214|  6.49k|                parents -= Ancestors(parent);
  215|  6.49k|                parents.Set(parent);
  216|  6.49k|            }
  217|  6.49k|        }
  218|  4.91k|        return parents;
  219|  4.91k|    }

_ZN15CheckVarIntModeIL10VarIntMode0EmEC2Ev:
  410|  17.0k|    {
  411|  17.0k|        static_assert(Mode != VarIntMode::DEFAULT || std::is_unsigned<I>::value, "Unsigned type required with mode DEFAULT.");
  412|  17.0k|        static_assert(Mode != VarIntMode::NONNEGATIVE_SIGNED || std::is_signed<I>::value, "Signed type required with mode NONNEGATIVE_SIGNED.");
  413|  17.0k|    }
_ZN7WrapperI15VarIntFormatterIL10VarIntMode0EERmEC2ES3_:
  481|  17.0k|    explicit Wrapper(T obj) : m_object(obj) {}
_ZN15CheckVarIntModeIL10VarIntMode1EiEC2Ev:
  410|  5.39k|    {
  411|  5.39k|        static_assert(Mode != VarIntMode::DEFAULT || std::is_unsigned<I>::value, "Unsigned type required with mode DEFAULT.");
  412|  5.39k|        static_assert(Mode != VarIntMode::NONNEGATIVE_SIGNED || std::is_signed<I>::value, "Signed type required with mode NONNEGATIVE_SIGNED.");
  413|  5.39k|    }
_ZN7WrapperI15VarIntFormatterIL10VarIntMode1EERiEC2ES3_:
  481|  5.39k|    explicit Wrapper(T obj) : m_object(obj) {}
cluster_linearize.cpp:_ZL5UsingIN12_GLOBAL__N_117DepGraphFormatterERN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEEE7WrapperIT_RT0_EOSB_:
  497|    831|static inline Wrapper<Formatter, T&> Using(T&& t) { return Wrapper<Formatter, T&>(t); }
cluster_linearize.cpp:_ZN7WrapperIN12_GLOBAL__N_117DepGraphFormatterERN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEEEC2ES8_:
  481|    831|    explicit Wrapper(T obj) : m_object(obj) {}
cluster_linearize.cpp:_Z11UnserializeI10SpanReaderR7WrapperIN12_GLOBAL__N_117DepGraphFormatterERN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEEEQ14UnserializableIT0_T_EEvRSE_OSD_:
  762|    831|{
  763|    831|    a.Unserialize(is);
  764|    831|}
cluster_linearize.cpp:_ZN7WrapperIN12_GLOBAL__N_117DepGraphFormatterERN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEEE11UnserializeI10SpanReaderEEvRT_:
  483|    831|    template<typename Stream> void Unserialize(Stream &s) { Formatter().Unser(s, m_object); }
_Z11UnserializeI10SpanReaderR7WrapperI15VarIntFormatterIL10VarIntMode1EERiEQ14UnserializableIT0_T_EEvRS9_OS8_:
  762|  5.39k|{
  763|  5.39k|    a.Unserialize(is);
  764|  5.39k|}
_ZN7WrapperI15VarIntFormatterIL10VarIntMode1EERiE11UnserializeI10SpanReaderEEvRT_:
  483|  5.39k|    template<typename Stream> void Unserialize(Stream &s) { Formatter().Unser(s, m_object); }
_ZN15VarIntFormatterIL10VarIntMode1EE5UnserI10SpanReaderiEEvRT_RT0_:
  514|  5.39k|    {
  515|  5.39k|        v = ReadVarInt<Stream,Mode,typename std::remove_cv<I>::type>(s);
  516|  5.39k|    }
_Z10ReadVarIntI10SpanReaderL10VarIntMode1EiET1_RT_:
  453|  5.39k|{
  454|  5.39k|    CheckVarIntMode<Mode, I>();
  455|  5.39k|    I n = 0;
  456|  6.23k|    while(true) {
  ------------------
  |  Branch (456:11): [Folded - Ignored]
  ------------------
  457|  6.23k|        unsigned char chData = ser_readdata8(is);
  458|  6.23k|        if (n > (std::numeric_limits<I>::max() >> 7)) {
  ------------------
  |  Branch (458:13): [True: 7, False: 6.22k]
  ------------------
  459|      7|           throw std::ios_base::failure("ReadVarInt(): size too large");
  460|      7|        }
  461|  6.22k|        n = (n << 7) | (chData & 0x7F);
  462|  6.22k|        if (chData & 0x80) {
  ------------------
  |  Branch (462:13): [True: 843, False: 5.38k]
  ------------------
  463|    843|            if (n == std::numeric_limits<I>::max()) {
  ------------------
  |  Branch (463:17): [True: 1, False: 842]
  ------------------
  464|      1|                throw std::ios_base::failure("ReadVarInt(): size too large");
  465|      1|            }
  466|    842|            n++;
  467|  5.38k|        } else {
  468|  5.38k|            return n;
  469|  5.38k|        }
  470|  6.22k|    }
  471|  5.39k|}
_Z13ser_readdata8I10SpanReaderEhRT_:
   84|  26.2k|{
   85|  26.2k|    uint8_t obj;
   86|  26.2k|    s.read(AsWritableBytes(Span{&obj, 1}));
   87|  26.2k|    return obj;
   88|  26.2k|}
cluster_linearize.cpp:_ZL5UsingI15VarIntFormatterIL10VarIntMode1EERiE7WrapperIT_RT0_EOS6_:
  497|  5.39k|static inline Wrapper<Formatter, T&> Using(T&& t) { return Wrapper<Formatter, T&>(t); }
cluster_linearize.cpp:_ZL5UsingI15VarIntFormatterIL10VarIntMode0EERmE7WrapperIT_RT0_EOS6_:
  497|  17.0k|static inline Wrapper<Formatter, T&> Using(T&& t) { return Wrapper<Formatter, T&>(t); }
_Z11UnserializeI10SpanReaderR7WrapperI15VarIntFormatterIL10VarIntMode0EERmEQ14UnserializableIT0_T_EEvRS9_OS8_:
  762|  17.0k|{
  763|  17.0k|    a.Unserialize(is);
  764|  17.0k|}
_ZN7WrapperI15VarIntFormatterIL10VarIntMode0EERmE11UnserializeI10SpanReaderEEvRT_:
  483|  17.0k|    template<typename Stream> void Unserialize(Stream &s) { Formatter().Unser(s, m_object); }
_ZN15VarIntFormatterIL10VarIntMode0EE5UnserI10SpanReadermEEvRT_RT0_:
  514|  17.0k|    {
  515|  17.0k|        v = ReadVarInt<Stream,Mode,typename std::remove_cv<I>::type>(s);
  516|  17.0k|    }
_Z10ReadVarIntI10SpanReaderL10VarIntMode0EmET1_RT_:
  453|  17.0k|{
  454|  17.0k|    CheckVarIntMode<Mode, I>();
  455|  17.0k|    I n = 0;
  456|  20.0k|    while(true) {
  ------------------
  |  Branch (456:11): [Folded - Ignored]
  ------------------
  457|  20.0k|        unsigned char chData = ser_readdata8(is);
  458|  20.0k|        if (n > (std::numeric_limits<I>::max() >> 7)) {
  ------------------
  |  Branch (458:13): [True: 88, False: 19.9k]
  ------------------
  459|     88|           throw std::ios_base::failure("ReadVarInt(): size too large");
  460|     88|        }
  461|  19.9k|        n = (n << 7) | (chData & 0x7F);
  462|  19.9k|        if (chData & 0x80) {
  ------------------
  |  Branch (462:13): [True: 3.03k, False: 16.8k]
  ------------------
  463|  3.03k|            if (n == std::numeric_limits<I>::max()) {
  ------------------
  |  Branch (463:17): [True: 34, False: 2.99k]
  ------------------
  464|     34|                throw std::ios_base::failure("ReadVarInt(): size too large");
  465|     34|            }
  466|  2.99k|            n++;
  467|  16.8k|        } else {
  468|  16.8k|            return n;
  469|  16.8k|        }
  470|  19.9k|    }
  471|  17.0k|}

_ZNK4SpanIKhE4sizeEv:
  187|  26.2k|    constexpr std::size_t size() const noexcept { return m_size; }
_ZNK4SpanIhE4dataEv:
  174|  26.2k|    constexpr C* data() const noexcept { return m_data; }
_ZNK4SpanIKhE4dataEv:
  174|  20.8k|    constexpr C* data() const noexcept { return m_data; }
_ZNK4SpanISt4byteE4sizeEv:
  187|  94.1k|    constexpr std::size_t size() const noexcept { return m_size; }
_ZNK4SpanISt4byteE4dataEv:
  174|  20.8k|    constexpr C* data() const noexcept { return m_data; }
_ZNK4SpanIKhE7subspanEm:
  196|  20.8k|    {
  197|  20.8k|        ASSERT_IF_DEBUG(size() >= offset);
  198|  20.8k|        return Span<C>(m_data + offset, m_size - offset);
  199|  20.8k|    }
_ZNK4SpanIhE10size_bytesEv:
  188|  26.2k|    constexpr std::size_t size_bytes() const noexcept { return sizeof(C) * m_size; }
_ZN4SpanIKhEC2IS0_TnNSt3__19enable_ifIXsr3std14is_convertibleIPA_T_PA_S0_EE5valueEiE4typeELi0EEEPS5_m:
  119|  20.8k|    constexpr Span(T* begin, std::size_t size) noexcept : m_data(begin), m_size(size) {}
_ZN4SpanISt4byteEC2IS0_TnNSt3__19enable_ifIXsr3std14is_convertibleIPA_T_PA_S0_EE5valueEiE4typeELi0EEEPS5_m:
  119|  26.2k|    constexpr Span(T* begin, std::size_t size) noexcept : m_data(begin), m_size(size) {}
_Z15AsWritableBytesIhE4SpanISt4byteES0_IT_E:
  264|  26.2k|{
  265|  26.2k|    return {reinterpret_cast<std::byte*>(s.data()), s.size_bytes()};
  266|  26.2k|}
_ZN4SpanIhEC2IhTnNSt3__19enable_ifIXsr3std14is_convertibleIPA_T_PA_hEE5valueEiE4typeELi0EEEPS4_m:
  119|  26.2k|    constexpr Span(T* begin, std::size_t size) noexcept : m_data(begin), m_size(size) {}
_ZN4SpanIKhEC2INSt3__14spanIS0_Lm18446744073709551615EEEEERT_NS3_9enable_ifIXaaaantsr7is_SpanIS6_EE5valuesr3std14is_convertibleIPA_NS3_14remove_pointerIDTcldtclsr3stdE7declvalIS7_EE4dataEEE4typeEPA_S0_EE5valuesr3std14is_convertibleIDTcldtclsr3stdE7declvalIS7_EE4sizeEEmEE5valueEDnE4typeE:
  165|    831|        : m_data(other.data()), m_size(other.size()){}
_ZN4SpanIKjEC2INSt3__16vectorIjNS3_9allocatorIjEEEEEERT_NS3_9enable_ifIXaaaantsr7is_SpanIS8_EE5valuesr3std14is_convertibleIPA_NS3_14remove_pointerIDTcldtclsr3stdE7declvalIS9_EE4dataEEE4typeEPA_S0_EE5valuesr3std14is_convertibleIDTcldtclsr3stdE7declvalIS9_EE4sizeEEmEE5valueEDnE4typeE:
  165|  6.64k|        : m_data(other.data()), m_size(other.size()){}
_ZN4SpanIK7FeeFracEC2INSt3__16vectorIS0_NS4_9allocatorIS0_EEEEEERT_NS4_9enable_ifIXaaaantsr7is_SpanIS9_EE5valuesr3std14is_convertibleIPA_NS4_14remove_pointerIDTcldtclsr3stdE7declvalISA_EE4dataEEE4typeEPA_S1_EE5valuesr3std14is_convertibleIDTcldtclsr3stdE7declvalISA_EE4sizeEEmEE5valueEDnE4typeE:
  165|  3.32k|        : m_data(other.data()), m_size(other.size()){}
_ZN4SpanIjEC2INSt3__16vectorIjNS2_9allocatorIjEEEEEERT_NS2_9enable_ifIXaaaantsr7is_SpanIS7_EE5valuesr3std14is_convertibleIPA_NS2_14remove_pointerIDTcldtclsr3stdE7declvalIS8_EE4dataEEE4typeEPA_jEE5valuesr3std14is_convertibleIDTcldtclsr3stdE7declvalIS8_EE4sizeEEmEE5valueEDnE4typeE:
  165|  1.66k|        : m_data(other.data()), m_size(other.size()){}
_ZNK4SpanIKjE4sizeEv:
  187|  4.15k|    constexpr std::size_t size() const noexcept { return m_size; }
_ZNK4SpanIKjEixEm:
  191|  11.9k|    {
  192|  11.9k|        ASSERT_IF_DEBUG(size() > pos);
  193|  11.9k|        return m_data[pos];
  194|  11.9k|    }
_ZNK4SpanIKjE5beginEv:
  175|  6.64k|    constexpr C* begin() const noexcept { return m_data; }
_ZNK4SpanIKjE3endEv:
  176|  6.64k|    constexpr C* end() const noexcept { return m_data + m_size; }
_ZNK4SpanIKjE5emptyEv:
  189|    831|    constexpr bool empty() const noexcept { return size() == 0; }
_ZNK4SpanIKjE5frontEv:
  178|    602|    {
  179|    602|        ASSERT_IF_DEBUG(size() > 0);
  180|    602|        return m_data[0];
  181|    602|    }
_ZNK4SpanIKjE7subspanEm:
  196|  3.26k|    {
  197|  3.26k|        ASSERT_IF_DEBUG(size() >= offset);
  198|  3.26k|        return Span<C>(m_data + offset, m_size - offset);
  199|  3.26k|    }
_ZN4SpanIKjEC2IS0_TnNSt3__19enable_ifIXsr3std14is_convertibleIPA_T_PA_S0_EE5valueEiE4typeELi0EEEPS5_m:
  119|  3.26k|    constexpr Span(T* begin, std::size_t size) noexcept : m_data(begin), m_size(size) {}
_ZNK4SpanIjE4sizeEv:
  187|  36.1k|    constexpr std::size_t size() const noexcept { return m_size; }
_ZNK4SpanIjEixEm:
  191|  19.6k|    {
  192|  19.6k|        ASSERT_IF_DEBUG(size() > pos);
  193|  19.6k|        return m_data[pos];
  194|  19.6k|    }
_ZNK4SpanIjE5beginEv:
  175|  9.83k|    constexpr C* begin() const noexcept { return m_data; }
_ZNK4SpanIjE3endEv:
  176|  9.83k|    constexpr C* end() const noexcept { return m_data + m_size; }
_ZNK4SpanIK7FeeFracE4sizeEv:
  187|  17.1k|    constexpr std::size_t size() const noexcept { return m_size; }
_ZNK4SpanIK7FeeFracEixEm:
  191|  38.8k|    {
  192|  38.8k|        ASSERT_IF_DEBUG(size() > pos);
  193|  38.8k|        return m_data[pos];
  194|  38.8k|    }

_ZN10SpanReaderC2E4SpanIKhE:
  109|    831|    explicit SpanReader(Span<const unsigned char> data) : m_data{data} {}
_ZN10SpanReader4readE4SpanISt4byteE:
  122|  26.2k|    {
  123|  26.2k|        if (dst.size() == 0) {
  ------------------
  |  Branch (123:13): [True: 0, False: 26.2k]
  ------------------
  124|      0|            return;
  125|      0|        }
  126|       |
  127|       |        // Read from the beginning of the buffer
  128|  26.2k|        if (dst.size() > m_data.size()) {
  ------------------
  |  Branch (128:13): [True: 5.39k, False: 20.8k]
  ------------------
  129|  5.39k|            throw std::ios_base::failure("SpanReader::read(): end of data");
  130|  5.39k|        }
  131|  20.8k|        memcpy(dst.data(), m_data.data(), dst.size());
  132|  20.8k|        m_data = m_data.subspan(dst.size());
  133|  20.8k|    }
cluster_linearize.cpp:_ZN10SpanReaderrsI7WrapperIN12_GLOBAL__N_117DepGraphFormatterERN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEEEEERS_OT_:
  113|    831|    {
  114|    831|        ::Unserialize(*this, obj);
  115|    831|        return (*this);
  116|    831|    }
_ZN10SpanReaderrsI7WrapperI15VarIntFormatterIL10VarIntMode1EERiEEERS_OT_:
  113|  5.39k|    {
  114|  5.39k|        ::Unserialize(*this, obj);
  115|  5.39k|        return (*this);
  116|  5.39k|    }
_ZN10SpanReaderrsI7WrapperI15VarIntFormatterIL10VarIntMode0EERmEEERS_OT_:
  113|  17.0k|    {
  114|  17.0k|        ::Unserialize(*this, obj);
  115|  17.0k|        return (*this);
  116|  17.0k|    }

_Z36clusterlin_postlinearize_fuzz_targetNSt3__14spanIKhLm18446744073709551615EEE:
  934|    831|{
  935|       |    // Verify expected properties of PostLinearize() on arbitrary linearizations.
  936|       |
  937|       |    // Retrieve a depgraph from the fuzz input.
  938|    831|    SpanReader reader(buffer);
  939|    831|    DepGraph<TestBitSet> depgraph;
  940|    831|    try {
  941|    831|        reader >> Using<DepGraphFormatter>(depgraph);
  942|    831|    } catch (const std::ios_base::failure&) {}
  943|       |
  944|       |    // Retrieve a linearization from the fuzz input.
  945|    831|    std::vector<ClusterIndex> linearization;
  946|    831|    linearization = ReadLinearization(depgraph, reader);
  947|    831|    SanityCheck(depgraph, linearization);
  948|       |
  949|       |    // Produce a post-processed version.
  950|    831|    auto post_linearization = linearization;
  951|    831|    PostLinearize(depgraph, post_linearization);
  952|    831|    SanityCheck(depgraph, post_linearization);
  953|       |
  954|       |    // Compare diagrams: post-linearization cannot worsen anywhere.
  955|    831|    auto chunking = ChunkLinearization(depgraph, linearization);
  956|    831|    auto post_chunking = ChunkLinearization(depgraph, post_linearization);
  957|    831|    auto cmp = CompareChunks(post_chunking, chunking);
  958|    831|    assert(cmp >= 0);
  959|       |
  960|       |    // Run again, things can keep improving (and never get worse)
  961|    831|    auto post_post_linearization = post_linearization;
  962|    831|    PostLinearize(depgraph, post_post_linearization);
  963|    831|    SanityCheck(depgraph, post_post_linearization);
  964|    831|    auto post_post_chunking = ChunkLinearization(depgraph, post_post_linearization);
  965|    831|    cmp = CompareChunks(post_post_chunking, post_chunking);
  966|    831|    assert(cmp >= 0);
  967|       |
  968|       |    // The chunks that come out of postlinearizing are always connected.
  969|    831|    LinearizationChunking linchunking(depgraph, post_linearization);
  970|  4.09k|    while (linchunking.NumChunksLeft()) {
  ------------------
  |  Branch (970:12): [True: 3.26k, False: 831]
  ------------------
  971|  3.26k|        assert(depgraph.IsConnected(linchunking.GetChunk(0).transactions));
  972|  3.26k|        linchunking.MarkDone(linchunking.GetChunk(0).transactions);
  973|  3.26k|    }
  974|    831|}
cluster_linearize.cpp:_ZN12_GLOBAL__N_117ReadLinearizationIN13bitset_detail9IntBitSetIjEEEENSt3__16vectorIjNS4_9allocatorIjEEEERKN17cluster_linearize8DepGraphIT_EER10SpanReader:
  207|    831|{
  208|    831|    std::vector<ClusterIndex> linearization;
  209|    831|    TestBitSet todo = depgraph.Positions();
  210|       |    // In every iteration one topologically-valid transaction is appended to linearization.
  211|  5.74k|    while (todo.Any()) {
  ------------------
  |  Branch (211:12): [True: 4.91k, False: 831]
  ------------------
  212|       |        // Compute the set of transactions with no not-yet-included ancestors.
  213|  4.91k|        TestBitSet potential_next;
  214|  46.5k|        for (auto j : todo) {
  ------------------
  |  Branch (214:21): [True: 46.5k, False: 4.91k]
  ------------------
  215|  46.5k|            if ((depgraph.Ancestors(j) & todo) == TestBitSet::Singleton(j)) {
  ------------------
  |  Branch (215:17): [True: 38.8k, False: 7.62k]
  ------------------
  216|  38.8k|                potential_next.Set(j);
  217|  38.8k|            }
  218|  46.5k|        }
  219|       |        // There must always be one (otherwise there is a cycle in the graph).
  220|  4.91k|        assert(potential_next.Any());
  221|       |        // Read a number from reader, and interpret it as index into potential_next.
  222|  4.91k|        uint64_t idx{0};
  223|  4.91k|        try {
  224|  4.91k|            reader >> VARINT(idx);
  ------------------
  |  |  500|  4.91k|#define VARINT(obj) Using<VarIntFormatter<VarIntMode::DEFAULT>>(obj)
  ------------------
  225|  4.91k|        } catch (const std::ios_base::failure&) {}
  226|  4.91k|        idx %= potential_next.Count();
  227|       |        // Find out which transaction that corresponds to.
  228|  5.51k|        for (auto j : potential_next) {
  ------------------
  |  Branch (228:21): [True: 5.51k, False: 0]
  ------------------
  229|  5.51k|            if (idx == 0) {
  ------------------
  |  Branch (229:17): [True: 4.91k, False: 603]
  ------------------
  230|       |                // When found, add it to linearization and remove it from todo.
  231|  4.91k|                linearization.push_back(j);
  232|  4.91k|                assert(todo[j]);
  233|  4.91k|                todo.Reset(j);
  234|  4.91k|                break;
  235|  4.91k|            }
  236|    603|            --idx;
  237|    603|        }
  238|  4.91k|    }
  239|    831|    return linearization;
  240|    831|}

LLVMFuzzerTestOneInput:
  222|    831|{
  223|    831|    test_one_input({data, size});
  224|    831|    return 0;
  225|    831|}
fuzz.cpp:_ZL14test_one_inputNSt3__14spanIKhLm18446744073709551615EEE:
   83|    831|{
   84|    831|    CheckGlobals check{};
   85|    831|    (*Assert(g_test_one_input))(buffer);
  ------------------
  |  |   85|    831|#define Assert(val) inline_assertion_check<true>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
   86|    831|}

_ZN12CheckGlobalsC2Ev:
   56|    831|CheckGlobals::CheckGlobals() : m_impl(std::make_unique<CheckGlobalsImpl>()) {}
_ZN12CheckGlobalsD2Ev:
   57|    831|CheckGlobals::~CheckGlobals() = default;
_ZN16CheckGlobalsImplC2Ev:
   17|    831|    {
   18|    831|        g_used_g_prng = false;
   19|    831|        g_seeded_g_prng_zero = false;
   20|    831|        g_used_system_time = false;
   21|    831|        SetMockTime(0s);
   22|    831|    }
_ZN16CheckGlobalsImplD2Ev:
   24|    831|    {
   25|    831|        if (g_used_g_prng && !g_seeded_g_prng_zero) {
  ------------------
  |  Branch (25:13): [True: 0, False: 831]
  |  Branch (25:30): [True: 0, False: 0]
  ------------------
   26|      0|            std::cerr << "\n\n"
   27|      0|                         "The current fuzz target used the global random state.\n\n"
   28|       |
   29|      0|                         "This is acceptable, but requires the fuzz target to call \n"
   30|      0|                         "SeedRandomStateForTest(SeedRand::ZEROS) in the first line \n"
   31|      0|                         "of the FUZZ_TARGET function.\n\n"
   32|       |
   33|      0|                         "An alternative solution would be to avoid any use of globals.\n\n"
   34|       |
   35|      0|                         "Without a solution, fuzz instability and non-determinism can lead \n"
   36|      0|                         "to non-reproducible bugs or inefficient fuzzing.\n\n"
   37|      0|                      << std::endl;
   38|      0|            std::abort(); // Abort, because AFL may try to recover from a std::exit
   39|      0|        }
   40|       |
   41|    831|        if (g_used_system_time) {
  ------------------
  |  Branch (41:13): [True: 0, False: 831]
  ------------------
   42|      0|            std::cerr << "\n\n"
   43|      0|                         "The current fuzz target accessed system time.\n\n"
   44|       |
   45|      0|                         "This is acceptable, but requires the fuzz target to call \n"
   46|      0|                         "SetMockTime() at the beginning of processing the fuzz input.\n\n"
   47|       |
   48|      0|                         "Without setting mock time, time-dependent behavior can lead \n"
   49|      0|                         "to non-reproducible bugs or inefficient fuzzing.\n\n"
   50|      0|                      << std::endl;
   51|      0|            std::abort();
   52|      0|        }
   53|    831|    }

cluster_linearize.cpp:_ZN12_GLOBAL__N_117DepGraphFormatter5UnserI10SpanReaderN13bitset_detail9IntBitSetIjEEEEvRT_RN17cluster_linearize8DepGraphIT0_EE:
  200|    831|    {
  201|       |        /** The dependency graph which we deserialize into first, with transactions in
  202|       |         *  topological serialization order, not original cluster order. */
  203|    831|        DepGraph<SetType> topo_depgraph;
  204|       |        /** Mapping from serialization order to cluster order, used later to reconstruct the
  205|       |         *  cluster order. */
  206|    831|        std::vector<ClusterIndex> reordering;
  207|       |        /** How big the entries vector in the reconstructed depgraph will be (including holes). */
  208|    831|        ClusterIndex total_size{0};
  209|       |
  210|       |        // Read transactions in topological order.
  211|  5.39k|        while (true) {
  ------------------
  |  Branch (211:16): [Folded - Ignored]
  ------------------
  212|  5.39k|            FeeFrac new_feerate; //!< The new transaction's fee and size.
  213|  5.39k|            SetType new_ancestors; //!< The new transaction's ancestors (excluding itself).
  214|  5.39k|            uint64_t diff{0}; //!< How many potential parents/insertions we have to skip.
  215|  5.39k|            bool read_error{false};
  216|  5.39k|            try {
  217|       |                // Read size. Size 0 signifies the end of the DepGraph.
  218|  5.39k|                int32_t size;
  219|  5.39k|                s >> VARINT_MODE(size, VarIntMode::NONNEGATIVE_SIGNED);
  ------------------
  |  |  499|  5.39k|#define VARINT_MODE(obj, mode) Using<VarIntFormatter<mode>>(obj)
  ------------------
  220|  5.39k|                size &= 0x3FFFFF; // Enough for size up to 4M.
  221|  5.39k|                static_assert(0x3FFFFF >= 4000000);
  222|  5.39k|                if (size == 0 || topo_depgraph.TxCount() == SetType::Size()) break;
  ------------------
  |  Branch (222:21): [True: 302, False: 5.09k]
  |  Branch (222:34): [True: 3, False: 5.08k]
  ------------------
  223|       |                // Read fee, encoded as an unsigned varint (odd=negative, even=non-negative).
  224|  5.34k|                uint64_t coded_fee;
  225|  5.34k|                s >> VARINT(coded_fee);
  ------------------
  |  |  500|  5.34k|#define VARINT(obj) Using<VarIntFormatter<VarIntMode::DEFAULT>>(obj)
  ------------------
  226|  5.34k|                coded_fee &= 0xFFFFFFFFFFFFF; // Enough for fee between -21M...21M BTC.
  227|  5.34k|                static_assert(0xFFFFFFFFFFFFF > uint64_t{2} * 21000000 * 100000000);
  228|  5.34k|                new_feerate = {UnsignedToSigned(coded_fee), size};
  229|       |                // Read dependency information.
  230|  5.34k|                auto topo_idx = reordering.size();
  231|  5.34k|                s >> VARINT(diff);
  ------------------
  |  |  500|  5.34k|#define VARINT(obj) Using<VarIntFormatter<VarIntMode::DEFAULT>>(obj)
  ------------------
  232|  44.9k|                for (ClusterIndex dep_dist = 0; dep_dist < topo_idx; ++dep_dist) {
  ------------------
  |  Branch (232:49): [True: 39.5k, False: 5.34k]
  ------------------
  233|       |                    /** Which topo_depgraph index we are currently considering as parent of topo_idx. */
  234|  39.5k|                    ClusterIndex dep_topo_idx = topo_idx - 1 - dep_dist;
  235|       |                    // Ignore transactions which are already known ancestors of topo_idx.
  236|  39.5k|                    if (new_ancestors[dep_topo_idx]) continue;
  ------------------
  |  Branch (236:25): [True: 3.65k, False: 35.9k]
  ------------------
  237|  35.9k|                    if (diff == 0) {
  ------------------
  |  Branch (237:25): [True: 2.08k, False: 33.8k]
  ------------------
  238|       |                        // When the skip counter has reached 0, add an actual dependency.
  239|  2.08k|                        new_ancestors |= topo_depgraph.Ancestors(dep_topo_idx);
  240|       |                        // And read the number of skips after it.
  241|  2.08k|                        s >> VARINT(diff);
  ------------------
  |  |  500|  2.08k|#define VARINT(obj) Using<VarIntFormatter<VarIntMode::DEFAULT>>(obj)
  ------------------
  242|  33.8k|                    } else {
  243|       |                        // Otherwise, dep_topo_idx is not a parent. Decrement and continue.
  244|  33.8k|                        --diff;
  245|  33.8k|                    }
  246|  35.9k|                }
  247|  5.34k|            } catch (const std::ios_base::failure&) {
  248|       |                // Continue even if a read error was encountered.
  249|    779|                read_error = true;
  250|    779|            }
  251|       |            // Construct a new transaction whenever we made it past the new_feerate construction.
  252|  5.34k|            if (new_feerate.IsEmpty()) break;
  ------------------
  |  Branch (252:17): [True: 425, False: 4.91k]
  ------------------
  253|  4.91k|            assert(reordering.size() < SetType::Size());
  254|  4.91k|            auto topo_idx = topo_depgraph.AddTransaction(new_feerate);
  255|  4.91k|            topo_depgraph.AddDependencies(new_ancestors, topo_idx);
  256|  4.91k|            if (total_size < SetType::Size()) {
  ------------------
  |  Branch (256:17): [True: 1.69k, False: 3.22k]
  ------------------
  257|       |                // Normal case.
  258|  1.69k|                diff %= SetType::Size();
  259|  1.69k|                if (diff <= total_size) {
  ------------------
  |  Branch (259:21): [True: 887, False: 806]
  ------------------
  260|       |                    // Insert the new transaction at distance diff back from the end.
  261|  3.64k|                    for (auto& pos : reordering) {
  ------------------
  |  Branch (261:36): [True: 3.64k, False: 887]
  ------------------
  262|  3.64k|                        pos += (pos >= total_size - diff);
  263|  3.64k|                    }
  264|    887|                    reordering.push_back(total_size++ - diff);
  265|    887|                } else {
  266|       |                    // Append diff - total_size holes at the end, plus the new transaction.
  267|    806|                    total_size = diff;
  268|    806|                    reordering.push_back(total_size++);
  269|    806|                }
  270|  3.22k|            } else {
  271|       |                // In case total_size == SetType::Size, it is not possible to insert the new
  272|       |                // transaction without exceeding SetType's size. Instead, interpret diff as an
  273|       |                // index into the holes, and overwrite a position there. This branch is never used
  274|       |                // when deserializing the output of the serializer, but gives meaning to otherwise
  275|       |                // invalid input.
  276|  3.22k|                diff %= (SetType::Size() - reordering.size());
  277|  3.22k|                SetType holes = SetType::Fill(SetType::Size());
  278|  37.3k|                for (auto pos : reordering) holes.Reset(pos);
  ------------------
  |  Branch (278:31): [True: 37.3k, False: 3.22k]
  ------------------
  279|  53.9k|                for (auto pos : holes) {
  ------------------
  |  Branch (279:31): [True: 53.9k, False: 0]
  ------------------
  280|  53.9k|                    if (diff == 0) {
  ------------------
  |  Branch (280:25): [True: 3.22k, False: 50.7k]
  ------------------
  281|  3.22k|                        reordering.push_back(pos);
  282|  3.22k|                        break;
  283|  3.22k|                    }
  284|  50.7k|                    --diff;
  285|  50.7k|                }
  286|  3.22k|            }
  287|       |            // Stop if a read error was encountered during deserialization.
  288|  4.91k|            if (read_error) break;
  ------------------
  |  Branch (288:17): [True: 354, False: 4.56k]
  ------------------
  289|  4.91k|        }
  290|       |
  291|       |        // Construct the original cluster order depgraph.
  292|    831|        depgraph = DepGraph(topo_depgraph, reordering, total_size);
  293|    831|    }
cluster_linearize.cpp:_ZN12_GLOBAL__N_117DepGraphFormatter16UnsignedToSignedEm:
  125|  4.91k|    {
  126|  4.91k|        if (x & 1) {
  ------------------
  |  Branch (126:13): [True: 3.41k, False: 1.49k]
  ------------------
  127|  3.41k|            return -int64_t(x / 2) - 1;
  128|  3.41k|        } else {
  129|  1.49k|            return int64_t(x / 2);
  130|  1.49k|        }
  131|  4.91k|    }
cluster_linearize.cpp:_ZN12_GLOBAL__N_111SanityCheckIN13bitset_detail9IntBitSetIjEEEEvRKN17cluster_linearize8DepGraphIT_EE4SpanIKjE:
  396|  2.49k|{
  397|       |    // Check completeness.
  398|  2.49k|    assert(linearization.size() == depgraph.TxCount());
  399|  2.49k|    TestBitSet done;
  400|  14.7k|    for (auto i : linearization) {
  ------------------
  |  Branch (400:17): [True: 14.7k, False: 2.49k]
  ------------------
  401|       |        // Check transaction position is in range.
  402|  14.7k|        assert(depgraph.Positions()[i]);
  403|       |        // Check topology and lack of duplicates.
  404|  14.7k|        assert((depgraph.Ancestors(i) - done) == TestBitSet::Singleton(i));
  405|  14.7k|        done.Set(i);
  406|  14.7k|    }
  407|  2.49k|}

_ZN13bitset_detail9IntBitSetIjE4SizeEv:
  177|  23.0k|    static constexpr unsigned Size() noexcept { return MAX_SIZE; }
_ZNK13bitset_detail9IntBitSetIjEixEj:
  170|  81.0k|    {
  171|  81.0k|        Assume(pos < MAX_SIZE);
  ------------------
  |  |   97|  81.0k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  172|  81.0k|        return (m_val >> pos) & 1U;
  173|  81.0k|    }
_ZN13bitset_detail9IntBitSetIjE3SetEj:
  152|  76.9k|    {
  153|  76.9k|        Assume(pos < MAX_SIZE);
  ------------------
  |  |   97|  76.9k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  154|  76.9k|        m_val |= I{1U} << pos;
  155|  76.9k|    }
_ZN13bitset_detail9IntBitSetIjE5ResetEj:
  164|  47.2k|    {
  165|  47.2k|        Assume(pos < MAX_SIZE);
  ------------------
  |  |   97|  47.2k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  166|  47.2k|        m_val &= ~I(I{1U} << pos);
  167|  47.2k|    }
_ZN13bitset_detail9IntBitSetIjE9SingletonEj:
  138|   108k|    {
  139|   108k|        Assume(i < MAX_SIZE);
  ------------------
  |  |   97|   108k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  140|   108k|        return IntBitSet(I(1U) << i);
  141|   108k|    }
_ZN13bitset_detail9IntBitSetIjEC2Ej:
   71|   191k|    IntBitSet(I val) noexcept : m_val{val} {}
_ZNK13bitset_detail9IntBitSetIjE3AnyEv:
  181|  25.4k|    constexpr bool Any() const noexcept { return !None(); }
_ZNK13bitset_detail9IntBitSetIjE4NoneEv:
  179|  39.3k|    constexpr bool None() const noexcept { return m_val == 0; }
_ZNK13bitset_detail9IntBitSetIjE5FirstEv:
  188|  8.18k|    {
  189|  8.18k|        Assume(m_val != 0);
  ------------------
  |  |   97|  8.18k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  190|  8.18k|        return std::countr_zero(m_val);
  191|  8.18k|    }
_ZNK13bitset_detail9IntBitSetIjE4LastEv:
  194|    602|    {
  195|    602|        Assume(m_val != 0);
  ------------------
  |  |   97|    602|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  196|    602|        return std::bit_width(m_val) - 1;
  197|    602|    }
_ZNK13bitset_detail9IntBitSetIjE5CountEv:
  175|  17.4k|    constexpr unsigned Count() const noexcept { return PopCount(m_val); }
_ZN13bitset_detail8PopCountIjEEjT_:
   39|  17.4k|{
   40|  17.4k|    static_assert(std::is_integral_v<I> && std::is_unsigned_v<I> && std::numeric_limits<I>::radix == 2);
   41|  17.4k|    constexpr auto BITS = std::numeric_limits<I>::digits;
   42|       |    // Algorithms from https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation.
   43|       |    // These seem to be faster than std::popcount when compiling for non-SSE4 on x86_64.
   44|  17.4k|    if constexpr (BITS <= 32) {
   45|  17.4k|        v -= (v >> 1) & 0x55555555;
   46|  17.4k|        v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
   47|  17.4k|        v = (v + (v >> 4)) & 0x0f0f0f0f;
   48|  17.4k|        if constexpr (BITS > 8) v += v >> 8;
   49|  17.4k|        if constexpr (BITS > 16) v += v >> 16;
   50|  17.4k|        return v & 0x3f;
   51|       |    } else {
   52|       |        static_assert(BITS <= 64);
   53|       |        v -= (v >> 1) & 0x5555555555555555;
   54|       |        v = (v & 0x3333333333333333) + ((v >> 2) & 0x3333333333333333);
   55|       |        v = (v + (v >> 4)) & 0x0f0f0f0f0f0f0f0f;
   56|       |        return (v * uint64_t{0x0101010101010101}) >> 56;
   57|       |    }
   58|  17.4k|}
_ZN13bitset_detail9IntBitSetIjEC2Ev:
  119|   132k|    constexpr IntBitSet() noexcept : m_val{0} {}
_ZN13bitset_detail9IntBitSetIjE4FillEj:
  144|  3.22k|    {
  145|  3.22k|        IntBitSet ret;
  146|  3.22k|        Assume(count <= MAX_SIZE);
  ------------------
  |  |   97|  3.22k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  147|  3.22k|        if (count) ret.m_val = I(~I{0}) >> (MAX_SIZE - count);
  ------------------
  |  Branch (147:13): [True: 3.22k, False: 0]
  ------------------
  148|  3.22k|        return ret;
  149|  3.22k|    }
_ZNK13bitset_detail9IntBitSetIjE5beginEv:
  183|  43.8k|    constexpr Iterator begin() const noexcept { return Iterator(m_val); }
_ZN13bitset_detail9IntBitSetIjE8IteratorC2Ej:
   86|  43.8k|        constexpr Iterator(I val) noexcept : m_val(val), m_pos(0)
   87|  43.8k|        {
   88|  43.8k|            if (m_val != 0) m_pos = std::countr_zero(m_val);
  ------------------
  |  Branch (88:17): [True: 26.7k, False: 17.1k]
  ------------------
   89|  43.8k|        }
_ZN13bitset_detaileqERKNS_9IntBitSetIjE8IteratorERKNS1_11IteratorEndE:
   98|   191k|        {
   99|   191k|            return a.m_val == 0;
  100|   191k|        }
_ZNK13bitset_detail9IntBitSetIjE3endEv:
  185|  43.8k|    constexpr IteratorEnd end() const noexcept { return IteratorEnd(); }
_ZNK13bitset_detail9IntBitSetIjE8IteratordeEv:
  111|   155k|        {
  112|   155k|            Assume(m_val != 0);
  ------------------
  |  |   97|   155k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  113|   155k|            return m_pos;
  114|   155k|        }
_ZN13bitset_detail9IntBitSetIjE8IteratorppEv:
  103|   147k|        {
  104|   147k|            Assume(m_val != 0);
  ------------------
  |  |   97|   147k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  105|   147k|            m_val &= m_val - I{1U};
  106|   147k|            if (m_val != 0) m_pos = std::countr_zero(m_val);
  ------------------
  |  Branch (106:17): [True: 128k, False: 18.5k]
  ------------------
  107|   147k|            return *this;
  108|   147k|        }
_ZN13bitset_detail9IntBitSetIjEoRERKS1_:
  199|  56.5k|    constexpr IntBitSet& operator|=(const IntBitSet& a) noexcept { m_val |= a.m_val; return *this; }
_ZN13bitset_detail9IntBitSetIjEaNERKS1_:
  201|  6.56k|    constexpr IntBitSet& operator&=(const IntBitSet& a) noexcept { m_val &= a.m_val; return *this; }
_ZN13bitset_detail9IntBitSetIjEmIERKS1_:
  203|  19.5k|    constexpr IntBitSet& operator-=(const IntBitSet& a) noexcept { m_val &= ~a.m_val; return *this; }
_ZN13bitset_detailanERKNS_9IntBitSetIjEES3_:
  209|  46.5k|    friend constexpr IntBitSet operator&(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val & b.m_val); }
_ZN13bitset_detailmiERKNS_9IntBitSetIjEES3_:
  213|  36.0k|    friend constexpr IntBitSet operator-(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val & ~b.m_val); }
_ZNK13bitset_detail9IntBitSetIjE10IsSubsetOfERKS1_:
  221|  13.0k|    constexpr bool IsSubsetOf(const IntBitSet& a) const noexcept { return (m_val & ~a.m_val) == 0; }
_ZN13bitset_detaileqERKNS_9IntBitSetIjEES3_:
  217|  67.7k|    friend constexpr bool operator==(const IntBitSet& a, const IntBitSet& b) noexcept = default;
_ZNK13bitset_detail9IntBitSetIjE8OverlapsERKS1_:
  207|  16.5k|    constexpr bool Overlaps(const IntBitSet& a) const noexcept { return m_val & a.m_val; }

_Z22inline_assertion_checkILb0EbEOT0_S1_PKciS3_S3_:
   52|   759k|{
   53|   759k|    if (IS_ASSERT || std::is_constant_evaluated() || G_FUZZING
  ------------------
  |  Branch (53:9): [Folded - Ignored]
  |  Branch (53:22): [Folded - Ignored]
  |  Branch (53:54): [Folded - Ignored]
  ------------------
   54|       |#ifdef ABORT_ON_FAILED_ASSUME
   55|       |        || true
   56|       |#endif
   57|   759k|    ) {
   58|   759k|        if (!val) {
  ------------------
  |  Branch (58:13): [True: 0, False: 759k]
  ------------------
   59|      0|            assertion_fail(file, line, func, assertion);
   60|      0|        }
   61|   759k|    }
   62|   759k|    return std::forward<T>(val);
   63|   759k|}
_Z22inline_assertion_checkILb1EbEOT0_S1_PKciS3_S3_:
   52|    831|{
   53|    831|    if (IS_ASSERT || std::is_constant_evaluated() || G_FUZZING
  ------------------
  |  Branch (53:9): [Folded - Ignored]
  |  Branch (53:22): [Folded - Ignored]
  |  Branch (53:54): [Folded - Ignored]
  ------------------
   54|       |#ifdef ABORT_ON_FAILED_ASSUME
   55|       |        || true
   56|       |#endif
   57|    831|    ) {
   58|    831|        if (!val) {
  ------------------
  |  Branch (58:13): [True: 0, False: 831]
  ------------------
   59|      0|            assertion_fail(file, line, func, assertion);
   60|      0|        }
   61|    831|    }
   62|    831|    return std::forward<T>(val);
   63|    831|}
_Z22inline_assertion_checkILb1ERPKNSt3__18functionIFvNS0_4spanIKhLm18446744073709551615EEEEEEEOT0_SB_PKciSD_SD_:
   52|    831|{
   53|    831|    if (IS_ASSERT || std::is_constant_evaluated() || G_FUZZING
  ------------------
  |  Branch (53:9): [Folded - Ignored]
  |  Branch (53:22): [Folded - Ignored]
  |  Branch (53:54): [Folded - Ignored]
  ------------------
   54|       |#ifdef ABORT_ON_FAILED_ASSUME
   55|       |        || true
   56|       |#endif
   57|    831|    ) {
   58|    831|        if (!val) {
  ------------------
  |  Branch (58:13): [True: 0, False: 831]
  ------------------
   59|      0|            assertion_fail(file, line, func, assertion);
   60|      0|        }
   61|    831|    }
   62|    831|    return std::forward<T>(val);
   63|    831|}

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

_ZN7FeeFrac3MulEli:
   55|   129k|    {
   56|       |        // If __int128 is available, use 128-bit wide multiply.
   57|   129k|        return __int128{a} * b;
   58|   129k|    }
_ZN7FeeFracC2Ev:
   67|  56.2k|    constexpr inline FeeFrac() noexcept : fee{0}, size{0} {}
_ZN7FeeFracC2Eli:
   70|  46.3k|    constexpr inline FeeFrac(int64_t f, int32_t s) noexcept : fee{f}, size{s} {}
_ZNK7FeeFrac7IsEmptyEv:
   76|  8.66k|    bool inline IsEmpty() const noexcept {
   77|  8.66k|        return size == 0;
   78|  8.66k|    }
_ZN7FeeFracpLERKS_:
   82|  26.3k|    {
   83|  26.3k|        fee += other.fee;
   84|  26.3k|        size += other.size;
   85|  26.3k|    }
_ZplRK7FeeFracS1_:
   96|  27.6k|    {
   97|  27.6k|        return {a.fee + b.fee, a.size + b.size};
   98|  27.6k|    }
_ZmiRK7FeeFracS1_:
  102|  13.8k|    {
  103|  13.8k|        return {a.fee - b.fee, a.size - b.size};
  104|  13.8k|    }
_Z14FeeRateCompareRK7FeeFracS1_:
  114|  6.91k|    {
  115|  6.91k|        auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
  116|  6.91k|        return cross_a <=> cross_b;
  117|  6.91k|    }
_ZrsRK7FeeFracS1_:
  128|  57.7k|    {
  129|  57.7k|        auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
  130|  57.7k|        return cross_a > cross_b;
  131|  57.7k|    }

_Z11SetMockTimeNSt3__16chrono8durationIxNS_5ratioILl1ELl1EEEEE:
   42|    831|{
   43|    831|    Assert(mock_time_in >= 0s);
  ------------------
  |  |   85|    831|#define Assert(val) inline_assertion_check<true>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
   44|    831|    g_mock_time.store(mock_time_in, std::memory_order_relaxed);
   45|    831|}