// Copyright 2016 Amanieu d'Antras // Copyright 2020 Amari Robinson // // Licensed under the Apache License, Version 2.0, or the MIT license , at your option. This file may not be // copied, modified, or distributed except according to those terms. //! Intrusive xor doubly-linked list which uses less memory than a regular doubly linked list. //! //! In exchange for less memory use, it is impossible to create a cursor from a pointer to //! an element. use core::cell::Cell; use core::fmt; use core::ptr::NonNull; 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; // ============================================================================= // XorLinkedListOps // ============================================================================= /// Link operations for `XorLinkedList`. pub unsafe trait XorLinkedListOps: link_ops::LinkOps { /// Returns the "next" link pointer of `ptr`. /// /// # Safety /// `prev` must have been previously passed to the [`set`] method, or /// `prev` must be equal to the `new` argument previously passed to [`replace_next_or_prev`]. /// /// An implementation of `next` must not panic. /// /// [`replace_next_or_prev`]: #tymethod.replace_next_or_prev /// [`set`]: #tymethod.set unsafe fn next(&self, ptr: Self::LinkPtr, prev: Option) -> Option; /// Returns the "prev" link pointer of `ptr`. /// /// # Safety /// `next` must have been previously passed to the [`set`] method, or /// `next` must be equal to the `new` argument previously passed to [`replace_next_or_prev`]. /// /// An implementation of `prev` must not panic. /// /// [`replace_next_or_prev`]: #tymethod.replace_next_or_prev /// [`set`]: #tymethod.set unsafe fn prev(&self, ptr: Self::LinkPtr, next: Option) -> Option; /// Assigns the "prev" and "next" link pointers of `ptr`. /// /// # Safety /// An implementation of `set` must not panic. unsafe fn set( &mut self, ptr: Self::LinkPtr, prev: Option, next: Option, ); /// Replaces the "next" or "prev" link pointer of `ptr`. /// /// # Safety /// `old` must be equal to either the `next` or `prev` argument previously passed to the [`set`] method, or /// `old` must be equal to the `new` argument previously passed to `replace_next_or_prev`. /// /// An implementation of `replace_next_or_prev` must not panic. /// /// [`set`]: #tymethod.set unsafe fn replace_next_or_prev( &mut self, ptr: Self::LinkPtr, old: Option, new: Option, ); } // ============================================================================= // Link // ============================================================================= /// Intrusive link that allows an object to be inserted into a /// `XorLinkedList`. #[repr(align(2))] pub struct Link { packed: Cell, } // Use a special value to indicate an unlinked node const UNLINKED_MARKER: usize = 1_usize; impl Link { /// Creates a new `Link`. #[inline] pub const fn new() -> Link { Link { packed: Cell::new(UNLINKED_MARKER), } } /// Checks whether the `Link` is linked into a `XorLinkedList`. #[inline] pub fn is_linked(&self) -> bool { self.packed.get() != UNLINKED_MARKER } /// Forcibly unlinks an object from a `XorLinkedList`. /// /// # Safety /// /// It is undefined behavior to call this function while still linked into a /// `XorLinkedList`. The only situation where this function is useful is /// after calling `fast_clear` on a `XorLinkedList`, since this clears /// the collection without marking the nodes as unlinked. #[inline] pub unsafe fn force_unlink(&self) { self.packed.set(UNLINKED_MARKER); } } impl DefaultLinkOps for Link { type Ops = LinkOps; const NEW: Self::Ops = LinkOps; } // An object containing a link can be sent to another thread if it is unlinked. unsafe impl Send for Link {} // Provide an implementation of Clone which simply initializes the new link as // unlinked. This allows structs containing a link to derive Clone. impl Clone for Link { #[inline] fn clone(&self) -> Link { Link::new() } } // Same as above impl Default for Link { #[inline] fn default() -> Link { Link::new() } } // Provide an implementation of Debug so that structs containing a link can // still derive Debug. impl fmt::Debug for Link { #[inline] fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { // There isn't anything sensible to print here except whether the link // is currently in a list. if self.is_linked() { write!(f, "linked") } else { write!(f, "unlinked") } } } // ============================================================================= // LinkOps // ============================================================================= /// Default `LinkOps` implementation for `XorLinkedList`. #[derive(Clone, Copy, Default)] pub struct LinkOps; unsafe impl link_ops::LinkOps for LinkOps { type LinkPtr = NonNull; #[inline] unsafe fn acquire_link(&mut self, ptr: Self::LinkPtr) -> bool { if ptr.as_ref().is_linked() { false } else { ptr.as_ref().packed.set(0); true } } #[inline] unsafe fn release_link(&mut self, ptr: Self::LinkPtr) { ptr.as_ref().packed.set(UNLINKED_MARKER); } } unsafe impl XorLinkedListOps for LinkOps { #[inline] unsafe fn next( &self, ptr: Self::LinkPtr, prev: Option, ) -> Option { let raw = ptr.as_ref().packed.get() ^ prev.map(|x| x.as_ptr() as usize).unwrap_or(0); NonNull::new(raw as *mut _) } #[inline] unsafe fn prev( &self, ptr: Self::LinkPtr, next: Option, ) -> Option { let raw = ptr.as_ref().packed.get() ^ next.map(|x| x.as_ptr() as usize).unwrap_or(0); NonNull::new(raw as *mut _) } #[inline] unsafe fn set( &mut self, ptr: Self::LinkPtr, prev: Option, next: Option, ) { let new_packed = prev.map(|x| x.as_ptr() as usize).unwrap_or(0) ^ next.map(|x| x.as_ptr() as usize).unwrap_or(0); ptr.as_ref().packed.set(new_packed); } #[inline] unsafe fn replace_next_or_prev( &mut self, ptr: Self::LinkPtr, old: Option, new: Option, ) { let new_packed = ptr.as_ref().packed.get() ^ old.map(|x| x.as_ptr() as usize).unwrap_or(0) ^ new.map(|x| x.as_ptr() as usize).unwrap_or(0); ptr.as_ref().packed.set(new_packed); } } unsafe impl SinglyLinkedListOps for LinkOps { #[inline] unsafe fn next(&self, ptr: Self::LinkPtr) -> Option { let raw = ptr.as_ref().packed.get(); NonNull::new(raw as *mut _) } #[inline] unsafe fn set_next(&mut self, ptr: Self::LinkPtr, next: Option) { ptr.as_ref() .packed .set(next.map(|x| x.as_ptr() as usize).unwrap_or(0)); } } #[inline] unsafe fn link_between( link_ops: &mut T, ptr: T::LinkPtr, prev: Option, next: Option, ) { if let Some(prev) = prev { let prev_of_prev = link_ops.prev(prev, next); link_ops.set(prev, prev_of_prev, Some(ptr)); } if let Some(next) = next { let next_of_next = link_ops.next(next, prev); link_ops.set(next, Some(ptr), next_of_next); } link_ops.set(ptr, prev, next); } // ============================================================================= // Cursor, CursorMut // ============================================================================= /// A cursor which provides read-only access to a `XorLinkedList`. pub struct Cursor<'a, A: Adapter> where A::LinkOps: XorLinkedListOps, { current: Option<::LinkPtr>, prev: Option<::LinkPtr>, next: Option<::LinkPtr>, list: &'a XorLinkedList, } impl<'a, A: Adapter> Clone for Cursor<'a, A> where A::LinkOps: XorLinkedListOps, { #[inline] fn clone(&self) -> Cursor<'a, A> { Cursor { current: self.current, prev: self.prev, next: self.next, list: self.list, } } } impl<'a, A: Adapter> Cursor<'a, A> where A::LinkOps: XorLinkedListOps, { /// Checks if the cursor is currently pointing to the null object. #[inline] pub fn is_null(&self) -> bool { self.current.is_none() } /// Returns a reference to the object that the cursor is currently /// pointing to. /// /// This returns `None` if the cursor is currently pointing to the null /// object. #[inline] pub fn get(&self) -> Option<&'a ::Value> { Some(unsafe { &*self.list.adapter.get_value(self.current?) }) } /// Clones and returns the pointer that points to the element that the /// cursor is referencing. /// /// This returns `None` if the cursor is currently pointing to the null /// object. #[inline] pub fn clone_pointer(&self) -> Option<::Pointer> where ::Pointer: Clone, { let raw_pointer = self.get()? as *const ::Value; Some(unsafe { crate::pointer_ops::clone_pointer_from_raw(self.list.adapter.pointer_ops(), raw_pointer) }) } /// Moves the cursor to the next element of the `XorLinkedList`. /// /// If the cursor is pointer to the null object then this will move it to /// the first element of the `XorLinkedList`. If it is pointing to the /// last element of the `XorLinkedList` then this will move it to the /// null object. #[inline] pub fn move_next(&mut self) { let prev = self.current; self.current = self.next; unsafe { if let Some(current) = self.current { self.prev = prev; self.next = self.list.adapter.link_ops().next(current, prev); } else { self.prev = self.list.tail; self.next = self.list.head; } } } /// Moves the cursor to the previous element of the `XorLinkedList`. /// /// If the cursor is pointer to the null object then this will move it to /// the last element of the `XorLinkedList`. If it is pointing to the first /// element of the `XorLinkedList` then this will move it to the null object. #[inline] pub fn move_prev(&mut self) { let next = self.current; self.current = self.prev; unsafe { if let Some(current) = self.current { self.prev = self.list.adapter.link_ops().prev(current, next); self.next = next; } else { self.prev = self.list.tail; self.next = self.list.head; } } } /// Returns a cursor pointing to the next element of the `XorLinkedList`. /// /// If the cursor is pointer to the null object then this will return the /// first element of the `XorLinkedList`. If it is pointing to the last /// element of the `XorLinkedList` then this will return a null cursor. #[inline] pub fn peek_next(&self) -> Cursor<'_, A> { let mut next = self.clone(); next.move_next(); next } /// Returns a cursor pointing to the previous element of the `XorLinkedList`. /// /// If the cursor is pointer to the null object then this will return the /// last element of the `XorLinkedList`. If it is pointing to the first /// element of the `XorLinkedList` then this will return a null cursor. #[inline] pub fn peek_prev(&self) -> Cursor<'_, A> { let mut prev = self.clone(); prev.move_prev(); prev } } /// A cursor which provides mutable access to a `XorLinkedList`. pub struct CursorMut<'a, A: Adapter> where A::LinkOps: XorLinkedListOps, { current: Option<::LinkPtr>, prev: Option<::LinkPtr>, next: Option<::LinkPtr>, list: &'a mut XorLinkedList, } impl<'a, A: Adapter> CursorMut<'a, A> where A::LinkOps: XorLinkedListOps, { /// Checks if the cursor is currently pointing to the null object. #[inline] pub fn is_null(&self) -> bool { self.current.is_none() } /// Returns a reference to the object that the cursor is currently /// pointing to. /// /// This returns None if the cursor is currently pointing to the null /// object. #[inline] pub fn get(&self) -> Option<&::Value> { Some(unsafe { &*self.list.adapter.get_value(self.current?) }) } /// Returns a read-only cursor pointing to the current element. /// /// The lifetime of the returned `Cursor` is bound to that of the /// `CursorMut`, which means it cannot outlive the `CursorMut` and that the /// `CursorMut` is frozen for the lifetime of the `Cursor`. #[inline] pub fn as_cursor(&self) -> Cursor<'_, A> { Cursor { current: self.current, prev: self.prev, next: self.next, list: self.list, } } /// Moves the cursor to the next element of the `XorLinkedList`. /// /// If the cursor is pointer to the null object then this will move it to /// the first element of the `XorLinkedList`. If it is pointing to the /// last element of the `XorLinkedList` then this will move it to the /// null object. #[inline] pub fn move_next(&mut self) { let prev = self.current; self.current = self.next; unsafe { if let Some(current) = self.current { self.prev = prev; self.next = self.list.adapter.link_ops().next(current, prev); } else { self.prev = self.list.tail; self.next = self.list.head; } } } /// Moves the cursor to the previous element of the `XorLinkedList`. /// /// If the cursor is pointer to the null object then this will move it to /// the last element of the `XorLinkedList`. If it is pointing to the first /// element of the `XorLinkedList` then this will move it to the null object. #[inline] pub fn move_prev(&mut self) { let next = self.current; self.current = self.prev; unsafe { if let Some(current) = self.current { self.prev = self.list.adapter.link_ops().prev(current, next); self.next = next; } else { self.prev = self.list.tail; self.next = self.list.head; } } } /// Returns a cursor pointing to the next element of the `XorLinkedList`. /// /// If the cursor is pointer to the null object then this will return the /// first element of the `XorLinkedList`. If it is pointing to the last /// element of the `XorLinkedList` then this will return a null cursor. #[inline] pub fn peek_next(&self) -> Cursor<'_, A> { let mut next = self.as_cursor(); next.move_next(); next } /// Returns a cursor pointing to the previous element of the `XorLinkedList`. /// /// If the cursor is pointer to the null object then this will return the /// last element of the `XorLinkedList`. If it is pointing to the first /// element of the `XorLinkedList` then this will return a null cursor. #[inline] pub fn peek_prev(&self) -> Cursor<'_, A> { let mut prev = self.as_cursor(); prev.move_prev(); prev } /// Removes the current element from the `XorLinkedList`. /// /// A pointer to the element that was removed is returned, and the cursor is /// moved to point to the next element in the `XorLinkedList`. /// /// If the cursor is currently pointing to the null object then no element /// is removed and `None` is returned. #[inline] pub fn remove(&mut self) -> Option<::Pointer> { use link_ops::LinkOps; unsafe { let current = self.current?; let result = current; self.list.adapter.link_ops_mut().release_link(current); if let Some(prev) = self.prev { self.list.adapter.link_ops_mut().replace_next_or_prev( prev, Some(current), self.next, ); } if let Some(next) = self.next { self.list.adapter.link_ops_mut().replace_next_or_prev( next, Some(current), self.prev, ); } if self.list.head == Some(current) { self.list.head = self.next; } if self.list.tail == Some(current) { self.list.tail = self.prev; } self.current = self.next; if let Some(current) = self.current { self.next = self.list.adapter.link_ops().next(current, self.prev); } else { self.prev = self.list.tail; self.next = self.list.head; } Some( self.list .adapter .pointer_ops() .from_raw(self.list.adapter.get_value(result)), ) } } /// Removes the current element from the `XorLinkedList` and inserts another /// object in its place. /// /// A pointer to the element that was removed is returned, and the cursor is /// modified to point to the newly added element. /// /// If the cursor is currently pointing to the null object then an error is /// returned containing the given `val` parameter. /// /// # Panics /// /// Panics if the new element is already linked to a different intrusive /// collection. #[inline] pub fn replace_with( &mut self, val: ::Pointer, ) -> Result<::Pointer, ::Pointer> { use link_ops::LinkOps; unsafe { if let Some(current) = self.current { let new = self.list.node_from_value(val); let result = current; if self.list.head == Some(current) { self.list.head = Some(new); } if self.list.tail == Some(current) { self.list.tail = Some(new); } if let Some(prev) = self.prev { self.list.adapter.link_ops_mut().replace_next_or_prev( prev, Some(current), Some(new), ); } if let Some(next) = self.next { self.list.adapter.link_ops_mut().replace_next_or_prev( next, Some(current), Some(new), ); } self.list .adapter .link_ops_mut() .set(new, self.prev, self.next); self.list.adapter.link_ops_mut().release_link(result); self.current = Some(new); Ok(self .list .adapter .pointer_ops() .from_raw(self.list.adapter.get_value(result))) } else { Err(val) } } } /// Inserts a new element into the `XorLinkedList` after the current one. /// /// If the cursor is pointing at the null object then the new element is /// inserted at the front of the `XorLinkedList`. /// /// # Panics /// /// Panics if the new element is already linked to a different intrusive /// collection. #[inline] pub fn insert_after(&mut self, val: ::Pointer) { unsafe { let new = self.list.node_from_value(val); if let Some(current) = self.current { link_between( self.list.adapter.link_ops_mut(), new, Some(current), self.next, ); if self.next.is_none() { // Current pointer was tail self.list.tail = Some(new); } self.next = Some(new); } else { link_between(self.list.adapter.link_ops_mut(), new, None, self.list.head); self.list.head = Some(new); if self.list.tail.is_none() { self.list.tail = Some(new); } self.prev = self.list.tail; self.next = self.list.head; } } } /// Inserts a new element into the `XorLinkedList` before the current one. /// /// If the cursor is pointing at the null object then the new element is /// inserted at the end of the `XorLinkedList`. /// /// # Panics /// /// Panics if the new element is already linked to a different intrusive /// collection. #[inline] pub fn insert_before(&mut self, val: ::Pointer) { unsafe { let new = self.list.node_from_value(val); if let Some(current) = self.current { link_between( self.list.adapter.link_ops_mut(), new, self.prev, Some(current), ); if self.prev.is_none() { // Current pointer was tail self.list.head = Some(new); } self.prev = Some(new); } else { link_between(self.list.adapter.link_ops_mut(), new, self.list.tail, None); self.list.tail = Some(new); if self.list.head.is_none() { self.list.head = Some(new); } self.prev = self.list.tail; self.next = self.list.head; } } } /// Inserts the elements from the given `XorLinkedList` after the current one. /// /// If the cursor is pointing at the null object then the new elements are /// inserted at the start of the `XorLinkedList`. #[inline] pub fn splice_after(&mut self, mut list: XorLinkedList) { if !list.is_empty() { unsafe { let head = list.head.unwrap_unchecked(); let tail = list.tail.unwrap_unchecked(); let link_ops = self.list.adapter.link_ops_mut(); if let Some(current) = self.current { if let Some(next) = self.next { link_ops.replace_next_or_prev(next, Some(current), Some(tail)); link_ops.replace_next_or_prev(tail, None, Some(next)); } link_ops.replace_next_or_prev(head, None, Some(current)); self.next = list.head; link_ops.set(current, self.prev, self.next); } else { if let Some(x) = self.list.head { link_ops.replace_next_or_prev(tail, None, Some(x)); link_ops.replace_next_or_prev(x, None, Some(tail)); } self.list.head = list.head; self.next = list.head; } if self.list.tail == self.current { self.list.tail = list.tail; } list.head = None; list.tail = None; } } } /// Moves all element from the given `XorLinkedList` before the current one. /// /// If the cursor is pointing at the null object then the new elements are /// inserted at the end of the `XorLinkedList`. #[inline] pub fn splice_before(&mut self, mut list: XorLinkedList) { if !list.is_empty() { unsafe { let head = list.head.unwrap_unchecked(); let tail = list.tail.unwrap_unchecked(); let link_ops = self.list.adapter.link_ops_mut(); if let Some(current) = self.current { if let Some(prev) = self.prev { link_ops.replace_next_or_prev(prev, Some(current), Some(head)); link_ops.replace_next_or_prev(head, None, Some(prev)); } link_ops.replace_next_or_prev(tail, None, Some(current)); self.prev = list.tail; link_ops.set(current, self.prev, self.next); } else { if let Some(x) = self.list.tail { link_ops.replace_next_or_prev(head, None, Some(x)); link_ops.replace_next_or_prev(x, None, Some(head)); } self.list.head = list.head; self.next = list.head; } if self.list.tail == self.current { self.list.tail = list.tail; } list.head = None; list.tail = None; } } } /// Splits the list into two after the current element. This will return a /// new list consisting of everything after the cursor, with the original /// list retaining everything before. /// /// If the cursor is pointing at the null object then the entire contents /// of the `XorLinkedList` are moved. #[inline] pub fn split_after(&mut self) -> XorLinkedList where A: Clone, { if let Some(current) = self.current { unsafe { let mut list = XorLinkedList { head: self.next, tail: self.list.tail, adapter: self.list.adapter.clone(), }; if let Some(head) = list.head { self.list.adapter.link_ops_mut().replace_next_or_prev( head, Some(current), None, ); self.next = None; } else { list.tail = None; } self.list .adapter .link_ops_mut() .set(current, self.prev, None); self.list.tail = self.current; list } } else { let list = XorLinkedList { head: self.list.head, tail: self.list.tail, adapter: self.list.adapter.clone(), }; self.list.head = None; self.list.tail = None; list } } /// Splits the list into two before the current element. This will return a /// new list consisting of everything before the cursor, with the original /// list retaining everything after. /// /// If the cursor is pointing at the null object then the entire contents /// of the `XorLinkedList` are moved. #[inline] pub fn split_before(&mut self) -> XorLinkedList where A: Clone, { if let Some(current) = self.current { unsafe { let mut list = XorLinkedList { head: self.list.head, tail: self.prev, adapter: self.list.adapter.clone(), }; if let Some(tail) = list.tail { self.list.adapter.link_ops_mut().replace_next_or_prev( tail, Some(current), None, ); self.prev = None; } else { list.head = None; } self.list .adapter .link_ops_mut() .set(current, None, self.next); self.list.head = self.current; list } } else { let list = XorLinkedList { head: self.list.head, tail: self.list.tail, adapter: self.list.adapter.clone(), }; self.list.head = None; self.list.tail = None; list } } } // ============================================================================= // XorLinkedList // ============================================================================= /// Intrusive xor doubly-linked list which uses less memory than a regular doubly linked list /// /// In exchange for less memory use, it is impossible to create a cursor from a pointer to /// an element. /// /// When this collection is dropped, all elements linked into it will be /// converted back to owned pointers and dropped. pub struct XorLinkedList where A::LinkOps: XorLinkedListOps, { head: Option<::LinkPtr>, tail: Option<::LinkPtr>, adapter: A, } impl XorLinkedList where A::LinkOps: XorLinkedListOps, { #[inline] fn node_from_value( &mut self, val: ::Pointer, ) -> ::LinkPtr { use link_ops::LinkOps; unsafe { let raw = self.adapter.pointer_ops().into_raw(val); let link = self.adapter.get_link(raw); if !self.adapter.link_ops_mut().acquire_link(link) { // convert the node back into a pointer self.adapter.pointer_ops().from_raw(raw); panic!("attempted to insert an object that is already linked"); } link } } /// Creates an empty `XorLinkedList`. #[cfg(not(feature = "nightly"))] #[inline] pub fn new(adapter: A) -> XorLinkedList { XorLinkedList { head: None, tail: None, adapter, } } /// Creates an empty `XorLinkedList`. #[cfg(feature = "nightly")] #[inline] pub const fn new(adapter: A) -> XorLinkedList { XorLinkedList { head: None, tail: None, adapter, } } /// Returns `true` if the `XorLinkedList` is empty. #[inline] pub fn is_empty(&self) -> bool { self.head.is_none() } /// Returns a null `Cursor` for this list. #[inline] pub fn cursor(&self) -> Cursor<'_, A> { Cursor { current: None, prev: self.tail, next: self.head, list: self, } } /// Returns a null `CursorMut` for this list. #[inline] pub fn cursor_mut(&mut self) -> CursorMut<'_, A> { CursorMut { 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 /// /// `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_from_ptr_and_prev( &self, ptr: *const ::Value, prev: *const ::Value, ) -> Cursor<'_, 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); Cursor { current: Some(current), prev, next, list: self, } } /// Creates a `CursorMut` 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_mut_from_ptr_and_prev( &mut self, ptr: *const ::Value, prev: *const ::Value, ) -> CursorMut<'_, 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); CursorMut { current: Some(current), prev, next, list: self, } } /// Creates a `Cursor` 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_from_ptr_and_next( &self, ptr: *const ::Value, next: *const ::Value, ) -> Cursor<'_, 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); Cursor { current: Some(current), prev, next, list: self, } } /// Creates a `CursorMut` 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_mut_from_ptr_and_next( &mut self, ptr: *const ::Value, next: *const ::Value, ) -> CursorMut<'_, 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); CursorMut { 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] pub fn front(&self) -> Cursor<'_, A> { let mut cursor = self.cursor(); cursor.move_next(); cursor } /// Returns a `CursorMut` pointing to the first element of the list. If the /// the list is empty then a null cursor is returned. #[inline] pub fn front_mut(&mut self) -> CursorMut<'_, A> { let mut cursor = self.cursor_mut(); cursor.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] pub fn back(&self) -> Cursor<'_, A> { let mut cursor = self.cursor(); cursor.move_prev(); cursor } /// Returns a `CursorMut` pointing to the last element of the list. If the /// list is empty then a null cursor is returned. #[inline] pub fn back_mut(&mut self) -> CursorMut<'_, A> { let mut cursor = self.cursor_mut(); cursor.move_prev(); cursor } /// Gets an iterator over the objects in the `XorLinkedList`. #[inline] pub fn iter(&self) -> Iter<'_, A> { Iter { prev_head: None, head: self.head, tail: self.tail, next_tail: None, list: self, } } /// Removes all elements from the `XorLinkedList`. /// /// This will unlink all object currently in the list, which requires /// iterating through all elements in the `XorLinkedList`. Each element is /// converted back to an owned pointer and then dropped. #[inline] pub fn clear(&mut self) { use link_ops::LinkOps; let mut current = self.head; let mut prev = None; self.head = None; self.tail = None; while let Some(x) = current { unsafe { let next = self.adapter.link_ops().next(x, prev); self.adapter.link_ops_mut().release_link(x); self.adapter .pointer_ops() .from_raw(self.adapter.get_value(x)); prev = current; current = next; } } } /// Empties the `XorLinkedList` without unlinking or freeing objects in it. /// /// Since this does not unlink any objects, any attempts to link these /// objects into another `XorLinkedList` will fail but will not cause any /// memory unsafety. To unlink those objects manually, you must call the /// `force_unlink` function on them. #[inline] pub fn fast_clear(&mut self) { self.head = None; self.tail = None; } /// Takes all the elements out of the `XorLinkedList`, leaving it empty. /// The taken elements are returned as a new `XorLinkedList`. #[inline] pub fn take(&mut self) -> XorLinkedList where A: Clone, { let list = XorLinkedList { head: self.head, tail: self.tail, adapter: self.adapter.clone(), }; self.head = None; self.tail = None; list } /// Inserts a new element at the start of the `XorLinkedList`. #[inline] pub fn push_front(&mut self, val: ::Pointer) { self.cursor_mut().insert_after(val); } /// Inserts a new element at the end of the `XorLinkedList`. #[inline] pub fn push_back(&mut self, val: ::Pointer) { self.cursor_mut().insert_before(val); } /// Removes the first element of the `XorLinkedList`. /// /// This returns `None` if the `XorLinkedList` is empty. #[inline] pub fn pop_front(&mut self) -> Option<::Pointer> { self.front_mut().remove() } /// Removes the last element of the `XorLinkedList`. /// /// This returns `None` if the `XorLinkedList` is empty. #[inline] pub fn pop_back(&mut self) -> Option<::Pointer> { self.back_mut().remove() } } // Allow read-only access to values from multiple threads unsafe impl Sync for XorLinkedList where ::Value: Sync, A::LinkOps: XorLinkedListOps, { } // Allow sending to another thread if the ownership (represented by the ::Pointer owned // pointer type) can be transferred to another thread. unsafe impl Send for XorLinkedList where ::Pointer: Send, A::LinkOps: XorLinkedListOps, { } // Drop all owned pointers if the collection is dropped impl Drop for XorLinkedList where A::LinkOps: XorLinkedListOps, { #[inline] fn drop(&mut self) { self.clear(); } } impl IntoIterator for XorLinkedList where A::LinkOps: XorLinkedListOps, { type Item = ::Pointer; type IntoIter = IntoIter; #[inline] fn into_iter(self) -> IntoIter { IntoIter { list: self } } } impl<'a, A: Adapter + 'a> IntoIterator for &'a XorLinkedList where A::LinkOps: XorLinkedListOps, { type Item = &'a ::Value; type IntoIter = Iter<'a, A>; #[inline] fn into_iter(self) -> Iter<'a, A> { self.iter() } } impl Default for XorLinkedList where A::LinkOps: XorLinkedListOps, { fn default() -> XorLinkedList { XorLinkedList::new(A::default()) } } impl fmt::Debug for XorLinkedList where A::LinkOps: XorLinkedListOps, ::Value: fmt::Debug, { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_list().entries(self.iter()).finish() } } // ============================================================================= // Iter // ============================================================================= /// An iterator over references to the items of a `XorLinkedList`. pub struct Iter<'a, A: Adapter> where A::LinkOps: XorLinkedListOps, { prev_head: Option<::LinkPtr>, head: Option<::LinkPtr>, tail: Option<::LinkPtr>, next_tail: Option<::LinkPtr>, list: &'a XorLinkedList, } impl<'a, A: Adapter + 'a> Iterator for Iter<'a, A> where A::LinkOps: XorLinkedListOps, { type Item = &'a ::Value; #[inline] fn next(&mut self) -> Option<&'a ::Value> { let head = self.head?; if Some(head) == self.tail { self.prev_head = None; self.head = None; self.next_tail = None; self.tail = None; } else { let next = unsafe { self.list.adapter.link_ops().next(head, self.prev_head) }; self.prev_head = self.head; self.head = next; } Some(unsafe { &*self.list.adapter.get_value(head) }) } } impl<'a, A: Adapter + 'a> DoubleEndedIterator for Iter<'a, A> where A::LinkOps: XorLinkedListOps, { #[inline] fn next_back(&mut self) -> Option<&'a ::Value> { let tail = self.tail?; if Some(tail) == self.head { self.prev_head = None; self.head = None; self.next_tail = None; self.tail = None; } else { let new_tail = unsafe { self.list.adapter.link_ops().prev(tail, self.next_tail) }; self.next_tail = self.tail; self.tail = new_tail; } Some(unsafe { &*self.list.adapter.get_value(tail) }) } } impl<'a, A: Adapter + 'a> Clone for Iter<'a, A> where A::LinkOps: XorLinkedListOps, { #[inline] fn clone(&self) -> Iter<'a, A> { Iter { prev_head: self.prev_head, head: self.head, tail: self.tail, next_tail: self.next_tail, list: self.list, } } } // ============================================================================= // IntoIter // ============================================================================= /// An iterator which consumes a `XorLinkedList`. pub struct IntoIter where A::LinkOps: XorLinkedListOps, { list: XorLinkedList, } impl Iterator for IntoIter where A::LinkOps: XorLinkedListOps, { type Item = ::Pointer; #[inline] fn next(&mut self) -> Option<::Pointer> { self.list.pop_front() } } impl DoubleEndedIterator for IntoIter where A::LinkOps: XorLinkedListOps, { #[inline] fn next_back(&mut self) -> Option<::Pointer> { self.list.pop_back() } } // ============================================================================= // Tests // ============================================================================= #[cfg(test)] mod tests { use super::{Link, XorLinkedList}; use core::cell::Cell; use core::ptr; use std::boxed::Box; use std::fmt; use std::format; use std::rc::Rc; use std::vec::Vec; 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 = Rc: Obj { link1: Link }); intrusive_adapter!(ObjAdapter2 = Rc: Obj { link2: Link }); fn make_obj(value: u32) -> Rc { Rc::new(Obj { link1: Link::new(), link2: Link::default(), value, }) } #[test] fn test_link() { let a = make_obj(1); assert!(!a.link1.is_linked()); assert!(!a.link2.is_linked()); let mut b = XorLinkedList::::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 = XorLinkedList::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 = XorLinkedList::new(ObjAdapter1::new()); l.push_front(a); assert_eq!(l.iter().map(|x| x.value).collect::>(), [1]); l.push_front(b); assert_eq!(l.iter().map(|x| x.value).collect::>(), [2, 1]); l.push_back(c); assert_eq!(l.iter().map(|x| x.value).collect::>(), [2, 1, 3]); assert_eq!(l.pop_front().unwrap().value, 2); assert_eq!(l.iter().map(|x| x.value).collect::>(), [1, 3]); assert_eq!(l.pop_back().unwrap().value, 3); assert_eq!(l.iter().map(|x| x.value).collect::>(), [1]); assert_eq!(l.pop_front().unwrap().value, 1); assert_eq!(l.iter().map(|x| x.value).collect::>(), []); assert!(l.pop_front().is_none()); assert_eq!(l.iter().map(|x| x.value).collect::>(), []); assert!(l.pop_back().is_none()); assert_eq!(l.iter().map(|x| x.value).collect::>(), []); } #[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); 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::>(), [1, 2, 3, 4]); assert_eq!(l2.iter().map(|x| x.value).collect::>(), []); assert_eq!(l3.iter().map(|x| x.value).collect::>(), []); { let mut cur = l1.front_mut(); cur.move_next(); l2 = cur.split_after(); } assert_eq!(l1.iter().map(|x| x.value).collect::>(), [1, 2]); assert_eq!(l2.iter().map(|x| x.value).collect::>(), [3, 4]); assert_eq!(l3.iter().map(|x| x.value).collect::>(), []); { let mut cur = l2.back_mut(); l3 = cur.split_before(); } assert_eq!(l1.iter().map(|x| x.value).collect::>(), [1, 2]); assert_eq!(l2.iter().map(|x| x.value).collect::>(), [4]); assert_eq!(l3.iter().map(|x| x.value).collect::>(), [3]); { let mut cur = l1.front_mut(); cur.splice_after(l2.take()); } assert_eq!(l1.iter().map(|x| x.value).collect::>(), [1, 4, 2]); assert_eq!(l2.iter().map(|x| x.value).collect::>(), []); assert_eq!(l3.iter().map(|x| x.value).collect::>(), [3]); { let mut cur = l1.front_mut(); cur.move_next(); cur.splice_before(l3.take()); } assert_eq!(l1.iter().map(|x| x.value).collect::>(), [1, 3, 4, 2]); assert_eq!(l2.iter().map(|x| x.value).collect::>(), []); assert_eq!(l3.iter().map(|x| x.value).collect::>(), []); { let mut cur = l2.cursor_mut(); cur.splice_after(l1.take()); } assert_eq!(l1.iter().map(|x| x.value).collect::>(), []); assert_eq!(l2.iter().map(|x| x.value).collect::>(), [1, 3, 4, 2]); assert_eq!(l3.iter().map(|x| x.value).collect::>(), []); { let mut cur = l1.cursor_mut(); cur.splice_before(l2.take()); } assert_eq!(l1.iter().map(|x| x.value).collect::>(), [1, 3, 4, 2]); assert_eq!(l2.iter().map(|x| x.value).collect::>(), []); assert_eq!(l3.iter().map(|x| x.value).collect::>(), []); { let mut cur = l1.cursor_mut(); l2 = cur.split_after(); } assert_eq!(l1.iter().map(|x| x.value).collect::>(), []); assert_eq!(l2.iter().map(|x| x.value).collect::>(), [1, 3, 4, 2]); assert_eq!(l3.iter().map(|x| x.value).collect::>(), []); { let mut cur = l2.cursor_mut(); l1 = cur.split_before(); } assert_eq!(l1.iter().map(|x| x.value).collect::>(), [1, 3, 4, 2]); assert_eq!(l2.iter().map(|x| x.value).collect::>(), []); assert_eq!(l3.iter().map(|x| x.value).collect::>(), []); { let mut cur = l1.front_mut(); l2 = cur.split_before(); } assert_eq!(l1.iter().map(|x| x.value).collect::>(), [1, 3, 4, 2]); assert_eq!(l2.iter().map(|x| x.value).collect::>(), []); assert_eq!(l3.iter().map(|x| x.value).collect::>(), []); { let mut cur = l1.back_mut(); l2 = cur.split_after(); } assert_eq!(l1.iter().map(|x| x.value).collect::>(), [1, 3, 4, 2]); assert_eq!(l2.iter().map(|x| x.value).collect::>(), []); assert_eq!(l3.iter().map(|x| x.value).collect::>(), []); } #[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); 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 { let mut cursor = l.cursor_from_ptr_and_prev(b.as_ref(), a.as_ref()); assert_eq!(cursor.get().unwrap().value, 2); cursor.move_next(); assert_eq!(cursor.get().unwrap().value, 3); assert_eq!( l.cursor_mut_from_ptr_and_next(c.as_ref(), d.as_ref()) .get() .unwrap() .value, 3 ); assert_eq!( l.cursor_mut_from_ptr_and_prev(a.as_ref(), ptr::null()) .get() .unwrap() .value, 1 ); assert_eq!( l.cursor_mut_from_ptr_and_next(d.as_ref(), ptr::null()) .get() .unwrap() .value, 4 ); let mut cursor = l.cursor_from_ptr_and_next(d.as_ref(), ptr::null()); assert_eq!(cursor.get().unwrap().value, 4); cursor.move_prev(); assert_eq!(cursor.get().unwrap().value, 3); cursor.move_next(); assert_eq!(cursor.get().unwrap().value, 4); cursor.move_next(); assert!(cursor.is_null()); } 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::>(), [1, 2, 3, 4] ); assert_eq!( l.iter().rev().map(|x| x.value).collect::>(), [4, 3, 2, 1] ); assert_eq!(l.iter().map(|x| x.value).collect::>(), [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 = 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); 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::>(), [1, 2, 3, 4]); assert_eq!(l2.iter().map(|x| x.value).collect::>(), [4, 3, 2, 1]); } #[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); 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 = XorLinkedList::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); } #[test] fn test_drop() { #[derive(Clone)] struct Obj<'a> { link: Link, value: &'a Cell, } impl<'a> Drop for Obj<'a> { fn drop(&mut self) { let val = self.value.get(); self.value.set(val + 1); } } intrusive_adapter!(ObjAdapter<'a> = Box>: Obj<'a> {link: Link}); let v = Cell::new(0); let obj = Obj { link: Link::new(), value: &v, }; let mut l = XorLinkedList::new(ObjAdapter::new()); l.cursor_mut().insert_before(Box::new(obj.clone())); l.cursor_mut().insert_before(Box::new(obj.clone())); assert_eq!(l.front().get().unwrap().value.get(), 0); assert_eq!(l.back().get().unwrap().value.get(), 0); assert_eq!(v.get(), 0); l.pop_front(); assert_eq!(v.get(), 1); l.front_mut().insert_after(Box::new(obj.clone())); assert_eq!(v.get(), 1); drop(l); assert_eq!(v.get(), 3); } 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 { link: Link }); let a = $ptr::new(Obj { link: Link::new(), value: 5, }); let mut l = XorLinkedList::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); } }