Structure lifetimes for structs that reference each other

I have the following structs

pub struct Site {
    pub name: String,
}

pub struct GatewayDevice {
    pub name: String,
    pub Vec<MeterDevice>,

    pub parent: Option<&Site>,
}

pub struct MeterDevice {
    pub name: String,
    pub parent: Option<&GatewayDevice>,
}

The relationship is like Site > GatewayDevice -> Meters

I would like to be able to have a reference (parent) that allows any entity to access its parent.

Is it possible to have lifetimes in the structs without get circular lifetime issues as am having trouble when trying to add lifetimes.

Or is this approach flawed? Is it recommended to just define a map for mapping each entry to its parent ?

Thanks

Self referential structs are not possible with references. Self-referential means that it contains a reference that points into itself. Using keys into a map or indexes into a vectors are both common solutions to this.

Your thinking reminds me of where I started when I first approached Rust. I was trying to create a node graph API where nodes could reference each other with bidirectional links all over the place. I'll explain the data structure I came up with, but full disclaimer that I'm not saying it's optimal in any way. It's just something that happens to fit within Rust's ownership model.

Anyway, I created a pool object, to hold all my objects in a Vec<>. That way, the pool owned everything. Then, within each object, I stored every "link" reference as an index object (just an enum wrapping a usize). And finally, I pass the reference to the pool to just about every function that needs to operate on the nodes. So, the code can look up the parent node, or any other node, in the pool when it's needed.

Obviously every situation is unique and you'll need to trade off flexibility of referencing against pointer-chasing & indexing overhead.

Also, my approach has some additional downsides - like I need to be careful because I can now leak memory in the form of adding nodes to the pool that nobody is keeping track of - basically defeating one of the benefits of the Rust memory model.

And finally, the pool Vec keeps all the nodes inside RefCells, so that I can mutate the nodes when I need to. And the quote from Too Many Linked Lists "RefCells make everything sadness"

Indexes are definitely a good approach!

Yes, and this is hard to solve. GCs solve it by going through the reachable nodes, and deleting what could not be reached.

I guess that not is a "leak" in the usual sense. All those nodes that become unused are still reachable by whoever ones the Vec. The pool in your case.

Which means one could make the pool a bit smarter and have it keep track of what is used or not. Then it could recycle unused Vec entries for new nodes as the come along.

Presumably many people have done this before. Is there a suggested algorithm to make such a "node collector". I'm sure whatever I came up with would be far from efficient in time or space. Perhaps just another Vec as bit map that records nodes in use or not.

Makes me think this technique would help C programmers keep their memory allocations in order. Don't do any! One can keep stuff in an array in C as well as a Vec in Rust.

Try structuring your program to not need parent in the struct (e.g pass parent as an argument).

If you need parent-child relationship, you will need to use Rc and Weak.

Rust references (temporary borrows) are not a general-purpose way of "referencing" objects. They also have semantic of locking objects to be read-only and tied to a specific scope. This makes structs with temporary references inside themselves temporary, and unusable for most things.

2 Likes

I was wondering...

If one uses Rc and the like then all your objects are individually allocated on the heap. I guess at the bottom of the pile is malloc/free or equivalent.

If one puts everything in a Vec and uses indices to locate it there is only one malloc. Sounds like a performance win. Provided one is happy to keep all that memory allocated until all the objects are not needed.

But then, one could implement a scheme in the Vec pool to recycle unused item space. But that will impact performance.

Which one wins? Anyone have experience of this?

Yeah, when that becomes a problem, and you need ability to delete, there are also generational arenas.

Oddly enough "generational arena" is not something that google knows much about, apart from links to Rust libraries. Wikipedia has never heard of it.

But the first link in the list of links you linked to summarizes it nicely https://github.com/fitzgen/generational-arena

Which brings us nicely to Entity Component System...

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