Rust has "coroutine" functions so that state machines can be written in a more normal way. The only kind currently available is async
, but there's also gen
in nightly rust.
Another situation that involves writing state machines is when implementing recursive algorithms with a heap-allocated stack. This is actually extremely similar, to the point where you can hack together an implementation of it using async.
The main required feature here is just allowing you to store let
variables on the heap, which boxed futures allow.
use std::pin::Pin;
use bumpalo::Bump; // 3.16.0
async fn quicksort<T: Ord>(arr: &mut [T], arena: &mut Bump) {
if arr.len() <= 1 {
return;
}
let pivot_index = partition(arr);
bumpalo::boxed::Box::pin_in(quicksort(&mut arr[0..pivot_index], arena), arena).await;
quicksort(&mut arr[pivot_index + 1..], arena);
}
fn partition<T: Ord>(arr: &mut [T]) -> usize {
let pivot_index = arr.len() / 2; // Choosing the middle element as the pivot
arr.swap(pivot_index, arr.len() - 1); // Move pivot to the end
let mut i = 0;
for j in 0..arr.len() - 1 {
if arr[j] <= arr[arr.len() - 1] {
arr.swap(i, j);
i += 1;
}
}
arr.swap(i, arr.len() - 1); // Move pivot to its correct place
i
}
fn main() {
let mut a = [4, 3, 10];
let mut arena = Bump::new();
quicksort(&mut a, &mut arena);
dbg!(a);
}