Skip to main content

search_share

Function search_share 

Source
fn search_share<P>(
    share: usize,
    unusable: impl Fn(&P) -> bool,
    search: impl FnMut(usize) -> Vec<P>,
) -> Vec<P>
Expand description

One first relayer’s continuations for its share of the pool.

Some continuations are unusable and dropped from the share: those of no value, and those that run through the source, which the single traversal from the source never returns but one that starts past it can. They must not take the places of usable ones, so while too few of the paths a search found are usable, the search is asked again for twice as many. The traversal shuffles each node’s edges, so every search is a fresh draw that keeps what it found first.

Returns the paths of the first search that found share usable, or every continuation there is, or else those of the last of SHARE_SEARCHES searches. Doubling bounds the work where nearly every continuation is unusable, as in a subtree that reaches the destination only past the source: such a share stays short rather than paying a search per continuation.