diff options
-rw-r--r-- | .cargo_vcs_info.json | 2 | ||||
-rw-r--r-- | .github/workflows/ci.yml | 13 | ||||
-rw-r--r-- | .gitignore | 1 | ||||
-rw-r--r-- | Android.bp | 2 | ||||
-rw-r--r-- | Cargo.toml | 4 | ||||
-rw-r--r-- | Cargo.toml.orig | 4 | ||||
-rw-r--r-- | METADATA | 23 | ||||
-rw-r--r-- | src/adapter.rs | 1 | ||||
-rw-r--r-- | src/linked_list.rs | 222 | ||||
-rw-r--r-- | src/pointer_ops.rs | 10 | ||||
-rw-r--r-- | src/rbtree.rs | 306 | ||||
-rw-r--r-- | src/singly_linked_list.rs | 221 | ||||
-rw-r--r-- | src/xor_linked_list.rs | 310 |
13 files changed, 902 insertions, 217 deletions
diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json index b0613bc..57b2e50 100644 --- a/.cargo_vcs_info.json +++ b/.cargo_vcs_info.json @@ -1,6 +1,6 @@ { "git": { - "sha1": "5b1d6a12c6eef1c94a94e5493cfb730edeee2ca2" + "sha1": "48ee32f2a00f8149d1fbff233007b0c82a54b47a" }, "path_in_vcs": "" }
\ No newline at end of file diff --git a/.github/workflows/ci.yml b/.github/workflows/ci.yml index 420045e..19bc32c 100644 --- a/.github/workflows/ci.yml +++ b/.github/workflows/ci.yml @@ -26,7 +26,6 @@ jobs: with: command: test args: --features nightly - fmt: name: Rustfmt runs-on: ubuntu-latest @@ -42,3 +41,15 @@ jobs: with: command: fmt args: -- --check + miri: + name: Miri + runs-on: ubuntu-latest + steps: + - uses: actions/checkout@v2 + - uses: actions-rs/toolchain@v1 + with: + profile: minimal + toolchain: nightly + override: true + - run: rustup component add miri + - run: cargo miri test --verbose --all-features
\ No newline at end of file @@ -1,2 +1,3 @@ target Cargo.lock +.DS_Store
\ No newline at end of file @@ -44,7 +44,7 @@ rust_library { host_supported: true, crate_name: "intrusive_collections", cargo_env_compat: true, - cargo_pkg_version: "0.9.5", + cargo_pkg_version: "0.9.6", srcs: ["src/lib.rs"], edition: "2018", features: [ @@ -12,7 +12,7 @@ [package] edition = "2018" name = "intrusive-collections" -version = "0.9.5" +version = "0.9.6" authors = ["Amanieu d'Antras <amanieu@gmail.com>"] description = "Intrusive collections for Rust (linked list and red-black tree)" documentation = "https://docs.rs/intrusive-collections" @@ -31,7 +31,7 @@ license = "Apache-2.0/MIT" repository = "https://github.com/Amanieu/intrusive-rs" [dependencies.memoffset] -version = "0.8" +version = "0.9" [dev-dependencies.rand] version = "0.8.4" diff --git a/Cargo.toml.orig b/Cargo.toml.orig index 5bd16b0..5d26514 100644 --- a/Cargo.toml.orig +++ b/Cargo.toml.orig @@ -1,6 +1,6 @@ [package] name = "intrusive-collections" -version = "0.9.5" +version = "0.9.6" authors = ["Amanieu d'Antras <amanieu@gmail.com>"] description = "Intrusive collections for Rust (linked list and red-black tree)" documentation = "https://docs.rs/intrusive-collections" @@ -17,7 +17,7 @@ alloc = [] default = ["alloc"] [dependencies] -memoffset = "0.8" +memoffset = "0.9" [dev-dependencies] rand = "0.8.4" @@ -1,23 +1,20 @@ # This project was upgraded with external_updater. -# Usage: tools/external_updater/updater.sh update rust/crates/intrusive-collections -# For more info, check https://cs.android.com/android/platform/superproject/+/master:tools/external_updater/README.md +# Usage: tools/external_updater/updater.sh update external/rust/crates/intrusive-collections +# For more info, check https://cs.android.com/android/platform/superproject/+/main:tools/external_updater/README.md name: "intrusive-collections" description: "Intrusive collections for Rust (linked list and red-black tree)" third_party { - url { - type: HOMEPAGE - value: "https://crates.io/crates/intrusive-collections" - } - url { - type: ARCHIVE - value: "https://static.crates.io/crates/intrusive-collections/intrusive-collections-0.9.5.crate" - } - version: "0.9.5" license_type: NOTICE last_upgrade_date { - year: 2023 + year: 2024 month: 2 - day: 16 + day: 1 + } + homepage: "https://crates.io/crates/intrusive-collections" + identifier { + type: "Archive" + value: "https://static.crates.io/crates/intrusive-collections/intrusive-collections-0.9.6.crate" + version: "0.9.6" } } diff --git a/src/adapter.rs b/src/adapter.rs index 5484a0f..9c21671 100644 --- a/src/adapter.rs +++ b/src/adapter.rs @@ -274,7 +274,6 @@ mod tests { link: LinkedListLink, } - #[deny(missing_docs)] intrusive_adapter! { /// Test doc comment ObjAdapter1 = Rc<Obj>: Obj { link: LinkedListLink } diff --git a/src/linked_list.rs b/src/linked_list.rs index efcdb8a..3d5c152 100644 --- a/src/linked_list.rs +++ b/src/linked_list.rs @@ -16,9 +16,11 @@ use core::sync::atomic::{AtomicPtr, 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::xor_linked_list::XorLinkedListOps; use crate::Adapter; +// Necessary for Rust 1.56 compatability +#[allow(unused_imports)] +use crate::unchecked_option::UncheckedOptionExt; // ============================================================================= // LinkedListOps @@ -581,7 +583,7 @@ unsafe fn splice<T: LinkedListOps>( } // ============================================================================= -// Cursor, CursorMut +// Cursor, CursorMut, CursorOwning // ============================================================================= /// A cursor which provides read-only access to a `LinkedList`. @@ -636,7 +638,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) }) @@ -1064,6 +1066,61 @@ where } } +/// A cursor with ownership over the `LinkedList` it points into. +pub struct CursorOwning<A: Adapter> +where + A::LinkOps: LinkedListOps, +{ + current: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>, + list: LinkedList<A>, +} + +impl<A: Adapter> CursorOwning<A> +where + A::LinkOps: LinkedListOps, +{ + /// Consumes self and returns the inner `LinkedList`. + #[inline] + pub fn into_inner(self) -> LinkedList<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, + 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, + list: &mut self.list, + }; + let ret = f(&mut cursor); + self.current = cursor.current; + ret + } +} +unsafe impl<A: Adapter> Send for CursorOwning<A> +where + LinkedList<A>: Send, + A::LinkOps: LinkedListOps, +{ +} + // ============================================================================= // LinkedList // ============================================================================= @@ -1153,6 +1210,15 @@ where } } + /// Returns a null `CursorOwning` for this list. + #[inline] + pub fn cursor_owning(self) -> CursorOwning<A> { + CursorOwning { + current: None, + list: self, + } + } + /// Creates a `Cursor` from a pointer to an element. /// /// # Safety @@ -1185,6 +1251,22 @@ where } } + /// Creates a `CursorOwning` from a pointer to an element. + /// + /// # Safety + /// + /// `ptr` must be a pointer to an object that is part of this list. + #[inline] + pub unsafe fn cursor_owning_from_ptr( + self, + ptr: *const <A::PointerOps as PointerOps>::Value, + ) -> CursorOwning<A> { + CursorOwning { + current: Some(self.adapter.get_link(ptr)), + 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] @@ -1203,6 +1285,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] @@ -1221,6 +1312,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 `LinkedList`. #[inline] pub fn iter(&self) -> Iter<'_, A> { @@ -1487,7 +1587,11 @@ where #[cfg(test)] mod tests { - use super::{Link, LinkedList}; + use alloc::boxed::Box; + + use crate::UnsafeRef; + + use super::{CursorOwning, Link, LinkedList}; use std::fmt; use std::format; use std::rc::Rc; @@ -1505,17 +1609,23 @@ mod tests { } intrusive_adapter!(ObjAdapter1 = Rc<Obj>: Obj { link1: Link }); intrusive_adapter!(ObjAdapter2 = Rc<Obj>: Obj { link2: Link }); - fn make_obj(value: u32) -> Rc<Obj> { - Rc::new(Obj { + intrusive_adapter!(UnsafeRefObjAdapter1 = UnsafeRef<Obj>: Obj { link1: Link }); + + 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()); @@ -1540,9 +1650,9 @@ 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 = LinkedList::new(ObjAdapter1::new()); let mut cur = l.cursor_mut(); @@ -1622,10 +1732,36 @@ mod tests { } #[test] + fn test_cursor_owning() { + struct Container { + cur: CursorOwning<ObjAdapter1>, + } + + let mut l = LinkedList::new(ObjAdapter1::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 = LinkedList::new(ObjAdapter1::new()); l.push_front(a); @@ -1652,10 +1788,10 @@ mod tests { 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); + 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); @@ -1740,10 +1876,10 @@ mod tests { #[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); + 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()); @@ -1814,10 +1950,10 @@ mod tests { 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); + 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()); @@ -1831,29 +1967,39 @@ mod tests { } #[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); + fn test_fast_clear_force_unlink() { + let mut l = LinkedList::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] diff --git a/src/pointer_ops.rs b/src/pointer_ops.rs index 716ac15..1d566ed 100644 --- a/src/pointer_ops.rs +++ b/src/pointer_ops.rs @@ -374,7 +374,7 @@ mod tests { unsafe { let pointer_ops = DefaultPointerOps::<Arc<_>>::new(); let p = Arc::new(1); - let raw = &*p as *const i32; + let raw = Arc::as_ptr(&p); let p2: Arc<i32> = clone_pointer_from_raw(&pointer_ops, raw); assert_eq!(2, Arc::strong_count(&p2)); } @@ -386,7 +386,7 @@ mod tests { unsafe { let pointer_ops = DefaultPointerOps::<Rc<_>>::new(); let p = Rc::new(1); - let raw = &*p as *const i32; + let raw = Rc::as_ptr(&p); let p2: Rc<i32> = clone_pointer_from_raw(&pointer_ops, raw); assert_eq!(2, Rc::strong_count(&p2)); } @@ -491,8 +491,9 @@ mod tests { unsafe { let pointer_ops = DefaultPointerOps::<Pin<Arc<_>>>::new(); let p = Pin::new(Arc::new(1)); - let raw = &*p as *const i32; + let raw = pointer_ops.into_raw(p); let p2: Pin<Arc<i32>> = clone_pointer_from_raw(&pointer_ops, raw); + let _p = pointer_ops.from_raw(raw); assert_eq!(2, Arc::strong_count(&Pin::into_inner(p2))); } } @@ -503,8 +504,9 @@ mod tests { unsafe { let pointer_ops = DefaultPointerOps::<Pin<Rc<_>>>::new(); let p = Pin::new(Rc::new(1)); - let raw = &*p as *const i32; + let raw = pointer_ops.into_raw(p); let p2: Pin<Rc<i32>> = clone_pointer_from_raw(&pointer_ops, raw); + let _p = pointer_ops.from_raw(raw); assert_eq!(2, Rc::strong_count(&Pin::into_inner(p2))); } } diff --git a/src/rbtree.rs b/src/rbtree.rs index 87badec..83d428e 100644 --- a/src/rbtree.rs +++ b/src/rbtree.rs @@ -22,10 +22,12 @@ use crate::link_ops::{self, DefaultLinkOps}; use crate::linked_list::LinkedListOps; use crate::pointer_ops::PointerOps; use crate::singly_linked_list::SinglyLinkedListOps; -use crate::unchecked_option::UncheckedOptionExt; use crate::xor_linked_list::XorLinkedListOps; use crate::Adapter; use crate::KeyAdapter; +// Necessary for Rust 1.56 compatability +#[allow(unused_imports)] +use crate::unchecked_option::UncheckedOptionExt; // ============================================================================= // RBTreeOps @@ -1037,7 +1039,7 @@ unsafe fn remove<T: RBTreeOps>(link_ops: &mut T, ptr: T::LinkPtr, root: &mut Opt } // ============================================================================= -// Cursor, CursorMut +// Cursor, CursorMut, CursorOwning // ============================================================================= /// A cursor which provides read-only access to a `RBTree`. @@ -1092,7 +1094,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.tree.adapter.get_value(self.current?) }; Some(unsafe { crate::pointer_ops::clone_pointer_from_raw(self.tree.adapter.pointer_ops(), raw_pointer) }) @@ -1449,6 +1451,61 @@ where } } +/// A cursor with ownership over the `RBTree` it points into. +pub struct CursorOwning<A: Adapter> +where + A::LinkOps: RBTreeOps, +{ + current: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>, + tree: RBTree<A>, +} + +impl<A: Adapter> CursorOwning<A> +where + A::LinkOps: RBTreeOps, +{ + /// Consumes self and returns the inner `RBTree`. + #[inline] + pub fn into_inner(self) -> RBTree<A> { + self.tree + } + + /// 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, + tree: &self.tree, + } + } + + /// 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, + tree: &mut self.tree, + }; + let ret = f(&mut cursor); + self.current = cursor.current; + ret + } +} +unsafe impl<A: Adapter> Send for CursorOwning<A> +where + RBTree<A>: Send, + A::LinkOps: RBTreeOps, +{ +} + // ============================================================================= // RBTree // ============================================================================= @@ -1542,6 +1599,15 @@ where } } + /// Returns a null `CursorOwning` for this tree. + #[inline] + pub fn cursor_owning(self) -> CursorOwning<A> { + CursorOwning { + current: None, + tree: self, + } + } + /// Creates a `Cursor` from a pointer to an element. /// /// # Safety @@ -1574,6 +1640,22 @@ where } } + /// Creates a `CursorOwning` from a pointer to an element. + /// + /// # Safety + /// + /// `ptr` must be a pointer to an object that is part of this tree. + #[inline] + pub unsafe fn cursor_owning_from_ptr( + self, + ptr: *const <A::PointerOps as PointerOps>::Value, + ) -> CursorOwning<A> { + CursorOwning { + current: Some(self.adapter.get_link(ptr)), + tree: self, + } + } + /// Returns a `Cursor` pointing to the first element of the tree. If the /// tree is empty then a null cursor is returned. #[inline] @@ -1592,6 +1674,15 @@ where cursor } + /// Returns a `CursorOwning` pointing to the first element of the tree. If the + /// the tree 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 tree. If the tree /// is empty then a null cursor is returned. #[inline] @@ -1610,6 +1701,15 @@ where cursor } + /// Returns a `CursorOwning` pointing to the last element of the tree. If the + /// tree 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 + } + #[inline] unsafe fn insert_root(&mut self, node: <A::LinkOps as link_ops::LinkOps>::LinkPtr) { self.adapter.link_ops_mut().set_parent(node, None); @@ -1758,6 +1858,23 @@ where } } + // Returns a `CursorOwning` pointing to an element with the given key. If no + /// such element is found then a null cursor is returned. + /// + /// If multiple elements with an identical key are found then an arbitrary + /// one is returned. + #[inline] + pub fn find_owning<'a, Q: ?Sized + Ord>(self, key: &Q) -> CursorOwning<A> + where + <A as KeyAdapter<'a>>::Key: Borrow<Q>, + Self: 'a, + { + CursorOwning { + current: self.find_internal(key), + tree: self, + } + } + #[inline] fn lower_bound_internal<'a, Q: ?Sized + Ord>( &self, @@ -1821,6 +1938,21 @@ where } } + /// Returns a `CursorOwning` pointing to the first element whose key is + /// above the given bound. If no such element is found then a null + /// cursor is returned. + #[inline] + pub fn lower_bound_owning<'a, Q: ?Sized + Ord>(self, bound: Bound<&Q>) -> CursorOwning<A> + where + <A as KeyAdapter<'a>>::Key: Borrow<Q>, + Self: 'a, + { + CursorOwning { + current: self.lower_bound_internal(bound), + tree: self, + } + } + #[inline] fn upper_bound_internal<'a, Q: ?Sized + Ord>( &self, @@ -1884,6 +2016,21 @@ where } } + /// Returns a `CursorOwning` pointing to the last element whose key is + /// below the given bound. If no such element is found then a null + /// cursor is returned. + #[inline] + pub fn upper_bound_owning<'a, Q: ?Sized + Ord>(self, bound: Bound<&Q>) -> CursorOwning<A> + where + <A as KeyAdapter<'a>>::Key: Borrow<Q>, + Self: 'a, + { + CursorOwning { + current: self.upper_bound_internal(bound), + tree: self, + } + } + /// Inserts a new element into the `RBTree`. /// /// The new element will be inserted at the correct position in the tree @@ -1927,6 +2074,7 @@ where } else { self.insert_root(new); } + CursorMut { current: Some(new), tree: self, @@ -2382,8 +2530,9 @@ where #[cfg(test)] mod tests { - use super::{Entry, KeyAdapter, Link, PointerOps, RBTree}; - use crate::Bound::*; + use super::{CursorOwning, Entry, KeyAdapter, Link, PointerOps, RBTree}; + use crate::{Bound::*, UnsafeRef}; + use alloc::boxed::Box; use rand::prelude::*; use rand_xorshift::XorShiftRng; use std::fmt; @@ -2401,27 +2550,42 @@ mod tests { write!(f, "{}", self.value) } } - intrusive_adapter!(ObjAdapter = Rc<Obj>: Obj { link: Link }); - impl<'a> KeyAdapter<'a> for ObjAdapter { + intrusive_adapter!(RcObjAdapter = Rc<Obj>: Obj { link: Link }); + + impl<'a> KeyAdapter<'a> for RcObjAdapter { type Key = i32; fn get_key(&self, value: &'a <Self::PointerOps as PointerOps>::Value) -> i32 { value.value } } - fn make_obj(value: i32) -> Rc<Obj> { - Rc::new(Obj { + + intrusive_adapter!(UnsafeRefObjAdapter = UnsafeRef<Obj>: Obj { link: Link }); + + impl<'a> KeyAdapter<'a> for UnsafeRefObjAdapter { + type Key = i32; + fn get_key(&self, value: &'a <Self::PointerOps as PointerOps>::Value) -> i32 { + value.value + } + } + + fn make_rc_obj(value: i32) -> Rc<Obj> { + Rc::new(make_obj(value)) + } + + fn make_obj(value: i32) -> Obj { + Obj { link: Link::new(), value, - }) + } } #[test] fn test_link() { - let a = make_obj(1); + let a = make_rc_obj(1); assert!(!a.link.is_linked()); assert_eq!(format!("{:?}", a.link), "unlinked"); - let mut b = RBTree::<ObjAdapter>::default(); + let mut b = RBTree::<RcObjAdapter>::default(); assert!(b.is_empty()); assert_eq!(b.insert(a.clone()).get().unwrap().value, 1); @@ -2447,10 +2611,10 @@ mod tests { #[test] fn test_cursor() { - let a = make_obj(1); - let b = make_obj(2); - let c = make_obj(3); - let mut t = RBTree::new(ObjAdapter::new()); + let a = make_rc_obj(1); + let b = make_rc_obj(2); + let c = make_rc_obj(3); + let mut t = RBTree::new(RcObjAdapter::new()); let mut cur = t.cursor_mut(); assert!(cur.is_null()); assert!(cur.get().is_none()); @@ -2488,9 +2652,9 @@ mod tests { } assert_eq!(cur.get().unwrap() as *const _, a.as_ref() as *const _); - let a2 = make_obj(1); - let b2 = make_obj(2); - let c2 = make_obj(3); + let a2 = make_rc_obj(1); + let b2 = make_rc_obj(2); + let c2 = make_rc_obj(3); assert_eq!( cur.replace_with(a2).unwrap().as_ref() as *const _, a.as_ref() as *const _ @@ -2515,12 +2679,41 @@ mod tests { ); } - #[cfg(not(miri))] + #[test] + fn test_cursor_owning() { + struct Container { + cur: CursorOwning<RcObjAdapter>, + } + + let mut t = RBTree::new(RcObjAdapter::new()); + t.insert(make_rc_obj(1)); + t.insert(make_rc_obj(2)); + t.insert(make_rc_obj(3)); + t.insert(make_rc_obj(4)); + let mut con = Container { + cur: t.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 = con.cur.into_inner().back_owning(); + assert_eq!(con.cur.as_cursor().get().unwrap().value, 4); + + con.cur = con.cur.into_inner().find_owning(&2); + assert_eq!(con.cur.as_cursor().get().unwrap().value, 2); + + con.cur.with_cursor_mut(|c| c.move_next()); + assert_eq!(con.cur.as_cursor().get().unwrap().value, 3); + } + #[test] fn test_insert_remove() { - let v = (0..100).map(make_obj).collect::<Vec<_>>(); + let len = if cfg!(miri) { 10 } else { 100 }; + let v = (0..len).map(make_rc_obj).collect::<Vec<_>>(); assert!(v.iter().all(|x| !x.link.is_linked())); - let mut t = RBTree::new(ObjAdapter::new()); + let mut t = RBTree::new(RcObjAdapter::new()); assert!(t.is_empty()); let mut rng = XorShiftRng::seed_from_u64(0); @@ -2635,11 +2828,10 @@ mod tests { } } - #[cfg(not(miri))] #[test] fn test_iter() { - let v = (0..10).map(|x| make_obj(x * 10)).collect::<Vec<_>>(); - let mut t = RBTree::new(ObjAdapter::new()); + let v = (0..10).map(|x| make_rc_obj(x * 10)).collect::<Vec<_>>(); + let mut t = RBTree::new(RcObjAdapter::new()); for x in v.iter() { t.insert(x.clone()); } @@ -2884,8 +3076,8 @@ mod tests { #[test] fn test_find() { - let v = (0..10).map(|x| make_obj(x * 10)).collect::<Vec<_>>(); - let mut t = RBTree::new(ObjAdapter::new()); + let v = (0..10).map(|x| make_rc_obj(x * 10)).collect::<Vec<_>>(); + let mut t = RBTree::new(RcObjAdapter::new()); for x in v.iter() { t.insert(x.clone()); } @@ -3012,40 +3204,50 @@ mod tests { } #[test] - fn test_fast_clear() { - let mut t = RBTree::new(ObjAdapter::new()); - let a = make_obj(1); - let b = make_obj(2); - let c = make_obj(3); + fn test_fast_clear_force_unlink() { + let mut t = RBTree::new(UnsafeRefObjAdapter::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))); t.insert(a.clone()); t.insert(b.clone()); t.insert(c.clone()); t.fast_clear(); assert!(t.is_empty()); - assert!(a.link.is_linked()); - assert!(b.link.is_linked()); - assert!(c.link.is_linked()); + unsafe { + assert!(a.link.is_linked()); + assert!(b.link.is_linked()); + assert!(c.link.is_linked()); + a.link.force_unlink(); b.link.force_unlink(); c.link.force_unlink(); + + assert!(t.is_empty()); + + assert!(!a.link.is_linked()); + assert!(!b.link.is_linked()); + assert!(!c.link.is_linked()); + } + + unsafe { + UnsafeRef::into_box(a); + UnsafeRef::into_box(b); + UnsafeRef::into_box(c); } - assert!(t.is_empty()); - assert!(!a.link.is_linked()); - assert!(!b.link.is_linked()); - assert!(!c.link.is_linked()); } #[test] fn test_entry() { - let mut t = RBTree::new(ObjAdapter::new()); - let a = make_obj(1); - let b = make_obj(2); - let c = make_obj(3); - let d = make_obj(4); - let e = make_obj(5); - let f = make_obj(6); + let mut t = RBTree::new(RcObjAdapter::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); + let e = make_rc_obj(5); + let f = make_rc_obj(6); t.entry(&3).or_insert(c); t.entry(&2).or_insert(b.clone()); t.entry(&1).or_insert(a); @@ -3089,8 +3291,8 @@ mod tests { link: Link, value: &'a T, } - intrusive_adapter!(ObjAdapter<'a, T> = &'a Obj<'a, T>: Obj<'a, T> {link: Link} where T: 'a); - impl<'a, 'b, T: 'a + 'b> KeyAdapter<'a> for ObjAdapter<'b, T> { + intrusive_adapter!(RcObjAdapter<'a, T> = &'a Obj<'a, T>: Obj<'a, T> {link: Link} where T: 'a); + impl<'a, 'b, T: 'a + 'b> KeyAdapter<'a> for RcObjAdapter<'b, T> { type Key = &'a T; fn get_key(&self, value: &'a Obj<'b, T>) -> &'a T { value.value @@ -3103,7 +3305,7 @@ mod tests { value: &v, }; let b = a.clone(); - let mut l = RBTree::new(ObjAdapter::new()); + let mut l = RBTree::new(RcObjAdapter::new()); l.insert(&a); l.insert(&b); assert_eq!(*l.front().get().unwrap().value, 5); @@ -3119,8 +3321,8 @@ mod tests { link: Link, value: usize, } - intrusive_adapter!(ObjAdapter = $ptr<Obj>: Obj { link: Link }); - impl<'a> KeyAdapter<'a> for ObjAdapter { + intrusive_adapter!(RcObjAdapter = $ptr<Obj>: Obj { link: Link }); + impl<'a> KeyAdapter<'a> for RcObjAdapter { type Key = usize; fn get_key(&self, value: &'a Obj) -> usize { value.value @@ -3131,7 +3333,7 @@ mod tests { link: Link::new(), value: 5, }); - let mut l = RBTree::new(ObjAdapter::new()); + let mut l = RBTree::new(RcObjAdapter::new()); l.insert(a.clone()); assert_eq!(2, $ptr::strong_count(&a)); diff --git a/src/singly_linked_list.rs b/src/singly_linked_list.rs index fb0618e..cf66418 100644 --- a/src/singly_linked_list.rs +++ b/src/singly_linked_list.rs @@ -497,7 +497,7 @@ unsafe fn splice<T: SinglyLinkedListOps>( } // ============================================================================= -// Cursor, CursorMut +// Cursor, CursorMut, CursorOwning // ============================================================================= /// A cursor which provides read-only access to a `SinglyLinkedList`. @@ -552,7 +552,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) }) @@ -840,6 +840,61 @@ where } } +/// A cursor with ownership over the `SinglyLinkedList` it points into. +pub struct CursorOwning<A: Adapter> +where + A::LinkOps: SinglyLinkedListOps, +{ + current: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>, + list: SinglyLinkedList<A>, +} + +impl<A: Adapter> CursorOwning<A> +where + A::LinkOps: SinglyLinkedListOps, +{ + /// Consumes self and returns the inner `SinglyLinkedList`. + #[inline] + pub fn into_inner(self) -> SinglyLinkedList<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, + 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, + list: &mut self.list, + }; + let ret = f(&mut cursor); + self.current = cursor.current; + ret + } +} +unsafe impl<A: Adapter> Send for CursorOwning<A> +where + SinglyLinkedList<A>: Send, + A::LinkOps: SinglyLinkedListOps, +{ +} + // ============================================================================= // SinglyLinkedList // ============================================================================= @@ -926,6 +981,15 @@ where } } + /// Returns a null `CursorOwning` for this list. + #[inline] + pub fn cursor_owning(self) -> CursorOwning<A> { + CursorOwning { + current: None, + list: self, + } + } + /// Creates a `Cursor` from a pointer to an element. /// /// # Safety @@ -958,6 +1022,22 @@ where } } + /// Creates a `CursorOwning` from a pointer to an element. + /// + /// # Safety + /// + /// `ptr` must be a pointer to an object that is part of this list. + #[inline] + pub unsafe fn cursor_owning_from_ptr( + self, + ptr: *const <A::PointerOps as PointerOps>::Value, + ) -> CursorOwning<A> { + CursorOwning { + current: Some(self.adapter.get_link(ptr)), + 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] @@ -976,6 +1056,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 + } + /// Gets an iterator over the objects in the `SinglyLinkedList`. #[inline] pub fn iter(&self) -> Iter<'_, A> { @@ -1190,7 +1279,11 @@ where #[cfg(test)] mod tests { - use super::{Link, SinglyLinkedList}; + use alloc::boxed::Box; + + use crate::UnsafeRef; + + use super::{CursorOwning, Link, SinglyLinkedList}; use std::fmt; use std::format; use std::rc::Rc; @@ -1206,23 +1299,28 @@ mod tests { write!(f, "{}", self.value) } } - intrusive_adapter!(ObjAdapter1 = Rc<Obj>: Obj { link1: Link }); - intrusive_adapter!(ObjAdapter2 = Rc<Obj>: Obj { link2: Link }); - fn make_obj(value: u32) -> Rc<Obj> { - Rc::new(Obj { + 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_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 = SinglyLinkedList::<ObjAdapter1>::default(); + let mut b = SinglyLinkedList::<RcObjAdapter1>::default(); assert!(b.is_empty()); b.push_front(a.clone()); @@ -1243,11 +1341,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 = SinglyLinkedList::new(ObjAdapter1::new()); + let mut l = SinglyLinkedList::new(RcObjAdapter1::new()); let mut cur = l.cursor_mut(); assert!(cur.is_null()); assert!(cur.get().is_none()); @@ -1323,15 +1421,38 @@ mod tests { } #[test] + fn test_cursor_owning() { + struct Container { + cur: CursorOwning<RcObjAdapter1>, + } + + let mut l = SinglyLinkedList::new(RcObjAdapter1::new()); + l.push_front(make_rc_obj(1)); + l.push_front(make_rc_obj(2)); + l.push_front(make_rc_obj(3)); + l.push_front(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, 4); + + con.cur.with_cursor_mut(|c| c.move_next()); + assert_eq!(con.cur.as_cursor().get().unwrap().value, 3); + } + + #[test] fn test_split_splice() { - let mut l1 = SinglyLinkedList::new(ObjAdapter1::new()); - let mut l2 = SinglyLinkedList::new(ObjAdapter1::new()); - let mut l3 = SinglyLinkedList::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 = SinglyLinkedList::new(RcObjAdapter1::new()); + let mut l2 = SinglyLinkedList::new(RcObjAdapter1::new()); + let mut l3 = SinglyLinkedList::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_after(d); l1.cursor_mut().insert_after(c); l1.cursor_mut().insert_after(b); @@ -1417,11 +1538,11 @@ mod tests { #[test] fn test_iter() { - let mut l = SinglyLinkedList::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 = SinglyLinkedList::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_after(d.clone()); l.cursor_mut().insert_after(c.clone()); l.cursor_mut().insert_after(b.clone()); @@ -1471,12 +1592,12 @@ mod tests { #[test] fn test_multi_list() { - let mut l1 = SinglyLinkedList::new(ObjAdapter1::new()); - let mut l2 = SinglyLinkedList::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 = SinglyLinkedList::new(RcObjAdapter1::new()); + let mut l2 = SinglyLinkedList::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_after(d.clone()); l1.cursor_mut().insert_after(c.clone()); l1.cursor_mut().insert_after(b.clone()); @@ -1490,29 +1611,39 @@ mod tests { } #[test] - fn test_fast_clear() { - let mut l = SinglyLinkedList::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 = SinglyLinkedList::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_after(a.clone()); l.cursor_mut().insert_after(b.clone()); l.cursor_mut().insert_after(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] 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] |