mtb_entity_slab/container/

list.rs

//! Linked list implementations for entity allocators.
//!
//! This module provides doubly linked list and ring list structures
//! that operate on entities managed by `EntityAlloc`. The lists
//! support various operations such as insertion, removal, and traversal.
//!
//! The lists are generic over entity ID types that implement the
//! `IEntityListNodeID` or `IEntityRingListNodeID` traits, allowing
//! flexible integration with different entity types (PtrID, IndexedID or
//! anything defined by yourself).
//!
//! The lists also support signaling mechanisms to notify entities
//! when they are added to or removed from a list, enabling custom
//! behaviors during these operations.
//!
//! # Safety
//!
//! These lists rely on the correctness of the entity allocator
//! and the entity ID implementations. Improper use may lead to
//! undefined behavior, such as broken lists or memory corruption.
//!
//! Ensure that entities are properly managed and that list operations
//! are performed in a safe manner.
//!
//! 基于 EntityAlloc 实现的链表结构。
//!
//! 本模块提供了双向链表和环形链表结构，支持在 EntityAlloc 管理的实体上进行各种操作。
//! 这些链表支持插入、删除和遍历等操作。
//!
//! 链表是泛型的，适用于实现了 `IEntityListNodeID` 或 `IEntityRingListNodeID` 特征的实体 ID 类型，
//! 允许与不同的实体类型（如 PtrID、IndexedID 或自定义类型）灵活集成。
//!
//! 链表还支持信号机制，在实体被添加到或从链表中移除时进行通知，从而实现自定义行为。
//!
//! # 安全性
//!
//! 这些链表依赖于实体分配器和实体 ID 实现的正确性。不当使用可能导致未定义行为，如链表损坏或内存损坏。

use crate::{IDBoundAlloc, IEntityAllocID, IPoliciedID};
use std::cell::Cell;

/// 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
    }
}

mod list_util {
    pub(super) struct RingList;
    pub(super) struct LinkList;
}
trait NodeOpsPrivate<KindT>: 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);
    }
}

/// 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>>;

/// Trait required for an entity ID to be used as a node in `EntityList`.
///
/// Implementors must provide accessors to load/store the embedded
/// `EntityListNodeHead` inside the entity object, create sentinel objects,
/// and handle optional push/unplug signals. This trait lets the list logic
/// remain generic over different ID representations (pointer-based or
/// index-based).
pub trait IEntityListNodeID: 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))
    }

    /// Check whether this node comes before another node in the same list.
    fn comes_before(self, latter: Self, alloc: &IDBoundAlloc<Self>) -> EntityListRes<Self, bool> {
        let mut node = self;
        while let Some(next) = node.get_next_id(alloc) {
            if next == latter {
                return Ok(true);
            }
            node = next;
        }
        if node.is_sentinel(alloc) {
            Ok(false)
        } else {
            Err(EntityListError::ListBroken)
        }
    }
}
impl<I: IEntityListNodeID> NodeOpsPrivate<list_util::LinkList> for I {
    fn obj_get_prev_id(obj: &Self::ObjectT) -> Option<Self> {
        I::obj_load_head(obj).get_prev()
    }
    fn obj_get_next_id(obj: &Self::ObjectT) -> Option<Self> {
        I::obj_load_head(obj).get_next()
    }
    fn obj_set_prev_id(obj: &Self::ObjectT, prev: Option<Self>) {
        Self::obj_store_head(obj, Self::obj_load_head(obj).prev(prev));
    }
    fn obj_set_next_id(obj: &Self::ObjectT, next: Option<Self>) {
        Self::obj_store_head(obj, Self::obj_load_head(obj).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: IEntityListNodeID> {
    /// Start ID (inclusive).
    pub start: I,
    /// Optional end ID (exclusive). If `None`, the range is open-ended.
    pub end: Option<I>,
}
impl<I: IEntityListNodeID> 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)
    }
}

