Accessing RefCell inside RefCell

1

im currently building double linked list using Refcell,Weak,Rc Pointer, everything goes well until i have requirement to add a node in the middle of the list.

here is my code so far :

use std::rc::{Rc,Weak};
use std::cell::RefCell;
#[derive(Debug)]
struct Node{
    prev:Option<Weak<RefCell<Node>>>,
    val:i32,
    next:Option<Rc<RefCell<Node>>>,
}

impl Node{
    fn new(val:i32)-> Self{
        Self{
            prev:None,
            val:val,
            next:None,
        }
    }
}

#[derive(Debug)]
struct DoubleLinkedList {
    head:Option<Rc<RefCell<Node>>>,
    tail:Option<Rc<RefCell<Node>>>,
    length:i32,
}

impl DoubleLinkedList {

    fn new() -> Self {
        Self{
            head:None,
            tail:None,
            length:0,
        }
    }
    
    fn add_at_head(&mut self, val: i32) {
        let mut newnode:Rc<RefCell<Node>>=Rc::new(RefCell::new(Node::new(val)));
        
        if self.length==0{
            self.head=Some(Rc::clone(&newnode));
            self.tail=Some(Rc::clone(&newnode));   
        }else{
            let mut borrownewnode=(newnode.borrow_mut());
            let mut borrowhead=(self.head.as_mut().unwrap().borrow_mut());
            borrowhead.prev=Some(Rc::downgrade(&newnode));
            drop(borrowhead);
            borrownewnode.next=self.head.take();
            drop(borrownewnode);
            self.head=Some(Rc::clone(&newnode));
        }
        
        self.length+=1;
    } 

    fn add_at_tail(&mut self, val: i32) {
        let mut newnode:Rc<RefCell<Node>>=Rc::new(RefCell::new(Node::new(val)));
        
        if self.length==0{
            self.head=Some(Rc::clone(&newnode));
            self.tail=Some(Rc::clone(&newnode));   
        }else{
            let mut borrownewnode=(newnode.borrow_mut());
            let mut borrowtail=(self.tail.as_mut().unwrap().borrow_mut());
            borrowtail.next=Some(Rc::clone(&newnode));
            drop(borrowtail);
            borrownewnode.prev=Some(Rc::downgrade(self.tail.take().as_ref().unwrap()));
            drop(borrownewnode);
            self.tail=Some(Rc::clone(&newnode));
        }
        
        self.length+=1;
    }
    
    fn add_at_index(&mut self,index:i32,val:i32){
        if index>self.length{
            return
        }
        
        let mut current:&Option<Rc<RefCell<Node>>>=&self.head;
        if index>0{
            for i in 0..index-1{
                let borrow=current.as_ref().unwrap().borrow();
                current=&borrow.next;
                drop(borrow);
            }
        }
        
        
        let mut newnode:Rc<RefCell<Node>>=Rc::new(RefCell::new(Node::new(val)));
        let mut borrownewnode=newnode.borrow_mut();
        /*if self.length==0{
            self.head=Some(Rc::clone(&newnode));
            self.tail=Some(Rc::clone(&newnode));
        }else if index==0{
            let mut borrowhead=self.head.as_mut().unwrap().borrow_mut();
            borrowhead.prev=Some(Rc::downgrade(&newnode));
            drop(borrowhead);
            borrownewnode.next=self.head.take();
            self.head=Some(Rc::clone(&newnode));
        }else if index==self.length{
            let mut borrowtail=self.tail.as_mut().unwrap().borrow_mut();
            borrowtail.next=Some(Rc::clone(&newnode));
            drop(borrowtail);
            borrownewnode.prev=Some(Rc::downgrade(self.tail.take().as_ref().unwrap()));
            self.tail=Some(Rc::clone(&newnode));
        }else{
            let mut borrowcur=current.as_mut().unwrap().borrow_mut();
            let mut next=borrowcur.next.take();
            drop(borrowcur);
            println!("{:?} {:?}",next,current);
        }
        */
        drop(borrownewnode);
        self.length+=1;
    }

}
    
let mut mylist:DoubleLinkedList=DoubleLinkedList::new();
mylist.add_at_head(1);
mylist.add_at_head(2);
mylist.add_at_tail(3);
mylist.add_at_index(2,6);
}

