mtb_entity_slab/container/

list_base.rs

//! Basic linked-list implementation for entity allocation, including
//! header definitions, error handling, and range + iterator support.

use crate::{IDBoundAlloc, IEntityAllocID, IPoliciedID};

/// Lightweight head metadata stored on each list node.
///
/// This small struct holds the previous and next node IDs for a node that
/// participates in either a linked list or a ring list. It is intended to be
/// embedded in entity storage so that list linkage does not require separate
/// allocation.
///
/// The `prev`/`next` options are `None` when the node is detached. In the
/// ring-list sentinel case both fields point to the sentinel itself.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct EntityListNodeHead<I: IPoliciedID> {
    /// Previous node ID, if any.
    pub prev: Option<I>,
    /// Next node ID, if any.
    pub next: Option<I>,
}
impl<I: IPoliciedID> EntityListNodeHead<I> {
    /// Create a new empty (detached) node head.
    pub fn none() -> Self {
        Self {
            prev: None,
            next: None,
        }
    }
    /// Create a new node head with given prev/next IDs.
    pub fn new_full(prev: Option<I>, next: Option<I>) -> Self {
        Self { prev, next }
    }
    /// Create a new node head from given prev/next IDs (both non-None).
    pub fn from_id(prev: I, next: I) -> Self {
        Self {
            prev: Some(prev),
            next: Some(next),
        }
    }
    /// Decompose the node head into its prev/next IDs.
    pub fn into_id(self) -> (Option<I>, Option<I>) {
        (self.prev, self.next)
    }

    /// Get the previous node ID, if any.
    pub fn get_prev(&self) -> Option<I> {
        self.prev
    }
    /// Get the next node ID, if any.
    pub fn get_next(&self) -> Option<I> {
        self.next
    }

    fn prev(mut self, prev: Option<I>) -> Self {
        self.prev = prev;
        self
    }
    fn next(mut self, next: Option<I>) -> Self {
        self.next = next;
        self
    }
}

/// Error kinds returned by `EntityList` operations.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum EntityListError<I: IPoliciedID> {
    /// The list is empty.
    EmptyList,
    /// The list structure is broken (inconsistent links).
    ListBroken,
    /// A sentinel node was used where a normal node was expected.
    NodeIsSentinel,
    /// The same node was added multiple times.
    RepeatedNode,
    /// Operations are done in the same list which is not allowed.
    RepeatedList,
    /// The node was expected to be attached but is not.
    SelfNotAttached(I),
    /// The node was expected to be detached but is attached.
    ItemFalselyAttached(I),
    /// The node was expected to be attached but is detached.
    ItemFalselyDetached(I),
}
impl<I: IPoliciedID> std::fmt::Display for EntityListError<I> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        std::fmt::Debug::fmt(&self, f)
    }
}
impl<I: IPoliciedID> std::error::Error for EntityListError<I> {}

/// Result type returned by list operations.
///
/// Uses `EntityListError<I>` as the error kind so callers can handle list
/// specific failures (broken invariants, sentinel misuse, etc.).
pub type EntityListRes<I, T = ()> = Result<T, EntityListError<I>>;

/// Basic doublely-linked list ID concept. Provides basic header(`prev|next`) management,
/// signals for list operations, and sentinel node support.
pub trait IBasicEntityListID: IPoliciedID {
    /// Load the `EntityListNodeHead` from the entity object.
    fn obj_load_head(obj: &Self::ObjectT) -> EntityListNodeHead<Self>;
    /// NOTE: Entity Lists are internally mutable
    fn obj_store_head(obj: &Self::ObjectT, head: EntityListNodeHead<Self>);
    /// Check if the entity object is a sentinel node.
    fn obj_is_sentinel(obj: &Self::ObjectT) -> bool;
    /// Create a new sentinel entity object.
    fn new_sentinel_obj() -> Self::ObjectT;

    /// Check if this node ID is a sentinel.
    #[inline]
    fn is_sentinel(self, alloc: &IDBoundAlloc<Self>) -> bool {
        Self::obj_is_sentinel(self.deref_alloc(alloc))
    }
    /// Create a new sentinel node ID allocated from the given allocator.
    fn new_sentinel(alloc: &IDBoundAlloc<Self>) -> Self {
        let obj = Self::new_sentinel_obj();
        Self::from_backend(Self::BackID::allocate_from(alloc, obj))
    }

    /// Signal: invoked when this node is being added after `prev` node.
    fn on_push_prev(self, prev: Self, alloc: &IDBoundAlloc<Self>) -> EntityListRes<Self>;
    /// Signal: invoked when this node is being added before `next` node.
    fn on_push_next(self, next: Self, alloc: &IDBoundAlloc<Self>) -> EntityListRes<Self>;
    /// Signal: invoked when this node is being unplugged from a list.
    fn on_unplug(self, alloc: &IDBoundAlloc<Self>) -> EntityListRes<Self>;

    /// Get the previous node ID, if any.
    fn get_prev_id(self, alloc: &IDBoundAlloc<Self>) -> Option<Self> {
        Self::obj_get_prev_id(self.deref_alloc(alloc))
    }
    /// Get the next node ID, if any.
    fn get_next_id(self, alloc: &IDBoundAlloc<Self>) -> Option<Self> {
        Self::obj_get_next_id(self.deref_alloc(alloc))
    }
    /// Check if this node is currently attached to a list.
    fn is_attached(self, alloc: &IDBoundAlloc<Self>) -> bool {
        Self::obj_is_attached(self.deref_alloc(alloc))
    }
}

