mtb_entity_slab/container/

ptrlist.rs

use crate::{EntityAlloc, IEntityAllocID, PtrID, alloc::IEntityAllocatable};
use std::{
    cell::Cell,
    error::Error,
    fmt::{Debug, Display},
    iter::Rev,
};

pub struct EntityListHead<E: IEntityAllocatable>(pub Option<PtrID<E>>, pub Option<PtrID<E>>);

impl<E: IEntityAllocatable> Clone for EntityListHead<E> {
    #[inline]
    fn clone(&self) -> Self {
        Self(self.0, self.1)
    }
}
impl<E: IEntityAllocatable> Copy for EntityListHead<E> {}
impl<E: IEntityAllocatable> EntityListHead<E> {
    #[inline]
    pub fn none() -> Self {
        Self(None, None)
    }

    fn get_prev_ptr(&self) -> Option<PtrID<E>> {
        self.0
    }
    fn get_next_ptr(&self) -> Option<PtrID<E>> {
        self.1
    }
    pub fn get_prev_id(&self) -> Option<E::PtrID> {
        self.0.map(E::PtrID::from)
    }
    pub fn get_next_id(&self) -> Option<E::PtrID> {
        self.1.map(E::PtrID::from)
    }

    fn prev_ptr(self, prev: Option<PtrID<E>>) -> Self {
        Self(prev, self.1)
    }
    fn next_ptr(self, next: Option<PtrID<E>>) -> Self {
        Self(self.0, next)
    }
    pub fn next_id(self, next: Option<E::PtrID>) -> Self {
        Self(self.0, next.map(E::ptr_of_id))
    }
    pub fn prev_id(self, prev: Option<E::PtrID>) -> Self {
        Self(prev.map(E::ptr_of_id), self.1)
    }
}

mod list_util {
    pub(super) struct RingList;
    pub(super) struct LinkList;
}

trait RawListNodeOps<E: IEntityAllocatable, KindT> {
    fn get_prev_ptr(&self) -> Option<PtrID<E>>;
    fn get_next_ptr(&self) -> Option<PtrID<E>>;
    fn set_prev_ptr(&self, prev: Option<PtrID<E>>);
    fn set_next_ptr(&self, next: Option<PtrID<E>>);
}

pub enum EntityListError<E: IEntityAllocatable> {
    EmptyList,
    ListBroken,
    NodeIsSentinel,
    RepeatedNode,
    RepeatedList,
    SelfNotAttached(PtrID<E>),
    ItemFalselyAttached(PtrID<E>),
    ItemFalselyDetached(PtrID<E>),
}
impl<E: IEntityAllocatable> Debug for EntityListError<E> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        use EntityListError::*;
        match self {
            EmptyList => write!(f, "EmptyList"),
            ListBroken => write!(f, "ListBroken"),
            NodeIsSentinel => write!(f, "NodeIsSentinel"),
            RepeatedNode => write!(f, "RepeatedNode"),
            RepeatedList => write!(f, "RepeatedList"),
            SelfNotAttached(id) => {
                write!(f, "SelfNotAttached({id:?})")
            }
            ItemFalselyAttached(id) => {
                write!(f, "ItemFalselyAttached({id:?})")
            }
            ItemFalselyDetached(id) => {
                write!(f, "ItemFalselyDetached({id:?})")
            }
        }
    }
}
impl<E: IEntityAllocatable> Clone for EntityListError<E> {
    fn clone(&self) -> Self {
        use EntityListError::*;
        match self {
            EmptyList => EmptyList,
            ListBroken => ListBroken,
            NodeIsSentinel => NodeIsSentinel,
            RepeatedNode => RepeatedNode,
            RepeatedList => RepeatedList,
            SelfNotAttached(id) => SelfNotAttached(*id),
            ItemFalselyAttached(id) => ItemFalselyAttached(*id),
            ItemFalselyDetached(id) => ItemFalselyDetached(*id),
        }
    }
}
impl<E: IEntityAllocatable> Copy for EntityListError<E> {}
impl<E: IEntityAllocatable> Display for EntityListError<E> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{self:?}")
    }
}
impl<E: IEntityAllocatable> Error for EntityListError<E> {}

