Lines Matching defs:runs
8200 // runs in Miri, which would detect such problems.
9670 // Sort with many pre-sorted runs.
22873 /// Merges non-decreasing runs `v[..mid]` and `v[mid..]` using `buf` as temporary storage, and
22992 /// natural runs. There is a stack of pending runs yet to be merged. Each newly found run is pushed
22993 /// onto the stack, and then some pairs of adjacent runs are merged until these two invariants are
22996 /// 1. for every `i` in `1..runs.len()`: `runs[i - 1].len > runs[i].len`
22997 /// 2. for every `i` in `2..runs.len()`: `runs[i - 2].len > runs[i - 1].len + runs[i].len`
23006 // Very short runs are extended using insertion sort to span at least this many elements.
23028 // `is_less` panics. When merging two sorted runs, this buffer holds a copy of the shorter run,
23032 // In order to identify natural runs in `v`, we traverse it backwards. That might seem like a
23035 // backwards. To conclude, identifying runs by traversing backwards improves performance.
23036 let mut runs = vec![];
23066 runs.push(Run { start, len: end - start });
23069 // Merge some pairs of adjacent runs to satisfy the invariants.
23070 while let Some(r) = collapse(&runs) {
23071 let left = runs[r + 1];
23072 let right = runs[r];
23081 runs[r] = Run { start: left.start, len: left.len + right.len };
23082 runs.remove(r + 1);
23087 debug_assert!(runs.len() == 1 && runs[0].start == 0 && runs[0].len == len);
23089 // Examines the stack of runs and identifies the next pair of runs to merge. More specifically,
23090 // if `Some(r)` is returned, that means `runs[r]` and `runs[r + 1]` must be merged next. If the
23096 // The gist of the story is: we must enforce the invariants on the top four runs on the stack.
23098 // hold for *all* runs in the stack.
23100 // This function correctly checks invariants for the top four runs. Additionally, if the top
23104 fn collapse(runs: &[Run]) -> Option<usize> {
23105 let n = runs.len();
23107 && (runs[n - 1].start == 0
23108 || runs[n - 2].len <= runs[n - 1].len
23109 || (n >= 3 && runs[n - 3].len <= runs[n - 2].len + runs[n - 1].len)
23110 || (n >= 4 && runs[n - 4].len <= runs[n - 3].len + runs[n - 2].len))
23112 if n >= 3 && runs[n - 3].len < runs[n - 1].len { Some(n - 3) } else { Some(n - 2) }
23147 /// A basic `block_on` function that takes a future and runs it to completion on
27926 // Continue the same loop we do below. This only runs when a destructor has
31250 // Continue the same loop we perform below. This only runs when unwinding, so we