/// Doubly-linked list view over entities stored in an `EntityAlloc`.
///
/// Logical structure: the list uses head/tail sentinel nodes (allocated via
/// the entity allocator) and maintains `EntityListNodeHead` inside each
/// entity to chain nodes. Physical structure: no extra heap nodes are
/// allocated—linkage is stored inline within entity storage.
///
/// The list invokes signals (`on_push_*`, `on_unplug`) on nodes before
/// modifying links; these signals may veto operations by returning an error.
/// Many operations assume the node is not already attached to another list;
/// violating that assumption may lead to an inconsistent list (reported as
/// `ListBroken`).
pub struct EntityList<I: IEntityListNodeID> {
    /// Head sentinel node ID.
    pub head: I,
    /// Tail sentinel node ID.
    pub tail: I,
    /// Number of nodes in the list (excluding sentinels).
    pub len: Cell<usize>,
}
impl<I: IEntityListNodeID> EntityList<I> {
    /// create a new empty list with head and tail sentinels linked
    /// with each other.
    pub fn new(alloc: &IDBoundAlloc<I>) -> Self {
        let head = I::new_sentinel(alloc);
        let tail = I::new_sentinel(alloc);
        head.set_next_id(alloc, Some(tail));
        tail.set_prev_id(alloc, Some(head));
        Self {
            head,
            tail,
            len: Cell::new(0),
        }
    }

    /// get the number of nodes in the list.
    #[inline]
    pub fn len(&self) -> usize {
        self.len.get()
    }
    /// check if the list is empty.
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// try to get the front node ID, or None if the list is empty
    #[inline]
    pub fn get_front_id(&self, alloc: &IDBoundAlloc<I>) -> Option<I> {
        let next = self.head.get_next_id(alloc)?;
        if next == self.tail { None } else { Some(next) }
    }
    /// try to get the back node ID, or None if the list is empty
    #[inline]
    pub fn get_back_id(&self, alloc: &IDBoundAlloc<I>) -> Option<I> {
        let prev = self.tail.get_prev_id(alloc)?;
        if prev == self.head { None } else { Some(prev) }
    }

    /// Add a new node after an existing node linked to `this` list.
    ///
    /// If the current node is linked to another list, then the operation is undefined.
    /// You'll get a broken list without reporting an error.
    ///
    /// ### Signal invocation
    ///
    /// `node_add_next` will invoke `on_push_next` on `node` before modifying any links.
    /// If the signal returns an error, the operation is aborted without modifying any links.
    pub fn node_add_next(&self, node: I, new_node: I, alloc: &IDBoundAlloc<I>) -> EntityListRes<I> {
        if node == new_node {
            return Err(EntityListError::RepeatedNode);
        }
        if node == self.tail {
            return Err(EntityListError::NodeIsSentinel);
        }
        node.on_push_next(new_node, alloc)?;

        let node_obj = node.deref_alloc(alloc);
        let new_node_obj = new_node.deref_alloc(alloc);

        debug_assert!(
            I::obj_is_attached(node_obj),
            "Cannot add next to a detached node"
        );
        debug_assert!(
            !I::obj_is_attached(new_node_obj),
            "Cannot add a node that is already attached"
        );

        let Some(old_next) = I::obj_get_next_id(node_obj) else {
            return Err(EntityListError::ListBroken);
        };
        I::obj_set_next_id(node_obj, Some(new_node));
        I::obj_store_head(new_node_obj, EntityListNodeHead::from_id(node, old_next));
        old_next.set_prev_id(alloc, Some(new_node));
        self.len.set(self.len.get() + 1);
        Ok(())
    }

    /// Add a new node before an existing node linked to `this` list.
    ///
    /// If the current node is linked to another list, then the operation is undefined.
    /// You'll get a broken list without reporting an error.
    ///
    /// ### Signal invocation
    ///
    /// `node_add_prev` will invoke `on_push_prev` on `node` before modifying any links.
    /// If the signal returns an error, the operation is aborted without modifying any links.
    pub fn node_add_prev(&self, node: I, new_node: I, alloc: &IDBoundAlloc<I>) -> EntityListRes<I> {
        if node == new_node {
            return Err(EntityListError::RepeatedNode);
        }
        if node == self.head {
            return Err(EntityListError::NodeIsSentinel);
        }
        node.on_push_prev(new_node, alloc)?;

        let node_obj = node.deref_alloc(alloc);
        let new_node_obj = new_node.deref_alloc(alloc);

        debug_assert!(
            I::obj_is_attached(node_obj),
            "Cannot add prev to a detached node"
        );
        debug_assert!(
            !I::obj_is_attached(new_node_obj),
            "Cannot add a node that is already attached"
        );

        let Some(old_prev) = I::obj_get_prev_id(node_obj) else {
            return Err(EntityListError::ListBroken);
        };
        I::obj_set_prev_id(node_obj, Some(new_node));
        I::obj_store_head(new_node_obj, EntityListNodeHead::from_id(old_prev, node));
        old_prev.set_next_id(alloc, Some(new_node));
        self.len.set(self.len.get() + 1);
        Ok(())
    }

