Here is an algorithm that reorders an array arr
given an array of indices indices
in such a way that every element arr[i]
is moved to arr[indices[i]]
after the reordering. This is done with only O(1) space.
Input: arr[] = [50, 40, 70, 60, 90]
indices[] = [3, 0, 4, 1, 2]
Output: arr[] = [40, 60, 90, 50, 70]
indices[] = [0, 1, 2, 3, 4]
There is a crate implementing this algorithm, which contained some undefined behaviors. I am trying to fix it up but I can't be too sure the resulting code is UB-free.
My Implementation:
pub fn reorder_index<A>(arr: &mut [A], indices: &mut [usize]) {
assert_eq!(arr.len(), indices.len());
let arr = unsafe { &mut *(arr as *mut [A] as *mut [MaybeUninit<A>]) };
for i in 0..arr.len() {
while indices[i] != i {
let old_target_i = indices[indices[i]];
//let old_target_e = arr[index[i]];
let mut old_target_e = std::mem::MaybeUninit::<A>::uninit();
unsafe {
old_target_e
.as_mut_ptr()
.write(arr[indices[i]].as_ptr().read());
}
// arr[index[i]] = arr[i];
// Since the object arr[index[i]] is aliased to old_target_e, we cannot produce
// mutable reference to it nor assign to it.
unsafe {
arr[indices[i]].as_mut_ptr().write(arr[i].as_ptr().read());
}
// Now that old_target_e is not longer aliased, we can call assume_init
let old_target_e = unsafe { old_target_e.assume_init() };
indices[indices[i]] = indices[i];
indices[i] = old_target_i;
//arr[i] = old_target_e;
// arr[i] is aliased to arr[index[i]
arr[i].as_mut_ptr().write(old_target_e);
}
}
}
I tested somewhat thoroughly locally and the business logic seems to be correct. It would be great if you guys can spot some more memory bugs.