Intrusive algorithms equivalents in Rust

Question

I'm looking at the Rust programming language and trying to convert my C++ thinking to Rust. Common data structures such as lists and trees and have previously been implemented with pointers in C++, and I'm not sure how implement the exact equivalents in Rust. The data structures I'm interested in are the intrusive algorithms, similar to what is found in Boost intrusive libraries, and these are useful in embedded/system programming.

The linked list example in Rust (Dlist) is pretty much straight forward, but it uses a container type where the actual type is inside the container. The intrusive algorithm I'm looking for is a little bit the other way around: you have a main type where the list node is inserted or inherited.

Also, the famous linked list in Linux is also another example where the list data is in the members of the structures. This is like Boost member variant of the intrusive algorithms. This enables that you use your type in several lists/trees many times. How would this work with Rust?

So I'm unsure how to convert these kind of design patterns to Rust that I'm used to in C/C++. Anyone who had any success understanding this?

Answer 1

Rust wants you to think about ownership and lifetimes. Who owns the members and how long will they live?

In the question of Dlist, the answer is 'the container'. With intrusive algorithms there is no clear answer. Members of one list might be reused in another list, while others get destroyed with the first list. Ultimately, you probably want to use reference counting (std::sync::Arc).

Answer 2

I think there are two ways to accomplish something like that in Rust. Let's take a look at implementation of graphs, which typically use intrusive links.

The first approach relies on Rc<RefCell<Node>>. You can find more details here: Graphs and arena allocation

The second approach relies on vector indexes. You can find more information here: Modeling Graphs in Rust Using Vector Indices.

I believe the second approach is better, but I have not done any testing.