    /// Unplug a node from the list.
    ///
    /// ### Signal invocation
    ///
    /// `node_unplug` will invoke `on_unplug` on `node` before modifying any links.
    /// If the signal returns an error, the operation is aborted without modifying any links.
    pub fn node_unplug(&self, node: I, alloc: &IDBoundAlloc<I>) -> EntityListRes<I> {
        if node == self.head || node == self.tail {
            return Err(EntityListError::NodeIsSentinel);
        }
        node.on_unplug(alloc)?;

        let node_obj = node.deref_alloc(alloc);

        debug_assert!(
            I::obj_is_attached(node_obj),
            "Cannot unplug a detached node"
        );

        let Some(prev) = I::obj_get_prev_id(node_obj) else {
            return Err(EntityListError::ListBroken);
        };
        let Some(next) = I::obj_get_next_id(node_obj) else {
            return Err(EntityListError::ListBroken);
        };
        prev.set_next_id(alloc, Some(next));
        next.set_prev_id(alloc, Some(prev));
        I::obj_store_head(node_obj, EntityListNodeHead::none());
        self.len.set(self.len.get() - 1);
        Ok(())
    }

    /// Push a new node to the back of the list.
    #[inline]
    pub fn push_back_id(&self, new_node: I, alloc: &IDBoundAlloc<I>) -> EntityListRes<I> {
        self.node_add_prev(self.tail, new_node, alloc)
    }

    /// Push a new node to the front of the list.
    #[inline]
    pub fn push_front_id(&self, new_node: I, alloc: &IDBoundAlloc<I>) -> EntityListRes<I> {
        self.node_add_next(self.head, new_node, alloc)
    }

    /// Pop a node from the back of the list.
    pub fn pop_back(&self, alloc: &IDBoundAlloc<I>) -> EntityListRes<I, I> {
        let back_id = self.get_back_id(alloc).ok_or(EntityListError::EmptyList)?;
        self.node_unplug(back_id, alloc)?;
        Ok(back_id)
    }

    /// Pop a node from the front of the list.
    pub fn pop_front(&self, alloc: &IDBoundAlloc<I>) -> EntityListRes<I, I> {
        let front_id = self.get_front_id(alloc).ok_or(EntityListError::EmptyList)?;
        self.node_unplug(front_id, alloc)?;
        Ok(front_id)
    }

    /// Get a range covering all nodes in the list (excluding sentinels).
    pub fn get_range(&self, alloc: &IDBoundAlloc<I>) -> EntityListRange<I> {
        EntityListRange {
            start: self.head.get_next_id(alloc).unwrap(),
            end: Some(self.tail),
        }
    }
    /// Get a range covering all nodes in the list (including sentinels).
    pub fn get_range_with_sentinels(&self) -> EntityListRange<I> {
        EntityListRange {
            start: self.head,
            end: None,
        }
    }

    /// Create an iterator over all nodes in the list (excluding sentinels).
    pub fn iter<'alloc>(&self, alloc: &'alloc IDBoundAlloc<I>) -> EntityListIter<'alloc, I> {
        EntityListIter::new(self.get_range(alloc), alloc)
    }
    /// Create an iterator over all nodes in the list (including sentinels).
    pub fn iter_with_sentinels<'alloc>(
        &self,
        alloc: &'alloc IDBoundAlloc<I>,
    ) -> EntityListIter<'alloc, I> {
        EntityListIter::new(self.get_range_with_sentinels(), alloc)
    }

    /// Apply a function to all nodes in the list (including sentinels).
    pub fn forall_with_sentinel(
        &self,
        alloc: &IDBoundAlloc<I>,
        mut f: impl FnMut(I, &I::ObjectT) -> EntityListRes<I>,
    ) -> EntityListRes<I, ()> {
        let mut curr = self.head;
        loop {
            f(curr, curr.deref_alloc(alloc))?;
            if curr == self.tail {
                break;
            }
            let next = curr.get_next_id(alloc).ok_or(EntityListError::ListBroken)?;
            curr = next;
        }
        Ok(())
    }
}

/// 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: IEntityListNodeID> {
    alloc: &'alloc IDBoundAlloc<I>,
    curr: Option<I>,
    end: Option<I>,
}
impl<'alloc, I: IEntityListNodeID> 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: IEntityListNodeID> 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,
        }
    }
}

