Rust 學習日記#鏈表

use std::fmt::Display;
use std::{alloc, ptr};
use std::marker::PhantomData;

pub(crate) struct Node<T> where T: Display + Default + Clone + PartialEq {
    data: T,
    next: *mut Node<T>,
    prev: *mut Node<T>,
}

impl<T> Node<T> where T: Display + Default + Clone + PartialEq {
    pub(crate) unsafe fn new(data: T) -> *mut Node<T> {
        let layout = alloc::Layout::new::<Node<T>>();

        let ptr = alloc::alloc(layout) as *mut Node<T>;

        if ptr.is_null() {
            alloc::handle_alloc_error(layout);
        }

        ptr.write(Node { data, next: ptr, prev: ptr });

        ptr
    }

    pub(crate) unsafe fn clear_node(node: *mut Node<T>) {
        (*node).prev = node;
        (*node).next = node;
    }
}

impl<T> Display for Node<T> where T: Display + Default + Clone + PartialEq {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        write!(f, "{}", self.data)
    }
}

impl<T> Drop for Node<T> where T: Display + Default + Clone + PartialEq {
    fn drop(&mut self) {
        unsafe {
            let layout = alloc::Layout::new::<Node<T>>();

            self.next = ptr::null_mut();
            self.prev = ptr::null_mut();

            alloc::dealloc(self as *mut Node<T> as *mut u8, layout);
        }
    }
}

pub struct LinkList<'a, T> where T: Display + Default + Clone + PartialEq {
    pub(crate) head: *mut Node<T>,
    pub(crate) len: usize,
    marker: PhantomData<&'a Node<T>>,
}

pub struct Iter<T> where T: Display + Default + Clone + PartialEq {
    pub(crate) current: *mut Node<T>,
    pub(crate) end: *mut Node<T>,
}

impl<T> Iterator for Iter<T> where T: Display + Default + Clone + PartialEq {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        if self.current == self.end {
            return None;
        }

        unsafe {
            let node = self.current;

            self.current = (*self.current).next;

            Some((*node).data.clone())
        }
    }
}

impl<'a, T> LinkList<'a, T> where T: Display + Default + Clone + PartialEq {
    pub fn new() -> LinkList<'a, T> {
        unsafe {
            Self {
                head: Node::<T>::new(T::default()),
                len: 0,
                marker: Default::default(),
            }
        }
    }

    pub fn push_back(&mut self, data: T) {
        unsafe {
            let node = Node::<T>::new(data);
            let last_node = (*self.head).prev;
            (*last_node).next = node;
            (*node).next = self.head;
            (*node).prev = last_node;
            (*self.head).prev = node;

            self.len += 1;
        }
    }

    pub fn pop_back(&mut self) -> Option<T> {
        unsafe {
            let last_node = (*self.head).prev;

            let prev_node = (*last_node).prev;
            let next_node = (*last_node).next;

            (*prev_node).next = next_node;
            (*next_node).prev = prev_node;

            let data = (*last_node).data.clone();

            ptr::drop_in_place(last_node);

            self.len -= 1;

            Some(data)
        }
    }

    pub fn push_front(&mut self, data: T) {
        unsafe {
            let node = Node::new(data);
            let first_node = (*self.head).next;
            (*first_node).prev = node;
            (*node).next = first_node;
            (*self.head).next = node;
            (*node).prev = self.head;

            self.len += 1;
        }
    }

    pub fn pop_front(&mut self) -> Option<T> {
        unsafe {
            let first_node = (*self.head).next;
            let next_node = (*first_node).next;
            Node::<T>::clear_node(first_node);
            (*self.head).next = next_node;
            (*next_node).prev = self.head;

            let data = (*first_node).data.clone();

            ptr::drop_in_place(first_node);

            self.len -= 1;

            Some(data)
        }
    }

    pub fn insert_after(&mut self, location: &T, new_data: T) {
        unsafe {
            let node = Node::new(new_data);

            if let Some(find_node) = self.find_or_default(location) {
                let next_node = (*find_node).next;
                (*find_node).next = node;
                (*node).prev = find_node;
                (*node).next = next_node;
                (*next_node).prev = node;

                self.len += 1;
            }
        }
    }

    pub fn remove_one(&mut self, data: &T) {
        if self.is_empty() {
            return;
        }

        unsafe {
            if let Some(node) = self.find_or_default(data) {
                let prev_node = (*node).prev;
                let next_node = (*node).next;

                (*prev_node).next = next_node;
                (*next_node).prev = prev_node;

                Node::<T>::clear_node(node);

                ptr::drop_in_place(node);

                self.len -= 1;
            }
        }
    }

    pub fn remove_all(&mut self, data: &T) {
        if self.is_empty() {
            return;
        }

        unsafe {
            while let Some(node) = self.find_or_default(data) {
                let prev_node = (*node).prev;
                let next_node = (*node).next;

                Node::<T>::clear_node(node);

                ptr::drop_in_place(node);

                (*prev_node).next = next_node;
                (*next_node).prev = prev_node;

                self.len -= 1;
            }
        }
    }

    pub(crate) fn find_or_default(&self, data: &T) -> Option<*mut Node<T>> {
        if self.is_empty() {
            return None;
        }

        unsafe {
            let mut current_node = (*self.head).next;
            let end = self.head;

            while current_node != end {
                if (*current_node).data == *data {
                    return Some(current_node);
                }

                current_node = (*current_node).next;
            }

            None
        }
    }

    pub(crate) fn find_all(&self, data: &T) -> Option<Vec<*mut Node<T>>> {
        if self.is_empty() {
            return None;
        }

        let mut vec = vec![];

        unsafe {
            let mut current_node = (*self.head).next;
            let end = self.head;

            while current_node != end {
                if (*current_node).data == *data {
                    vec.push(current_node);
                }

                current_node = (*current_node).next;
            }

            Some(vec)
        }
    }

    pub fn is_empty(&self) -> bool {
        unsafe { (*self.head).next == self.head && (*self.head).prev == self.head }
    }

    pub fn len(&self) -> usize {
        self.len
    }

    pub fn iter(&self) -> Iter<T> {
        unsafe {
            Iter { current: (*self.head).next, end: self.head }
        }
    }

    pub fn last(&'a self) -> Option<&T> {
        if self.is_empty() {
            return None;
        }

        let last = unsafe { (*self.head).prev };

        Some(unsafe { &((*last).data) })
    }

    pub fn first(&'a self) -> Option<&T> {
        if self.is_empty() {
            return None;
        }

        let first = unsafe { (*self.head).next };

        Some(unsafe { &((*first).data) })
    }
}