pub type PtrListRes<E, T = ()> = Result<T, EntityListError<E>>;

pub trait IEntityListNode: Sized + IEntityAllocatable {
    fn load_head(&self) -> EntityListHead<Self>;
    fn store_head(&self, head: EntityListHead<Self>);
    fn is_sentinel(&self) -> bool;
    fn new_sentinel() -> Self;
    fn on_push_next(
        curr: Self::PtrID,
        next: Self::PtrID,
        alloc: &EntityAlloc<Self>,
    ) -> PtrListRes<Self>;
    fn on_push_prev(
        curr: Self::PtrID,
        prev: Self::PtrID,
        alloc: &EntityAlloc<Self>,
    ) -> PtrListRes<Self>;
    fn on_unplug(curr: Self::PtrID, alloc: &EntityAlloc<Self>) -> PtrListRes<Self>;

    #[inline]
    fn get_prev_id(&self) -> Option<Self::PtrID> {
        self.load_head().get_prev_id()
    }
    #[inline]
    fn get_next_id(&self) -> Option<Self::PtrID> {
        self.load_head().get_next_id()
    }

    #[inline]
    fn set_prev_id(&self, prev: Option<Self::PtrID>) {
        self.store_head(self.load_head().prev_id(prev));
    }
    #[inline]
    fn set_next_id(&self, next: Option<Self::PtrID>) {
        self.store_head(self.load_head().next_id(next));
    }

    #[inline]
    fn is_attached(&self) -> bool {
        let EntityListHead(prev, next) = self.load_head();
        assert!(
            self.is_sentinel() || prev.is_some() == next.is_some(),
            "ptrlist node is corrupted"
        );
        prev.is_some() || next.is_some()
    }