/// An entity pointer list node that supports ring lists.
pub trait IEntityRingListNodeID: IPoliciedID {
    /// Load the `EntityListNodeHead` from the entity object.
    fn obj_load_head(obj: &Self::ObjectT) -> EntityListNodeHead<Self>;
    /// Store the `EntityListNodeHead` into the entity object.
    /// 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;

    /// Create a new sentinel node ID allocated from the given allocator.
    fn new_sentinel(alloc: &IDBoundAlloc<Self>) -> Self {
        let obj = Self::new_sentinel_obj();
        let back = Self::BackID::allocate_from(alloc, obj);
        let id = Self::from_backend(back);
        let obj = id.deref_alloc(alloc);
        let head = EntityListNodeHead::from_id(id, id);
        Self::obj_store_head(obj, head);
        id
    }

    /// Signal: invoked when this node is being unplugged from a list.
    fn on_unplug(self, obj: &Self::ObjectT, alloc: &IDBoundAlloc<Self>) -> EntityListRes<Self>;

    /// Check if this node ID is a sentinel.
    fn is_sentinel(self, alloc: &IDBoundAlloc<Self>) -> bool {
        Self::obj_is_sentinel(self.deref_alloc(alloc))
    }
    /// 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))
    }

    /// Detach the given node from its current ring list.
    fn obj_detach(obj: &Self::ObjectT, alloc: &IDBoundAlloc<Self>) -> EntityListRes<Self> {
        if Self::obj_is_sentinel(obj) {
            return Err(EntityListError::NodeIsSentinel);
        }
        let (Some(prev), Some(next)) = Self::obj_load_head(obj).into_id() else {
            // detach() 在节点未连接时调用是合法的，直接返回 Ok(())
            return Ok(());
        };
        prev.set_next_id(alloc, Some(next));
        next.set_prev_id(alloc, Some(prev));
        Self::obj_store_head(obj, EntityListNodeHead::none());
        Ok(())
    }

    /// Detach this node from the ring list it is currently attached to.
    ///
    /// ### Signal invocation
    ///
    /// `detach` will invoke `on_unplug` on `self` before modifying any links.
    /// If the signal returns an error, the operation is aborted without modifying any links.
    fn detach(self, alloc: &IDBoundAlloc<Self>) -> EntityListRes<Self> {
        Self::obj_detach(self.deref_alloc(alloc), alloc)
    }
}
impl<I: IEntityRingListNodeID> NodeOpsPrivate<list_util::RingList> for I {
    fn obj_get_prev_id(obj: &Self::ObjectT) -> Option<Self> {
        I::obj_load_head(obj).get_prev()
    }
    fn obj_get_next_id(obj: &Self::ObjectT) -> Option<Self> {
        I::obj_load_head(obj).get_next()
    }
    fn obj_set_prev_id(obj: &Self::ObjectT, prev: Option<Self>) {
        I::obj_store_head(obj, I::obj_load_head(obj).prev(prev));
    }
    fn obj_set_next_id(obj: &Self::ObjectT, next: Option<Self>) {
        I::obj_store_head(obj, I::obj_load_head(obj).next(next));
    }
    fn obj_is_attached(obj: &Self::ObjectT) -> bool {
        let head = Self::obj_load_head(obj);
        let has_prev = head.prev.is_some();
        let has_next = head.next.is_some();
        if cfg!(debug_assertions) && (has_prev != has_next) {
            panic!("EntityRingListNodeID: obj_is_attached: inconsistent attachment state detected");
        }
        has_prev || has_next
    }
}

/// Ring list (circular) view over entities stored in an `EntityAlloc`.
///
/// The ring list is backed by a sentinel node that always exists; an empty
/// ring has the sentinel's `next`/`prev` pointing to itself. Nodes embed
/// `EntityListNodeHead` for linkage and can be detached/attached at O(1).
pub struct EntityRingList<I: IEntityRingListNodeID> {
    /// Sentinel node ID.
    pub sentinel: I,
}

