pub struct XorLinkedList<A: Adapter>{ /* private fields */ }
Expand description

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.

Implementations§

source§

impl<A: Adapter> XorLinkedList<A>

source

pub fn new(adapter: A) -> XorLinkedList<A>

Creates an empty XorLinkedList.

source

pub fn is_empty(&self) -> bool

Returns true if the XorLinkedList is empty.

source

pub fn cursor(&self) -> Cursor<'_, A>

Returns a null Cursor for this list.

source

pub fn cursor_mut(&mut self) -> CursorMut<'_, A>

Returns a null CursorMut for this list.

source

pub fn cursor_owning(self) -> CursorOwning<A>

Returns a null CursorOwning for this list.

source

pub unsafe fn cursor_from_ptr_and_prev( &self, ptr: *const <A::PointerOps as PointerOps>::Value, prev: *const <A::PointerOps as PointerOps>::Value, ) -> Cursor<'_, A>

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)

source

pub unsafe fn cursor_mut_from_ptr_and_prev( &mut self, ptr: *const <A::PointerOps as PointerOps>::Value, prev: *const <A::PointerOps as PointerOps>::Value, ) -> CursorMut<'_, A>

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)

source

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>

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)

source

pub unsafe fn cursor_from_ptr_and_next( &self, ptr: *const <A::PointerOps as PointerOps>::Value, next: *const <A::PointerOps as PointerOps>::Value, ) -> Cursor<'_, A>

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)

source

pub unsafe fn cursor_mut_from_ptr_and_next( &mut self, ptr: *const <A::PointerOps as PointerOps>::Value, next: *const <A::PointerOps as PointerOps>::Value, ) -> CursorMut<'_, A>

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)

source

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>

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)

source

pub fn front(&self) -> Cursor<'_, A>

Returns a Cursor pointing to the first element of the list. If the list is empty then a null cursor is returned.

source

pub fn front_mut(&mut self) -> CursorMut<'_, A>

Returns a CursorMut pointing to the first element of the list. If the the list is empty then a null cursor is returned.

source

pub fn front_owning(self) -> CursorOwning<A>

Returns a CursorOwning pointing to the first element of the list. If the the list is empty then a null cursor is returned.

source

pub fn back(&self) -> Cursor<'_, A>

Returns a Cursor pointing to the last element of the list. If the list is empty then a null cursor is returned.

source

pub fn back_mut(&mut self) -> CursorMut<'_, A>

Returns a CursorMut pointing to the last element of the list. If the list is empty then a null cursor is returned.

source

pub fn back_owning(self) -> CursorOwning<A>

Returns a CursorOwning pointing to the last element of the list. If the list is empty then a null cursor is returned.

source

pub fn iter(&self) -> Iter<'_, A>

Gets an iterator over the objects in the XorLinkedList.

source

pub fn clear(&mut 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.

source

pub fn fast_clear(&mut self)

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.

source

pub fn take(&mut self) -> XorLinkedList<A>
where A: Clone,

Takes all the elements out of the XorLinkedList, leaving it empty. The taken elements are returned as a new XorLinkedList.

source

pub fn push_front(&mut self, val: <A::PointerOps as PointerOps>::Pointer)

Inserts a new element at the start of the XorLinkedList.

source

pub fn push_back(&mut self, val: <A::PointerOps as PointerOps>::Pointer)

Inserts a new element at the end of the XorLinkedList.

source

pub fn pop_front(&mut self) -> Option<<A::PointerOps as PointerOps>::Pointer>

Removes the first element of the XorLinkedList.

This returns None if the XorLinkedList is empty.

source

pub fn pop_back(&mut self) -> Option<<A::PointerOps as PointerOps>::Pointer>

Removes the last element of the XorLinkedList.

This returns None if the XorLinkedList is empty.

source

pub fn reverse(&mut self)

Reverses the list in-place.

Due to the structure of XorLinkedList, this operation is O(1).

Trait Implementations§

source§

impl<A: Adapter> Debug for XorLinkedList<A>

source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
source§

impl<A: Adapter + Default> Default for XorLinkedList<A>

source§

fn default() -> XorLinkedList<A>

Returns the “default value” for a type. Read more
source§

impl<A: Adapter> Drop for XorLinkedList<A>

source§

fn drop(&mut self)

Executes the destructor for this type. Read more
source§

impl<'a, A: Adapter + 'a> IntoIterator for &'a XorLinkedList<A>

source§

type Item = &'a <<A as Adapter>::PointerOps as PointerOps>::Value

The type of the elements being iterated over.
source§

type IntoIter = Iter<'a, A>

Which kind of iterator are we turning this into?
source§

fn into_iter(self) -> Iter<'a, A>

Creates an iterator from a value. Read more
source§

impl<A: Adapter> IntoIterator for XorLinkedList<A>

source§

type Item = <<A as Adapter>::PointerOps as PointerOps>::Pointer

The type of the elements being iterated over.
source§

type IntoIter = IntoIter<A>

Which kind of iterator are we turning this into?
source§

fn into_iter(self) -> IntoIter<A>

Creates an iterator from a value. Read more
source§

impl<A: Adapter + Send> Send for XorLinkedList<A>

source§

impl<A: Adapter + Sync> Sync for XorLinkedList<A>

Auto Trait Implementations§

§

impl<A> Freeze for XorLinkedList<A>
where A: Freeze, <<A as Adapter>::LinkOps as LinkOps>::LinkPtr: Freeze,

§

impl<A> RefUnwindSafe for XorLinkedList<A>

§

impl<A> Unpin for XorLinkedList<A>
where A: Unpin, <<A as Adapter>::LinkOps as LinkOps>::LinkPtr: Unpin,

§

impl<A> UnwindSafe for XorLinkedList<A>

Blanket Implementations§

source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

source§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.