I'm writing a linked list where there are weak references linking the previous node.
use std::cell::{Ref, RefCell, RefMut};
use std::rc::{Rc, Weak};
pub struct List<T> {
head: NextLink<T>,
tail: PrevLink<T>,
}
type NextLink<T> = Option<Rc<RefCell<Node<T>>>>;
type PrevLink<T> = Weak<RefCell<Node<T>>>;
struct Node<T> {
elem: T,
prev: PrevLink<T>,
next: NextLink<T>,
}
impl<T> Node<T> {
fn new(elem: T) -> Rc<RefCell<Self>> {
Rc::new(RefCell::new(Self {
elem,
prev: Weak::new(),
next: None,
}))
}
}
impl<T> List<T> {
pub fn new() -> Self {
Self {
head: None,
tail: Weak::new(),
}
}
// add to tail
pub fn push(&mut self, elem: T) {
let new_node = Node::new(elem);
match self.tail.upgrade().take() {
Some(old_tail) => {
new_node.borrow_mut().prev = Rc::downgrade(&old_tail);
old_tail.borrow_mut().next = Some(new_node);
}
None => {
self.tail = Rc::downgrade(&new_node);
self.head = Some(new_node);
}
}
}
pub fn pop(&mut self) -> Option<T> {
self.tail.upgrade().map(|old_tail| {
match old_tail.borrow_mut().prev.upgrade() {
Some(new_tail) => {
new_tail.borrow_mut().next = None;
self.tail = Rc::downgrade(&new_tail);
}
None => {
self.head.take();
self.tail = Weak::new();
}
};
Rc::try_unwrap(old_tail).ok().unwrap().into_inner().elem
})
}
// add to head
pub fn unshift(&mut self, elem: T) {
let new_node = Node::new(elem);
match self.head.take() {
Some(old_head) => {
old_head.borrow_mut().prev = Rc::downgrade(&new_node);
new_node.borrow_mut().next = Some(old_head);
}
None => {
self.tail = Rc::downgrade(&new_node);
self.head = Some(new_node);
}
}
}
pub fn shift(&mut self) -> Option<T> {
self.head.take().map(|old_head| {
match old_head.borrow_mut().next.take() {
Some(new_head) => {
new_head.borrow_mut().prev = Weak::new();
self.head = Some(new_head);
}
None => {
self.tail = Weak::new();
}
};
Rc::try_unwrap(old_head).ok().unwrap().into_inner().elem
})
}
pub fn peek_head(&self) -> Option<Ref<T>> {
self.head
.as_ref()
.map(|node| Ref::map(node.borrow(), |node| &node.elem))
}
pub fn peek_tail(&self) -> Option<Ref<T>> {
self.tail
.upgrade()
.map(|node| Ref::map(node.borrow(), |node| &node.elem))
}
pub fn peek_head_mut(&mut self) -> Option<RefMut<T>> {
self.head
.as_ref()
.map(|node| RefMut::map(node.borrow_mut(), |node| &mut node.elem))
}
pub fn peek_tail_mut(&mut self) -> Option<RefMut<T>> {
unimplemented!()
}
}
impl<T> Drop for List<T> {
fn drop(&mut self) {
while let Some(old_head) = self.head.take() {
self.head = old_head.borrow_mut().next.take();
}
}
}
There is a compilation error:
error[E0515]: cannot return value referencing function parameter `node`
--> src/lib.rs:106:25
|
106 | .map(|node| Ref::map(node.borrow(), |node| &node.elem))
| ^^^^^^^^^----^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
| | |
| | `node` is borrowed here
| returns a value referencing data owned by the current function
It seems that when the weak reference of the tail node upgrades to Rc, this Rc is owned by this function, and will be consumed in the end.
How can I fix that?
