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

⚠️ WARNING: MEMORY LEAK RISK ⚠️

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 without_leak_check(self) -> Self

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<Index<T>, 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<Index<T>, 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 retain<F>(&mut self, pool: &mut ElemPool<T>, f: F)

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

Retains only the elements for which the predicate returns true.

Elements for which f returns false are removed from the list and returned to the pool’s free list.

Complexity

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

Example

let mut list = PieList::new(&mut pool);
for v in 0..10 {
    list.push_back(v, &mut pool).unwrap();
}
list.retain(&mut pool, |x| x % 2 == 0);
let items: Vec<_> = list.iter(&pool).copied().collect();
assert_eq!(items, vec![0, 2, 4, 6, 8]);

pub fn set_leak_check(&mut self, _leak_check: bool)

Enable/disable the leak check for this list in debug builds

NOTE: No leak check is performed in release builds

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.

Implementation

Uses an optimized bottom-up iterative merge sort that allocates at most O(log n) temporary sentinel nodes, which are reused across all merge operations. This is significantly more efficient than a naive recursive approach that would allocate O(n) temporary sentinels.

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.

Uses slot-based traversal for maximum performance.

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.

Uses slot-based traversal for maximum performance.

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

Creates an immutable view of the list using the provided pool.

The view bundles the list and pool together, offering a simplified API for read-only operations.

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

Creates a mutable view of the list using the provided pool.

The view bundles the list and pool together, offering a simplified API for mutable operations (push, pop, etc.).

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

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

The cursor allows for bidirectional navigation.

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

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

Complexity

O(min(k, n-k)) traversal.

Errors

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

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().

pub fn remap(&mut self, map: &HashMap<Index<T>, Index<T>>)

Updates the list’s internal sentinel index if it was affected by a shrink_to_fit operation.

This method checks the provided remapping table to see if the sentinel node for this list was moved to a new index. If so, it updates the PieList handle to point to the new location.

Complexity

O(1) - It performs a single hash map lookup.

Trait Implementations

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

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

Formats the value using the given formatter.

impl<T> Drop for PieList<T>

Available on debug-assertions enabled only.

fn drop(&mut self)

Executes the destructor for this type.