Created
December 31, 2022 00:19
-
-
Save kkolyan/72275945b97f162bb8badd1a4783b65d to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| use std::alloc::{alloc, dealloc, Layout}; | |
| use std::mem; | |
| use std::ptr::null_mut; | |
| struct Node<T> { | |
| value: T, | |
| next: *mut Node<T>, | |
| } | |
| fn create_list<T>(values: Vec<T>) -> *mut Node<T> { | |
| unsafe fn allocate<T>(value: T) -> *mut T { | |
| let ptr = alloc(Layout::new::<T>()) as *mut T; | |
| *ptr = value; | |
| ptr | |
| } | |
| let mut node: *mut Node<T> = null_mut(); | |
| for value in values.into_iter().rev() { | |
| unsafe { | |
| node = allocate(Node { | |
| value, | |
| next: node, | |
| }); | |
| } | |
| } | |
| node | |
| } | |
| unsafe fn drop_list<T>(node: *mut Node<T>) { | |
| unsafe fn deallocate<T>(ptr: *mut T) { | |
| dealloc(ptr as *mut u8, Layout::new::<T>()) | |
| } | |
| if node.is_null() { | |
| return; | |
| } | |
| drop_list((*node).next); | |
| deallocate(node); | |
| } | |
| unsafe fn list_to_vec<T: Clone>(x: *mut Node<T>) -> Vec<T> { | |
| let mut vec = vec![]; | |
| let mut p = x; | |
| while !p.is_null() { | |
| let node = p.as_ref().unwrap(); | |
| vec.push(node.value.clone()); | |
| p = node.next; | |
| } | |
| vec | |
| } | |
| unsafe fn sort_inplace<T: Ord>(node: &mut *mut Node<T>) { | |
| if !node.is_null() { | |
| let mut second: *mut Node<T> = split_inplace(*node); | |
| if !second.is_null() { | |
| sort_inplace(node); | |
| sort_inplace(&mut second); | |
| merge_inplace(node, second); | |
| } | |
| } | |
| } | |
| unsafe fn split_inplace<T: Ord>(root: *mut Node<T>) -> *mut Node<T> { | |
| let mut double_stepper = root; | |
| let mut single_stepper = root; | |
| loop { | |
| let prev = single_stepper; | |
| double_stepper = (*double_stepper).next; | |
| if !double_stepper.is_null() { | |
| double_stepper = (*double_stepper).next; | |
| } | |
| single_stepper = (*single_stepper).next; | |
| if double_stepper.is_null() { | |
| if prev.is_null() { | |
| return single_stepper; | |
| } | |
| return mem::replace(&mut (*prev).next, null_mut()); | |
| } | |
| if double_stepper == single_stepper { | |
| panic!("dead loop detected!") | |
| } | |
| } | |
| } | |
| unsafe fn merge_inplace<T: Ord>(left: &mut *mut Node<T>, mut right: *mut Node<T>) { | |
| let mut mount_place = left as *mut _; | |
| loop { | |
| if right.is_null() { | |
| break; | |
| } | |
| let mut left: *mut Node<T> = *mount_place; | |
| if left.is_null() { | |
| *mount_place = mem::replace(&mut right, null_mut()); | |
| break; | |
| } | |
| if (*left).value > (*right).value { | |
| mem::swap(&mut left, &mut right); | |
| } | |
| *mount_place = left; | |
| mount_place = &mut (**mount_place).next; | |
| } | |
| } | |
| #[cfg(test)] | |
| mod tests { | |
| use crate::{create_list, drop_list, list_to_vec, sort_inplace}; | |
| fn test_common(a: Vec<i32>, expected_result: Vec<i32>) { | |
| unsafe { | |
| let mut a = create_list(a); | |
| sort_inplace(&mut a); | |
| assert_eq!(list_to_vec(a), expected_result); | |
| drop_list(a); | |
| } | |
| } | |
| #[test] | |
| fn it_works() { | |
| test_common(vec![5, 4, 17, 1, 2, 8, 42], vec![1, 2, 4, 5, 8, 17, 42]); | |
| } | |
| #[test] | |
| fn empty() { | |
| test_common(vec![], vec![]); | |
| } | |
| #[test] | |
| fn single() { | |
| test_common(vec![1], vec![1]); | |
| } | |
| #[test] | |
| fn preserve_pair() { | |
| test_common(vec![1, 2], vec![1, 2]); | |
| } | |
| #[test] | |
| fn flip_pair() { | |
| test_common(vec![2, 1], vec![1, 2]); | |
| } | |
| } | |
| fn main() {} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment