Hi all, I have a scenario where I have a set of structs that form a tree, e.g.:
struct A {
// data fields ...
bs: Vec<B>,
}
struct B {
// data fields ...
a: // pointer to A
siblings: Vec</*pointer to B*/>
cs: Vec<C>,
}
struct C {
// data fields ...
b: // pointer to B
ds: Vec<D>,
}
struct D {
// data fields ...
c: // pointer to C
es: Vec<E>
}
A few conditions:
- There is only ever one root
A
. - "Parent" pointers are never modified after the child is created.
- New children can be added to a struct at any time.
- Some structs need sibling pointers.
- The lifetimes of all objects under an
A
never outliveA
.
I've tried a few solutions, but nothing sticks. Given that these relations are standard in C++, I'm hoping the community can guide me here. Some ideas:
-
Arena I have a single arena containing all structs and pass this to
A
,B
,C
etc asRc<RefCell<Arena>>
. This allows any struct in the hierarchy to effectively modify the tree (e.g., aB
can create and add newC
s to itself). However, who owns the root (A
)?A
needs the arena, too, but the arena only has a singleA
, so do we wrap it in anOption
and set it after creating theA
, like:
struct Arena {
a: Option<A>,
b: Vec<B>,
// rest ...
}
- Store a weak
RefCell
self-link in each element and pass this to children for parent pointers. This works, but it does mean I need to always useweak_link.upgrade().unwrap().borrow()
and rely on runtime checks for multiple borrows. I'd like to avoid this. - Pass along parent references to children functions when need be. This get's very unwieldy because each struct is fairly complex.
- Use an arena, but store data and functionality separately, like:
struct Arena { a: Vec<AData> }
struct AData { ... }
struct ARef<'a> {
arena: &'a Arena,
a_idx: usize
}
But then I need an ARef
and an ARefMut
depending on what I want to do and duplicate methods across these types. This seems clunky.
Thoughts from the community on the proper solution to what seems like a simple design in other languages?