Initialize sized members of DST in Rust (on the heap)

306 Views Asked by At

I'm trying to implement a chunk list a.k.a. a linked list where each node contains multiple elements, a tradeoff between a linked list and a Vec.

The intuitive way to do this is:

pub struct Node<T> {
    next: /* ref to next node */,
    data: Vec<T>,
}

The problem here is the fact that, to access elements of the vector from a reference to a node, 2 dereference operations are needed: the first to dereference the actual node and the second to dereference the heap-stored slice of the vector.

My solution was to define Node<T> as a DST with its last field being a slice:

pub struct Node<T> {
    next: /* ref to next node */,
    data: [T],
}
// this Node is a DST, it doesn't have a size known at compile time
// and it always needs to be handled behind a pointer, say Box for ownership

which makes it interesting to initialise the struct since it can't be instantiated on the stack.

I have tried both the experimental box syntax and std::alloc::alloc but haven't succeeded.

My question is the following: ignoring all good practice,

  1. Is this actually any more efficient than the Vec version, if no then why, did I miscount dereferences or does the compiler optimise them away?

  2. Is there a way to allocate a DST like this directly on the heap with the slice being allocated as a certain size. More specifically (if this is the way to go), say Node had multiple sized members before the slice, how can I ptr.write(...) any of them (to avoid dropping uninitialised bits) if the compiler might have done some reordering?

I believe the second question is related to the discussion about offset_of! but I'm unsure.

0

There are 0 best solutions below