impl<T> Drop for LinkList<'_, T> where T: Display + Default + Clone + PartialEq {
    fn drop(&mut self) {
        unsafe {
            let mut start = (*self.head).next;
            let end = self.head;

            while start != end {
                let next_node = (*start).next;
                ptr::drop_in_place(start);
                start = next_node;
            }

            ptr::drop_in_place(end);
        }
    }
}

impl<T> Display for LinkList<'_, T> where T: Display + Default + Clone + PartialEq {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        unsafe {
            let mut start = (*self.head).next;
            let end = self.head;

            let mut s = String::new();

            while start != end {
                s.push_str(format!("{} ", *start).as_str());

                start = (*start).next;
            }

            write!(f, "{}", s)
        }
    }
}

#[cfg(test)]
mod tests {
    use crate::{LinkList, Node};

    #[test]
    fn node_test() {
        unsafe {
            let node = Node::<i32>::new(32);
        }
    }

    #[test]
    fn push_back_test() {
        let mut list = LinkList::<i32>::new();
        list.push_back(32);
        list.push_back(33);

        println!("{}", list);
    }

    #[test]
    fn push_front_test() {
        let mut list = LinkList::<i32>::new();
        list.push_front(32);
        list.push_front(33);
        list.push_front(34);

        println!("{}", list);
    }

    #[test]
    fn find_or_default_test() {
        let mut list = LinkList::<i32>::new();
        list.push_back(32);
        list.push_back(33);
        list.push_back(34);
        if let Some(x) = list.find_or_default(&32) {
            unsafe { println!("{}", (*x).data); }
        }
    }

    #[test]
    fn insert_after_test() {
        let mut list = LinkList::<i32>::new();
        list.push_back(32);
        list.push_back(33);
        list.push_back(34);
        list.push_back(35);
        list.push_back(36);
        list.push_back(37);
        list.insert_after(&32, 100);

        println!("{}", list);
    }

    #[test]
    fn remove_one_test() {
        let mut list = LinkList::<i32>::new();
        list.push_back(32);
        list.push_back(33);
        list.push_back(33);

        println!("Remove before: {}", list);

        list.remove_one(&32);
        list.remove_one(&33);

        println!("After remove: {}", list);
    }

    #[test]
    fn len_test() {
        let mut list = LinkList::<i32>::new();
        list.push_back(32);
        list.push_back(33);
        list.push_back(34);
        list.push_back(35);
        list.push_back(36);
        list.push_back(37);
        list.insert_after(&32, 100);

        println!("Pop back before: {}\n{}", list, list.len());

        list.pop_back();

        println!("Pop back after: {}\n{}", list, list.len());
    }

    #[test]
    fn iter_test() {
        let mut list = LinkList::<i32>::new();
        list.push_back(32);
        list.push_back(33);
        list.push_back(34);
        list.push_back(35);

        let mut iter = list.iter();

        list.pop_back();

        while let Some(value) = iter.next() {
            println!("{}", value);
        }
    }

    #[test]
    fn find_all_test() {
        let mut list = LinkList::<i32>::new();
        list.push_back(32);
        list.push_back(33);
        list.push_back(34);
        list.push_back(35);
        list.push_back(32);
        list.push_front(32);

        if let Some(vec) = list.find_all(&32) {
            for item in vec {
                unsafe {
                    println!("{}", *item);
                }
            }
        }
    }

    #[test]
    fn remove_all_test() {
        let mut list = LinkList::<i32>::new();
        list.push_back(32);
        list.push_back(33);
        list.push_back(34);
        list.push_back(35);
        list.push_back(32);
        list.push_back(33);
        list.push_front(33);

        println!("Remove before: {}\n{}", list, list.len());

        list.remove_all(&33);

        println!("Remove after: {}\n{}", list, list.len());
    }

    #[test]
    fn first_last_test() {
        let mut list = LinkList::<i32>::new();
        list.push_back(32);
        list.push_back(33);
        list.push_back(34);
        list.push_back(35);

        if let Some(first) = list.first() {
            println!("first node value: {}", first);
        }

        if let Some(last) = list.last() {
            println!("last node value: {}", last);
        }
    }
}

本作品采用《CC 协议》，转载必须注明作者和本文链接