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 协议》,转载必须注明作者和本文链接
代码真优雅