use crate::Adapter;
use crate::IntrusivePointer;
use core::cell::Cell;
use core::fmt;
use core::ptr;
pub struct Link {
next: Cell<NodePtr>,
prev: Cell<NodePtr>,
}
impl Link {
#[inline]
pub const fn new() -> Link {
Link {
next: Cell::new(UNLINKED_MARKER),
prev: Cell::new(UNLINKED_MARKER),
}
}
#[inline]
pub fn is_linked(&self) -> bool {
self.next.get() != UNLINKED_MARKER
}
#[inline]
pub unsafe fn force_unlink(&self) {
self.next.set(UNLINKED_MARKER);
}
}
unsafe impl Send for Link {}
impl Clone for Link {
#[inline]
fn clone(&self) -> Link {
Link::new()
}
}
impl Default for Link {
#[inline]
fn default() -> Link {
Link::new()
}
}
impl fmt::Debug for Link {
#[inline]
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
if self.is_linked() {
write!(f, "linked")
} else {
write!(f, "unlinked")
}
}
}
#[derive(Copy, Clone, PartialEq, Eq)]
struct NodePtr(*const Link);
const UNLINKED_MARKER: NodePtr = NodePtr(1 as *const _);
impl NodePtr {
#[inline]
fn null() -> NodePtr {
NodePtr(ptr::null())
}
#[inline]
fn is_null(self) -> bool {
self.0.is_null()
}
#[inline]
unsafe fn next(self) -> NodePtr {
(*self.0).next.get()
}
#[inline]
unsafe fn prev(self) -> NodePtr {
(*self.0).prev.get()
}
#[inline]
unsafe fn set_next(self, next: NodePtr) {
(*self.0).next.set(next);
}
#[inline]
unsafe fn set_prev(self, prev: NodePtr) {
(*self.0).prev.set(prev);
}
#[inline]
unsafe fn unlink(self) {
self.set_next(UNLINKED_MARKER);
}
#[inline]
unsafe fn link_between(self, prev: NodePtr, next: NodePtr) {
if !prev.is_null() {
prev.set_next(self);
}
if !next.is_null() {
next.set_prev(self);
}
self.set_next(next);
self.set_prev(prev);
}
#[inline]
unsafe fn link_after(self, prev: NodePtr) {
self.link_between(prev, prev.next());
}
#[inline]
unsafe fn link_before(self, next: NodePtr) {
self.link_between(next.prev(), next);
}
#[inline]
unsafe fn replace_with(self, new: NodePtr) {
if !self.prev().is_null() {
self.prev().set_next(new);
}
if !self.next().is_null() {
self.next().set_prev(new);
}
new.set_next(self.next());
new.set_prev(self.prev());
self.unlink();
}
#[inline]
unsafe fn remove(self) {
if !self.next().is_null() {
self.next().set_prev(self.prev());
}
if !self.prev().is_null() {
self.prev().set_next(self.next());
}
self.unlink();
}
#[inline]
unsafe fn splice(start: NodePtr, end: NodePtr, prev: NodePtr, next: NodePtr) {
start.set_prev(prev);
end.set_next(next);
if !prev.is_null() {
prev.set_next(start);
}
if !next.is_null() {
next.set_prev(end);
}
}
}
pub struct Cursor<'a, A: Adapter<Link = Link>> {
current: NodePtr,
list: &'a LinkedList<A>,
}
impl<'a, A: Adapter<Link = Link> + 'a> Clone for Cursor<'a, A> {
#[inline]
fn clone(&self) -> Cursor<'a, A> {
Cursor {
current: self.current,
list: self.list,
}
}
}
impl<'a, A: Adapter<Link = Link>> Cursor<'a, A> {
#[inline]
pub fn is_null(&self) -> bool {
self.current.is_null()
}
#[inline]
pub fn get(&self) -> Option<&'a A::Value> {
if self.is_null() {
None
} else {
Some(unsafe { &*self.list.adapter.get_value(self.current.0) })
}
}
#[inline]
pub fn clone_pointer(&self) -> Option<A::Pointer>
where
A::Pointer: Clone,
{
let raw_pointer = self.get()? as *const A::Value;
Some(unsafe { crate::intrusive_pointer::clone_pointer_from_raw(raw_pointer) })
}
#[inline]
pub fn move_next(&mut self) {
if self.is_null() {
self.current = self.list.head;
} else {
self.current = unsafe { self.current.next() };
}
}
#[inline]
pub fn move_prev(&mut self) {
if self.is_null() {
self.current = self.list.tail;
} else {
self.current = unsafe { self.current.prev() };
}
}
#[inline]
pub fn peek_next(&self) -> Cursor<'_, A> {
let mut next = self.clone();
next.move_next();
next
}
#[inline]
pub fn peek_prev(&self) -> Cursor<'_, A> {
let mut prev = self.clone();
prev.move_prev();
prev
}
}
pub struct CursorMut<'a, A: Adapter<Link = Link>> {
current: NodePtr,
list: &'a mut LinkedList<A>,
}
impl<'a, A: Adapter<Link = Link>> CursorMut<'a, A> {
#[inline]
pub fn is_null(&self) -> bool {
self.current.is_null()
}
#[inline]
pub fn get(&self) -> Option<&A::Value> {
if self.is_null() {
None
} else {
Some(unsafe { &*self.list.adapter.get_value(self.current.0) })
}
}
#[inline]
pub fn as_cursor(&self) -> Cursor<'_, A> {
Cursor {
current: self.current,
list: self.list,
}
}
#[inline]
pub fn move_next(&mut self) {
if self.is_null() {
self.current = self.list.head;
} else {
self.current = unsafe { self.current.next() };
}
}
#[inline]
pub fn move_prev(&mut self) {
if self.is_null() {
self.current = self.list.tail;
} else {
self.current = unsafe { self.current.prev() };
}
}
#[inline]
pub fn peek_next(&self) -> Cursor<'_, A> {
let mut next = self.as_cursor();
next.move_next();
next
}
#[inline]
pub fn peek_prev(&self) -> Cursor<'_, A> {
let mut prev = self.as_cursor();
prev.move_prev();
prev
}
#[inline]
pub fn remove(&mut self) -> Option<A::Pointer> {
unsafe {
if self.is_null() {
return None;
}
if self.list.head == self.current {
self.list.head = self.current.next();
}
if self.list.tail == self.current {
self.list.tail = self.current.prev();
}
let next = self.current.next();
let result = self.current.0;
self.current.remove();
self.current = next;
Some(A::Pointer::from_raw(self.list.adapter.get_value(result)))
}
}
#[inline]
pub fn replace_with(&mut self, val: A::Pointer) -> Result<A::Pointer, A::Pointer> {
if self.is_null() {
return Err(val);
}
unsafe {
let new = self.list.node_from_value(val);
if self.list.head == self.current {
self.list.head = new;
}
if self.list.tail == self.current {
self.list.tail = new;
}
let result = self.current.0;
self.current.replace_with(new);
self.current = new;
Ok(A::Pointer::from_raw(self.list.adapter.get_value(result)))
}
}
#[inline]
pub fn insert_after(&mut self, val: A::Pointer) {
unsafe {
let new = self.list.node_from_value(val);
if self.is_null() {
new.link_between(NodePtr::null(), self.list.head);
self.list.head = new;
} else {
new.link_after(self.current);
}
if self.list.tail == self.current {
self.list.tail = new;
}
}
}
#[inline]
pub fn insert_before(&mut self, val: A::Pointer) {
unsafe {
let new = self.list.node_from_value(val);
if self.is_null() {
new.link_between(self.list.tail, NodePtr::null());
self.list.tail = new;
} else {
new.link_before(self.current);
}
if self.list.head == self.current {
self.list.head = new;
}
}
}
#[inline]
pub fn splice_after(&mut self, mut list: LinkedList<A>) {
if !list.is_empty() {
unsafe {
if self.is_null() {
NodePtr::splice(list.head, list.tail, NodePtr::null(), self.list.head);
self.list.head = list.head;
} else {
NodePtr::splice(list.head, list.tail, self.current, self.current.next());
}
if self.list.tail == self.current {
self.list.tail = list.tail;
}
list.head = NodePtr::null();
}
}
}
#[inline]
pub fn splice_before(&mut self, mut list: LinkedList<A>) {
if !list.is_empty() {
unsafe {
if self.is_null() {
NodePtr::splice(list.head, list.tail, self.list.tail, NodePtr::null());
self.list.tail = list.tail;
} else {
NodePtr::splice(list.head, list.tail, self.current.prev(), self.current);
}
if self.list.head == self.current {
self.list.head = list.head;
}
list.head = NodePtr::null();
}
}
}
#[inline]
pub fn split_after(&mut self) -> LinkedList<A>
where
A: Clone,
{
if self.is_null() {
let list = LinkedList {
head: self.list.head,
tail: self.list.tail,
adapter: self.list.adapter.clone(),
};
self.list.head = NodePtr::null();
self.list.tail = NodePtr::null();
list
} else {
unsafe {
let mut list = LinkedList {
head: self.current.next(),
tail: self.list.tail,
adapter: self.list.adapter.clone(),
};
if !list.head.is_null() {
list.head.set_prev(NodePtr::null());
} else {
list.tail = NodePtr::null();
}
self.current.set_next(NodePtr::null());
self.list.tail = self.current;
list
}
}
}
#[inline]
pub fn split_before(&mut self) -> LinkedList<A>
where
A: Clone,
{
if self.is_null() {
let list = LinkedList {
head: self.list.head,
tail: self.list.tail,
adapter: self.list.adapter.clone(),
};
self.list.head = NodePtr::null();
self.list.tail = NodePtr::null();
list
} else {
unsafe {
let mut list = LinkedList {
head: self.list.head,
tail: self.current.prev(),
adapter: self.list.adapter.clone(),
};
if !list.tail.is_null() {
list.tail.set_next(NodePtr::null());
} else {
list.head = NodePtr::null();
}
self.current.set_prev(NodePtr::null());
self.list.head = self.current;
list
}
}
}
}
pub struct LinkedList<A: Adapter<Link = Link>> {
head: NodePtr,
tail: NodePtr,
adapter: A,
}
impl<A: Adapter<Link = Link>> LinkedList<A> {
#[inline]
fn node_from_value(&self, val: A::Pointer) -> NodePtr {
unsafe {
assert!(
!(*self.adapter.get_link(&*val)).is_linked(),
"attempted to insert an object that is already linked"
);
NodePtr(self.adapter.get_link(val.into_raw()))
}
}
#[cfg(feature = "nightly")]
#[inline]
pub const fn new(adapter: A) -> LinkedList<A> {
LinkedList {
head: NodePtr(ptr::null()),
tail: NodePtr(ptr::null()),
adapter,
}
}
#[cfg(not(feature = "nightly"))]
#[inline]
pub fn new(adapter: A) -> LinkedList<A> {
LinkedList {
head: NodePtr::null(),
tail: NodePtr::null(),
adapter,
}
}
#[inline]
pub fn is_empty(&self) -> bool {
self.head.is_null()
}
#[inline]
pub fn cursor(&self) -> Cursor<'_, A> {
Cursor {
current: NodePtr::null(),
list: self,
}
}
#[inline]
pub fn cursor_mut(&mut self) -> CursorMut<'_, A> {
CursorMut {
current: NodePtr::null(),
list: self,
}
}
#[inline]
pub unsafe fn cursor_from_ptr(&self, ptr: *const A::Value) -> Cursor<'_, A> {
Cursor {
current: NodePtr(self.adapter.get_link(ptr)),
list: self,
}
}
#[inline]
pub unsafe fn cursor_mut_from_ptr(&mut self, ptr: *const A::Value) -> CursorMut<'_, A> {
CursorMut {
current: NodePtr(self.adapter.get_link(ptr)),
list: self,
}
}
#[inline]
pub fn front(&self) -> Cursor<'_, A> {
let mut cursor = self.cursor();
cursor.move_next();
cursor
}
#[inline]
pub fn front_mut(&mut self) -> CursorMut<'_, A> {
let mut cursor = self.cursor_mut();
cursor.move_next();
cursor
}
#[inline]
pub fn back(&self) -> Cursor<'_, A> {
let mut cursor = self.cursor();
cursor.move_prev();
cursor
}
#[inline]
pub fn back_mut(&mut self) -> CursorMut<'_, A> {
let mut cursor = self.cursor_mut();
cursor.move_prev();
cursor
}
#[inline]
pub fn iter(&self) -> Iter<'_, A> {
Iter {
head: self.head,
tail: self.tail,
list: self,
}
}
#[inline]
pub fn clear(&mut self) {
let mut current = self.head;
self.head = NodePtr::null();
self.tail = NodePtr::null();
while !current.is_null() {
unsafe {
let next = current.next();
current.unlink();
A::Pointer::from_raw(self.adapter.get_value(current.0));
current = next;
}
}
}
#[inline]
pub fn fast_clear(&mut self) {
self.head = NodePtr::null();
}
#[inline]
pub fn take(&mut self) -> LinkedList<A>
where
A: Clone,
{
let list = LinkedList {
head: self.head,
tail: self.tail,
adapter: self.adapter.clone(),
};
self.head = NodePtr::null();
self.tail = NodePtr::null();
list
}
#[inline]
pub fn push_front(&mut self, val: A::Pointer) {
self.cursor_mut().insert_after(val);
}
#[inline]
pub fn push_back(&mut self, val: A::Pointer) {
self.cursor_mut().insert_before(val);
}
#[inline]
pub fn pop_front(&mut self) -> Option<A::Pointer> {
self.front_mut().remove()
}
#[inline]
pub fn pop_back(&mut self) -> Option<A::Pointer> {
self.back_mut().remove()
}
}
unsafe impl<A: Adapter<Link = Link> + Sync> Sync for LinkedList<A> where A::Value: Sync {}
unsafe impl<A: Adapter<Link = Link> + Send> Send for LinkedList<A> where A::Pointer: Send {}
impl<A: Adapter<Link = Link>> Drop for LinkedList<A> {
#[inline]
fn drop(&mut self) {
self.clear();
}
}
impl<A: Adapter<Link = Link>> IntoIterator for LinkedList<A> {
type Item = A::Pointer;
type IntoIter = IntoIter<A>;
#[inline]
fn into_iter(self) -> IntoIter<A> {
IntoIter { list: self }
}
}
impl<'a, A: Adapter<Link = Link> + 'a> IntoIterator for &'a LinkedList<A> {
type Item = &'a A::Value;
type IntoIter = Iter<'a, A>;
#[inline]
fn into_iter(self) -> Iter<'a, A> {
self.iter()
}
}
impl<A: Adapter<Link = Link> + Default> Default for LinkedList<A> {
fn default() -> LinkedList<A> {
LinkedList::new(A::default())
}
}
impl<A: Adapter<Link = Link>> fmt::Debug for LinkedList<A>
where
A::Value: fmt::Debug,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_list().entries(self.iter()).finish()
}
}
pub struct Iter<'a, A: Adapter<Link = Link>> {
head: NodePtr,
tail: NodePtr,
list: &'a LinkedList<A>,
}
impl<'a, A: Adapter<Link = Link> + 'a> Iterator for Iter<'a, A> {
type Item = &'a A::Value;
#[inline]
fn next(&mut self) -> Option<&'a A::Value> {
if self.head.is_null() {
None
} else {
let head = self.head;
if head == self.tail {
self.head = NodePtr::null();
self.tail = NodePtr::null();
} else {
self.head = unsafe { head.next() };
}
Some(unsafe { &*self.list.adapter.get_value(head.0) })
}
}
}
impl<'a, A: Adapter<Link = Link> + 'a> DoubleEndedIterator for Iter<'a, A> {
#[inline]
fn next_back(&mut self) -> Option<&'a A::Value> {
if self.tail.is_null() {
None
} else {
let tail = self.tail;
if self.head == tail {
self.tail = NodePtr::null();
self.head = NodePtr::null();
} else {
self.tail = unsafe { tail.prev() };
}
Some(unsafe { &*self.list.adapter.get_value(tail.0) })
}
}
}
impl<'a, A: Adapter<Link = Link> + 'a> Clone for Iter<'a, A> {
#[inline]
fn clone(&self) -> Iter<'a, A> {
Iter {
head: self.head,
tail: self.tail,
list: self.list,
}
}
}
pub struct IntoIter<A: Adapter<Link = Link>> {
list: LinkedList<A>,
}
impl<A: Adapter<Link = Link>> Iterator for IntoIter<A> {
type Item = A::Pointer;
#[inline]
fn next(&mut self) -> Option<A::Pointer> {
self.list.pop_front()
}
}
impl<A: Adapter<Link = Link>> DoubleEndedIterator for IntoIter<A> {
#[inline]
fn next_back(&mut self) -> Option<A::Pointer> {
self.list.pop_back()
}
}
#[cfg(test)]
mod tests {
use super::{Link, LinkedList};
use crate::UnsafeRef;
use std::boxed::Box;
use std::fmt;
use std::vec::Vec;
#[derive(Clone)]
struct Obj {
link1: Link,
link2: Link,
value: u32,
}
impl fmt::Debug for Obj {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{}", self.value)
}
}
intrusive_adapter!(ObjAdapter1 = UnsafeRef<Obj>: Obj { link1: Link });
intrusive_adapter!(ObjAdapter2 = UnsafeRef<Obj>: Obj { link2: Link });
fn make_obj(value: u32) -> UnsafeRef<Obj> {
UnsafeRef::from_box(Box::new(Obj {
link1: Link::new(),
link2: Link::default(),
value: value,
}))
}
#[test]
fn test_link() {
let a = make_obj(1);
assert!(!a.link1.is_linked());
assert!(!a.link2.is_linked());
let mut b = LinkedList::<ObjAdapter1>::default();
assert!(b.is_empty());
b.cursor_mut().insert_after(a.clone());
assert!(!b.is_empty());
assert!(a.link1.is_linked());
assert!(!a.link2.is_linked());
assert_eq!(format!("{:?}", a.link1), "linked");
assert_eq!(format!("{:?}", a.link2), "unlinked");
assert_eq!(
b.front_mut().remove().unwrap().as_ref() as *const _,
a.as_ref() as *const _
);
assert!(b.is_empty());
assert!(!a.link1.is_linked());
assert!(!a.link2.is_linked());
}
#[test]
fn test_cursor() {
let a = make_obj(1);
let b = make_obj(2);
let c = make_obj(3);
let mut l = LinkedList::new(ObjAdapter1::new());
let mut cur = l.cursor_mut();
assert!(cur.is_null());
assert!(cur.get().is_none());
assert!(cur.remove().is_none());
assert_eq!(
cur.replace_with(a.clone()).unwrap_err().as_ref() as *const _,
a.as_ref() as *const _
);
cur.insert_before(a.clone());
cur.insert_before(c.clone());
cur.move_prev();
cur.insert_before(b.clone());
assert!(cur.peek_next().is_null());
cur.move_next();
assert!(cur.is_null());
cur.move_next();
assert!(cur.peek_prev().is_null());
assert!(!cur.is_null());
assert_eq!(cur.get().unwrap() as *const _, a.as_ref() as *const _);
{
let mut cur2 = cur.as_cursor();
assert_eq!(cur2.get().unwrap() as *const _, a.as_ref() as *const _);
assert_eq!(cur2.peek_next().get().unwrap().value, 2);
cur2.move_next();
assert_eq!(cur2.get().unwrap().value, 2);
cur2.move_next();
assert_eq!(cur2.peek_prev().get().unwrap().value, 2);
assert_eq!(cur2.get().unwrap() as *const _, c.as_ref() as *const _);
cur2.move_prev();
assert_eq!(cur2.get().unwrap() as *const _, b.as_ref() as *const _);
cur2.move_next();
assert_eq!(cur2.get().unwrap() as *const _, c.as_ref() as *const _);
cur2.move_next();
assert!(cur2.is_null());
assert!(cur2.clone().get().is_none());
}
assert_eq!(cur.get().unwrap() as *const _, a.as_ref() as *const _);
cur.move_next();
assert_eq!(
cur.remove().unwrap().as_ref() as *const _,
b.as_ref() as *const _
);
assert_eq!(cur.get().unwrap() as *const _, c.as_ref() as *const _);
cur.insert_after(b.clone());
assert_eq!(cur.get().unwrap() as *const _, c.as_ref() as *const _);
cur.move_prev();
assert_eq!(cur.get().unwrap() as *const _, a.as_ref() as *const _);
assert_eq!(
cur.remove().unwrap().as_ref() as *const _,
a.as_ref() as *const _
);
assert!(!a.link1.is_linked());
assert!(c.link1.is_linked());
assert_eq!(cur.get().unwrap() as *const _, c.as_ref() as *const _);
assert_eq!(
cur.replace_with(a.clone()).unwrap().as_ref() as *const _,
c.as_ref() as *const _
);
assert!(a.link1.is_linked());
assert!(!c.link1.is_linked());
assert_eq!(cur.get().unwrap() as *const _, a.as_ref() as *const _);
cur.move_next();
assert_eq!(
cur.replace_with(c.clone()).unwrap().as_ref() as *const _,
b.as_ref() as *const _
);
assert!(a.link1.is_linked());
assert!(!b.link1.is_linked());
assert!(c.link1.is_linked());
assert_eq!(cur.get().unwrap() as *const _, c.as_ref() as *const _);
}
#[test]
fn test_push_pop() {
let a = make_obj(1);
let b = make_obj(2);
let c = make_obj(3);
let mut l = LinkedList::new(ObjAdapter1::new());
l.push_front(a);
assert_eq!(l.iter().map(|x| x.value).collect::<Vec<_>>(), [1]);
l.push_front(b);
assert_eq!(l.iter().map(|x| x.value).collect::<Vec<_>>(), [2, 1]);
l.push_back(c);
assert_eq!(l.iter().map(|x| x.value).collect::<Vec<_>>(), [2, 1, 3]);
assert_eq!(l.pop_front().unwrap().value, 2);
assert_eq!(l.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 3]);
assert_eq!(l.pop_back().unwrap().value, 3);
assert_eq!(l.iter().map(|x| x.value).collect::<Vec<_>>(), [1]);
assert_eq!(l.pop_front().unwrap().value, 1);
assert_eq!(l.iter().map(|x| x.value).collect::<Vec<_>>(), []);
assert!(l.pop_front().is_none());
assert_eq!(l.iter().map(|x| x.value).collect::<Vec<_>>(), []);
assert!(l.pop_back().is_none());
assert_eq!(l.iter().map(|x| x.value).collect::<Vec<_>>(), []);
}
#[test]
fn test_split_splice() {
let mut l1 = LinkedList::new(ObjAdapter1::new());
let mut l2 = LinkedList::new(ObjAdapter1::new());
let mut l3 = LinkedList::new(ObjAdapter1::new());
let a = make_obj(1);
let b = make_obj(2);
let c = make_obj(3);
let d = make_obj(4);
l1.cursor_mut().insert_before(a);
l1.cursor_mut().insert_before(b);
l1.cursor_mut().insert_before(c);
l1.cursor_mut().insert_before(d);
assert_eq!(l1.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 2, 3, 4]);
assert_eq!(l2.iter().map(|x| x.value).collect::<Vec<_>>(), []);
assert_eq!(l3.iter().map(|x| x.value).collect::<Vec<_>>(), []);
{
let mut cur = l1.front_mut();
cur.move_next();
l2 = cur.split_after();
}
assert_eq!(l1.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 2]);
assert_eq!(l2.iter().map(|x| x.value).collect::<Vec<_>>(), [3, 4]);
assert_eq!(l3.iter().map(|x| x.value).collect::<Vec<_>>(), []);
{
let mut cur = l2.back_mut();
l3 = cur.split_before();
}
assert_eq!(l1.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 2]);
assert_eq!(l2.iter().map(|x| x.value).collect::<Vec<_>>(), [4]);
assert_eq!(l3.iter().map(|x| x.value).collect::<Vec<_>>(), [3]);
{
let mut cur = l1.front_mut();
cur.splice_after(l2.take());
}
assert_eq!(l1.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 4, 2]);
assert_eq!(l2.iter().map(|x| x.value).collect::<Vec<_>>(), []);
assert_eq!(l3.iter().map(|x| x.value).collect::<Vec<_>>(), [3]);
{
let mut cur = l1.front_mut();
cur.move_next();
cur.splice_before(l3.take());
}
assert_eq!(l1.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 3, 4, 2]);
assert_eq!(l2.iter().map(|x| x.value).collect::<Vec<_>>(), []);
assert_eq!(l3.iter().map(|x| x.value).collect::<Vec<_>>(), []);
{
let mut cur = l2.cursor_mut();
cur.splice_after(l1.take());
}
assert_eq!(l1.iter().map(|x| x.value).collect::<Vec<_>>(), []);
assert_eq!(l2.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 3, 4, 2]);
assert_eq!(l3.iter().map(|x| x.value).collect::<Vec<_>>(), []);
{
let mut cur = l1.cursor_mut();
cur.splice_before(l2.take());
}
assert_eq!(l1.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 3, 4, 2]);
assert_eq!(l2.iter().map(|x| x.value).collect::<Vec<_>>(), []);
assert_eq!(l3.iter().map(|x| x.value).collect::<Vec<_>>(), []);
{
let mut cur = l1.cursor_mut();
l2 = cur.split_after();
}
assert_eq!(l1.iter().map(|x| x.value).collect::<Vec<_>>(), []);
assert_eq!(l2.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 3, 4, 2]);
assert_eq!(l3.iter().map(|x| x.value).collect::<Vec<_>>(), []);
{
let mut cur = l2.cursor_mut();
l1 = cur.split_before();
}
assert_eq!(l1.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 3, 4, 2]);
assert_eq!(l2.iter().map(|x| x.value).collect::<Vec<_>>(), []);
assert_eq!(l3.iter().map(|x| x.value).collect::<Vec<_>>(), []);
{
let mut cur = l1.front_mut();
l2 = cur.split_before();
}
assert_eq!(l1.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 3, 4, 2]);
assert_eq!(l2.iter().map(|x| x.value).collect::<Vec<_>>(), []);
assert_eq!(l3.iter().map(|x| x.value).collect::<Vec<_>>(), []);
{
let mut cur = l1.back_mut();
l2 = cur.split_after();
}
assert_eq!(l1.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 3, 4, 2]);
assert_eq!(l2.iter().map(|x| x.value).collect::<Vec<_>>(), []);
assert_eq!(l3.iter().map(|x| x.value).collect::<Vec<_>>(), []);
}
#[test]
fn test_iter() {
let mut l = LinkedList::new(ObjAdapter1::new());
let a = make_obj(1);
let b = make_obj(2);
let c = make_obj(3);
let d = make_obj(4);
l.cursor_mut().insert_before(a.clone());
l.cursor_mut().insert_before(b.clone());
l.cursor_mut().insert_before(c.clone());
l.cursor_mut().insert_before(d.clone());
assert_eq!(l.front().get().unwrap().value, 1);
assert_eq!(l.back().get().unwrap().value, 4);
unsafe {
assert_eq!(l.cursor_from_ptr(b.as_ref()).get().unwrap().value, 2);
assert_eq!(l.cursor_mut_from_ptr(c.as_ref()).get().unwrap().value, 3);
}
let mut v = Vec::new();
for x in &l {
v.push(x.value);
}
assert_eq!(v, [1, 2, 3, 4]);
assert_eq!(
l.iter().clone().map(|x| x.value).collect::<Vec<_>>(),
[1, 2, 3, 4]
);
assert_eq!(
l.iter().rev().map(|x| x.value).collect::<Vec<_>>(),
[4, 3, 2, 1]
);
assert_eq!(l.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 2, 3, 4]);
assert_eq!(format!("{:?}", l), "[1, 2, 3, 4]");
let mut v = Vec::new();
for x in l.take() {
v.push(x.value);
}
assert_eq!(v, [1, 2, 3, 4]);
assert!(l.is_empty());
assert!(!a.link1.is_linked());
assert!(!b.link1.is_linked());
assert!(!c.link1.is_linked());
assert!(!d.link1.is_linked());
l.cursor_mut().insert_before(a.clone());
l.cursor_mut().insert_before(b.clone());
l.cursor_mut().insert_before(c.clone());
l.cursor_mut().insert_before(d.clone());
l.clear();
assert!(l.is_empty());
assert!(!a.link1.is_linked());
assert!(!b.link1.is_linked());
assert!(!c.link1.is_linked());
assert!(!d.link1.is_linked());
v.clear();
l.cursor_mut().insert_before(a.clone());
l.cursor_mut().insert_before(b.clone());
l.cursor_mut().insert_before(c.clone());
l.cursor_mut().insert_before(d.clone());
for x in l.into_iter().rev() {
v.push(x.value);
}
assert_eq!(v, [4, 3, 2, 1]);
assert!(!a.link1.is_linked());
assert!(!b.link1.is_linked());
assert!(!c.link1.is_linked());
assert!(!d.link1.is_linked());
}
#[test]
fn test_multi_list() {
let mut l1 = LinkedList::new(ObjAdapter1::new());
let mut l2 = LinkedList::new(ObjAdapter2::new());
let a = make_obj(1);
let b = make_obj(2);
let c = make_obj(3);
let d = make_obj(4);
l1.cursor_mut().insert_before(a.clone());
l1.cursor_mut().insert_before(b.clone());
l1.cursor_mut().insert_before(c.clone());
l1.cursor_mut().insert_before(d.clone());
l2.cursor_mut().insert_after(a.clone());
l2.cursor_mut().insert_after(b.clone());
l2.cursor_mut().insert_after(c.clone());
l2.cursor_mut().insert_after(d.clone());
assert_eq!(l1.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 2, 3, 4]);
assert_eq!(l2.iter().map(|x| x.value).collect::<Vec<_>>(), [4, 3, 2, 1]);
}
#[test]
fn test_force_unlink() {
let mut l = LinkedList::new(ObjAdapter1::new());
let a = make_obj(1);
let b = make_obj(2);
let c = make_obj(3);
l.cursor_mut().insert_before(a.clone());
l.cursor_mut().insert_before(b.clone());
l.cursor_mut().insert_before(c.clone());
l.fast_clear();
assert!(l.is_empty());
assert!(a.link1.is_linked());
assert!(b.link1.is_linked());
assert!(c.link1.is_linked());
unsafe {
a.link1.force_unlink();
b.link1.force_unlink();
c.link1.force_unlink();
}
assert!(l.is_empty());
assert!(!a.link1.is_linked());
assert!(!b.link1.is_linked());
assert!(!c.link1.is_linked());
}
#[test]
fn test_non_static() {
#[derive(Clone)]
struct Obj<'a, T> {
link: Link,
value: &'a T,
}
intrusive_adapter!(ObjAdapter<'a, T> = &'a Obj<'a, T>: Obj<'a, T> {link: Link} where T: 'a);
let v = 5;
let a = Obj {
link: Link::new(),
value: &v,
};
let b = a.clone();
let mut l = LinkedList::new(ObjAdapter::new());
l.cursor_mut().insert_before(&a);
l.cursor_mut().insert_before(&b);
assert_eq!(*l.front().get().unwrap().value, 5);
assert_eq!(*l.back().get().unwrap().value, 5);
}
macro_rules! test_clone_pointer {
($ptr: ident, $ptr_import: path) => {
use $ptr_import;
#[derive(Clone)]
struct Obj {
link: Link,
value: usize,
}
intrusive_adapter!(ObjAdapter = $ptr<Obj>: Obj { link: Link });
let a = $ptr::new(Obj {
link: Link::new(),
value: 5,
});
let mut l = LinkedList::new(ObjAdapter::new());
l.cursor_mut().insert_before(a.clone());
assert_eq!(2, $ptr::strong_count(&a));
let pointer = l.front().clone_pointer().unwrap();
assert_eq!(pointer.value, 5);
assert_eq!(3, $ptr::strong_count(&a));
l.front_mut().remove();
assert!(l.front().clone_pointer().is_none());
}
}
#[test]
fn test_clone_pointer_rc() {
test_clone_pointer!(Rc, std::rc::Rc);
}
#[test]
fn test_clone_pointer_arc() {
test_clone_pointer!(Arc, std::sync::Arc);
}
}