core/slice/sort/stable/
merge.rs

Help
1//! This module contains logic for performing a merge of two sorted sub-slices.
2
3use crate::mem::MaybeUninit;
4use crate::{cmp, ptr};
5
6/// Merges non-decreasing runs `v[..mid]` and `v[mid..]` using `scratch` as
7/// temporary storage, and stores the result into `v[..]`.
8pub fn merge<T, F: FnMut(&T, &T) -> bool>(
9    v: &mut [T],
10    scratch: &mut [MaybeUninit<T>],
11    mid: usize,
12    is_less: &mut F,
13) {
14    let len = v.len();
15
16    if mid == 0 || mid >= len || scratch.len() < cmp::min(mid, len - mid) {
17        return;
18    }
19
20    // SAFETY: We checked that the two slices are non-empty and `mid` is in-bounds.
21    // We checked that the buffer `scratch` has enough capacity to hold a copy of
22    // the shorter slice. `merge_up` and `merge_down` are written in such a way that
23    // they uphold the contract described in `MergeState::drop`.
24    unsafe {
25        // The merge process first copies the shorter run into `buf`. Then it traces
26        // the newly copied run and the longer run forwards (or backwards), comparing
27        // their next unconsumed elements and copying the lesser (or greater) one into `v`.
28        //
29        // As soon as the shorter run is fully consumed, the process is done. If the
30        // longer run gets consumed first, then we must copy whatever is left of the
31        // shorter run into the remaining gap in `v`.
32        //
33        // Intermediate state of the process is always tracked by `gap`, which serves
34        // two purposes:
35        //  1. Protects integrity of `v` from panics in `is_less`.
36        //  2. Fills the remaining gap in `v` if the longer run gets consumed first.
37
38        let buf = MaybeUninit::slice_as_mut_ptr(scratch);
39
40        let v_base = v.as_mut_ptr();
41        let v_mid = v_base.add(mid);
42        let v_end = v_base.add(len);
43
44        let left_len = mid;
45        let right_len = len - mid;
46
47        let left_is_shorter = left_len <= right_len;
48        let save_base = if left_is_shorter { v_base } else { v_mid };
49        let save_len = if left_is_shorter { left_len } else { right_len };
50
51        ptr::copy_nonoverlapping(save_base, buf, save_len);
52
53        let mut merge_state = MergeState { start: buf, end: buf.add(save_len), dst: save_base };
54
55        if left_is_shorter {
56            merge_state.merge_up(v_mid, v_end, is_less);
57        } else {
58            merge_state.merge_down(v_base, buf, v_end, is_less);
59        }
60        // Finally, `merge_state` gets dropped. If the shorter run was not fully
61        // consumed, whatever remains of it will now be copied into the hole in `v`.
62    }
63}
64
65// When dropped, copies the range `start..end` into `dst..`.
66struct MergeState<T> {
67    start: *mut T,
68    end: *mut T,
69    dst: *mut T,
70}
71
72impl<T> MergeState<T> {
73    /// # Safety
74    /// The caller MUST guarantee that `self` is initialized in a way where `start -> end` is
75    /// the longer sub-slice and so that `dst` can be written to at least the shorter sub-slice
76    /// length times. In addition `start -> end` and `right -> right_end` MUST be valid to be
77    /// read. This function MUST only be called once.
78    unsafe fn merge_up<F: FnMut(&T, &T) -> bool>(
79        &mut self,
80        mut right: *const T,
81        right_end: *const T,
82        is_less: &mut F,
83    ) {
84        // SAFETY: See function safety comment.
85        unsafe {
86            let left = &mut self.start;
87            let out = &mut self.dst;
88
89            while *left != self.end && right as *const T != right_end {
90                let consume_left = !is_less(&*right, &**left);
91
92                let src = if consume_left { *left } else { right };
93                ptr::copy_nonoverlapping(src, *out, 1);
94
95                *left = left.add(consume_left as usize);
96                right = right.add(!consume_left as usize);
97
98                *out = out.add(1);
99            }
100        }
101    }
102
103    /// # Safety
104    /// The caller MUST guarantee that `self` is initialized in a way where `left_end <- dst` is
105    /// the shorter sub-slice and so that `out` can be written to at least the shorter sub-slice
106    /// length times. In addition `left_end <- dst` and `right_end <- end` MUST be valid to be
107    /// read. This function MUST only be called once.
108    unsafe fn merge_down<F: FnMut(&T, &T) -> bool>(
109        &mut self,
110        left_end: *const T,
111        right_end: *const T,
112        mut out: *mut T,
113        is_less: &mut F,
114    ) {
115        // SAFETY: See function safety comment.
116        unsafe {
117            loop {
118                let left = self.dst.sub(1);
119                let right = self.end.sub(1);
120                out = out.sub(1);
121
122                let consume_left = is_less(&*right, &*left);
123
124                let src = if consume_left { left } else { right };
125                ptr::copy_nonoverlapping(src, out, 1);
126
127                self.dst = left.add(!consume_left as usize);
128                self.end = right.add(consume_left as usize);
129
130                if self.dst as *const T == left_end || self.end as *const T == right_end {
131                    break;
132                }
133            }
134        }
135    }
136}
137
138impl<T> Drop for MergeState<T> {
139    fn drop(&mut self) {
140        // SAFETY: The user of MergeState MUST ensure, that at any point this drop
141        // impl MAY run, for example when the user provided `is_less` panics, that
142        // copying the contiguous region between `start` and `end` to `dst` will
143        // leave the input slice `v` with each original element and all possible
144        // modifications observed.
145        unsafe {
146            let len = self.end.offset_from_unsigned(self.start);
147            ptr::copy_nonoverlapping(self.start, self.dst, len);
148        }
149    }
150}
core/slice/sort/stable/merge.rs

core/slice/sort/stable/
merge.rs
