又一个rust实现的双向list
简要说明
在上一个list的实现中，重点是是用Option<Rc<RevCell<Node<T>>>>模仿指向前后node的指针，实现了list的功能，特别是中间节点的删除、插入功能。整个代码基本都是safe代码，没有unsafe的代码。
本次的list采用的是Option<Box<Node<T>>>和*mut Node模拟next和pre指针，代码相对精炼，只是为了将*mut Node转换为&mut Node，采用了少许unsafe代码。
两者比较起来，本次的实现更加c++一些，同时也完全遵守了rust的生命周期管理。
数据结构
首先定义list中的node，如下：
type Pointer<T> = *mut Node<T>;
type NodeRef<'list, T> = &'list Node<T>;
type NodeRefMut<'list, T> = &'list mut Node<T>;
// --
#[derive(Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
pub struct Node<T> {
pub value: T,
pre: Pointer<T>,
next: Option<Box<Node<T>>>,
}
impl<T> Node<T> {
fn new_box(value: T) -> Box<Self> {
Box::new(Self {
value,
pre: ptr::null_mut(),
next: None,
})
}
fn ref_mut_from<'list>(ptr: Pointer<T>) -> NodeRefMut<'list, T> {
unsafe { &mut *ptr }
}
fn as_ptr(&self) -> Pointer<T> {
self as *const _ as *mut _
}
}
#[cfg(test)]
impl<T> Drop for Node<T> {
fn drop(&mut self) {
// dbg!(1);
}
}
#[cfg(test)]
impl<T: std::fmt::Debug> std::fmt::Debug for Node<T> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(
f,
"({}{:?}{})",
if self.pre.is_null() { "|" } else { "<" },
self.value,
if self.next.is_none() { "|" } else { ">" },
)
}
}
注意，Node中只有value是pub的，其他都是外界不可操作的，Node的new方法也不是pub。
下来是List的定义：
#[derive(Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
pub struct List<T> {
head: Option<Box<Node<T>>>,
tail: Pointer<T>,
}
#[cfg(test)]
impl<T: std::fmt::Debug> std::fmt::Debug for List<T> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
assert_eq!(true, write!(f, "[").is_ok());
for p in self.node_iter() {
assert_eq!(true, write!(f, "{:?}", p).is_ok());
}
write!(f, "]")
}
}
impl<T> Default for List<T> {
fn default() -> Self {
Self::new()
}
}
impl<T> Drop for List<T> {
fn drop(&mut self) {
while !self.is_empty() {
self.pop_back();
}
}
}
impl<T> List<T> {
fn node_ptr(&self, at: usize) -> Pointer<T> {
self.node_iter()
.nth(at)
.map_or(ptr::null_mut(), |v| v.as_ptr())
}
fn node(&self, at: usize) -> Option<NodeRef<T>> {
self.node_iter().nth(at)
}
fn node_mut(&mut self, at: usize) -> Option<NodeRefMut<T>> {
self.node_iter_mut().nth(at)
}
fn link_head(&mut self, mut node: Box<Node<T>>) -> NodeRef<T> {
node.pre = ptr::null_mut();
if let Some(head) = self.head.as_mut() {
// node is not the first element, so we should point to the node from self.head.pre
head.pre = node.as_ptr();
} else {
// node is the first element, so we should set the self.tail
self.tail = node.as_ptr();
}
node.next = self.head.take();
self.head.replace(node);
self.head.as_ref().unwrap()
}
fn link_tail(&mut self, mut node: Box<Node<T>>) -> NodeRef<T> {
debug_assert_eq!(false, self.tail.is_null());
node.next.take();
let tail = Node::<T>::ref_mut_from(self.tail);
node.pre = self.tail;
self.tail = node.as_ptr();
tail.next.replace(node);
tail.next.as_ref().unwrap()
}
fn link_between<'list>(
&'list mut self,
left: NodeRefMut<'list, T>,
right: NodeRefMut<'list, T>,
mut node: Box<Node<T>>,
) -> NodeRef<'list, T> {
node.pre = right.pre;
right.pre = node.as_ptr();
node.next = left.next.take();
left.next.replace(node);
left.next.as_ref().unwrap()
}
fn insert_unchecked(&mut self, ptr: Pointer<T>, value: T) -> NodeRef<T> {
let at = Node::<T>::ref_mut_from(ptr);
let node = Node::new_box(value);
if at.pre.is_null() {
// the at was the head, so the node will be the head now.
self.link_head(node)
} else {
let pre = Node::<T>::ref_mut_from(at.pre);
self.link_between(pre, at, node)
}
}
fn remove_unchecked(&mut self, ptr: Pointer<T>) -> Box<Node<T>> {
let at = Node::<T>::ref_mut_from(ptr);
// at实际就是指向这个node
let node = if !at.pre.is_null() {
// at不是head
let pre = Node::<T>::ref_mut_from(at.pre);
if at.next.is_some() {
// at不是tail
let next = at.next.take();
let node = pre.next.take().unwrap();
pre.next = next;
pre.next.as_mut().map(|v| v.pre = at.pre);
node
} else {
// at是tail，tail改为前一个
self.tail = at.pre;
pre.next.take().unwrap()
}
} else {
// at is head
if at.next.is_some() {
// at is not tail
at.next.as_mut().map(|v| v.pre = ptr::null_mut());
let node = self.head.take().unwrap();
self.head = at.next.take();
node
} else {
// at is tail
self.tail = ptr::null_mut();
self.head.take().unwrap()
}
};
node
}
fn node_iter(&self) -> NodeIter<'_, T> {
NodeIter {
node: self.head.as_ref().map(|v| v.as_ref()),
}
}
fn node_iter_mut(&mut self) -> NodeIterMut<'_, T> {
NodeIterMut {
node: self.head.as_mut().map(|v| v.as_mut()),
}
}
}
本次List提供了如下的功能，基本是模仿的std库中LindedList的功能，增加了在list中间增加删除node，将node移动到top和bottom的功能：
impl<T> List<T> {
pub fn new() -> Self {
Self {
head: None,
tail: std::ptr::null_mut(),
}
}
pub fn contains(&self, ptr: Pointer<T>) -> bool {
self.node_iter().any(|v| v.as_ptr() == ptr)
}
pub fn clear(&mut self) {
while self.is_empty() {
self.pop_back();
}
}
pub fn is_empty(&self) -> bool {
self.head.is_none() && self.tail.is_null()
}
pub fn len(&self) -> usize {
self.iter().count()
}
pub fn back(&self) -> Option<&T> {
if self.tail.is_null() {
None
} else {
let tail = Node::<T>::ref_mut_from(self.tail);
Some(&tail.value)
}
}
pub fn back_mut(&mut self) -> Option<&mut T> {
if self.tail.is_null() {
None
} else {
let tail = Node::<T>::ref_mut_from(self.tail);
Some(&mut tail.value)
}
}
pub fn get(&self, at: usize) -> Option<&T> {
let p = self.node(at);
p.map(|v| &v.value)
}
pub fn get_mut(&mut self, at: usize) -> Option<&mut T> {
let p = self.node_mut(at);
p.map(|v| &mut v.value)
}
pub fn front(&self) -> Option<&T> {
self.head.as_ref().map(|v| &v.value)
}
pub fn front_mut(&mut self) -> Option<&mut T> {
self.head.as_mut().map(|v| &mut v.value)
}
pub fn push_front(&mut self, value: T) -> NodeRef<T> {
if self.head.is_some() {
let at = self.head.as_ref().unwrap().as_ptr();
let at = Node::<T>::ref_mut_from(at);
self.insert_unchecked(at, value)
} else {
// list is empty
let node = Node::new_box(value);
self.link_head(node)
}
}
pub fn push_back(&mut self, value: T) -> NodeRef<T> {
if self.tail.is_null() {
// list is empty
self.push_front(value)
} else {
let node = Node::new_box(value);
self.link_tail(node)
}
}
pub fn pop_front(&mut self) -> Option<Box<Node<T>>> {
let p: Pointer<T> = self.head.as_mut().map_or(ptr::null_mut(), |v| v.as_ptr());
if p.is_null() {
None
} else {
Some(self.remove_unchecked(p))
}
}
pub fn pop_back(&mut self) -> Option<Box<Node<T>>> {
if self.tail.is_null() {
None
} else {
Some(self.remove_unchecked(self.tail))
}
}
pub fn insert(&mut self, at: usize, value: T) -> NodeRef<T> {
let p = self.node_ptr(at);
if p.is_null() {
self.push_back(value)
} else {
self.insert_unchecked(p, value)
}
}
pub fn insert_on(&mut self, ptr: Pointer<T>, value: T) -> Option<NodeRef<T>> {
if ptr.is_null() || !self.contains(ptr) {
None
} else {
Some(self.insert_unchecked(ptr, value))
}
}
pub fn remove(&mut self, at: usize) -> Option<Box<Node<T>>> {
let p = self.node_ptr(at);
if p.is_null() {
None
} else {
Some(self.remove_unchecked(p))
}
}
pub fn remove_on(&mut self, ptr: Pointer<T>) -> Option<Box<Node<T>>> {
if ptr.is_null() || !self.contains(ptr) {
None
} else {
Some(self.remove_unchecked(ptr))
}
}
pub fn top(&mut self, ptr: Pointer<T>) -> bool {
if !self.contains(ptr) {
return false;
}
if self.head.as_ref().map_or(false, |v| v.as_ptr() == ptr) {
// ptr is head
return true;
}
let mut node = self.remove_unchecked(ptr);
self.head.as_mut().map(|v| v.pre = node.as_ptr());
node.next = self.head.take();
node.pre = ptr::null_mut();
self.head.replace(node);
true
}
pub fn bottom(&mut self, ptr: Pointer<T>) -> bool {
if !self.contains(ptr) {
return false;
}
if self.tail == ptr {
// ptr is tail
return true;
}
let mut node = self.remove_unchecked(ptr);
node.pre = self.tail;
node.next.take();
let tail = Node::<T>::ref_mut_from(self.tail);
self.tail = node.as_ptr();
tail.next.replace(node);
true
}
pub fn iter(&self) -> Iter<T> {
Iter {
node: self.head.as_ref().map(|v| v.as_ref()),
}
}
pub fn iter_mut(&mut self) -> IterMut<T> {
IterMut {
node: self.head.as_mut().map(|v| v.as_mut()),
}
}
pub fn reverse_iter(&self) -> ReverseIter<T> {
ReverseIter {
node: if self.tail.is_null() {
None
} else {
Some(Node::<T>::ref_mut_from(self.tail))
},
}
}
pub fn reverse_iter_mut(&mut self) -> ReverseIterMut<T> {
ReverseIterMut {
node: if self.tail.is_null() {
None
} else {
Some(Node::<T>::ref_mut_from(self.tail))
},
}
}
}
impl<T> IntoIterator for List<T> {
type Item = Box<Node<T>>;
type IntoIter = IntoIter<T>;
#[inline]
fn into_iter(self) -> IntoIter<T> {
IntoIter(self)
}
}
impl<T> FromIterator<T> for List<T> {
fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
let mut list = Self::new();
list.extend(iter);
list
}
}
impl<'a, T: 'a + Copy> Extend<&'a T> for List<T> {
fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
self.extend(iter.into_iter().cloned());
}
}
impl<T> Extend<T> for List<T> {
fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
iter.into_iter().for_each(|v| {
self.push_back(v);
});
}
}
再最后，是相关iteraotr的定义：
struct NodeIter<'list, T> {
node: Option<NodeRef<'list, T>>,
}
impl<'list, T> Iterator for NodeIter<'list, T> {
type Item = NodeRef<'list, T>;
fn next(&mut self) -> Option<Self::Item> {
let r = self.node.take();
r.map(|v| self.node = v.next.as_ref().map(|v2| v2.as_ref()));
r
}
}
struct NodeIterMut<'list, T> {
node: Option<NodeRefMut<'list, T>>,
}
impl<'list, T> Iterator for NodeIterMut<'list, T> {
type Item = NodeRefMut<'list, T>;
fn next(&mut self) -> Option<Self::Item> {
let r = self.node.take();
r.map(|v| {
let p = v as *mut _;
self.node = v.next.as_mut().map(|v2| v2.as_mut());
Node::<T>::ref_mut_from(p)
})
}
}
pub struct Iter<'list, T> {
node: Option<NodeRef<'list, T>>,
}
impl<'list, T> Iterator for Iter<'list, T> {
type Item = &'list T;
fn next(&mut self) -> Option<Self::Item> {
let r = self.node.take();
r.map(|v| self.node = v.next.as_ref().map(|v2| v2.as_ref()));
r.map(|v| &v.value)
}
}
pub struct IterMut<'list, T> {
node: Option<NodeRefMut<'list, T>>,
}
impl<'list, T> Iterator for IterMut<'list, T> {
type Item = &'list mut T;
fn next(&mut self) -> Option<Self::Item> {
let r = self.node.take();
r.map(|v| {
let p: Pointer<T> = v as *mut _;
self.node = v.next.as_mut().map(|v2| v2.as_mut());
&mut Node::<T>::ref_mut_from(p).value
})
}
}
pub struct ReverseIter<'list, T> {
node: Option<NodeRef<'list, T>>,
}
impl<'list, T> Iterator for ReverseIter<'list, T> {
type Item = &'list T;
fn next(&mut self) -> Option<Self::Item> {
let r = self.node.take();
r.map(|v| {
self.node = if v.pre.is_null() {
None
} else {
Some(Node::<T>::ref_mut_from(v.pre))
}
});
r.map(|v| &v.value)
}
}
pub struct ReverseIterMut<'list, T> {
node: Option<NodeRefMut<'list, T>>,
}
impl<'list, T> Iterator for ReverseIterMut<'list, T> {
type Item = &'list mut T;
fn next(&mut self) -> Option<Self::Item> {
let r = self.node.take();
r.map(|v| {
let p: Pointer<T> = v as *mut _;
self.node = if v.pre.is_null() {
None
} else {
Some(Node::<T>::ref_mut_from(v.pre))
};
&mut Node::<T>::ref_mut_from(p).value
})
}
}
pub struct IntoIter<T>(List<T>);
impl<T> Iterator for IntoIter<T> {
type Item = Box<Node<T>>;
fn next(&mut self) -> Option<Self::Item> {
self.0.pop_front()
}
}
又是关于Send和Sync
List<T>和Node<T>都是!Send + !Sync，原因是他们都包含了*mut Node的filed。就算是将Node包含在Mutex中，List<T>仍然是!Send + !Sync。
那么可以使List<T>支持Send + Sync吗？好像没有什么好办法了。
在多线程或异步环境下，如何使用List<T>呢？
有一个直接生硬的办法：
- 就是直接对
List<T>实现Send，注意这是unsafe代码，自己要想清楚，后续List<T>的使用环境是否符合Send要求。代码如下：
unsafe impl<T> Send for Pointer<T> {}
- 再将
List<T>嵌入到Arc和Mutex中，如下所示：
type ListInArcMutex = Arc<Mutex<List<T>>>;
这样的ListInArcMutex就是Send + Sync了，可以在多线程之家send和sync。
注意Node仍然不是Send + Sync，在多线程操作时，要自己做同步。
Node<T>和List<T>的size是多少？
如下所说都是在64为平台，如果是32平台，请自己转换。
Node<T>中有两个指针，分别为8 bytes，value有自己实际的大小，假如value是u8、u16、u32、u64，由于内存pack的原因，所占大小都是8 bytes，所以Node<T>大小是32 bytes。
List<T>中只是两个指针，分别为8 bytes，所以List<T>的大小就是16 bytes。
具体参考第一个测试结果。
扩展
这个list目前只能插入、移动node，如果要插入另外的list，将一个list分拆成两个，需要增添一些代码，在现有的框架下修改很容易，相信聪明的你能够很容易的做到。
宏
同样的定义宏list，用来生成List<T>：
macro_rules! list {
[] => { List::new() };
[$($x: expr),+] => {{
let mut list = List::new();
$(list.push_tail($x);)+
list
}};
[$($x: expr,)+] => { list![$($x),+] }
}
测试
内存大小测试
测试代码如下：
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_list_size() {
assert_eq!(24, std::mem::size_of::<Node<f32>>());
assert_eq!(24, std::mem::size_of::<Node<u8>>());
assert_eq!(24, std::mem::size_of::<Node<u16>>());
assert_eq!(24, std::mem::size_of::<Node<u32>>());
assert_eq!(24, std::mem::size_of::<Node<u64>>());
assert_eq!(24, std::mem::size_of::<Node<usize>>());
assert_eq!(24, std::mem::size_of::<Node<char>>());
assert_eq!(24, std::mem::size_of::<Node<Box<String>>>());
assert_eq!(40, std::mem::size_of::<Node<String>>());
assert_eq!(40, std::mem::size_of::<Node<Vec<String>>>());
assert_eq!(16, std::mem::size_of::<List<u32>>());
assert_eq!(16, std::mem::size_of::<List<usize>>());
assert_eq!(16, std::mem::size_of::<List<String>>());
assert_eq!(16, std::mem::size_of::<List<char>>());
assert_eq!(16, std::mem::size_of::<List<Box<String>>>());
assert_eq!(16, std::mem::size_of::<List<Vec<String>>>());
let mut l = List::<i32>::new();
l.push_back(1);
assert_eq!(16, std::mem::size_of_val(&l));
l.push_back(2);
assert_eq!(16, std::mem::size_of_val(&l));
let node: Option<Box<Node<i32>>> = l.pop_back();
assert_eq!(8, std::mem::size_of_val(&node));
let node: Box<Node<i32>> = node.unwrap();
assert_eq!(8, std::mem::size_of_val(&node));
let node: Node<i32> = *node;
assert_eq!(24, std::mem::size_of_val(&node));
let node: &Node<i32> = &node;
assert_eq!(8, std::mem::size_of_val(&node));
let l = list![1_u32, 2, 3, 4];
assert_eq!(16, std::mem::size_of_val(&l));
}
}
如下的测试命令：
cargo test test_list_size -- --nocapture --test-threads=1
输出如下：
running 1 test
test utilites::list4::tests::test_list4_size ... ok
test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 58 filtered out
drop()方法
测试代码如下：
#[test]
fn test_list4_drop() {
let mut l2 = list![11, 22];
l2.push_back(33);
l2.push_back(55);
dbg!(&l2);
{
l2.pop_front();
}
dbg!(&l2);
l2.push_back(66);
dbg!(&l2);
let mut l = List::new();
l.push_front(10);
let n9 = l.push_front(9).as_ptr();
l.push_front(8);
assert_eq!(&8, l.get(0).unwrap());
assert_eq!(&10, l.get(2).unwrap());
assert_eq!(l.get(3).is_none(), true);
dbg!(&l);
let n7 = l.push_back(7).as_ptr();
assert_eq!(&7, l.get(3).unwrap());
let n6 = l.push_back(6).as_ptr();
assert_eq!(&6, l.get(4).unwrap());
dbg!(&l);
l.top(n7);
l.top(n6);
assert_eq!(&6, l.get(0).unwrap());
assert_eq!(&7, l.get(1).unwrap());
assert_eq!(&8, l.get(2).unwrap());
assert_eq!(&9, l.get(3).unwrap());
assert_eq!(&10, l.get(4).unwrap());
assert_eq!(l.get(5).is_none(), true);
dbg!(&l);
assert_eq!(true, l.bottom(n7));
dbg!(&l);
assert_eq!(&6, l.get(0).unwrap());
assert_eq!(&8, l.get(1).unwrap());
assert_eq!(&9, l.get(2).unwrap());
assert_eq!(&10, l.get(3).unwrap());
assert_eq!(&7, l.get(4).unwrap());
assert_eq!(l.get(5).is_none(), true);
dbg!(&l);
l.bottom(n6);
assert_eq!(&8, l.get(0).unwrap());
assert_eq!(&9, l.get(1).unwrap());
assert_eq!(&10, l.get(2).unwrap());
assert_eq!(&7, l.get(3).unwrap());
assert_eq!(&6, l.get(4).unwrap());
assert_eq!(l.get(5).is_none(), true);
dbg!(&l);
l.remove_on(n7).unwrap();
assert_eq!(&6, l.get(3).unwrap());
assert_eq!(l.get(4).is_none(), true);
dbg!(&l);
l.pop_back().unwrap();
assert_eq!(l.get(3).is_none(), true);
dbg!(&l);
assert_eq!(false, l.top(n7));
assert_eq!(false, l.bottom(n6));
assert_eq!(&8, l.get(0).unwrap());
assert_eq!(&9, l.get(1).unwrap());
assert_eq!(&10, l.get(2).unwrap());
assert_eq!(l.get(3).is_none(), true);
dbg!(&l);
l.remove_on(n9);
assert_eq!(&8, l.get(0).unwrap());
assert_eq!(&10, l.get(1).unwrap());
assert_eq!(l.get(2).is_none(), true);
dbg!(&l);
assert_eq!(true, l.remove_on(n7).is_none());
assert_eq!(true, l.remove_on(n6).is_none());
assert_eq!(&8, l.get(0).unwrap());
assert_eq!(&10, l.get(1).unwrap());
assert_eq!(l.get(2).is_none(), true);
dbg!(&l);
{
l.pop_front();
}
assert_eq!(&10, l.get(0).unwrap());
assert_eq!(l.get(1).is_none(), true);
dbg!(&l);
let v: Vec<_> = l.iter().map(|v| *v).collect();
dbg!(&v);
}
输出如下：
running 1 test
test utilites::list4::tests::test_list4_drop ... [leetcode/src/utilites/list4.rs:886] &l2 = [(|11>)(<22>)(<33>)(<55|)]
[leetcode/src/utilites/list4.rs:53] 1 = 1
[leetcode/src/utilites/list4.rs:890] &l2 = [(|22>)(<33>)(<55|)]
[leetcode/src/utilites/list4.rs:892] &l2 = [(|22>)(<33>)(<55>)(<66|)]
[leetcode/src/utilites/list4.rs:901] &l = [(|8>)(<9>)(<10|)]
[leetcode/src/utilites/list4.rs:907] &l = [(|8>)(<9>)(<10>)(<7>)(<6|)]
[leetcode/src/utilites/list4.rs:917] &l = [(|6>)(<7>)(<8>)(<9>)(<10|)]
[leetcode/src/utilites/list4.rs:920] &l = [(|6>)(<8>)(<9>)(<10>)(<7|)]
[leetcode/src/utilites/list4.rs:927] &l = [(|6>)(<8>)(<9>)(<10>)(<7|)]
[leetcode/src/utilites/list4.rs:936] &l = [(|8>)(<9>)(<10>)(<7>)(<6|)]
[leetcode/src/utilites/list4.rs:53] 1 = 1
[leetcode/src/utilites/list4.rs:941] &l = [(|8>)(<9>)(<10>)(<6|)]
[leetcode/src/utilites/list4.rs:53] 1 = 1
[leetcode/src/utilites/list4.rs:945] &l = [(|8>)(<9>)(<10|)]
[leetcode/src/utilites/list4.rs:953] &l = [(|8>)(<9>)(<10|)]
[leetcode/src/utilites/list4.rs:53] 1 = 1
[leetcode/src/utilites/list4.rs:959] &l = [(|8>)(<10|)]
[leetcode/src/utilites/list4.rs:966] &l = [(|8>)(<10|)]
[leetcode/src/utilites/list4.rs:53] 1 = 1
[leetcode/src/utilites/list4.rs:973] &l = [(|10|)]
[leetcode/src/utilites/list4.rs:976] &v = [
10,
]
[leetcode/src/utilites/list4.rs:53] 1 = 1
[leetcode/src/utilites/list4.rs:53] 1 = 1
[leetcode/src/utilites/list4.rs:53] 1 = 1
[leetcode/src/utilites/list4.rs:53] 1 = 1
[leetcode/src/utilites/list4.rs:53] 1 = 1
ok
test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 58 filtered out
playground上的代码
更多的测试代码，就不在这里啰嗦了，请参考playground的链接，有兴趣可以玩玩。 https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=decc6c31671133fba30699e3698c5f76
1
共 0 条评论, 1 页
评论区
写评论还没有评论