Question is how to do these in Rust. An example might be a browser DOM: each node has a parent pointer, a list of child pointers, left and right sibling pointers, maybe a CSS node pointer, etc. Inserting or deleting nodes has to repair the pointers to and from the neighboring nodes as needed.

I know this is doable since obviously Servo (Rust's initial driving application) has to do it. I hope the answer doesn't involve the word "unsafe". But I am quite unclear about how to create such a structure under Rust's rules of pointer ownership, and also how to reliably reclaim storage when nodes and trees/subtrees are deleted. Plus there will be thread safety rules that should be statically enforced if possible.

I've heard that doubly linked lists in Rust are handled by an unsafe library, yet this seems even worse. Thanks.

you are viewing a single comment's thread
view the rest of the comments

[–] [email protected] 0 points 2 weeks ago* (last edited 2 weeks ago)

Thanks, I'll look at the box-tree crate, but I'd say using indices instead of pointers is somewhat unsatisfying. C++'s advertised property is zero-cost abstractions, and Rust is supposed to have C++'s performance without the footguns. But if you compare those vector index operatons with primitive pointer dereferences, there are a bunch of extra instructions run at each operation, including a layer of memory lookups that can cause cache pressure and misses.

I think the most practical answers I've heard so far are to 1) use Rc/Arc and weakrefs, or 2) use unsafe operations on machine pointers in a hopefully carefully contained and abstracted part of the code.

Sorry about the slow responses as I'm occupied with RL stuff most of the time for now.