impl<I: IEntityRingListNodeID> EntityRingList<I> {
    /// Create a new empty ring list with a sentinel node.
    pub fn new(alloc: &IDBoundAlloc<I>) -> Self {
        Self {
            sentinel: I::new_sentinel(alloc),
        }
    }
    /// Get the front node ID, or None if the list is empty. (Not sentinel)
    pub fn front_id(&self, alloc: &IDBoundAlloc<I>) -> Option<I> {
        let next = self.sentinel.get_next_id(alloc)?;
        if next == self.sentinel {
            None
        } else {
            Some(next)
        }
    }
    /// Get the back node ID, or None if the list is empty. (Not sentinel)
    pub fn back_id(&self, alloc: &IDBoundAlloc<I>) -> Option<I> {
        let prev = self.sentinel.get_prev_id(alloc)?;
        if prev == self.sentinel {
            None
        } else {
            Some(prev)
        }
    }
    /// Check if the ring list is empty.
    pub fn is_empty(&self, alloc: &IDBoundAlloc<I>) -> bool {
        self.front_id(alloc).is_none()
    }
    /// Check if the ring list has exactly one node (excluding sentinel).
    pub fn is_single(&self, alloc: &IDBoundAlloc<I>) -> bool {
        let sentinel = self.sentinel.deref_alloc(alloc);
        let head = I::obj_load_head(sentinel);
        let (Some(prev), Some(next)) = head.into_id() else {
            return false;
        };
        prev == next && prev != self.sentinel
    }
    /// Check if the ring list has multiple nodes (excluding sentinel).
    pub fn is_multiple(&self, alloc: &IDBoundAlloc<I>) -> bool {
        let sentinel = self.sentinel.deref_alloc(alloc);
        let head = I::obj_load_head(sentinel);
        let (Some(prev), Some(next)) = head.into_id() else {
            return false;
        };
        prev != next
    }

    /// traverse each node in the list, invoking `pred` on each node.
    ///
    /// ### panics
    ///
    /// If a broken ring list is detected, this function will panic.
    pub fn foreach(
        &self,
        alloc: &IDBoundAlloc<I>,
        mut pred: impl FnMut(I, &I::ObjectT) -> bool,
    ) -> bool {
        let mut curr = self.sentinel.get_next_id(alloc);
        let mut count = 0;
        while let Some(node_id) = curr {
            if node_id == self.sentinel {
                return true;
            }
            let node_obj = node_id.deref_alloc(alloc);
            if !pred(node_id, node_obj) {
                return false;
            }
            curr = node_id.get_next_id(alloc);
            count += 1;
        }
        panic!("Broken ring list detected after {count} nodes");
    }

    /// traverse each node in the list starting from the sentinel, invoking `pred` on each node.
    ///
    /// ### panics
    ///
    /// If a broken ring list is detected, this function will panic.
    pub fn forall_with_sentinel(
        &self,
        alloc: &IDBoundAlloc<I>,
        mut pred: impl FnMut(I, &I::ObjectT) -> bool,
    ) -> bool {
        let mut curr = Some(self.sentinel);
        let mut count = 0;
        while let Some(node_id) = curr {
            let node_obj = node_id.deref_alloc(alloc);
            if !pred(node_id, node_obj) {
                return false;
            }
            curr = node_id.get_next_id(alloc);
            count += 1;
            if curr == Some(self.sentinel) {
                return true;
            }
        }
        panic!("Broken ring list detected after {count} nodes");
    }

    /// Get the number of nodes in the ring list (excluding sentinel).
    ///
    /// NOTE: This function traverses the entire list to count nodes,
    /// so its time complexity is `O(n)`.
    pub fn len(&self, alloc: &IDBoundAlloc<I>) -> usize {
        let mut len = 0;
        self.foreach(alloc, |_, _| {
            len += 1;
            true
        });
        len
    }
    /// Check if the ring list contains the given node.
    pub fn contains(&self, node: I, alloc: &IDBoundAlloc<I>) -> bool {
        !self.foreach(alloc, |id, _| id != node)
    }

    /// Create a clone of this ring list view (shares the same sentinel).
    #[inline]
    pub fn clone_view(&self) -> Self {
        Self {
            sentinel: self.sentinel,
        }
    }

    /// Push a new node to the back of the ring list.
    pub fn push_back(&self, new_node: I, alloc: &IDBoundAlloc<I>) -> EntityListRes<I> {
        const ERRMSG: &str = "Broken ring detected during push_back";

        let sentinel_obj = self.sentinel.deref_alloc(alloc);
        let prev = I::obj_get_prev_id(sentinel_obj).expect(ERRMSG);
        if prev == new_node {
            return Err(EntityListError::RepeatedNode);
        }
        if new_node.is_attached(alloc) {
            return Err(EntityListError::ItemFalselyAttached(new_node));
        }
        // Link new_node between prev and sentinel
        let new_node_obj = new_node.deref_alloc(alloc);
        I::obj_store_head(
            new_node_obj,
            EntityListNodeHead::from_id(prev, self.sentinel),
        );
        // Update neighbors to point to new_node
        prev.set_next_id(alloc, Some(new_node));
        self.sentinel.set_prev_id(alloc, Some(new_node));
        Ok(())
    }