    fn comes_before(
        curr: Self::PtrID,
        other: Self::PtrID,
        alloc: &EntityAlloc<Self>,
    ) -> PtrListRes<Self> {
        let mut node = Self::ptr_of_id(curr);
        while let Some(next) = node.deref(alloc).get_next_ptr() {
            if next == other.into() {
                return Ok(());
            }
            node = next;
        }
        Err(EntityListError::ListBroken)
    }
}
impl<E: IEntityListNode> RawListNodeOps<E, list_util::LinkList> for E {
    fn get_prev_ptr(&self) -> Option<PtrID<E>> {
        self.load_head().get_prev_ptr()
    }
    fn get_next_ptr(&self) -> Option<PtrID<E>> {
        self.load_head().get_next_ptr()
    }
    fn set_prev_ptr(&self, prev: Option<PtrID<E>>) {
        self.store_head(self.load_head().prev_ptr(prev))
    }
    fn set_next_ptr(&self, next: Option<PtrID<E>>) {
        self.store_head(self.load_head().next_ptr(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.
pub struct EntityListRange<E: IEntityListNode> {
    pub start: E::PtrID,
    pub end: Option<E::PtrID>,
}

impl<E: IEntityListNode> EntityListRange<E> {
    #[inline]
    pub fn is_empty(&self) -> bool {
        Some(self.start) == self.end
    }

    pub fn iter<'alloc>(&self, alloc: &'alloc EntityAlloc<E>) -> EntityListReadIter<'alloc, E> {
        EntityListReadIter {
            alloc,
            curr: Some(E::ptr_of_id(self.start)),
            end: self.end.map(E::ptr_of_id),
        }
    }
}

pub struct EntityList<E: IEntityListNode> {
    pub head: PtrID<E>,
    pub tail: PtrID<E>,
    pub len: Cell<usize>,
}

impl<E: IEntityListNode> EntityList<E> {
    /// create a new empty list with head and tail sentinels linked
    /// with each other.
    pub fn new(alloc: &EntityAlloc<E>) -> Self {
        let head = alloc.allocate(E::new_sentinel());
        let tail = alloc.allocate(E::new_sentinel());
        head.deref(alloc).set_next_ptr(Some(tail));
        tail.deref(alloc).set_prev_ptr(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.get() == 0
    }

    /// try to get the front node ID, or None if the list is empty
    #[inline]
    pub fn get_front_id(&self, alloc: &EntityAlloc<E>) -> Option<E::PtrID> {
        self.get_front_ptr(alloc).map(E::id_of_ptr)
    }
    /// try to get the back node ID, or None if the list is empty
    #[inline]
    pub fn get_back_id(&self, alloc: &EntityAlloc<E>) -> Option<E::PtrID> {
        self.get_back_ptr(alloc).map(E::id_of_ptr)
    }
    fn get_front_ptr(&self, alloc: &EntityAlloc<E>) -> Option<PtrID<E>> {
        let next = self.head.deref(alloc).get_next_ptr()?;
        if next == self.tail { None } else { Some(next) }
    }
    fn get_back_ptr(&self, alloc: &EntityAlloc<E>) -> Option<PtrID<E>> {
        let prev = self.tail.deref(alloc).get_prev_ptr()?;
        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.
    pub fn node_add_next(
        &self,
        node: E::PtrID,
        new_node: E::PtrID,
        alloc: &EntityAlloc<E>,
    ) -> PtrListRes<E> {
        if node == new_node {
            return Err(EntityListError::RepeatedNode);
        }
        let node_ptr = node.into();
        let new_node_ptr = new_node.into();
        // Disallow inserting after tail sentinel; the new node would be unreachable
        if node_ptr == self.tail {
            return Err(EntityListError::NodeIsSentinel);
        }
        E::on_push_next(node, new_node, alloc)?;

        let node_obj = node_ptr.deref(alloc);
        let new_node_obj = new_node_ptr.deref(alloc);
        assert!(node_obj.is_attached(), "Cannot add next to a detached node");
        assert!(
            !new_node_obj.is_attached(),
            "Cannot add a node that is already attached"
        );

        let orig_next = node_obj.get_next_ptr();
        new_node_obj.store_head(EntityListHead(Some(node_ptr), orig_next));
        node_obj.set_next_ptr(Some(new_node_ptr));
        if let Some(orig_next) = orig_next {
            orig_next.deref(alloc).set_prev_ptr(Some(new_node_ptr));
        }
        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.
    pub fn node_add_prev(
        &self,
        node: E::PtrID,
        new_node: E::PtrID,
        alloc: &EntityAlloc<E>,
    ) -> PtrListRes<E> {
        if node == new_node {
            return Err(EntityListError::RepeatedNode);
        }
        E::on_push_prev(node, new_node, alloc)?;
        // Disallow inserting before head sentinel; it would corrupt invariants
        let node_ptr = node.into();
        let new_node_ptr = new_node.into();
        if node_ptr == self.head {
            return Err(EntityListError::NodeIsSentinel);
        }
        let node_obj = node_ptr.deref(alloc);
        let new_node_obj = new_node_ptr.deref(alloc);

        assert!(node_obj.is_attached(), "Cannot add prev to a detached node");
        assert!(
            !new_node_obj.is_attached(),
            "Cannot add a node that is already attached"
        );
        let orig_prev = node_obj.get_prev_ptr();
        new_node_obj.store_head(EntityListHead(orig_prev, Some(node_ptr)));
        node_obj.set_prev_ptr(Some(new_node_ptr));
        if let Some(orig_prev) = orig_prev {
            orig_prev.deref(alloc).set_next_ptr(Some(new_node_ptr));
        }
        self.len.set(self.len.get() + 1);
        Ok(())
    }
    pub fn node_unplug(&self, node: E::PtrID, alloc: &EntityAlloc<E>) -> PtrListRes<E> {
        let node_ptr = node.into();
        if node_ptr == self.head || node_ptr == self.tail {
            return Err(EntityListError::NodeIsSentinel);
        }
        E::on_unplug(node, alloc)?;
        let node_obj = node_ptr.deref(alloc);
        assert!(node_obj.is_attached(), "Cannot unplug a detached node");

        let prev = node_obj.get_prev_ptr().ok_or(EntityListError::ListBroken)?;
        let next = node_obj.get_next_ptr().ok_or(EntityListError::ListBroken)?;
        prev.deref(alloc).set_next_ptr(Some(next));
        next.deref(alloc).set_prev_ptr(Some(prev));
        node_obj.store_head(EntityListHead(None, None));
        self.len.set(self.len.get() - 1);
        Ok(())
    }

    #[inline]
    pub fn push_back_id(&self, new_node: E::PtrID, alloc: &EntityAlloc<E>) -> PtrListRes<E> {
        self.node_add_prev(E::id_of_ptr(self.tail), new_node, alloc)
    }
    #[inline]
    pub fn push_front_id(&self, new_node: E::PtrID, alloc: &EntityAlloc<E>) -> PtrListRes<E> {
        self.node_add_next(E::id_of_ptr(self.head), new_node, alloc)
    }
    #[inline]
    pub fn push_back_val(&self, val: E, alloc: &EntityAlloc<E>) -> PtrListRes<E> {
        self.push_back_id(E::PtrID::from(alloc.allocate(val)), alloc)
    }
    #[inline]
    pub fn push_front_val(&self, val: E, alloc: &EntityAlloc<E>) -> PtrListRes<E> {
        self.push_front_id(E::PtrID::from(alloc.allocate(val)), alloc)
    }

    pub fn pop_back(&self, alloc: &EntityAlloc<E>) -> PtrListRes<E, E::PtrID> {
        let back_id = self.get_back_id(alloc).ok_or(EntityListError::EmptyList)?;
        self.node_unplug(back_id, alloc)?;
        Ok(back_id)
    }
    pub fn pop_front(&self, alloc: &EntityAlloc<E>) -> PtrListRes<E, E::PtrID> {
        let front_id = self.get_front_id(alloc).ok_or(EntityListError::EmptyList)?;
        self.node_unplug(front_id, alloc)?;
        Ok(front_id)
    }

    pub fn foreach(&self, alloc: &EntityAlloc<E>, mut f: impl FnMut(E::PtrID, &E) -> bool) -> bool {
        let mut node_opt = self.get_front_ptr(alloc);
        let mut count = 0;
        while let Some(node) = node_opt {
            let node_obj = node.deref(alloc);
            if !f(E::id_of_ptr(node), node_obj) {
                return false;
            }
            node_opt = node_obj.get_next_ptr();
            if node_opt == Some(self.tail) {
                assert_eq!(count, self.len(), "Broken list detected in foreach");
                return true;
            }
            count += 1;
        }
        unreachable!("Broken list {self:p} detected in foreach after {count} nodes");
    }
    pub fn forall_with_sentinel(
        &self,
        alloc: &EntityAlloc<E>,
        mut f: impl FnMut(E::PtrID, &E) -> bool,
    ) -> bool {
        let mut node_opt = Some(self.head);
        let mut count = 0;
        while let Some(node) = node_opt {
            let node_obj = node.deref(alloc);
            if !f(E::PtrID::from(node), node_obj) {
                return false;
            }
            node_opt = node_obj.get_next_ptr();
            count += 1;
        }
        assert_eq!(
            count,
            self.len() + 2,
            "Broken list {self:p} detected in forall_with_sentinel after {count} nodes"
        );
        true
    }

    pub fn get_range(&self, alloc: &EntityAlloc<E>) -> EntityListRange<E> {
        let Some(start) = self.head.deref(alloc).get_next_id() else {
            panic!("EntityList corrupted: head has no next");
        };
        EntityListRange {
            start,
            end: Some(E::id_of_ptr(self.tail)),
        }
    }
    /// Get the range including sentinels.
    pub fn get_range_with_sentinels(&self) -> EntityListRange<E> {
        EntityListRange {
            start: E::id_of_ptr(self.head),
            end: None,
        }
    }

    pub fn iter<'alloc>(
        &'alloc self,
        alloc: &'alloc EntityAlloc<E>,
    ) -> EntityListReadIter<'alloc, E> {
        EntityListReadIter {
            alloc,
            curr: self.head.deref(alloc).get_next_ptr(),
            end: Some(self.tail),
        }
    }
    pub fn iter_with_sentinels<'alloc>(
        &'alloc self,
        alloc: &'alloc EntityAlloc<E>,
    ) -> EntityListReadIter<'alloc, E> {
        EntityListReadIter {
            alloc,
            curr: Some(self.head),
            end: None,
        }
    }
}

pub struct EntityListReadIter<'alloc, E: IEntityListNode> {
    alloc: &'alloc EntityAlloc<E>,
    curr: Option<PtrID<E>>,
    end: Option<PtrID<E>>,
}
impl<'alloc, E: IEntityListNode> Iterator for EntityListReadIter<'alloc, E> {
    type Item = (E::PtrID, &'alloc E);

    fn next(&mut self) -> Option<Self::Item> {
        let curr_ptr = self.curr?;
        if Some(curr_ptr) == self.end {
            return None;
        }
        let curr_obj = curr_ptr.deref(self.alloc);
        self.curr = curr_obj.get_next_ptr();
        Some((E::id_of_ptr(curr_ptr), curr_obj))
    }
}

/// An entity pointer list node that supports ring lists.
pub trait IEntityRingListNode: Sized + IEntityAllocatable {
    fn load_head(&self) -> EntityListHead<Self>;
    fn store_head(&self, head: EntityListHead<Self>);
    fn is_sentinel(&self) -> bool;
    fn new_sentinel() -> Self;

