| 1858 | */ |
| 1859 | template<typename SetType> |
| 1860 | void PostLinearize(const DepGraph<SetType>& depgraph, std::span<DepGraphIndex> linearization) |
| 1861 | { |
| 1862 | // This algorithm performs a number of passes (currently 2); the even ones operate from back to |
| 1863 | // front, the odd ones from front to back. Each results in an equal-or-better linearization |
| 1864 | // than the one started from. |
| 1865 | // - One pass in either direction guarantees that the resulting chunks are connected. |
| 1866 | // - Each direction corresponds to one shape of tree being linearized optimally (forward passes |
| 1867 | // guarantee this for graphs where each transaction has at most one child; backward passes |
| 1868 | // guarantee this for graphs where each transaction has at most one parent). |
| 1869 | // - Starting with a backward pass guarantees the moved-tree property. |
| 1870 | // |
| 1871 | // During an odd (forward) pass, the high-level operation is: |
| 1872 | // - Start with an empty list of groups L=[]. |
| 1873 | // - For every transaction i in the old linearization, from front to back: |
| 1874 | // - Append a new group C=[i], containing just i, to the back of L. |
| 1875 | // - While L has at least one group before C, and the group immediately before C has feerate |
| 1876 | // lower than C: |
| 1877 | // - If C depends on P: |
| 1878 | // - Merge P into C, making C the concatenation of P+C, continuing with the combined C. |
| 1879 | // - Otherwise: |
| 1880 | // - Swap P with C, continuing with the now-moved C. |
| 1881 | // - The output linearization is the concatenation of the groups in L. |
| 1882 | // |
| 1883 | // During even (backward) passes, i iterates from the back to the front of the existing |
| 1884 | // linearization, and new groups are prepended instead of appended to the list L. To enable |
| 1885 | // more code reuse, both passes append groups, but during even passes the meanings of |
| 1886 | // parent/child, and of high/low feerate are reversed, and the final concatenation is reversed |
| 1887 | // on output. |
| 1888 | // |
| 1889 | // In the implementation below, the groups are represented by singly-linked lists (pointing |
| 1890 | // from the back to the front), which are themselves organized in a singly-linked circular |
| 1891 | // list (each group pointing to its predecessor, with a special sentinel group at the front |
| 1892 | // that points back to the last group). |
| 1893 | // |
| 1894 | // Information about transaction t is stored in entries[t + 1], while the sentinel is in |
| 1895 | // entries[0]. |
| 1896 | |
| 1897 | /** Index of the sentinel in the entries array below. */ |
| 1898 | static constexpr DepGraphIndex SENTINEL{0}; |
| 1899 | /** Indicator that a group has no previous transaction. */ |
| 1900 | static constexpr DepGraphIndex NO_PREV_TX{0}; |
| 1901 | |
| 1902 | |
| 1903 | /** Data structure per transaction entry. */ |
| 1904 | struct TxEntry |
| 1905 | { |
| 1906 | /** The index of the previous transaction in this group; NO_PREV_TX if this is the first |
| 1907 | * entry of a group. */ |
| 1908 | DepGraphIndex prev_tx; |
| 1909 | |
| 1910 | // The fields below are only used for transactions that are the last one in a group |
| 1911 | // (referred to as tail transactions below). |
| 1912 | |
| 1913 | /** Index of the first transaction in this group, possibly itself. */ |
| 1914 | DepGraphIndex first_tx; |
| 1915 | /** Index of the last transaction in the previous group. The first group (the sentinel) |
| 1916 | * points back to the last group here, making it a singly-linked circular list. */ |
| 1917 | DepGraphIndex prev_group; |