Struct OrderCachedList 

pub struct OrderCachedList<I: IOrderCachedListNodeID> {
    pub head: I,
    pub tail: I,
    /* private fields */
}

Order-cached doubly-linked list.

Fields

head: I

Head sentinel node ID. Order is always 0 and do not represent a valid item.

tail: I

Tail sentinel node ID. Order is always usize::MAX and does not represent a valid item.

Implementations

impl<I: IOrderCachedListNodeID> OrderCachedList<I>

pub const HEAD_ORDER: usize = 0

Order value of the head sentinel.

pub const TAIL_ORDER: usize = usize::MAX

Order value of the tail sentinel.

pub const MAX_LEN: usize = Self::LEN_MASK

Maximum length supported by the list: 2^(usize::BITS - 1) - 1.

pub fn new(alloc: &IDBoundAlloc<I>) -> Self

Create a new empty order-cached list with given head and tail sentinels.

pub fn len(&self) -> usize

Get the length of the list.

pub fn is_empty(&self) -> bool

Check if the list is empty.

pub fn get_front_id(&self, alloc: &IDBoundAlloc<I>) -> Option<I>

try to get the front node ID, or None if the list is empty

pub fn get_back_id(&self, alloc: &IDBoundAlloc<I>) -> Option<I>

try to get the back node ID, or None if the list is empty

pub fn order_valid(&self) -> bool

Check whether the order cache is valid.

pub fn invalidate_order(&self)

Invalidate the order cache.

pub fn rebuild_order(&self, alloc: &IDBoundAlloc<I>)

Rebuild the order cache regardless of its current validity.

pub fn get_node_order(&self, alloc: &IDBoundAlloc<I>, node: I) -> usize

Get the order of a node. If the order cache is invalid, it will be rebuilt first.

pub fn node_comes_before(&self, alloc: &IDBoundAlloc<I>, a: I, b: I) -> bool

Check whether node a comes before node b in the list.

pub fn node_comes_after(&self, alloc: &IDBoundAlloc<I>, a: I, b: I) -> bool

Check whether node a comes after node b in the list.

pub fn get_range(&self, alloc: &IDBoundAlloc<I>) -> EntityListRange<I>

Get the range covering all nodes in the order-cached list (excluding sentinels).

pub fn get_range_with_sentinels(&self) -> EntityListRange<I>

Get the range covering all nodes including sentinels.

pub fn debug<'a>( &self, alloc: &'a IDBoundAlloc<I>, ) -> EntityListRangeDebug<'a, I>

Create a debug view for this range.

pub fn iter<'a>(&self, alloc: &'a IDBoundAlloc<I>) -> EntityListIter<'a, I>

Create an iterator over the nodes in the order-cached list.

pub fn iter_with_sentinels<'a>( &self, alloc: &'a IDBoundAlloc<I>, ) -> EntityListIter<'a, I>

Create an iterator over all nodes including sentinels.

pub fn forall_with_sentinel( &self, alloc: &IDBoundAlloc<I>, f: impl FnMut(I, &I::ObjectT) -> EntityListRes<I>, ) -> EntityListRes<I, ()>

Apply a function to all nodes in the list (including sentinels).

pub fn node_unplug(&self, node: I, alloc: &IDBoundAlloc<I>) -> EntityListRes<I>

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.

Order maintaining

If the order representation is Exact, the order cache will be invalidated unless the unplugged node is the last node in the list. Otherwise, the order cache validity is left unchanged.

pub fn node_add_next( &self, node: I, new_node: I, alloc: &IDBoundAlloc<I>, ) -> EntityListRes<I>

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.

Order maintaining

The order cache will be invalidated unless the new node is added at the end of the list.

pub fn node_add_prev( &self, node: I, new_node: I, alloc: &IDBoundAlloc<I>, ) -> EntityListRes<I>

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.

Order maintaining

The order cache will be invalidated unless the node is the tail sentinel.

pub fn push_back_id( &self, new_node: I, alloc: &IDBoundAlloc<I>, ) -> EntityListRes<I>

Push a new node to the back of the list. Will not invalidate order cache if possible.

pub fn push_front_id( &self, new_node: I, alloc: &IDBoundAlloc<I>, ) -> EntityListRes<I>

Push a new node to the front of the list. Will invalidate order cache.

pub fn pop_back(&self, alloc: &IDBoundAlloc<I>) -> EntityListRes<I, I>

Pop a node from the back of the list. Will not invalidate order cache if possible.

pub fn pop_front(&self, alloc: &IDBoundAlloc<I>) -> EntityListRes<I, I>

Pop a node from the front of the list. Will invalidate order cache if repr is Exact.