Struct PieList 

pub struct PieList<T> { /* private fields */ }

A handle to a doubly-linked list within a shared ElemPool.

A PieList itself is a lightweight struct containing only an Index to a sentinel node and the list’s length. All list elements are stored and managed by a separate ElemPool. This design allows for many PieLists to share memory from a single pool.

All operations that modify or access the list’s elements, such as push_back or front, require a mutable or immutable reference to the ElemPool where the data is stored.

Important: Memory Management

When a PieList is dropped, the elements it references are not automatically returned to the pool. This is a deliberate design choice to allow lists to be moved and managed without unintended side effects on the pool.

To prevent memory leaks within the pool, you must call clear() or drain() on a list when you are finished with it. This will iterate through all its elements and return them to the pool’s free list, making them available for reuse.

Implementations

impl<T> PieList<T>

pub fn new(pool: &mut ElemPool<T>) -> Self

Creates a new, empty list handle.

This operation allocates a single sentinel node from the provided pool. The sentinel acts as a fixed entry point for the list, simplifying the logic for insertions and removals at the boundaries.

Panics

Panics if the ElemPool cannot allocate a new element for the sentinel, which would typically only happen in an out-of-memory situation.

pub fn len(&self) -> usize

Returns the number of elements in the list.

Complexity

O(1)

pub fn is_empty(&self) -> bool

Returns true if the list contains no elements.

Complexity

O(1)

pub fn front<'a>(&self, pool: &'a ElemPool<T>) -> Option<&'a T>

Provides a reference to the front element’s data, or None if the list is empty.

Complexity

O(1)

pub fn front_mut<'a>(&mut self, pool: &'a mut ElemPool<T>) -> Option<&'a mut T>

Provides a mutable reference to the front element’s data, or None if empty.

Complexity

O(1)

pub fn back<'a>(&self, pool: &'a ElemPool<T>) -> Option<&'a T>

Provides a reference to the back element’s data, or None if the list is empty.

Complexity

O(1)

pub fn back_mut<'a>(&mut self, pool: &'a mut ElemPool<T>) -> Option<&'a mut T>

Provides a mutable reference to the back element’s data, or None if empty.

Complexity

O(1)

pub fn push_front( &mut self, data: T, pool: &mut ElemPool<T>, ) -> Result<(), IndexError>

Adds an element to the front of the list.

Complexity

O(1)

Errors

Returns an IndexError if the pool is unable to allocate a new element.

pub fn push_back( &mut self, data: T, pool: &mut ElemPool<T>, ) -> Result<(), IndexError>

Adds an element to the back of the list.

Complexity

O(1)

Errors

Returns an IndexError if the pool is unable to allocate a new element.

pub fn pop_front(&mut self, pool: &mut ElemPool<T>) -> Option<T>

Removes the first element and returns its data, or None if the list is empty.

The removed element’s node is returned to the pool’s free list.

Complexity

O(1)

pub fn pop_back(&mut self, pool: &mut ElemPool<T>) -> Option<T>

Removes the last element and returns its data, or None if the list is empty.

The removed element’s node is returned to the pool’s free list.

Complexity

O(1)

pub fn clear(&mut self, pool: &mut ElemPool<T>)

Removes all elements from the list, returning them to the pool’s free list.

This is a critical method for memory management. Failure to call clear on a list that is no longer needed will result in its elements being leaked within the pool, as they will never be added to the free list for reuse.

Complexity

O(n), where n is the number of elements in the list.

pub fn drain<'a>(&'a mut self, pool: &'a mut ElemPool<T>) -> Drain<'a, T>

Creates a draining iterator that removes all elements from the list and yields them from front to back.

The removed nodes are returned to the pool’s free list.

Note

If the iterator is dropped before it is fully consumed, it will still remove the remaining elements from the list to ensure that the list is left empty.

Complexity

O(n), where n is the number of elements in the list. Each element is visited once.

Example

let mut list = PieList::new(&mut pool);
list.push_back(1, &mut pool).unwrap();
list.push_back(2, &mut pool).unwrap();
list.push_back(3, &mut pool).unwrap();

let drained_items: Vec<_> = list.drain(&mut pool).collect();

assert_eq!(drained_items, vec![1, 2, 3]);
assert!(list.is_empty());
assert_eq!(pool.len(), 0); // All elements returned to pool

pub fn sort<F>(&mut self, pool: &mut ElemPool<T>, compare: F)

where F: FnMut(&T, &T) -> Ordering,

Sorts the list in place using a stable merge sort algorithm.

Complexity

O(n log n) comparisons, where n is the number of elements in the list. The merge operations are done in-place without new allocations from the pool.

Example

let mut list = PieList::new(&mut pool);
list.push_back(5, &mut pool).unwrap();
list.push_back(2, &mut pool).unwrap();
list.push_back(8, &mut pool).unwrap();
list.push_back(1, &mut pool).unwrap();

// Sort in ascending order
list.sort(&mut pool, |a, b| a.cmp(b));

let sorted: Vec<_> = list.iter(&pool).copied().collect();
assert_eq!(sorted, vec![1, 2, 5, 8]);

pub fn append( &mut self, other: &mut PieList<T>, pool: &mut ElemPool<T>, ) -> Result<(), IndexError>

Moves all elements from other to the end of self.

After the operation, other is left empty.

Complexity

O(1)

Errors

Returns an IndexError if the pool’s internal linking fails, though this is highly unlikely if the lists are valid.

pub fn prepend( &mut self, other: &mut PieList<T>, pool: &mut ElemPool<T>, ) -> Result<(), IndexError>

Moves all elements from other to the beginning of self.

After the operation, other is left empty.

Complexity

O(1)

Errors

Returns an IndexError if the pool’s internal linking fails, though this is highly unlikely if the lists are valid.

pub fn iter<'a>(&self, pool: &'a ElemPool<T>) -> Iter<'a, T>

Returns an iterator that provides immutable references to the elements from front to back.

pub fn iter_mut<'a>(&mut self, pool: &'a mut ElemPool<T>) -> IterMut<'a, T>

Returns an iterator that provides mutable references to the elements from front to back.

pub fn cursor_mut<'a>(&'a mut self, pool: &mut ElemPool<T>) -> CursorMut<'a, T>

Returns a mutable cursor pointing to the first element of the list.

The cursor provides an efficient API for arbitrary insertion, deletion, and moving through the list.

pub fn cursor_mut_at<'a>( &'a mut self, index: usize, pool: &mut ElemPool<T>, ) -> Result<CursorMut<'a, T>, IndexError>

Returns a mutable cursor pointing to the element at the given logical index.

Complexity

O(min(k, n-k)), where k is the index and n is the list’s length. The method traverses from the nearest end of the list to find the element.

Errors

Returns Err(IndexError::IndexOutOfBounds) if index >= self.len().

Trait Implementations

impl<T> Clone for PieList<T>

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for PieList<T>

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

Formats the value using the given formatter.

impl<T> Copy for PieList<T>