too-many-lists/unsafe-queue/final-code

[giscus[bot]]

too-many-lists/unsafe-queue/final-code

https://course.rs/too-many-lists/unsafe-queue/final-code.html

[zhaoyao73]

指针终于看起来家简单很多

[ytianxia6]

drop 很重要，要不然会内存泄漏，miri 测试会失败。

[YaQia]

真的不要有unsafe包袱，也不要有指针包袱，觉得unsafe/指针就是不应该出现在rust代码里的。很明显链表、树这种复杂的数据结构最方便的方式还是用指针来实现，没必要让呆板的borrow checker和lifetime checker给自己徒增烦恼。我想用rust实现链表前前后后都实现了3、4版了，前面用Rc、RefCell的怎么用怎么卡壳。最终版用unsafe指针直接实现，天空都晴朗了。

pub struct List<T> {
    head: Option<*mut Node<T>>,
    tail: Option<*mut Node<T>>,
    len: usize,
}

struct Node<T> {
    next: Option<*mut Node<T>>,
    prev: Option<*mut Node<T>>,
    elem: T,
}

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

impl<T> List<T> {
    pub fn new() -> Self {
        List {
            head: None,
            tail: None,
            len: 0,
        }
    }
    pub fn push_back(&mut self, elem: T) {
        let node = Box::new(Node::new(elem));
        unsafe {
            let node_ptr = Box::leak(node) as *mut Node<T>;
            (*node_ptr).next = None;
            (*node_ptr).prev = self.tail;
            let node = Some(node_ptr);
            match self.tail {
                None => self.head = node,
                Some(tail) => (*tail).next = node,
            }
            self.tail = node;
            self.len += 1;
        }
    }
    pub fn push_front(&mut self, elem: T) {
        let node = Box::new(Node::new(elem));
        unsafe {
            let node_ptr = Box::leak(node) as *mut Node<T>;
            (*node_ptr).prev = None;
            (*node_ptr).next = self.head;
            let node = Some(node_ptr);
            match self.head {
                None => self.tail = node,
                Some(head) => (*head).prev = node,
            }
            self.head = node;
            self.len += 1;
        }
    }
    pub fn pop_back(&mut self) -> Option<T> {
        match self.tail {
            None => None,
            Some(tail) => unsafe {
                self.tail = (*tail).prev;
                match self.tail {
                    None => self.head = None,
                    Some(tail) => (*tail).next = None,
                }
                self.len -= 1;
                let node = Box::from_raw(tail);
                Some(node.elem)
            },
        }
    }
    pub fn pop_front(&mut self) -> Option<T> {
        match self.head {
            None => None,
            Some(head) => unsafe {
                self.head = (*head).next;
                match self.head {
                    None => self.tail = None,
                    Some(head) => (*head).prev = None,
                }
                self.len -= 1;
                let node = Box::from_raw(head);
                Some(node.elem)
            },
        }
    }
}

impl<T> Default for List<T> {
    fn default() -> Self {
        Self::new()
    }
}

// important, or you will easily get memory leak (when you have not poped all elements)
impl<T> Drop for List<T> {
    fn drop(&mut self) {
        while self.pop_front().is_some() {}
    }
}

impl<T: std::fmt::Display> std::fmt::Display for List<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let mut ptr = self.head;
        let mut str = String::new();
        while let Some(node) = ptr {
            unsafe {
                str.push_str(&format!("{},", (*node).elem));
                ptr = (*node).next;
            }
        }
        str.pop();
        write!(f, "{}", str)
    }
}