A reference-counted pointer enables shared ownership when one owner, such as a Box, is too restrictive. Each new pointer copy increases a count; destroying a copy decreases it. When the count reaches zero, the referenced allocation can be released. section 5.6
Choose the pointer for where ownership must be shared:
- Use Rc for single-threaded shared ownership. section 5.6
- Use Arc when ownership must be shared across threads. section 5.6
- For a linked-list node held through multiple links, an Rc<RefCell<ListItem<T>>> alias keeps the pointer type manageable; the node can separately hold its data in a Box<T>. section 5.6
Listing 5.6 Code of a doubly linked list using Rc, RefCell, and Box
use std::cell::RefCell;
use std::rc::Rc;
struct ListItem<T> {
prev: Option<ItemRef<T>>, #1
data: Box<T>, #2
next: Option<ItemRef<T>>,
}
type ItemRef<T> = Rc<RefCell<ListItem<T>>>; #3
struct DoublyLinkedList<T> {
head: ItemRef<T>,
}
impl<T> ListItem<T> {
fn new(data: T) -> Self {
ListItem {
prev: None,
data: Box::new(data), #4
next: None,
}
}
fn data(&self) -> &T {
self.data.as_ref()
}
}
impl<T> DoublyLinkedList<T> {
fn new(data: T) -> Self {
DoublyLinkedList {
head: Rc::new(RefCell::new(ListItem::new(data))),
}
}
fn append(&mut self, data: T) {
let tail = Self::find_tail(self.head.clone()); #5
let new_item = Rc::new(RefCell::new(ListItem::new(data))); #6
new_item.borrow_mut().prev = Some(tail.clone()); #7
tail.borrow_mut().next = Some(new_item); #8
}
fn head(&self) -> ItemRef<T> {
self.head.clone()
}
fn tail(&self) -> ItemRef<T> {
Self::find_tail(self.head())
}
fn find_tail(item: ItemRef<T>) -> ItemRef<T> {
if let Some(next) = &item.borrow().next { #9
Self::find_tail(next.clone()) #10
} else {
item.clone() #11
}
}
}
The doubly linked-list listing shows Rc, RefCell, and Box in one node representation. Inspect its ItemRef alias and prev and next fields to see where shared pointers enter the structure. section 5.6
Prefer Rc or Arc to writing a reference-counted pointer yourself. A custom implementation is an advanced exercise requiring raw, unsafe pointers. section 5.6
