[How to] : Data Structure with inside link and mutability

Hey Rustaceans !

My title is not really good one, but I didn't find a way to summarize it :confused: ..

So, I would like to do a data structure which has some link between some nodes, and have a variable which link to the working node.

I tried multiple times to find a working data structure but I'm quite lost in my thought process :sweat_smile:.

The main data structure, node and exterior link can be represented as follow

main_data_struct: Vec<Node>

working_node : Option<&'static Node>

struct Node {
    sub_node : Vec<Node>,
    parent_node : Option<&Node>,
// DATA ....
}

As I build my vector, I can add a new node inside my current node, or at the same level of my current node. Also, I will need to modify and test some data in my current node.

I tried to encapsulate the node, or the vector in a RC<RefCell<_>>, but i didn't find a way to make it work and have a clean code.

Anyone have an idea, or some advice to help me on that ?

If you have a node with a child node, and this child node has a reference to its parent, you have a self referential data type. This is not possible with ordinary references.

Typically this kind of stuff is done using either Rc or with indexes into a vector of nodes.

Alright,

I finally achieved what I wanted. but I don't know if it is a good Rust code. Here is the POC code

use std::rc::Rc;
use std::cell::RefCell;
use std::rc::Weak;

pub type Node = Rc<RefCell<State>>;
pub type WeakNode = Weak<RefCell<State>>;

pub type Link = Option<Node>;
pub type WeakLink = Option<WeakNode>;

#[derive(Debug)]
pub struct State {
    pub name: String,
    pub sub_state : Vec<Node>,
    pub parent_state : Option<Weak<RefCell<State>>>,
    pub data : u16,

}

impl State {
    pub fn new(_name: String, _parent : WeakLink) -> State {
        State {
            name : _name,
            sub_state : Vec::new(),
            parent_state : _parent,
            data : 0,
        }
    }
}

fn main() {
    let mut _v_parse: Vec<Node> = Vec::new();

    let mut _current_state: Link = None;

    _v_parse.push(Rc::new(RefCell::new(State::new("A".to_string(), None))));
    _current_state = Some(_v_parse[0].clone());

    println!("_v_parse   {:#?}", _v_parse);
    println!("_current_state     {:#?}", _current_state);
    println!("###########################");


    _current_state.clone().unwrap().borrow_mut().sub_state.push(Rc::new(RefCell::new(State::new("B".to_string(), Some(Rc::downgrade(&_current_state.clone().unwrap()))))));
    _current_state = Some(_current_state.clone().unwrap().borrow_mut().sub_state.last().unwrap().clone());

    println!("_v_parse   {:#?}", _v_parse);
    println!("_current_state     {:#?}", _current_state);
    println!("###########################");

    _current_state.clone().unwrap().borrow_mut().data = 10;
    _current_state.clone().unwrap().borrow().parent_state.as_ref().unwrap().upgrade().unwrap().borrow_mut().data = 11;

    println!("_v_parse   {:#?}", _v_parse);
    println!("_current_state     {:#?}", _current_state);
    println!("###########################");

    {
        let parent = _current_state.clone().unwrap().borrow().parent_state.as_ref().unwrap().upgrade().unwrap();

        parent.borrow_mut().sub_state.push(Rc::new(RefCell::new(State::new("C".to_string(), Some(Rc::downgrade(&parent.clone()))))));
        _current_state = Some(parent.borrow().sub_state.last().unwrap().clone());
    }

    println!("_v_parse   {:#?}", _v_parse);
    println!("_current_state     {:#?}", _current_state);
    println!("###########################");

    println!("{:?}", Rc::strong_count(&_v_parse[0]));
    println!("{:?}", Rc::weak_count(&_v_parse[0]));
}

I used the Rc::Weak to prevent recursive print while debugging. I don't know if I will keep it in the final code.

Also how can I make the code more readable ?

I thought about making some function like 'getParent()' to prevent having the LOOOONG line clone().unwrap().borrow().parent_state.as_ref().unwrap().upgrade().unwrap() for example.

If you haven't already, I'd suggest having a look at Learn Rust With Entirely Too Many Linked Lists. It's a good resource for anyone needing to create a data structure with a complicated ownership story (parent pointers, internal mutability with shared ownership, etc.).

You may also want to look into some sort of arena type which can manage the memory for each node. Depending on how the links and interior mutability are done you may also want to check out a graph library like petgraph (a graph is just a specialized arena type).

Depending on your use case, in particular the typical access patters, you may even find that creating your own data structure using raw pointers and unsafe (like you would in C or C++) has less cognitive load than the corresponding Rc<RefCell<T>> approach. The std::collections::LinkedList or std::collections::BTreeMap source code may be useful here.

2 Likes

I typically make an RcCell and a WeakCell newtype wrapper around Rc<RefCell<T>> and Weak<RefCell<T>>, respecticely, which only expose borrow() and borrow_mut() in a way that they perform the internal calls to upgrade().unwrap() etc. bookkeeping.

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