diff options
Diffstat (limited to 'src/xor_linked_list.rs')
| -rw-r--r-- | src/xor_linked_list.rs | 310 |
1 files changed, 253 insertions, 57 deletions
diff --git a/src/xor_linked_list.rs b/src/xor_linked_list.rs index d5c2ca3..4b8bd28 100644 --- a/src/xor_linked_list.rs +++ b/src/xor_linked_list.rs @@ -19,8 +19,10 @@ use core::sync::atomic::{AtomicUsize, Ordering}; use crate::link_ops::{self, DefaultLinkOps}; use crate::pointer_ops::PointerOps; use crate::singly_linked_list::SinglyLinkedListOps; -use crate::unchecked_option::UncheckedOptionExt; use crate::Adapter; +// Necessary for Rust 1.56 compatability +#[allow(unused_imports)] +use crate::unchecked_option::UncheckedOptionExt; // ============================================================================= // XorLinkedListOps @@ -466,7 +468,7 @@ unsafe fn link_between<T: XorLinkedListOps>( } // ============================================================================= -// Cursor, CursorMut +// Cursor, CursorMut, CursorOwning // ============================================================================= /// A cursor which provides read-only access to a `XorLinkedList`. @@ -525,7 +527,7 @@ where where <A::PointerOps as PointerOps>::Pointer: Clone, { - let raw_pointer = self.get()? as *const <A::PointerOps as PointerOps>::Value; + let raw_pointer = unsafe { self.list.adapter.get_value(self.current?) }; Some(unsafe { crate::pointer_ops::clone_pointer_from_raw(self.list.adapter.pointer_ops(), raw_pointer) }) @@ -1082,6 +1084,72 @@ where } } +/// A cursor with ownership over the `XorLinkedList` it points into. +pub struct CursorOwning<A: Adapter> +where + A::LinkOps: XorLinkedListOps, +{ + current: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>, + prev: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>, + next: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>, + list: XorLinkedList<A>, +} + +impl<A: Adapter> CursorOwning<A> +where + A::LinkOps: XorLinkedListOps, +{ + /// Consumes self and returns the inner `XorLinkedList`. + #[inline] + pub fn into_inner(self) -> XorLinkedList<A> { + self.list + } + + /// Returns a read-only cursor pointing to the current element. + /// + /// The lifetime of the returned `Cursor` is bound to that of the + /// `CursorOwning`, which means it cannot outlive the `CursorOwning` and that the + /// `CursorOwning` is frozen for the lifetime of the `Cursor`. + /// + /// Mutations of the returned cursor are _not_ reflected in the original. + #[inline] + pub fn as_cursor(&self) -> Cursor<'_, A> { + Cursor { + current: self.current, + prev: self.prev, + next: self.next, + list: &self.list, + } + } + + /// Perform action with mutable reference to the cursor. + /// + /// All mutations of the cursor are reflected in the original. + #[inline] + pub fn with_cursor_mut<T>(&mut self, f: impl FnOnce(&mut CursorMut<'_, A>) -> T) -> T { + let mut cursor = CursorMut { + current: self.current, + prev: self.prev, + next: self.next, + list: &mut self.list, + }; + + let ret = f(&mut cursor); + + self.current = cursor.current; + self.prev = cursor.prev; + self.next = cursor.next; + + ret + } +} +unsafe impl<A: Adapter> Send for CursorOwning<A> +where + XorLinkedList<A>: Send, + A::LinkOps: XorLinkedListOps, +{ +} + // ============================================================================= // XorLinkedList // ============================================================================= @@ -1178,6 +1246,17 @@ where } } + /// Returns a null `CursorOwning` for this list. + #[inline] + pub fn cursor_owning(self) -> CursorOwning<A> { + CursorOwning { + current: None, + prev: self.tail, + next: self.head, + list: self, + } + } + /// Creates a `Cursor` from a pointer to an element and a pointer to the previous element. /// /// # Safety @@ -1234,6 +1313,34 @@ where } } + /// Creates a `CursorOwning` from a pointer to an element and a pointer to the previous element. + /// + /// # Safety + /// + /// `ptr` must be a pointer to an object that is part of this list. + /// `prev` must be a pointer to an object that is the previous object in this list (null for the head) + #[inline] + pub unsafe fn cursor_owning_from_ptr_and_prev( + self, + ptr: *const <A::PointerOps as PointerOps>::Value, + prev: *const <A::PointerOps as PointerOps>::Value, + ) -> CursorOwning<A> { + let current = self.adapter.get_link(ptr); + let prev = if !prev.is_null() { + Some(self.adapter.get_link(prev)) + } else { + None + }; + let next = self.adapter.link_ops().next(current, prev); + + CursorOwning { + current: Some(current), + prev, + next, + list: self, + } + } + /// Creates a `Cursor` from a pointer to an element and a pointer to the next element. /// /// # Safety @@ -1290,6 +1397,34 @@ where } } + /// Creates a `CursorOwning` from a pointer to an element and a pointer to the next element. + /// + /// # Safety + /// + /// `ptr` must be a pointer to an object that is part of this list. + /// `next` must be a pointer to an object that is the next object in this list (null for the tail) + #[inline] + pub unsafe fn cursor_owning_from_ptr_and_next( + self, + ptr: *const <A::PointerOps as PointerOps>::Value, + next: *const <A::PointerOps as PointerOps>::Value, + ) -> CursorOwning<A> { + let current = self.adapter.get_link(ptr); + let next = if !next.is_null() { + Some(self.adapter.get_link(next)) + } else { + None + }; + let prev = self.adapter.link_ops().prev(current, next); + + CursorOwning { + current: Some(current), + prev, + next, + list: self, + } + } + /// Returns a `Cursor` pointing to the first element of the list. If the /// list is empty then a null cursor is returned. #[inline] @@ -1308,6 +1443,15 @@ where cursor } + /// Returns a `CursorOwning` pointing to the first element of the list. If the + /// the list is empty then a null cursor is returned. + #[inline] + pub fn front_owning(self) -> CursorOwning<A> { + let mut cursor = self.cursor_owning(); + cursor.with_cursor_mut(|c| c.move_next()); + cursor + } + /// Returns a `Cursor` pointing to the last element of the list. If the list /// is empty then a null cursor is returned. #[inline] @@ -1326,6 +1470,15 @@ where cursor } + /// Returns a `CursorOwning` pointing to the last element of the list. If the + /// list is empty then a null cursor is returned. + #[inline] + pub fn back_owning(self) -> CursorOwning<A> { + let mut cursor = self.cursor_owning(); + cursor.with_cursor_mut(|c| c.move_prev()); + cursor + } + /// Gets an iterator over the objects in the `XorLinkedList`. #[inline] pub fn iter(&self) -> Iter<'_, A> { @@ -1616,7 +1769,9 @@ where #[cfg(test)] mod tests { - use super::{Link, XorLinkedList}; + use crate::UnsafeRef; + + use super::{CursorOwning, Link, XorLinkedList}; use core::cell::Cell; use core::ptr; use std::boxed::Box; @@ -1635,24 +1790,29 @@ mod tests { write!(f, "{}", self.value) } } - intrusive_adapter!(ObjAdapter1 = Rc<Obj>: Obj { link1: Link }); - intrusive_adapter!(ObjAdapter2 = Rc<Obj>: Obj { link2: Link }); + intrusive_adapter!(RcObjAdapter1 = Rc<Obj>: Obj { link1: Link }); + intrusive_adapter!(RcObjAdapter2 = Rc<Obj>: Obj { link2: Link }); + intrusive_adapter!(UnsafeRefObjAdapter1 = UnsafeRef<Obj>: Obj { link1: Link }); - fn make_obj(value: u32) -> Rc<Obj> { - Rc::new(Obj { + fn make_rc_obj(value: u32) -> Rc<Obj> { + Rc::new(make_obj(value)) + } + + fn make_obj(value: u32) -> Obj { + Obj { link1: Link::new(), link2: Link::default(), value, - }) + } } #[test] fn test_link() { - let a = make_obj(1); + let a = make_rc_obj(1); assert!(!a.link1.is_linked()); assert!(!a.link2.is_linked()); - let mut b = XorLinkedList::<ObjAdapter1>::default(); + let mut b = XorLinkedList::<RcObjAdapter1>::default(); assert!(b.is_empty()); b.cursor_mut().insert_after(a.clone()); @@ -1673,11 +1833,11 @@ mod tests { #[test] fn test_cursor() { - let a = make_obj(1); - let b = make_obj(2); - let c = make_obj(3); + let a = make_rc_obj(1); + let b = make_rc_obj(2); + let c = make_rc_obj(3); - let mut l = XorLinkedList::new(ObjAdapter1::new()); + let mut l = XorLinkedList::new(RcObjAdapter1::new()); let mut cur = l.cursor_mut(); assert!(cur.is_null()); assert!(cur.get().is_none()); @@ -1755,12 +1915,38 @@ mod tests { } #[test] + fn test_cursor_owning() { + struct Container { + cur: CursorOwning<RcObjAdapter1>, + } + + let mut l = XorLinkedList::new(RcObjAdapter1::new()); + l.push_back(make_rc_obj(1)); + l.push_back(make_rc_obj(2)); + l.push_back(make_rc_obj(3)); + l.push_back(make_rc_obj(4)); + let mut con = Container { + cur: l.cursor_owning(), + }; + assert!(con.cur.as_cursor().is_null()); + + con.cur = con.cur.into_inner().front_owning(); + assert_eq!(con.cur.as_cursor().get().unwrap().value, 1); + + con.cur.with_cursor_mut(|c| c.move_next()); + assert_eq!(con.cur.as_cursor().get().unwrap().value, 2); + + con.cur = con.cur.into_inner().back_owning(); + assert_eq!(con.cur.as_cursor().get().unwrap().value, 4); + } + + #[test] fn test_push_pop() { - let a = make_obj(1); - let b = make_obj(2); - let c = make_obj(3); + let a = make_rc_obj(1); + let b = make_rc_obj(2); + let c = make_rc_obj(3); - let mut l = XorLinkedList::new(ObjAdapter1::new()); + let mut l = XorLinkedList::new(RcObjAdapter1::new()); l.push_front(a); assert_eq!(l.iter().map(|x| x.value).collect::<Vec<_>>(), [1]); l.push_front(b); @@ -1781,14 +1967,14 @@ mod tests { #[test] fn test_split_splice() { - let mut l1 = XorLinkedList::new(ObjAdapter1::new()); - let mut l2 = XorLinkedList::new(ObjAdapter1::new()); - let mut l3 = XorLinkedList::new(ObjAdapter1::new()); - - let a = make_obj(1); - let b = make_obj(2); - let c = make_obj(3); - let d = make_obj(4); + let mut l1 = XorLinkedList::new(RcObjAdapter1::new()); + let mut l2 = XorLinkedList::new(RcObjAdapter1::new()); + let mut l3 = XorLinkedList::new(RcObjAdapter1::new()); + + let a = make_rc_obj(1); + let b = make_rc_obj(2); + let c = make_rc_obj(3); + let d = make_rc_obj(4); l1.cursor_mut().insert_before(a); l1.cursor_mut().insert_before(b); l1.cursor_mut().insert_before(c); @@ -1872,11 +2058,11 @@ mod tests { #[test] fn test_iter() { - let mut l = XorLinkedList::new(ObjAdapter1::new()); - let a = make_obj(1); - let b = make_obj(2); - let c = make_obj(3); - let d = make_obj(4); + let mut l = XorLinkedList::new(RcObjAdapter1::new()); + let a = make_rc_obj(1); + let b = make_rc_obj(2); + let c = make_rc_obj(3); + let d = make_rc_obj(4); l.cursor_mut().insert_before(a.clone()); l.cursor_mut().insert_before(b.clone()); l.cursor_mut().insert_before(c.clone()); @@ -1979,12 +2165,12 @@ mod tests { #[test] fn test_multi_list() { - let mut l1 = XorLinkedList::new(ObjAdapter1::new()); - let mut l2 = XorLinkedList::new(ObjAdapter2::new()); - let a = make_obj(1); - let b = make_obj(2); - let c = make_obj(3); - let d = make_obj(4); + let mut l1 = XorLinkedList::new(RcObjAdapter1::new()); + let mut l2 = XorLinkedList::new(RcObjAdapter2::new()); + let a = make_rc_obj(1); + let b = make_rc_obj(2); + let c = make_rc_obj(3); + let d = make_rc_obj(4); l1.cursor_mut().insert_before(a.clone()); l1.cursor_mut().insert_before(b.clone()); l1.cursor_mut().insert_before(c.clone()); @@ -1998,46 +2184,56 @@ mod tests { } #[test] - fn test_force_unlink() { - let mut l = XorLinkedList::new(ObjAdapter1::new()); - let a = make_obj(1); - let b = make_obj(2); - let c = make_obj(3); + fn test_fast_clear_force_unlink() { + let mut l = XorLinkedList::new(UnsafeRefObjAdapter1::new()); + let a = UnsafeRef::from_box(Box::new(make_obj(1))); + let b = UnsafeRef::from_box(Box::new(make_obj(2))); + let c = UnsafeRef::from_box(Box::new(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 { + assert!(a.link1.is_linked()); + assert!(b.link1.is_linked()); + assert!(c.link1.is_linked()); + 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()); + } + + unsafe { + UnsafeRef::into_box(a); + UnsafeRef::into_box(b); + UnsafeRef::into_box(c); } - assert!(l.is_empty()); - assert!(!a.link1.is_linked()); - assert!(!b.link1.is_linked()); - assert!(!c.link1.is_linked()); } #[test] fn test_reverse() { - let mut l = XorLinkedList::new(ObjAdapter1::new()); + let mut l = XorLinkedList::new(RcObjAdapter1::new()); - l.push_back(make_obj(1)); - l.push_back(make_obj(2)); - l.push_back(make_obj(3)); - l.push_back(make_obj(4)); + l.push_back(make_rc_obj(1)); + l.push_back(make_rc_obj(2)); + l.push_back(make_rc_obj(3)); + l.push_back(make_rc_obj(4)); assert_eq!(l.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 2, 3, 4]); l.reverse(); assert_eq!(l.iter().map(|x| x.value).collect::<Vec<_>>(), [4, 3, 2, 1]); - l.push_back(make_obj(5)); - l.push_back(make_obj(6)); + l.push_back(make_rc_obj(5)); + l.push_back(make_rc_obj(6)); assert_eq!( l.iter().map(|x| x.value).collect::<Vec<_>>(), [4, 3, 2, 1, 5, 6] |