In c++, it's often needed to avoid heap allocation. Intrusive linked list is a good way, and we can use inheritance to hide generic classes under base class, then use pointer to parent class to store different types in one intrusive list. It's totally heapless and keep the dynamic behaviors. Here is an example (stdexec/execution.hpp at main · NVIDIA/stdexec · GitHub).
But I have no idea how to implement that in rust. Here's some of my experiment and requirements.
-
Pick some intrusive list implementation. I choose to use tokio's (tokio/linked_list.rs at d459a9345334911be4af1bba58b6c796d92fde66 · tokio-rs/tokio · GitHub)
-
Define the intrusive list node
struct Task {
pointers: linked_list::Pointers<Task>,
operation: NonNull<dyn Executable>,
}
unsafe impl linked_list::Link for Task {
type Handle = NonNull<Task>;
type Target = Task;
fn as_raw(handle: &NonNull<Task>) -> NonNull<Task> {
*handle
}
unsafe fn from_raw(ptr: NonNull<Task>) -> NonNull<Task> {
ptr
}
unsafe fn pointers(target: NonNull<Task>) -> NonNull<linked_list::Pointers<Task>> {
Task::addr_of_pointers(target)
}
}
Here, like in C++, I don't want to leak generic types in Task
since that will make the linked list support only one type (like Vec). So I hide it behind one trait (since rust has no inheritance and I cannot use Task
as base class of more generic types)
- Define some real type, maybe with generics and implement the trait
struct Operation<R> {
receiver: Option<R>,
}
impl<R> Executable for Operation<R>
where
R: SetValue<Value = ()>,
{
fn execute(&mut self) {
if let Some(receiver) = self.receiver.take() {
receiver.set_value(());
}
}
}
- Everything seems to work well. But unlike C++ where subclass share the storage with base class, now I need to store the
Task
andOperation
in different space on stack, and use the link with address.
pub struct TaskOperation<R>(pub Task, pub Operation<R>);
fn connect(self, receiver: R) -> TaskOperation {
let operation = Operation {
receiver: Some(receiver),
run_loop: self.run_loop,
};
let task = Task {
pointers: linked_list::Pointers::new(),
operation: NonNull::from(&operation),
_p: PhantomPinned,
};
TaskOperation(task, operation)
}
Now, there's bug here. Since the address of variable may changed after returning from the function. The only correct way is to eliminate the function call and never move these two objects.
I think the core issue here is rust's not supporting inheritence so I need to split the base part and child part of one class in order to hide generic types.
Any idea or advice on this question? Here is my code (exec-rs/run_loop.rs at master · npuichigo/exec-rs · GitHub)