    fn ring_list_node_dispose(&self, alloc: &EntityAlloc<Self>) {
        self.detach(alloc)
            .expect("Failed to detach node during disposal");
    }
    fn on_self_unplug(&self, self_id: Self::PtrID, alloc: &EntityAlloc<Self>);

    #[inline]
    fn get_prev_id(&self) -> Option<Self::PtrID> {
        self.load_head().get_prev_id()
    }
    #[doc(hidden)]
    fn get_prev_ptr(&self) -> Option<PtrID<Self>> {
        self.load_head().get_prev_ptr()
    }
    #[inline]
    fn get_next_id(&self) -> Option<Self::PtrID> {
        self.load_head().get_next_id()
    }
    #[doc(hidden)]
    fn get_next_ptr(&self) -> Option<PtrID<Self>> {
        self.load_head().get_next_ptr()
    }
    #[inline]
    fn set_prev_id(&self, prev: Option<Self::PtrID>) {
        self.store_head(self.load_head().prev_id(prev));
    }
    #[doc(hidden)]
    fn set_prev_ptr(&self, prev: Option<PtrID<Self>>) {
        self.store_head(self.load_head().prev_ptr(prev));
    }
    #[inline]
    fn set_next_id(&self, next: Option<Self::PtrID>) {
        self.store_head(self.load_head().next_id(next));
    }
    #[doc(hidden)]
    fn set_next_ptr(&self, next: Option<PtrID<Self>>) {
        self.store_head(self.load_head().next_ptr(next));
    }

