Struct ElemPool 

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

A pool of elements that provides memory for multiple data structures.

Struct-of-Arrays Design

Each element stores its metadata (links + generation/state) and user data inline, providing optimal cache locality for linked list operations.

Rationale

The ElemPool is the cornerstone of this library’s design. It acts as a specialized memory allocator. By pre-allocating memory in Vecs 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.

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 validate_integrity(&self) -> Result<(), String>

Validates the structural integrity of the pool after deserialization.

Checks the following invariants:

1. The pool is non-empty (slot 0 must exist and be a sentinel).
2. All next/prev links are bidirectional (if A.next == B then B.prev == A).
3. All links point to valid slots (within bounds).
4. The freed count matches the actual number of free-list elements.
5. The used count matches the actual number of USED elements.
6. No elements are in the ZOMBIE state (which is transient).

Returns Ok(()) if all checks pass, or an error string describing the first failure.

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.

pub fn iter_elems(&self) -> Iter<'_, Elem<T>>

Returns an iterator over the pool’s raw element metadata.

This is primarily used internally (e.g. by FibHeap) to perform operations that require traversing the entire pool structure, such as remapping internal pointers after a shrink_to_fit operation.

pub fn iter_elems_mut(&mut self) -> IterMut<'_, Elem<T>>

Returns a mutable iterator over the pool’s raw elements.

This is primarily used internally (e.g. by FibHeap) to perform operations that require traversing the entire pool structure, such as remapping internal pointers after a shrink_to_fit operation.

pub fn shrink_to_fit(&mut self) -> HashMap<Index<T>, Index<T>>

Compacts the pool by moving elements from the end of the internal vector into free slots at the beginning.

This implementation relies on the internal free list to identify holes efficiently, avoiding a full scan of the pool’s lower bounds.

Performance

The algorithm is O(f) where f is the number of freed elements, plus O(m) for fixing neighbor pointers where m is the number of moved elements. Memory usage is O(f) for the temporary data structures.

For large pools with many freed elements, the implementation uses:

• A compact boolean array for tracking free slots in the tail region
• Pre-sized collections to minimize allocations
• A slot-indexed remapping array (instead of hash lookups) for O(1) neighbor resolution

Trait Implementations

impl<T: Clone> Clone for ElemPool<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 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.

impl<T> Drop for ElemPool<T>

fn drop(&mut self)

Executes the destructor for this type.