mtb_entity_slab/container/

ring_list.rs

//! Ring list implementation for entity allocation.
//!
//! # 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.

use crate::{
    EntityListError, EntityListIter, EntityListNodeHead, EntityListRange, EntityListRes,
    IBasicEntityListID, IDBoundAlloc, container::list_base::NodeOps,
};

/// An entity pointer list node that supports ring lists.
pub trait IEntityRingListNodeID: IBasicEntityListID {
    /// 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.on_unplug(alloc)?;
        Self::obj_detach(self.deref_alloc(alloc), alloc)
    }
}

/// 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 {
        let sentinel = I::new_sentinel(alloc);
        I::obj_store_head(
            sentinel.deref_alloc(alloc),
            EntityListNodeHead {
                prev: Some(sentinel),
                next: Some(sentinel),
            },
        );
        Self { sentinel }
    }
    /// 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]
    #[deprecated = "Use 'get_range' instead of cloning the view"]
    pub fn clone_view(&self) -> Self {
        Self {
            sentinel: self.sentinel,
        }
    }

    /// Get the range covering all nodes in the ring list (excluding sentinel).
    pub fn get_range(&self, alloc: &IDBoundAlloc<I>) -> EntityListRange<I> {
        EntityListRange {
            start: self
                .sentinel
                .get_next_id(alloc)
                .expect("Broken ring list detected in get_range()"),
            end: Some(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);
        }
        let mut curr = self.sentinel;
        loop {
            let Some(next) = curr.get_next_id(alloc) else {
                break;
            };
            if next == self.sentinel {
                return Ok(());
            }
            let next_obj = next.deref_alloc(alloc);
            if !pred(next, next_obj) {
                curr = next;
                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>) -> EntityListIter<'a, I> {
        let next_node = self
            .sentinel
            .get_next_id(alloc)
            .expect("Broken ring list detected in iter()");
        EntityListIter {
            alloc,
            curr: Some(next_node),
            end: Some(self.sentinel),
        }
    }
}