glidesort 0.1.2

Glidesort sorting algorithm
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

use crate::mut_slice::states::{Init, Uninit, Weak};
use crate::mut_slice::{Brand, MutSlice};
use crate::tracking::ptr;
use crate::util::*;

/// A struct that makes sure the gap is always filled.
pub struct GapGuard<'data, 'gap, DataB, GapB, T> {
    data: MutSlice<'data, DataB, T, Weak>,
    gap: MutSlice<'gap, GapB, T, Weak>,
}

impl<'data, 'gap, DataB: Brand, GapB: Brand, T> GapGuard<'data, 'gap, DataB, GapB, T> {
    pub fn new_disjoint(
        data: MutSlice<'data, DataB, T, Init>,
        gap: MutSlice<'gap, GapB, T, Uninit>,
    ) -> Self {
        unsafe { Self::new_unchecked(data.weak(), gap.weak()) }
    }

    /// SAFETY: it is the caller's responsibility to make sure that when any
    /// method other than len, split_at, concat, data_weak or gap_weak is called,
    /// or when this struct is dropped, that data is Init.
    pub unsafe fn new_unchecked(
        data: MutSlice<'data, DataB, T, Weak>,
        gap: MutSlice<'gap, GapB, T, Weak>,
    ) -> Self {
        if data.len() != gap.len() {
            abort();
        }

        Self { data, gap }
    }

    pub fn len(&self) -> usize {
        self.data.len()
    }

    pub fn data_weak(&self) -> MutSlice<'data, DataB, T, Weak> {
        self.data.weak()
    }

    pub fn gap_weak(&self) -> MutSlice<'gap, GapB, T, Weak> {
        self.gap.weak()
    }

    pub fn split_at(self, i: usize) -> Option<(Self, Self)> {
        unsafe {
            let (data, gap) = self.take_disjoint();
            if let Some((dl, dr)) = data.split_at(i) {
                let (gl, gr) = gap.split_at(i).unwrap_abort();
                Some((
                    GapGuard::new_disjoint(dl, gl),
                    GapGuard::new_disjoint(dr, gr),
                ))
            } else {
                None
            }
        }
    }

    pub fn take_data(self) -> MutSlice<'data, DataB, T, Init> {
        unsafe {
            let data = self.data.weak();
            core::mem::forget(self);
            data.upgrade().assume_init()
        }
    }

    pub fn as_mut_slice(&mut self) -> &mut [T] {
        unsafe {
            let begin = self.data.begin();
            core::slice::from_raw_parts_mut(begin, self.data.len())
        }
    }

    /// Borrows the gap slice.
    ///
    /// SAFETY: the gap must be disjoint from the data.
    pub unsafe fn borrow_gap<'a>(&'a mut self) -> MutSlice<'a, GapB, T, Uninit> {
        unsafe { self.gap.clone().upgrade().assume_uninit() }
    }

    /// SAFETY: it is now the callers responsibility to make sure the gap is
    /// always filled. The data and gap slices must be disjoint.
    pub unsafe fn take_disjoint(
        self,
    ) -> (
        MutSlice<'data, DataB, T, Init>,
        MutSlice<'gap, GapB, T, Uninit>,
    ) {
        unsafe {
            let data = self.data.weak();
            let gap = self.gap.weak();
            core::mem::forget(self);
            (data.upgrade().assume_init(), gap.upgrade().assume_uninit())
        }
    }
}

impl<'gap, 'data, GapB, DataB, T> Drop for GapGuard<'gap, 'data, GapB, DataB, T> {
    #[inline(never)]
    #[cold]
    fn drop(&mut self) {
        unsafe {
            let data_ptr = self.data.begin();
            let gap_ptr = self.gap.begin();
            ptr::copy(data_ptr, gap_ptr, self.data.len());
        }
    }
}