Struct ElemPool 

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

A pool of ListElem<T> nodes that provides memory for multiple data structures.

Rationale

The ElemPool is the cornerstone of this library’s design. It acts as a specialized memory allocator. By pre-allocating memory in a Vec and managing its own free list, it avoids the performance cost of frequent calls to the global allocator. This makes creating and destroying elements extremely fast.

All list elements, regardless of which PieList or FibHeap they belong to, are stored contiguously within this single structure, leading to better cache locality during traversals compared to traditional node-based linked lists.

Its public API is minimal, as most interactions are performed through PieList, CursorMut, or FibHeap methods, which take the pool as an argument.

Implementations

impl<T> ElemPool<T>

pub fn new() -> Self

Creates a new, empty element pool.

The pool is initialized with a capacity for zero elements but contains one internal node to act as the sentinel for the free list.

pub fn len(&self) -> usize

Returns the number of elements holding user data in the pool.

This is a semantic count that excludes sentinel nodes for active lists and any elements on the free list. It provides a clear measure of how many items are actually being stored across all lists.

pub fn is_empty(&self) -> bool

Returns true if the pool contains no user data.

pub fn capacity(&self) -> usize

Returns the total number of elements (used, sentinels, or free) that the pool can hold without reallocating its internal vector. This count excludes the pool’s own free-list sentinel.

pub fn free_len(&self) -> usize

Returns the number of free elements in the pool.

pub fn list_count(&self) -> usize

Returns the number of active lists associated with this pool.

This is calculated by subtracting the number of data-holding elements and free elements from the total capacity, with the remainder being the sentinel nodes for active lists.

pub fn reserve(&mut self, additional: usize)

Reserves capacity for at least additional more elements to be allocated in the pool.

The pool’s underlying storage may reallocate if its capacity is less than the current length plus additional. If the capacity is already sufficient, this does nothing.

This is useful to avoid multiple reallocations when a large number of elements are expected to be added.

Panics

Panics if the new capacity overflows isize::MAX.

pub fn contains(&self, index: Index<T>) -> bool

Checks if a given index points to an element that contains user data.

Returns false if the index is NONE, out of bounds, or points to a free/sentinel element.

pub fn validate_index(&self, index: Index<T>) -> Result<(), IndexError>

Performs a detailed validation of an index and its surrounding links.

This is a powerful debugging tool to verify the structural integrity of a list. It checks that:

1. The index is valid and in bounds.
2. The element at the index contains data.
3. The prev element’s next link points back to this index.
4. The next element’s prev link points back to this index.

Errors

Returns Ok(()) on success, or an IndexError variant describing the first validation failure encountered.

Trait Implementations

impl<T: Clone> Clone for ElemPool<T>

fn clone(&self) -> ElemPool<T>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for ElemPool<T>

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

Formats the value using the given formatter.

impl<T> Default for ElemPool<T>

fn default() -> Self

Creates a new ElemPool, initialized with a single sentinel element for its internal free list.

impl<T> Display for ElemPool<T>

where T: Display,

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

Formats the value using the given formatter.