-
Notifications
You must be signed in to change notification settings - Fork 18
/
hoare_crumsort.rs
150 lines (123 loc) · 4.3 KB
/
hoare_crumsort.rs
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
use core::mem::MaybeUninit;
use core::ptr;
partition_impl!("hoare_crumsort");
struct FulcrumState<T> {
r_ptr: *mut T,
x_ptr: *mut T,
elem_i: usize,
}
#[inline(always)]
unsafe fn fulcrum_rotate<T, F>(
arr_ptr: *mut T,
state: &mut FulcrumState<T>,
offset_val: isize,
loop_len: usize,
pivot: &T,
is_less: &mut F,
) where
F: FnMut(&T, &T) -> bool,
{
for _ in 0..loop_len {
let is_l = is_less(&*state.x_ptr, pivot);
let target_ptr = if is_l {
arr_ptr.add(state.elem_i)
} else {
state.r_ptr.add(state.elem_i)
};
ptr::copy(state.x_ptr, target_ptr, 1);
state.elem_i += is_l as usize;
state.x_ptr = state.x_ptr.wrapping_offset(offset_val);
state.r_ptr = state.r_ptr.wrapping_sub(1);
}
}
unsafe fn small_aux_partition<T, F>(
v: &mut [T],
swap_ptr: *mut T,
pivot: &T,
is_less: &mut F,
) -> usize
where
F: FnMut(&T, &T) -> bool,
{
let len = v.len();
let arr_ptr = v.as_mut_ptr();
// SAFETY: TODO
unsafe {
let mut swap_ptr_l = swap_ptr;
let mut swap_ptr_r = swap_ptr.add(len - 1);
// This could probably be sped-up by interleaving the two loops.
for i in 0..len {
let elem_ptr = arr_ptr.add(i);
let is_l = is_less(&*elem_ptr, pivot);
let target_ptr = if is_l { swap_ptr_l } else { swap_ptr_r };
ptr::copy_nonoverlapping(elem_ptr, target_ptr, 1);
swap_ptr_l = swap_ptr_l.add(is_l as usize);
swap_ptr_r = swap_ptr_r.sub(!is_l as usize);
}
// SAFETY: swap now contains all elements that belong on the left side of the pivot. All
// comparisons have been done if is_less would have panicked v would have stayed untouched.
// Now that swap has the correct order overwrite arr_ptr.
ptr::copy_nonoverlapping(swap_ptr, arr_ptr, len);
swap_ptr_l.sub_ptr(swap_ptr)
}
}
// This function is *NOT* safe-to-use for non `Freeze` types.
fn partition<T, F: FnMut(&T, &T) -> bool>(v: &mut [T], pivot: &T, is_less: &mut F) -> usize {
// Novel partition implementation by Igor van den Hoven as part of his work in quadsort and
// crumsort.
let len = v.len();
const ROTATION_ELEMS: usize = 32;
let advance_left = |a_ptr: *const T, arr_ptr: *const T, elem_i: usize| -> bool {
// SAFETY: TODO
unsafe { (a_ptr.sub_ptr(arr_ptr) - elem_i) <= ROTATION_ELEMS }
};
let mut swap = MaybeUninit::<[T; ROTATION_ELEMS * 2]>::uninit();
let swap_ptr = swap.as_mut_ptr() as *mut T;
let arr_ptr = v.as_mut_ptr();
// SAFETY: TODO
unsafe {
if len <= (ROTATION_ELEMS * 2) {
return small_aux_partition(v, swap_ptr, pivot, is_less);
}
}
// SAFETY: TODO
unsafe {
ptr::copy_nonoverlapping(arr_ptr, swap_ptr, ROTATION_ELEMS);
ptr::copy_nonoverlapping(
arr_ptr.add(len - ROTATION_ELEMS),
swap_ptr.add(ROTATION_ELEMS),
ROTATION_ELEMS,
);
let mut state = FulcrumState {
r_ptr: arr_ptr.add(len - 1),
x_ptr: ptr::null_mut(),
elem_i: 0,
};
let mut a_ptr = arr_ptr.add(ROTATION_ELEMS);
let mut t_ptr = arr_ptr.add(len - (ROTATION_ELEMS + 1));
for _ in 0..((len / ROTATION_ELEMS) - 2) {
let loop_len = ROTATION_ELEMS;
if advance_left(a_ptr, arr_ptr, state.elem_i) {
state.x_ptr = a_ptr;
fulcrum_rotate(arr_ptr, &mut state, 1, loop_len, pivot, is_less);
a_ptr = state.x_ptr;
} else {
state.x_ptr = t_ptr;
fulcrum_rotate(arr_ptr, &mut state, -1, loop_len, pivot, is_less);
t_ptr = state.x_ptr;
}
}
let loop_len = len % ROTATION_ELEMS;
if advance_left(a_ptr, arr_ptr, state.elem_i) {
state.x_ptr = a_ptr;
fulcrum_rotate(arr_ptr, &mut state, 1, loop_len, pivot, is_less);
} else {
state.x_ptr = t_ptr;
fulcrum_rotate(arr_ptr, &mut state, -1, loop_len, pivot, is_less);
}
let loop_len = ROTATION_ELEMS * 2;
state.x_ptr = swap_ptr;
fulcrum_rotate(arr_ptr, &mut state, 1, loop_len, pivot, is_less);
state.elem_i
}
}