Pin and doubly-linked list

Hello,

So I take a look into std::pin documentation. It's part says that the pinning helps with double-linked list implementation by its nature. Well, a node in the list is pointed by its neighbors so the access to the node is shared. It can be implemented with raw pointers only in spite of reference counters.

So in order to make an item you do let item_ptr = Box::into_raw(Box::new(Item::new(value))) where value is stored value in the item e. g. an item owns a value. Neighbors points to the item having a copy of the raw pointer. In order to remove the item you make the neighbors to point each other and do Box::from_raw(that_item_ptr) and drop the box.

As far as I see Pin is not converted into a raw pointer and I'm not sure if supposed implementation means that. So how std::pin can be involved in doubly linked list implementation?

1 Like

I guess it all depends on how you plan to access list items. If the only interface to them is through raw pointers, then that suggests an unsafe interface. In which case, it doesn't really matter whether you use Pin or not because you're just as likely to make a mistake normally accessing the item as you are causing a move that invalidates the sibling pointers.

If you provide a safe interface, however, then you need to consider the possibility that items can be moved through mutable references with mem::swap, and even dropped outright without going through your linked list protocol. Your safe interface can still lead to UB as pointers are invalidated. Pin prevents these kinds of problems.

Pin can be useful for writing an intrusive (doubly or singly) linked list. It gives you the guarantee that your nodes will be in a static location, which may include other stack frames, not just the heap. You will still be converting them into raw pointers internally, but by taking in a Pin in the public API you have been provided the guarantee for that allocation.

It's still not clear. If I get you correct and I should expose Pin in public API but internally store a raw pointer then how can I make a Pin of a raw pointer of a structure which has marker PinnedData? I removed everything in the code snippet before publish to be clear.

struct Node(
    u32,
    Cell<*mut Node>,
    Cell<*mut Node>,
    marker::PhantomPinned,
);

impl Node {
    fn next(&mut self) -> Pin<&mut Node> {
        // what should I do with self.1?
    }

    fn prev(&mut self) -> Pin<&mut Node> {
        // what should I do with self.2?
    }
}

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.