Rust lang series episode #28 — linking data structures (#rust-series)

Hello everyone, new Rust lang series episode is here. Today we will play with references and composing data across structures or simply said with linking data structures.

In the past we've used Article struct that describes an article with basic properties. Imagine you have multiple structs which you want to reference each other. For example, article is written just by one user which makes it relation one-to-one. Second case would be an user writing multiple articles. That gives us one-to-many relation. Today we will try to implement these relations in Rust.

We will utilize this new API:

• std::rc::Rc
• std::rc::Weak
• std::cell::RefCell

Simple unidirectional reference

Let's start with a one-to-one situation we want to have Article that has reference to User. Check the code first and we will break it down jut after that.

use std::rc::Rc;

#[derive(Debug)]
struct User {
    username: String,
    email: String,
}

#[derive(Debug)]
struct Article {
    id: i32,
    upvotes: i32,
    author: Rc<User>
}


fn main() {
    let u1: Rc<User> = Rc::new(User {
        username: "dan".to_string(),
        email: "[email protected]".to_string()
    });
    let u2: Rc<User> = Rc::new(User {
        username: "ned".to_string(),
        email: "[email protected]".to_string()
    });

    let a1 = Article{id:1, upvotes: 10, author: u1.clone() };
    let a2 = Article{id:2, upvotes: 20, author: u1.clone() };
    let a3 = Article{id:3, upvotes: 30, author: u2.clone() };

    println!("{:?}", a1);
    println!("{:?}", a2);
    println!("{:?}", a3);

Output

Article { id: 1, upvotes: 10, author: User { username: "dan", email: "[email protected]" } }
Article { id: 2, upvotes: 20, author: User { username: "dan", email: "[email protected]" } }
Article { id: 3, upvotes: 30, author: User { username: "ned", email: "[email protected]" } }

Breaking down

Reference counted boxes Rc can be created with:

let counted_reference = Rc::new(variable);

When we have defined a countable reference type we can copy this reference (clone it) whenever we want by using clone() method.

let counted_reference2 = counted_refernce.clone();
let counted_reference3 = counted_refernce.clone();
let counted_reference4 = counted_reference.clone();

Besides that there is nothing special needed for our needs. It basically means that when a new reference clone is created, counter is increased. Why we need Rc at all? Because we need to provide multiple ownership for User value and Rc provides handy and guaranteed way how to do it.

Bidirectional references

Now let's take a look at more complex example where we want to also keep reference to all articles written by a User. We cannot achieve that just with Rc because it would bring cycle to our references. We need some other types like Weak and RefCell to achieve this goal. Weak will provide weak pointer that will not be counted as a new reference and RefCell will provide mutability for our vector. First take a look at the code and we will break it down below to explain new things.

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

struct User {
    username: String,
    email: String,
    articles: RefCell<Vec<Weak<Article>>>
}

struct Article {
    id: i32,
    upvotes: i32,
    author: Rc<User>
}

fn main() {
    // defining users
    let u1 = User {
        username: "dan".to_string(),
        email: "[email protected]".to_string(),
        articles: RefCell::new(Vec::new())
    };

    let u2 = User {
        username: "ned".to_string(),
        email: "[email protected]".to_string(),
        articles: RefCell::new(Vec::new())
    };

    // defining users counted references
    let u1_rc: Rc<User> = Rc::new(u1);
    let u2_rc: Rc<User> = Rc::new(u2);

    // defining articles
    let a1 = Article { id: 1, upvotes: 0, author: u1_rc.clone() };
    let a2 = Article { id: 2, upvotes: 0, author: u1_rc.clone() };
    let a3 = Article { id: 2, upvotes: 0, author: u2_rc.clone() };

    // defining article counted references
    let a1_rc = Rc::new(a1);
    let a2_rc = Rc::new(a2);
    let a3_rc = Rc::new(a3);

    // pushing article references to users
    u1_rc.articles.borrow_mut().push(Rc::downgrade(&a1_rc));
    u1_rc.articles.borrow_mut().push(Rc::downgrade(&a2_rc));
    u2_rc.articles.borrow_mut().push(Rc::downgrade(&a3_rc));

    for article in u1_rc.articles.borrow().iter() {
        let a = article.upgrade().unwrap();
        println!("Article with ID: {} written by {}", a.id, a.author.username);
    }

Output

Article with ID: 1 written by dan
Article with ID: 2 written by dan

Breaking down

Let's break it down and summarize a bit:

RefCell provides mutable reference over the wrapped object, in our case vector of articles

Weak provides weak pointer that wee need to avoid memory leaks and cycles for bi-directional referencing.

downgrade() method returns Weak non-owning pointer from Rc

upgrade() method returns Rc reference from Weak reference. We cannot work directly with Weak because it doesn't guarantee that data are still valid. For simplicity I've used unwrap() but you should consider better error handling.

borrow_mut() method mutably borrows the wrapped value of RefMut

Like this you can compose your data structures. Note that this will work in single-threaded environment. For multi-threaded approach we will take a look in the future.

Postfix

That's all for now, thank you for your appreciations, feel free to comment and point out possible mistakes (first 24 hours works the best but any time is fine). May Jesus bless your programming skills, use them wisely and see you next time.

Meanwhile you can also check the official documentation for more related information:

• https://doc.rust-lang.org/std/rc/struct.Rc.html
• https://doc.rust-lang.org/std/rc/struct.Weak.html
• https://doc.rust-lang.org/std/cell/struct.RefCell.html

#rust-series
#rust-lang
#rust