    #[inline]
    fn is_attached(&self) -> bool {
        let EntityListHead(prev, next) = self.load_head();
        assert_eq!(prev.is_some(), next.is_some(), "ptrlist node is corrupted");
        prev.is_some() || next.is_some()
    }
    fn detach(&self, alloc: &EntityAlloc<Self>) -> PtrListRes<Self> {
        if self.is_sentinel() {
            return Err(EntityListError::NodeIsSentinel);
        }
        let EntityListHead(Some(prev), Some(next)) = self.load_head() else {
            // detach() 在节点未连接时调用是合法的，直接返回 Ok(())
            return Ok(());
        };
        prev.deref(alloc).set_next_ptr(Some(next));
        next.deref(alloc).set_prev_ptr(Some(prev));
        self.store_head(EntityListHead(None, None));
        Ok(())
    }
}
impl<E: IEntityRingListNode> RawListNodeOps<E, list_util::RingList> for E {
    fn get_prev_ptr(&self) -> Option<PtrID<E>> {
        self.load_head().get_prev_ptr()
    }
    fn get_next_ptr(&self) -> Option<PtrID<E>> {
        self.load_head().get_next_ptr()
    }
    fn set_prev_ptr(&self, prev: Option<PtrID<E>>) {
        self.store_head(self.load_head().prev_ptr(prev))
    }
    fn set_next_ptr(&self, next: Option<PtrID<E>>) {
        self.store_head(self.load_head().next_ptr(next))
    }
}

impl<E: IEntityRingListNode> PtrID<E> {
    pub fn detach(self, alloc: &EntityAlloc<E>) -> PtrListRes<E> {
        self.deref(alloc).detach(alloc)
    }
}

/// A doubly-linked ring list of entity pointers.
pub struct EntityRingList<E: IEntityRingListNode> {
    pub sentinel: E::PtrID,
}

impl<E: IEntityRingListNode> EntityRingList<E> {
    pub fn new(alloc: &EntityAlloc<E>) -> Self {
        let sentinel = alloc.allocate(E::new_sentinel());
        let head = Some(sentinel);
        sentinel.deref(alloc).store_head(EntityListHead(head, head));
        Self {
            sentinel: E::id_of_ptr(sentinel),
        }
    }
    pub fn len(&self, alloc: &EntityAlloc<E>) -> usize {
        let mut count = 0;
        self.foreach(alloc, |_, _| {
            count += 1;
            true
        });
        count
    }
    pub fn front_id(&self, alloc: &EntityAlloc<E>) -> Option<E::PtrID> {
        let sentinel = E::ptr_of_id(self.sentinel);
        let next = sentinel.deref(alloc).get_next_id()?;
        if next == self.sentinel {
            None
        } else {
            Some(next)
        }
    }
    pub fn back_id(&self, alloc: &EntityAlloc<E>) -> Option<E::PtrID> {
        let sentinel = E::ptr_of_id(self.sentinel);
        let prev = sentinel.deref(alloc).get_prev_id()?;
        if prev == self.sentinel {
            None
        } else {
            Some(prev)
        }
    }