pub(super) trait NodeOps: IPoliciedID {
    fn obj_get_prev_id(obj: &Self::ObjectT) -> Option<Self>;
    fn obj_get_next_id(obj: &Self::ObjectT) -> Option<Self>;

    fn obj_set_prev_id(obj: &Self::ObjectT, prev: Option<Self>);
    fn obj_set_next_id(obj: &Self::ObjectT, next: Option<Self>);
    fn obj_is_attached(obj: &Self::ObjectT) -> bool;

    fn set_prev_id(self, alloc: &IDBoundAlloc<Self>, prev: Option<Self>) {
        Self::obj_set_prev_id(self.deref_alloc(alloc), prev);
    }
    fn set_next_id(self, alloc: &IDBoundAlloc<Self>, next: Option<Self>) {
        Self::obj_set_next_id(self.deref_alloc(alloc), next);
    }
}
impl<I: IBasicEntityListID> NodeOps for I {
    fn obj_get_prev_id(obj: &Self::ObjectT) -> Option<Self> {
        Self::obj_load_head(obj).prev
    }
    fn obj_get_next_id(obj: &Self::ObjectT) -> Option<Self> {
        Self::obj_load_head(obj).next
    }

    fn obj_set_prev_id(obj: &Self::ObjectT, prev: Option<Self>) {
        let head = Self::obj_load_head(obj);
        Self::obj_store_head(obj, head.prev(prev));
    }
    fn obj_set_next_id(obj: &Self::ObjectT, next: Option<Self>) {
        let head = Self::obj_load_head(obj);
        Self::obj_store_head(obj, head.next(next));
    }

    fn obj_is_attached(obj: &Self::ObjectT) -> bool {
        let head = Self::obj_load_head(obj);
        let is_sentinel = Self::obj_is_sentinel(obj);
        let has_prev = head.prev.is_some();
        let has_next = head.next.is_some();
        if cfg!(debug_assertions) && !is_sentinel && has_prev != has_next {
            panic!("EntityListNodeID: obj_is_attached: inconsistent attachment state detected");
        }
        has_prev || has_next
    }
}

/// A partial-close range of an entity pointer list representing `[start, end)`.
///
/// - if `end is None`, the range is open-ended.
/// - the `start` is non-nullable, meaning any range must have a valid start.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct EntityListRange<I: IBasicEntityListID> {
    /// Start ID (inclusive).
    pub start: I,
    /// Optional end ID (exclusive). If `None`, the range is open-ended.
    pub end: Option<I>,
}
impl<I: IBasicEntityListID> EntityListRange<I> {
    /// Check if the range is empty.
    pub fn is_empty(&self) -> bool {
        Some(self.start) == self.end
    }

    /// Create an iterator over this range.
    pub fn iter<'a>(&self, alloc: &'a IDBoundAlloc<I>) -> EntityListIter<'a, I> {
        EntityListIter::new(*self, alloc)
    }

    /// count the length of this range.
    pub fn count_len(&self, alloc: &IDBoundAlloc<I>) -> usize {
        self.iter(alloc).count()
    }

    /// Create a debug view for this range.
    pub fn debug<'a>(&self, alloc: &'a IDBoundAlloc<I>) -> EntityListRangeDebug<'a, I> {
        EntityListRangeDebug {
            alloc,
            range: *self,
        }
    }
}

/// Iterator over a range of nodes in an `EntityList`.
///
/// Yields `(I, &I::ObjectT)` pairs where the ID identifies the node and the
/// reference points to the underlying entity. The iterator borrows the
/// `EntityAlloc` for the duration of the iteration and follows the `next`
/// pointers stored inside node objects.
pub struct EntityListIter<'alloc, I: IBasicEntityListID> {
    pub(super) alloc: &'alloc IDBoundAlloc<I>,
    pub(super) curr: Option<I>,
    pub(super) end: Option<I>,
}
impl<'alloc, I: IBasicEntityListID> Iterator for EntityListIter<'alloc, I>
where
    I::ObjectT: 'alloc,
{
    type Item = (I, &'alloc I::ObjectT);

    fn next(&mut self) -> Option<Self::Item> {
        let curr = self.curr?;
        if Some(curr) == self.end {
            return None;
        }
        let obj = curr.deref_alloc(self.alloc);
        self.curr = curr.get_next_id(self.alloc);
        Some((curr, obj))
    }
}
impl<'alloc, I: IBasicEntityListID> EntityListIter<'alloc, I> {
    /// Create a new iterator over the given range.
    pub fn new(range: EntityListRange<I>, alloc: &'alloc IDBoundAlloc<I>) -> Self {
        Self {
            alloc,
            curr: Some(range.start),
            end: range.end,
        }
    }
}

/// Debug view for an entity list range.
pub struct EntityListRangeDebug<'a, I: IBasicEntityListID> {
    /// Allocator reference.
    pub alloc: &'a IDBoundAlloc<I>,
    /// Range to debug.
    pub range: EntityListRange<I>,
}
impl<'a, I> std::fmt::Debug for EntityListRangeDebug<'a, I>
where
    I: IBasicEntityListID,
    I::ObjectT: std::fmt::Debug,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let mut list_dbg = f.debug_list();
        for (_id, obj) in self.range.iter(self.alloc) {
            list_dbg.entry(obj);
        }
        list_dbg.finish()
    }
}