my main problem is traversing the linkedlist throught Rc and Refcell , i already try all possible thing i know but nothing still works. and i even doubt if its possible to add node in the middle of double linked list using this method.

main problem:

        let mut current:&Option<Rc<RefCell<Node>>>=&self.head;
        if index>0{
            for i in 0..index-1{
                let borrow=current.as_ref().unwrap().borrow();
                current=&borrow.next;
                drop(borrow);
            }
        }

want to loop list and get the next Option<Rc<RefCell>> and referenced it

2

First off, obligatory reading: Introduction - Learning Rust With Entirely Too Many Linked Lists

To address the question:

RefCell works by dynamically tracking borrows using the Ref returned from borrow. The Ref must not be dropped while you're accessing any other RefCell deeper down.

This means that to access the nth node, you need to keep n Refs alive (each with different lifetimes).

The easiest way to accomplish that is simply to use recursion instead of your loop:

fn add_at_index(&mut self, index: i32, val: i32) {
    if index > self.length {
        return;
    }

    fn helper(current: &Option<Rc<RefCell<Node>>>, index: i32, val: i32) {
        if index > 0 {
            let borrow = current.as_ref().unwrap().borrow();

            // all the next "iterations" happen in this call
            // `borrow` is alive the whole time
            helper(&borrow.next, index - 1, val);

            drop(borrow);
        } else {
            //...
        }
    }

    helper(&self.head, index, val);
}

Playground

1 Like
3

The easiest fix is to clone the Rc instead of keeping an & reference around:

        let mut current: Option<Rc<RefCell<Node>>>=self.head.clone();
        if index>0{
            for i in 0..index-1{
                let next = current.as_ref().unwrap().borrow().next.clone();
                current=next;
            }
        }
4 Likes
4

Nice,i have consider this solution, but i have a "clone=bad" mentality so i skipped it,

5

Didnt know that about refcell, thanks for new information

6

It is largely the point of Rc that you can clone it cheaply (i.e., without cloning the underlying data).

"Cheaply" is relative, but in the context of a shared-ownership linked list, where you're already using the reference count to support the list, it almost certainly doesn't serve a purpose to avoid cloning.

4 Likes
7

when cloning rc, is it the same as Rc::clone()? or we clone the Parent rc (Rc::new().clone());
in my head when cloning rc its like this(Rc::new().clone()) that is why i avoid it.

8

Cloning an Rc means incrementing the reference count. I'm not sure what you mean by cloning the "parent". It's certainly not comparable to doing Rc::new on a cloned T, if that's what you mean.

9

what i mean by "cloning the parent" is creating a new rc with count of 1, using value from previous rc

10

If cloning an Rc made a new Rc with a reference count of 1, how would you ever get an Rc with a reference count of 2 or greater?

1 Like
11

The reference count is stored in the shared allocation. All clones of a given Rc simply point to that same shared allocation. Cloning increments the reference count in the shared allocation.

You may not have seen the doc explaining Rc in detail because it is not on the Rc type, is is on the rc module:

12

because i thought rc::clone() and .clone() on a rc is a different thing, but turn out its the samething

13

yes, thank you for the reference

14

what is the difference between your code and my code?

        let mut current=self.head.clone();
        for i in 0..index{
            let borrow=current.as_mut().unwrap().borrow_mut();
            let next=borrow.next.clone();
            drop(borrow);
            current=next;
        }

if there is no difference when does the borrow get dropped in your code?(fyi i like to code it this way because it more easy to understand and dodge error)

15

The only difference between this

    let next = current.as_ref().unwrap().borrow().next.clone();

and this

    let borrow=current.as_mut().unwrap().borrow_mut();
    let next=borrow.next.clone();
    drop(borrow);

is that, in the first case, the borrow is a temporary value in the larger expression and is dropped when the expression is completed.

Also for some reason you're getting a mut borrow in the second case, don't know why. You don't need a mut reference to call clone.

16

thanks for the explanation, i use borrow_mut() because after looping the borrow i want to mutate the value. (even though i clone it, and can access its inside with as_mut() later. which make borrow_mut() redundant in this scenario)

1 Like