    pub fn is_empty(&self, alloc: &EntityAlloc<E>) -> bool {
        const ERRMSG: &str = "ring list corrupted when checking is_empty";
        let sentinel = E::ptr_of_id(self.sentinel);
        let sentinel_obj = sentinel.deref(alloc);
        let next = sentinel_obj.get_next_ptr().expect(ERRMSG);
        next == sentinel
    }
    pub fn is_single(&self, alloc: &EntityAlloc<E>) -> bool {
        const ERRMSG: &str = "ring list corrupted when checking is_single";
        let sentinel = E::ptr_of_id(self.sentinel);
        let sentinel_obj = sentinel.deref(alloc);
        let next = sentinel_obj.get_next_ptr().expect(ERRMSG);
        let prev = sentinel_obj.get_prev_ptr().expect(ERRMSG);
        next == prev && next != sentinel
    }
    pub fn is_multiple(&self, alloc: &EntityAlloc<E>) -> bool {
        const ERRMSG: &str = "ring list corrupted when checking is_multiple";
        let sentinel = E::ptr_of_id(self.sentinel);
        let sentinel_obj = sentinel.deref(alloc);
        let next = sentinel_obj.get_next_ptr().expect(ERRMSG);
        let prev = sentinel_obj.get_prev_ptr().expect(ERRMSG);
        next != prev
    }
    pub fn foreach(
        &self,
        alloc: &EntityAlloc<E>,
        mut pred: impl FnMut(E::PtrID, &E) -> bool,
    ) -> bool {
        let sentinel = E::ptr_of_id(self.sentinel);
        let mut node_opt = sentinel.deref(alloc).get_next_ptr();
        let mut count = 0;
        while let Some(node_ptr) = node_opt {
            if node_ptr == sentinel {
                return true;
            }
            let node_obj = node_ptr.deref(alloc);
            if !pred(E::id_of_ptr(node_ptr), node_obj) {
                return false;
            }
            node_opt = node_obj.get_next_ptr();
            count += 1;
        }
        panic!("Broken ring list detected after {count} iterations");
    }
    pub fn forall_with_sentinel(
        &self,
        alloc: &EntityAlloc<E>,
        mut pred: impl FnMut(E::PtrID, &E) -> bool,
    ) -> bool {
        let mut node_opt = Some(self.sentinel);
        let mut count = 0;
        while let Some(node_id) = node_opt {
            let node_ptr = E::ptr_of_id(node_id);
            let node_obj = node_ptr.deref(alloc);
            if !pred(node_id, node_obj) {
                return false;
            }
            node_opt = node_obj.get_next_id();
            if node_opt == Some(self.sentinel) {
                return true;
            }
            count += 1;
        }
        panic!("Broken ring list detected after {count} iterations");
    }
    pub fn contains(&self, node: E::PtrID, alloc: &EntityAlloc<E>) -> bool {
        self.foreach(alloc, |id, _| id == node)
    }
    /// Clone a view over the same ring list (shares the sentinel)
    #[inline]
    pub fn clone_view(&self) -> Self {
        Self {
            sentinel: self.sentinel,
        }
    }
    pub fn iter<'alloc>(
        &'alloc self,
        alloc: &'alloc EntityAlloc<E>,
    ) -> EntityRingListReadIter<'alloc, E> {
        let sentinel = E::ptr_of_id(self.sentinel);
        let Some(curr) = sentinel.deref(alloc).get_next_ptr() else {
            panic!("ring list corrupted when creating iterator");
        };
        EntityRingListReadIter { alloc, curr }
    }
    pub fn back_iter<'alloc>(
        &'alloc self,
        alloc: &'alloc EntityAlloc<E>,
    ) -> Rev<EntityRingListReadIter<'alloc, E>> {
        let sentinel = E::ptr_of_id(self.sentinel);
        let Some(curr) = sentinel.deref(alloc).get_prev_ptr() else {
            panic!("ring list corrupted when creating back iterator");
        };
        EntityRingListReadIter { alloc, curr }.rev()
    }

    /// Push to back (before sentinel)
    pub fn push_back_id(&self, new_node: E::PtrID, alloc: &EntityAlloc<E>) -> PtrListRes<E> {
        const ERRMSG: &str = "Broken ring detected during push_back";

        // Insert immediately before sentinel: prev <-> new_node <-> sentinel
        let new_node = E::ptr_of_id(new_node);
        let sentinel = E::ptr_of_id(self.sentinel);
        let sentinel_obj = sentinel.deref(alloc);

        let prev = sentinel_obj.get_prev_ptr().expect(ERRMSG);
        // new_node must not already be attached
        assert!(!new_node.deref(alloc).is_attached());
        new_node
            .deref(alloc)
            .store_head(EntityListHead(Some(prev), Some(sentinel)));
        sentinel_obj.set_prev_ptr(Some(new_node));
        prev.deref(alloc).set_next_ptr(Some(new_node));
        Ok(())
    }

    // pop_front/pop_back are intentionally omitted for Remusys IR use-cases;
    // detach a known node explicitly when needed.

    /// Move all nodes from `self` into `other`, preserving order; invoke on_move for each moved node.
    pub fn move_all_to(
        &self,
        other: &EntityRingList<E>,
        alloc: &EntityAlloc<E>,
        mut on_move: impl FnMut(E::PtrID),
    ) -> PtrListRes<E> {
        if self.sentinel == other.sentinel {
            return Ok(());
        }
        let mut cur = self.front_id(alloc).map(E::ptr_of_id);
        while let Some(ptr) = cur {
            let next = ptr.deref(alloc).get_next_ptr();
            ptr.detach(alloc)?;

            let id = E::id_of_ptr(ptr);
            other.push_back_id(id, alloc)?;
            on_move(id);
            cur = match next {
                Some(n) if !n.deref(alloc).is_sentinel() => Some(n),
                _ => None,
            };
        }
        Ok(())
    }
    /// Move nodes that satisfy `predicate` from `self` to `other`, preserving order.
    pub fn move_to_if(
        &self,
        other: &EntityRingList<E>,
        alloc: &EntityAlloc<E>,
        mut predicate: impl FnMut(E::PtrID, &E) -> bool,
        mut on_move: impl FnMut(E::PtrID),
    ) -> PtrListRes<E> {
        if self.sentinel == other.sentinel {
            return Ok(());
        }
        let mut cur = self.front_id(alloc).map(E::ptr_of_id);
        while let Some(ptr) = cur {
            let next = ptr.deref(alloc).get_next_ptr();
            let id = E::PtrID::from(ptr);
            let obj = ptr.deref(alloc);
            if predicate(id, obj) {
                ptr.detach(alloc)?;
                other.push_back_id(id, alloc)?;
                on_move(id);
            }
            cur = match next {
                Some(n) if !n.deref(alloc).is_sentinel() => Some(n),
                _ => None,
            };
        }
        Ok(())
    }

    /// notifies all nodes in the ring list that the list is being dropped
    pub fn clean(&self, alloc: &EntityAlloc<E>) {
        let sentinel = E::ptr_of_id(self.sentinel);
        let mut node = sentinel.deref(alloc).get_next_ptr();
        let mut count = 0;
        while let Some(node_ptr) = node {
            if node_ptr == sentinel {
                let head = EntityListHead(Some(sentinel), Some(sentinel));
                sentinel.deref(alloc).store_head(head);
                return;
            }
            let next = node_ptr.deref(alloc).get_next_ptr();
            let node_obj = node_ptr.deref(alloc);
            node_obj.store_head(EntityListHead(None, None));
            node_obj.on_self_unplug(E::id_of_ptr(node_ptr), alloc);
            node = next;
            count += 1;
        }
        panic!("Broken ring list detected during clean after {count} iterations");
    }

    pub fn pop_back(&self, alloc: &EntityAlloc<E>) -> PtrListRes<E, E::PtrID> {
        let back_id = self.back_id(alloc).ok_or(EntityListError::EmptyList)?;
        let back_ptr = E::ptr_of_id(back_id);
        back_ptr.detach(alloc)?;
        back_ptr.deref(alloc).on_self_unplug(back_id, alloc);
        Ok(back_id)
    }
    pub fn pop_front(&self, alloc: &EntityAlloc<E>) -> PtrListRes<E, PtrID<E>> {
        let front_id = self.front_id(alloc).ok_or(EntityListError::EmptyList)?;
        let front_ptr = E::ptr_of_id(front_id);
        front_ptr.detach(alloc)?;
        front_ptr.deref(alloc).on_self_unplug(front_id, alloc);
        Ok(front_ptr)
    }
}