    /// Pop a node from the back of the ring list.
    pub fn pop_back(&self, alloc: &IDBoundAlloc<I>) -> EntityListRes<I, I> {
        let back_id = self.back_id(alloc).ok_or(EntityListError::EmptyList)?;
        back_id.detach(alloc)?;
        Ok(back_id)
    }
    /// Pop a node from the front of the ring list.
    pub fn pop_front(&self, alloc: &IDBoundAlloc<I>) -> EntityListRes<I, I> {
        let front_id = self.front_id(alloc).ok_or(EntityListError::EmptyList)?;
        front_id.detach(alloc)?;
        Ok(front_id)
    }

    /// Move all nodes from `self` into `other`, preserving order; invoke on_move for each moved node.
    pub fn move_all_to(
        &self,
        other: &Self,
        alloc: &IDBoundAlloc<I>,
        mut on_move: impl FnMut(I),
    ) -> EntityListRes<I> {
        if self.sentinel == other.sentinel {
            return Ok(());
        }
        loop {
            let node = match self.pop_front(alloc) {
                Ok(n) => n,
                Err(EntityListError::EmptyList) => break Ok(()),
                Err(e) => break Err(e),
            };
            other.push_back(node, alloc)?;
            on_move(node);
        }
    }

    /// Move nodes that satisfy `predicate` from `self` to `other`, preserving order.
    pub fn move_to_if(
        &self,
        other: &Self,
        alloc: &IDBoundAlloc<I>,
        mut pred: impl FnMut(I, &I::ObjectT) -> bool,
        mut on_move: impl FnMut(I),
    ) -> EntityListRes<I> {
        if self.sentinel == other.sentinel {
            return Err(EntityListError::RepeatedList);
        }
        loop {
            let Some(next) = self.sentinel.get_next_id(alloc) else {
                break;
            };
            if next == self.sentinel {
                return Ok(());
            }
            let next_obj = next.deref_alloc(alloc);
            if !pred(next, next_obj) {
                continue;
            }
            next.detach(alloc)?;
            other.push_back(next, alloc)?;
            on_move(next);
        }
        Err(EntityListError::ListBroken)
    }

    /// Clean up the ring list by removing all nodes; panic if a broken ring is detected.
    pub fn clean(&self, alloc: &IDBoundAlloc<I>) {
        let mut count = 0;
        let err = loop {
            match self.pop_front(alloc) {
                Ok(_) => count += 1,
                Err(EntityListError::EmptyList) => return,
                Err(e) => break e,
            };
        };
        panic!("Broken ring list detected after removing {count} nodes: {err}");
    }

    /// Create an iterator over all nodes in the ring list (excluding sentinel).
    pub fn iter<'a>(&self, alloc: &'a IDBoundAlloc<I>) -> EntityRingListIter<'a, I> {
        EntityRingListIter {
            alloc,
            curr: self
                .sentinel
                .get_next_id(alloc)
                .expect("Broken ring list detected in iter()"),
        }
    }
}

/// Iterator for `EntityRingList` that visits each node once starting after the sentinel.
///
/// The iterator yields `(I, &I::ObjectT)` and will stop when it encounters
/// the sentinel again. It assumes the ring is structurally sound; a broken
/// ring will cause a panic during iteration.
#[derive(Clone, Copy)]
pub struct EntityRingListIter<'alloc, I: IEntityRingListNodeID> {
    alloc: &'alloc IDBoundAlloc<I>,
    curr: I,
}
impl<'alloc, I: IEntityRingListNodeID> Iterator for EntityRingListIter<'alloc, I>
where
    I::ObjectT: 'alloc,
{
    type Item = (I, &'alloc I::ObjectT);

    fn next(&mut self) -> Option<Self::Item> {
        let curr = self.curr;
        if curr.is_sentinel(self.alloc) {
            return None;
        }
        let obj = curr.deref_alloc(self.alloc);
        let Some(next) = curr.get_next_id(self.alloc) else {
            panic!("Broken ring list detected during iteration");
        };
        self.curr = next;
        Some((curr, obj))
    }
}