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

[–] FizzyOrange@programming.dev 9 points 1 month ago (2 children)

Basically, if your tree is static or you only add nodes, the easiest option is to store all nodes in a Vec and have the child/parent links be indices. I recommend the typed-index-collection crate if you go that route.

If you need to move/delete nodes a lot then either Rc<Refcell< or you can wrap the Vec in something that takes care of the admin of fixing up pointers.

E.g. see this crate https://crates.io/crates/orx-tree

If you want to get really fancy you can even do things like compacting GC. You're basically implementing a memory allocator at that point.

Note that you might say "what's the point of Rust if I just have to implement a memory allocator to bypass the borrow checker?" but that's silly. You still get the benefits of Rust for the rest of your code, and Rust still prevents things like type confusion and UB.

[–] janriemer@floss.social -1 points 1 month ago

@FizzyOrange

Wow, this crate looks like the most feature-rich tree crate I've ever seen!

It seems very underrated (only ~1000 downloads and one star on GitHub (by me)).

Thank you for the suggestion!😊

#Rust #RustLang #DataStructure #Tree #Algorithms

load more comments (1 replies)