mtb_entity_slab/container/

entity_list.rs

//! Doubly-linked list over entities stored in an entity allocator.
//!
//! This module provides doubly linked list structure that operate on entities
//! managed by `EntityAlloc`. The list support various operations such as insertion,
//! removal, and traversal.
//!
//! The list is generic over entity ID types that implement the
//! `IEntityListNodeID` trait, allowing flexible integration with different
//! entity types (PtrID, IndexedID or anything defined by yourself).
//!
//! The list 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.

use std::cell::Cell;

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

/// 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: IBasicEntityListID {
    /// 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)
        }
    }
}

/// 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);
        };
        NodeOps::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(())
    }
}