too-many-lists/production-unsafe-deque/layout

[giscus[bot]]

too-many-lists/production-unsafe-deque/layout

https://course.rs/too-many-lists/production-unsafe-deque/layout.html

[KINGFIOX]

这鸡汤十分的珍贵，直接来吧！！！

[haydenzhourepo]

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

pub struct List<T> {
    head: Link<T>,
    tail: Link<T>,
}

type Link<T> = Option<Rc<RefCell<Node<T>>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
    prev: Link<T>,
}

impl<T> Node<T> {
    fn new(elem: T) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Node {
            elem: elem,
            prev: None,
            next: None,
        }))
    }
}

impl<T> List<T> {
    pub fn new() -> Self {
        List {
            head: None,
            tail: None,
        }
    }

    pub fn push_front(&mut self, elem: T) {
        let node = Node::new(elem);

        let temp = self.head.take();
        if let Some(n) = temp {
            (*node).borrow_mut().next.replace(Rc::clone(&n));
            (*n).borrow_mut().prev.replace(Rc::clone(&node));
        }

        self.head.replace(Rc::clone(&node));

        if let None = self.tail {
            self.tail.replace(Rc::clone(&node));
        }
    }

    pub fn pop_front(&mut self) -> Option<T> {
        match self.head.take() {
            None => None,
            Some(node) => {
                match (*node).borrow_mut().next.take() {
                    None => {
                        self.tail = None;
                    }
                    Some(n) => {
                        self.head.replace(Rc::clone(&n));
                        (*n).borrow_mut().prev.take();
                    }
                }

                Some(Rc::try_unwrap(node).ok().unwrap().into_inner().elem)
            }
        }
    }
}

[naosense]

没看懂传统方法和虚拟节点方法在讨论啥

[Executioner2]

虚拟节点应该是指哨兵节点。在队列的两端增加两个不存储数据的哨兵节点。这样就不用处理队列中没有数据这种边缘情况下，head和tail的指向问题。类似这种：哨兵节点Head ⇄ [数据节点A] ⇄ [数据节点B] ⇄ 哨兵节点Tail

[max201904]

不实现 Drop 时, long_list 测试不会栈溢出, 因为 next 和 prev 自成一条循环引用, 会导致内存泄漏. 必须实现 Drop 防止内存泄漏

[FortuneOreo]

自己增加了从链表尾部插入节点和取出节点的接口：

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

pub struct List {
head: Link,
tail: Link
}

type Link = Option<Rc<RefCell<Node>>>;

struct Node {
elem: T,
next: Link,
prev: Link
}

impl Node {
fn new(elem: T) -> Rc<RefCell> {
Rc::new(RefCell::new(
Node {
elem: elem,
prev: None,
next: None
}
))
}
}

impl List {
pub fn new() -> Self {
List { head: None, tail: None }
}

pub fn push_front(&mut self, elem: T) {
	let new_head = Node::new(elem);
	match self.head.take() {
		Some(old_head) => {
			old_head.borrow_mut().prev = Some(new_head.clone());
			new_head.borrow_mut().next = Some(old_head);
			self.head = Some(new_head);
		},
		None => {
			self.tail = Some(new_head.clone());
			self.head = Some(new_head);
		}
	}
}

pub fn pop_front(&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.take();
				self.head = Some(new_head);
			},
			None => {
				self.tail.take();
			}
		}
		Rc::try_unwrap(old_head).ok().unwrap().into_inner().elem
	})
}

pub fn push_back(&mut self, elem: T) {
	let new_node = Node::new(elem);

	match self.tail.take() {
		Some(old_tail) => {
			old_tail.borrow_mut().next = Some(new_node.clone());
			new_node.borrow_mut().prev = Some(old_tail);
			self.tail = Some(new_node);
		},
		None => {
			self.head = Some(new_node.clone());
			self.tail = Some(new_node);
		}
	}
}

pub fn pop_back(&mut self) -> Option<T> {
	self.tail.take().map(|old_tail| {
		match old_tail.borrow_mut().prev.take() {
			Some(new_tail) => {
				new_tail.borrow_mut().next.take();
				self.tail = Some(new_tail);
			},
			None => {
				self.head.take();
			}
		}

		Rc::try_unwrap(old_tail).ok().unwrap().into_inner().elem
	})
}

}

impl Drop for List {
fn drop(&mut self) {
while self.pop_front().is_some() {}
}
}

#[cfg(test)]
mod test {
use super::List;

#[test]
fn basics() {
    let mut list = List::new();

    // Check empty list behaves right
    assert_eq!(list.pop_front(), None);

    // Populate list
    list.push_front(1);
    list.push_front(2);
    list.push_front(3);

    // Check normal removal
    assert_eq!(list.pop_front(), Some(3));
    assert_eq!(list.pop_front(), Some(2));

    // Push some more just to make sure nothing's corrupted
    list.push_front(4);
    list.push_front(5);

    // Check normal removal
    assert_eq!(list.pop_front(), Some(5));
    assert_eq!(list.pop_front(), Some(4));

    // Check exhaustion
    assert_eq!(list.pop_front(), Some(1));
    assert_eq!(list.pop_front(), None);

	assert_eq!(list.pop_back(), None);

	list.push_back(10);
	list.push_back(11);
	list.push_back(12);

	assert_eq!(list.pop_back(), Some(12));
	assert_eq!(list.pop_back(), Some(11));
	assert_eq!(list.pop_back(), Some(10));

	assert_eq!(list.pop_back(), None);

	list.push_back(1);
	list.push_back(2);
	list.push_back(3);

	assert_eq!(list.pop_front(), Some(1));
	assert_eq!(list.pop_back(), Some(3));
}

}

[2506575085]

print一下list直接爆栈了