pub struct EntityRingListReadIter<'alloc, E: IEntityRingListNode> {
    alloc: &'alloc EntityAlloc<E>,
    curr: PtrID<E>,
}

impl<'alloc, E: IEntityRingListNode> Iterator for EntityRingListReadIter<'alloc, E> {
    type Item = (E::PtrID, &'alloc E);

    fn next(&mut self) -> Option<Self::Item> {
        let curr_ptr = self.curr;
        let curr_obj = curr_ptr.deref(self.alloc);
        if curr_obj.is_sentinel() {
            return None;
        }
        let Some(next_ptr) = curr_obj.get_next_ptr() else {
            panic!("Broken ring list detected during iteration");
        };
        if next_ptr == curr_ptr {
            return None;
        }
        self.curr = next_ptr;
        Some((E::id_of_ptr(curr_ptr), curr_obj))
    }
}
impl<'alloc, E: IEntityRingListNode> DoubleEndedIterator for EntityRingListReadIter<'alloc, E> {
    fn next_back(&mut self) -> Option<Self::Item> {
        let curr_ptr = self.curr;
        let curr_obj = curr_ptr.deref(self.alloc);
        if curr_obj.is_sentinel() {
            return None;
        }
        let Some(prev_ptr) = curr_obj.get_prev_ptr() else {
            panic!("Broken ring list detected during back iteration");
        };
        if prev_ptr == curr_ptr {
            return None;
        }
        self.curr = prev_ptr;
        Some((E::id_of_ptr(curr_ptr), curr_obj))
    }
}