mtb_entity_slab/container/
ptrlist.rs

1use crate::{EntityAlloc, IPolicyPtrID};
2use std::cell::Cell;
3
4#[derive(Debug, Clone, Copy, PartialEq, Eq)]
5pub struct EntityListNodeHead<I: IPolicyPtrID> {
6    pub prev: Option<I>,
7    pub next: Option<I>,
8}
9impl<I: IPolicyPtrID> EntityListNodeHead<I> {
10    pub fn none() -> Self {
11        Self {
12            prev: None,
13            next: None,
14        }
15    }
16    pub fn new_full(prev: Option<I>, next: Option<I>) -> Self {
17        Self { prev, next }
18    }
19    pub fn from_id(prev: I, next: I) -> Self {
20        Self {
21            prev: Some(prev),
22            next: Some(next),
23        }
24    }
25    pub fn into_id(self) -> (Option<I>, Option<I>) {
26        (self.prev, self.next)
27    }
28
29    pub fn get_prev(&self) -> Option<I> {
30        self.prev
31    }
32    pub fn get_next(&self) -> Option<I> {
33        self.next
34    }
35
36    fn prev(mut self, prev: Option<I>) -> Self {
37        self.prev = prev;
38        self
39    }
40    fn next(mut self, next: Option<I>) -> Self {
41        self.next = next;
42        self
43    }
44}
45
46mod list_util {
47    pub(super) struct RingList;
48    pub(super) struct LinkList;
49}
50trait NodeOpsPrivate<KindT>: IPolicyPtrID {
51    fn obj_get_prev_id(obj: &Self::ObjectT) -> Option<Self>;
52    fn obj_get_next_id(obj: &Self::ObjectT) -> Option<Self>;
53
54    fn obj_set_prev_id(obj: &Self::ObjectT, prev: Option<Self>);
55    fn obj_set_next_id(obj: &Self::ObjectT, next: Option<Self>);
56    fn obj_is_attached(obj: &Self::ObjectT) -> bool;
57
58    fn set_prev_id(self, alloc: &EntityAlloc<Self::ObjectT, Self::PolicyT>, prev: Option<Self>) {
59        Self::obj_set_prev_id(self.deref_alloc(alloc), prev);
60    }
61    fn set_next_id(self, alloc: &EntityAlloc<Self::ObjectT, Self::PolicyT>, next: Option<Self>) {
62        Self::obj_set_next_id(self.deref_alloc(alloc), next);
63    }
64}
65
66#[derive(Debug, Clone, Copy, PartialEq, Eq)]
67pub enum EntityListError<I: IPolicyPtrID> {
68    EmptyList,
69    ListBroken,
70    NodeIsSentinel,
71    RepeatedNode,
72    RepeatedList,
73    SelfNotAttached(I),
74    ItemFalselyAttached(I),
75    ItemFalselyDetached(I),
76}
77impl<I: IPolicyPtrID> std::fmt::Display for EntityListError<I> {
78    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
79        std::fmt::Debug::fmt(&self, f)
80    }
81}
82impl<I: IPolicyPtrID> std::error::Error for EntityListError<I> {}
83
84pub type EntityListRes<I, T = ()> = Result<T, EntityListError<I>>;
85
86pub trait IEntityListNodeID: IPolicyPtrID {
87    fn obj_load_head(obj: &Self::ObjectT) -> EntityListNodeHead<Self>;
88    /// NOTE: Entity Lists are internally mutable
89    fn obj_store_head(obj: &Self::ObjectT, head: EntityListNodeHead<Self>);
90    fn obj_is_sentinel(obj: &Self::ObjectT) -> bool;
91    fn new_sentinel_obj() -> Self::ObjectT;
92
93    #[inline]
94    fn is_sentinel(self, alloc: &EntityAlloc<Self::ObjectT, Self::PolicyT>) -> bool {
95        Self::obj_is_sentinel(self.deref_alloc(alloc))
96    }
97    fn new_sentinel(alloc: &EntityAlloc<Self::ObjectT, Self::PolicyT>) -> Self {
98        let obj = Self::new_sentinel_obj();
99        Self::from_raw_ptrid(alloc.as_ref().allocate(obj))
100    }
101
102    fn on_push_prev(
103        self,
104        prev: Self,
105        alloc: &EntityAlloc<Self::ObjectT, Self::PolicyT>,
106    ) -> EntityListRes<Self>;
107    fn on_push_next(
108        self,
109        next: Self,
110        alloc: &EntityAlloc<Self::ObjectT, Self::PolicyT>,
111    ) -> EntityListRes<Self>;
112    fn on_unplug(self, alloc: &EntityAlloc<Self::ObjectT, Self::PolicyT>) -> EntityListRes<Self>;
113
114    fn get_prev_id(self, alloc: &EntityAlloc<Self::ObjectT, Self::PolicyT>) -> Option<Self> {
115        Self::obj_get_prev_id(self.deref_alloc(alloc))
116    }
117    fn get_next_id(self, alloc: &EntityAlloc<Self::ObjectT, Self::PolicyT>) -> Option<Self> {
118        Self::obj_get_next_id(self.deref_alloc(alloc))
119    }
120    fn is_attached(self, alloc: &EntityAlloc<Self::ObjectT, Self::PolicyT>) -> bool {
121        Self::obj_is_attached(self.deref_alloc(alloc))
122    }
123
124    fn comes_before(
125        self,
126        latter: Self,
127        alloc: &EntityAlloc<Self::ObjectT, Self::PolicyT>,
128    ) -> EntityListRes<Self, bool> {
129        let mut node = self;
130        while let Some(next) = node.get_next_id(alloc) {
131            if next == latter {
132                return Ok(true);
133            }
134            node = next;
135        }
136        if node.is_sentinel(alloc) {
137            Ok(false)
138        } else {
139            Err(EntityListError::ListBroken)
140        }
141    }
142}
143impl<I: IEntityListNodeID> NodeOpsPrivate<list_util::LinkList> for I {
144    fn obj_get_prev_id(obj: &Self::ObjectT) -> Option<Self> {
145        I::obj_load_head(obj).get_prev()
146    }
147    fn obj_get_next_id(obj: &Self::ObjectT) -> Option<Self> {
148        I::obj_load_head(obj).get_next()
149    }
150    fn obj_set_prev_id(obj: &Self::ObjectT, prev: Option<Self>) {
151        Self::obj_store_head(obj, Self::obj_load_head(obj).prev(prev));
152    }
153    fn obj_set_next_id(obj: &Self::ObjectT, next: Option<Self>) {
154        Self::obj_store_head(obj, Self::obj_load_head(obj).next(next));
155    }
156    fn obj_is_attached(obj: &Self::ObjectT) -> bool {
157        let head = Self::obj_load_head(obj);
158        let is_sentinel = Self::obj_is_sentinel(obj);
159        let has_prev = head.prev.is_some();
160        let has_next = head.next.is_some();
161        if cfg!(debug_assertions) && !is_sentinel && has_prev != has_next {
162            panic!("EntityListNodeID: obj_is_attached: inconsistent attachment state detected");
163        }
164        has_prev || has_next
165    }
166}
167
168/// A partial-close range of an entity pointer list representing `[start, end)`.
169///
170/// - if `end is None`, the range is open-ended.
171/// - the `start` is non-nullable, meaning any range must have a valid start.
172#[derive(Debug, Clone, Copy, PartialEq, Eq)]
173pub struct EntityListRange<I: IEntityListNodeID> {
174    pub start: I,
175    pub end: Option<I>,
176}
177impl<I: IEntityListNodeID> EntityListRange<I> {
178    pub fn is_empty(&self) -> bool {
179        Some(self.start) == self.end
180    }
181}
182
183pub struct EntityList<I: IEntityListNodeID> {
184    pub head: I,
185    pub tail: I,
186    pub len: Cell<usize>,
187}
188impl<I: IEntityListNodeID> EntityList<I> {
189    /// create a new empty list with head and tail sentinels linked
190    /// with each other.
191    pub fn new(alloc: &EntityAlloc<I::ObjectT, I::PolicyT>) -> Self {
192        let head = I::new_sentinel(alloc);
193        let tail = I::new_sentinel(alloc);
194        head.set_next_id(alloc, Some(tail));
195        tail.set_prev_id(alloc, Some(head));
196        Self {
197            head,
198            tail,
199            len: Cell::new(0),
200        }
201    }
202
203    /// get the number of nodes in the list.
204    #[inline]
205    pub fn len(&self) -> usize {
206        self.len.get()
207    }
208    /// check if the list is empty.
209    #[inline]
210    pub fn is_empty(&self) -> bool {
211        self.len() == 0
212    }
213
214    /// try to get the front node ID, or None if the list is empty
215    #[inline]
216    pub fn get_front_id(&self, alloc: &EntityAlloc<I::ObjectT, I::PolicyT>) -> Option<I> {
217        let next = self.head.get_next_id(alloc)?;
218        if next == self.tail { None } else { Some(next) }
219    }
220    /// try to get the back node ID, or None if the list is empty
221    #[inline]
222    pub fn get_back_id(&self, alloc: &EntityAlloc<I::ObjectT, I::PolicyT>) -> Option<I> {
223        let prev = self.tail.get_prev_id(alloc)?;
224        if prev == self.head { None } else { Some(prev) }
225    }
226
227    /// Add a new node after an existing node linked to `this` list.
228    ///
229    /// If the current node is linked to another list, then the operation is undefined.
230    /// You'll get a broken list without reporting an error.
231    ///
232    /// ### Signal invocation
233    ///
234    /// `node_add_next` will invoke `on_push_next` on `node` before modifying any links.
235    /// If the signal returns an error, the operation is aborted without modifying any links.
236    pub fn node_add_next(
237        &self,
238        node: I,
239        new_node: I,
240        alloc: &EntityAlloc<I::ObjectT, I::PolicyT>,
241    ) -> EntityListRes<I> {
242        if node == new_node {
243            return Err(EntityListError::RepeatedNode);
244        }
245        if node == self.tail {
246            return Err(EntityListError::NodeIsSentinel);
247        }
248        node.on_push_next(new_node, alloc)?;
249
250        let node_obj = node.deref_alloc(alloc);
251        let new_node_obj = new_node.deref_alloc(alloc);
252
253        debug_assert!(
254            I::obj_is_attached(node_obj),
255            "Cannot add next to a detached node"
256        );
257        debug_assert!(
258            !I::obj_is_attached(new_node_obj),
259            "Cannot add a node that is already attached"
260        );
261
262        let Some(old_next) = I::obj_get_next_id(node_obj) else {
263            return Err(EntityListError::ListBroken);
264        };
265        I::obj_set_next_id(node_obj, Some(new_node));
266        I::obj_store_head(new_node_obj, EntityListNodeHead::from_id(node, old_next));
267        old_next.set_prev_id(alloc, Some(new_node));
268        self.len.set(self.len.get() + 1);
269        Ok(())
270    }
271
272    /// Add a new node before an existing node linked to `this` list.
273    ///
274    /// If the current node is linked to another list, then the operation is undefined.
275    /// You'll get a broken list without reporting an error.
276    ///
277    /// ### Signal invocation
278    ///
279    /// `node_add_prev` will invoke `on_push_prev` on `node` before modifying any links.
280    /// If the signal returns an error, the operation is aborted without modifying any links.
281    pub fn node_add_prev(
282        &self,
283        node: I,
284        new_node: I,
285        alloc: &EntityAlloc<I::ObjectT, I::PolicyT>,
286    ) -> EntityListRes<I> {
287        if node == new_node {
288            return Err(EntityListError::RepeatedNode);
289        }
290        if node == self.head {
291            return Err(EntityListError::NodeIsSentinel);
292        }
293        node.on_push_prev(new_node, alloc)?;
294
295        let node_obj = node.deref_alloc(alloc);
296        let new_node_obj = new_node.deref_alloc(alloc);
297
298        debug_assert!(
299            I::obj_is_attached(node_obj),
300            "Cannot add prev to a detached node"
301        );
302        debug_assert!(
303            !I::obj_is_attached(new_node_obj),
304            "Cannot add a node that is already attached"
305        );
306
307        let Some(old_prev) = I::obj_get_prev_id(node_obj) else {
308            return Err(EntityListError::ListBroken);
309        };
310        I::obj_set_prev_id(node_obj, Some(new_node));
311        I::obj_store_head(new_node_obj, EntityListNodeHead::from_id(old_prev, node));
312        old_prev.set_next_id(alloc, Some(new_node));
313        self.len.set(self.len.get() + 1);
314        Ok(())
315    }
316
317    /// Unplug a node from the list.
318    ///
319    /// ### Signal invocation
320    ///
321    /// `node_unplug` will invoke `on_unplug` on `node` before modifying any links.
322    /// If the signal returns an error, the operation is aborted without modifying any links.
323    pub fn node_unplug(
324        &self,
325        node: I,
326        alloc: &EntityAlloc<I::ObjectT, I::PolicyT>,
327    ) -> EntityListRes<I> {
328        if node == self.head || node == self.tail {
329            return Err(EntityListError::NodeIsSentinel);
330        }
331        node.on_unplug(alloc)?;
332
333        let node_obj = node.deref_alloc(alloc);
334
335        debug_assert!(
336            I::obj_is_attached(node_obj),
337            "Cannot unplug a detached node"
338        );
339
340        let Some(prev) = I::obj_get_prev_id(node_obj) else {
341            return Err(EntityListError::ListBroken);
342        };
343        let Some(next) = I::obj_get_next_id(node_obj) else {
344            return Err(EntityListError::ListBroken);
345        };
346        prev.set_next_id(alloc, Some(next));
347        next.set_prev_id(alloc, Some(prev));
348        I::obj_store_head(node_obj, EntityListNodeHead::none());
349        self.len.set(self.len.get() - 1);
350        Ok(())
351    }
352
353    /// Push a new node to the back of the list.
354    #[inline]
355    pub fn push_back_id(
356        &self,
357        new_node: I,
358        alloc: &EntityAlloc<I::ObjectT, I::PolicyT>,
359    ) -> EntityListRes<I> {
360        self.node_add_prev(self.tail, new_node, alloc)
361    }
362
363    /// Push a new node to the front of the list.
364    #[inline]
365    pub fn push_front_id(
366        &self,
367        new_node: I,
368        alloc: &EntityAlloc<I::ObjectT, I::PolicyT>,
369    ) -> EntityListRes<I> {
370        self.node_add_next(self.head, new_node, alloc)
371    }
372
373    /// Pop a node from the back of the list.
374    pub fn pop_back(&self, alloc: &EntityAlloc<I::ObjectT, I::PolicyT>) -> EntityListRes<I, I> {
375        let back_id = self.get_back_id(alloc).ok_or(EntityListError::EmptyList)?;
376        self.node_unplug(back_id, alloc)?;
377        Ok(back_id)
378    }
379
380    /// Pop a node from the front of the list.
381    pub fn pop_front(&self, alloc: &EntityAlloc<I::ObjectT, I::PolicyT>) -> EntityListRes<I, I> {
382        let front_id = self.get_front_id(alloc).ok_or(EntityListError::EmptyList)?;
383        self.node_unplug(front_id, alloc)?;
384        Ok(front_id)
385    }
386
387    pub fn get_range(&self, alloc: &EntityAlloc<I::ObjectT, I::PolicyT>) -> EntityListRange<I> {
388        EntityListRange {
389            start: self.head.get_next_id(alloc).unwrap(),
390            end: Some(self.tail),
391        }
392    }
393    pub fn get_range_with_sentinels(&self) -> EntityListRange<I> {
394        EntityListRange {
395            start: self.head,
396            end: None,
397        }
398    }
399
400    pub fn iter<'alloc>(
401        &self,
402        alloc: &'alloc EntityAlloc<I::ObjectT, I::PolicyT>,
403    ) -> EntityListIter<'alloc, I> {
404        EntityListIter::new(self.get_range(alloc), alloc)
405    }
406    pub fn iter_with_sentinels<'alloc>(
407        &self,
408        alloc: &'alloc EntityAlloc<I::ObjectT, I::PolicyT>,
409    ) -> EntityListIter<'alloc, I> {
410        EntityListIter::new(self.get_range_with_sentinels(), alloc)
411    }
412
413    pub fn forall_with_sentinel(
414        &self,
415        alloc: &EntityAlloc<I::ObjectT, I::PolicyT>,
416        mut f: impl FnMut(I, &I::ObjectT) -> EntityListRes<I>,
417    ) -> EntityListRes<I, ()> {
418        let mut curr = self.head;
419        loop {
420            f(curr, curr.deref_alloc(alloc))?;
421            if curr == self.tail {
422                break;
423            }
424            let next = curr.get_next_id(alloc).ok_or(EntityListError::ListBroken)?;
425            curr = next;
426        }
427        Ok(())
428    }
429}
430
431pub struct EntityListIter<'alloc, I: IEntityListNodeID> {
432    alloc: &'alloc EntityAlloc<I::ObjectT, I::PolicyT>,
433    curr: Option<I>,
434    end: Option<I>,
435}
436impl<'alloc, I: IEntityListNodeID> Iterator for EntityListIter<'alloc, I>
437where
438    I::ObjectT: 'alloc,
439{
440    type Item = (I, &'alloc I::ObjectT);
441
442    fn next(&mut self) -> Option<Self::Item> {
443        let curr = self.curr?;
444        if Some(curr) == self.end {
445            return None;
446        }
447        let obj = curr.deref_alloc(self.alloc);
448        self.curr = curr.get_next_id(self.alloc);
449        Some((curr, obj))
450    }
451}
452impl<'alloc, I: IEntityListNodeID> EntityListIter<'alloc, I> {
453    pub fn new(
454        range: EntityListRange<I>,
455        alloc: &'alloc EntityAlloc<I::ObjectT, I::PolicyT>,
456    ) -> Self {
457        Self {
458            alloc,
459            curr: Some(range.start),
460            end: range.end,
461        }
462    }
463}
464
465/// An entity pointer list node that supports ring lists.
466pub trait IEntityRingListNodeID: IPolicyPtrID {
467    fn obj_load_head(obj: &Self::ObjectT) -> EntityListNodeHead<Self>;
468    /// NOTE: Entity Lists are internally mutable
469    fn obj_store_head(obj: &Self::ObjectT, head: EntityListNodeHead<Self>);
470    fn obj_is_sentinel(obj: &Self::ObjectT) -> bool;
471    fn new_sentinel_obj() -> Self::ObjectT;
472
473    fn new_sentinel(alloc: &EntityAlloc<Self::ObjectT, Self::PolicyT>) -> Self {
474        let obj = Self::new_sentinel_obj();
475        let id = Self::from_raw_ptrid(alloc.as_ref().allocate(obj));
476        let obj = id.deref_alloc(alloc);
477        let head = EntityListNodeHead::from_id(id, id);
478        Self::obj_store_head(obj, head);
479        id
480    }
481
482    /// Signal: invoked when this node is being unplugged from a list.
483    fn on_unplug(
484        self,
485        obj: &Self::ObjectT,
486        alloc: &EntityAlloc<Self::ObjectT, Self::PolicyT>,
487    ) -> EntityListRes<Self>;
488
489    fn is_sentinel(self, alloc: &EntityAlloc<Self::ObjectT, Self::PolicyT>) -> bool {
490        Self::obj_is_sentinel(self.deref_alloc(alloc))
491    }
492    fn get_prev_id(self, alloc: &EntityAlloc<Self::ObjectT, Self::PolicyT>) -> Option<Self> {
493        Self::obj_get_prev_id(self.deref_alloc(alloc))
494    }
495    fn get_next_id(self, alloc: &EntityAlloc<Self::ObjectT, Self::PolicyT>) -> Option<Self> {
496        Self::obj_get_next_id(self.deref_alloc(alloc))
497    }
498    fn is_attached(self, alloc: &EntityAlloc<Self::ObjectT, Self::PolicyT>) -> bool {
499        Self::obj_is_attached(self.deref_alloc(alloc))
500    }
501
502    fn obj_detach(
503        obj: &Self::ObjectT,
504        alloc: &EntityAlloc<Self::ObjectT, Self::PolicyT>,
505    ) -> EntityListRes<Self> {
506        if Self::obj_is_sentinel(obj) {
507            return Err(EntityListError::NodeIsSentinel);
508        }
509        let (Some(prev), Some(next)) = Self::obj_load_head(obj).into_id() else {
510            // detach() 在节点未连接时调用是合法的，直接返回 Ok(())
511            return Ok(());
512        };
513        prev.set_next_id(alloc, Some(next));
514        next.set_prev_id(alloc, Some(prev));
515        Self::obj_store_head(obj, EntityListNodeHead::none());
516        Ok(())
517    }
518
519    /// Detach this node from the ring list it is currently attached to.
520    ///
521    /// ### Signal invocation
522    ///
523    /// `detach` will invoke `on_unplug` on `self` before modifying any links.
524    /// If the signal returns an error, the operation is aborted without modifying any links.
525    fn detach(self, alloc: &EntityAlloc<Self::ObjectT, Self::PolicyT>) -> EntityListRes<Self> {
526        Self::obj_detach(self.deref_alloc(alloc), alloc)
527    }
528}
529impl<I: IEntityRingListNodeID> NodeOpsPrivate<list_util::RingList> for I {
530    fn obj_get_prev_id(obj: &Self::ObjectT) -> Option<Self> {
531        I::obj_load_head(obj).get_prev()
532    }
533    fn obj_get_next_id(obj: &Self::ObjectT) -> Option<Self> {
534        I::obj_load_head(obj).get_next()
535    }
536    fn obj_set_prev_id(obj: &Self::ObjectT, prev: Option<Self>) {
537        I::obj_store_head(obj, I::obj_load_head(obj).prev(prev));
538    }
539    fn obj_set_next_id(obj: &Self::ObjectT, next: Option<Self>) {
540        I::obj_store_head(obj, I::obj_load_head(obj).next(next));
541    }
542    fn obj_is_attached(obj: &Self::ObjectT) -> bool {
543        let head = Self::obj_load_head(obj);
544        let has_prev = head.prev.is_some();
545        let has_next = head.next.is_some();
546        if cfg!(debug_assertions) && (has_prev != has_next) {
547            panic!("EntityRingListNodeID: obj_is_attached: inconsistent attachment state detected");
548        }
549        has_prev || has_next
550    }
551}
552
553pub struct EntityRingList<I: IEntityRingListNodeID> {
554    pub sentinel: I,
555}
556
557impl<I: IEntityRingListNodeID> EntityRingList<I> {
558    /// Create a new empty ring list with a sentinel node.
559    pub fn new(alloc: &EntityAlloc<I::ObjectT, I::PolicyT>) -> Self {
560        Self {
561            sentinel: I::new_sentinel(alloc),
562        }
563    }
564    pub fn front_id(&self, alloc: &EntityAlloc<I::ObjectT, I::PolicyT>) -> Option<I> {
565        let next = self.sentinel.get_next_id(alloc)?;
566        if next == self.sentinel {
567            None
568        } else {
569            Some(next)
570        }
571    }
572    pub fn back_id(&self, alloc: &EntityAlloc<I::ObjectT, I::PolicyT>) -> Option<I> {
573        let prev = self.sentinel.get_prev_id(alloc)?;
574        if prev == self.sentinel {
575            None
576        } else {
577            Some(prev)
578        }
579    }
580    pub fn is_empty(&self, alloc: &EntityAlloc<I::ObjectT, I::PolicyT>) -> bool {
581        self.front_id(alloc).is_none()
582    }
583    pub fn is_single(&self, alloc: &EntityAlloc<I::ObjectT, I::PolicyT>) -> bool {
584        let sentinel = self.sentinel.deref_alloc(alloc);
585        let head = I::obj_load_head(sentinel);
586        let (Some(prev), Some(next)) = head.into_id() else {
587            return false;
588        };
589        prev == next && prev != self.sentinel
590    }
591    pub fn is_multiple(&self, alloc: &EntityAlloc<I::ObjectT, I::PolicyT>) -> bool {
592        let sentinel = self.sentinel.deref_alloc(alloc);
593        let head = I::obj_load_head(sentinel);
594        let (Some(prev), Some(next)) = head.into_id() else {
595            return false;
596        };
597        prev != next
598    }
599
600    /// traverse each node in the list, invoking `pred` on each node.
601    ///
602    /// ### panics
603    ///
604    /// If a broken ring list is detected, this function will panic.
605    pub fn foreach(
606        &self,
607        alloc: &EntityAlloc<I::ObjectT, I::PolicyT>,
608        mut pred: impl FnMut(I, &I::ObjectT) -> bool,
609    ) -> bool {
610        let mut curr = self.sentinel.get_next_id(alloc);
611        let mut count = 0;
612        while let Some(node_id) = curr {
613            if node_id == self.sentinel {
614                return true;
615            }
616            let node_obj = node_id.deref_alloc(alloc);
617            if !pred(node_id, node_obj) {
618                return false;
619            }
620            curr = node_id.get_next_id(alloc);
621            count += 1;
622        }
623        panic!("Broken ring list detected after {count} nodes");
624    }
625
626    /// traverse each node in the list starting from the sentinel, invoking `pred` on each node.
627    ///
628    /// ### panics
629    ///
630    /// If a broken ring list is detected, this function will panic.
631    pub fn forall_with_sentinel(
632        &self,
633        alloc: &EntityAlloc<I::ObjectT, I::PolicyT>,
634        mut pred: impl FnMut(I, &I::ObjectT) -> bool,
635    ) -> bool {
636        let mut curr = Some(self.sentinel);
637        let mut count = 0;
638        while let Some(node_id) = curr {
639            let node_obj = node_id.deref_alloc(alloc);
640            if !pred(node_id, node_obj) {
641                return false;
642            }
643            curr = node_id.get_next_id(alloc);
644            count += 1;
645            if curr == Some(self.sentinel) {
646                return true;
647            }
648        }
649        panic!("Broken ring list detected after {count} nodes");
650    }
651
652    pub fn len(&self, alloc: &EntityAlloc<I::ObjectT, I::PolicyT>) -> usize {
653        let mut len = 0;
654        self.foreach(alloc, |_, _| {
655            len += 1;
656            true
657        });
658        len
659    }
660    pub fn contains(&self, node: I, alloc: &EntityAlloc<I::ObjectT, I::PolicyT>) -> bool {
661        !self.foreach(alloc, |id, _| id != node)
662    }
663
664    #[inline]
665    pub fn clone_view(&self) -> Self {
666        Self {
667            sentinel: self.sentinel,
668        }
669    }
670
671    pub fn push_back(
672        &self,
673        new_node: I,
674        alloc: &EntityAlloc<I::ObjectT, I::PolicyT>,
675    ) -> EntityListRes<I> {
676        const ERRMSG: &str = "Broken ring detected during push_back";
677
678        let sentinel_obj = self.sentinel.deref_alloc(alloc);
679        let prev = I::obj_get_prev_id(sentinel_obj).expect(ERRMSG);
680        if prev == new_node {
681            return Err(EntityListError::RepeatedNode);
682        }
683        if new_node.is_attached(alloc) {
684            return Err(EntityListError::ItemFalselyAttached(new_node));
685        }
686
687        I::obj_store_head(
688            new_node.deref_alloc(alloc),
689            EntityListNodeHead::from_id(prev, self.sentinel),
690        );
691        Ok(())
692    }
693
694    pub fn pop_back(&self, alloc: &EntityAlloc<I::ObjectT, I::PolicyT>) -> EntityListRes<I, I> {
695        let back_id = self.back_id(alloc).ok_or(EntityListError::EmptyList)?;
696        back_id.detach(alloc)?;
697        Ok(back_id)
698    }
699    pub fn pop_front(&self, alloc: &EntityAlloc<I::ObjectT, I::PolicyT>) -> EntityListRes<I, I> {
700        let front_id = self.front_id(alloc).ok_or(EntityListError::EmptyList)?;
701        front_id.detach(alloc)?;
702        Ok(front_id)
703    }
704
705    /// Move all nodes from `self` into `other`, preserving order; invoke on_move for each moved node.
706    pub fn move_all_to(
707        &self,
708        other: &Self,
709        alloc: &EntityAlloc<I::ObjectT, I::PolicyT>,
710        mut on_move: impl FnMut(I),
711    ) -> EntityListRes<I> {
712        if self.sentinel == other.sentinel {
713            return Ok(());
714        }
715        loop {
716            let node = match self.pop_front(alloc) {
717                Ok(n) => n,
718                Err(EntityListError::EmptyList) => break Ok(()),
719                Err(e) => break Err(e),
720            };
721            other.push_back(node, alloc)?;
722            on_move(node);
723        }
724    }
725
726    /// Move nodes that satisfy `predicate` from `self` to `other`, preserving order.
727    pub fn move_to_if(
728        &self,
729        other: &Self,
730        alloc: &EntityAlloc<I::ObjectT, I::PolicyT>,
731        mut pred: impl FnMut(I, &I::ObjectT) -> bool,
732        mut on_move: impl FnMut(I),
733    ) -> EntityListRes<I> {
734        if self.sentinel == other.sentinel {
735            return Err(EntityListError::RepeatedList);
736        }
737        loop {
738            let Some(next) = self.sentinel.get_next_id(alloc) else {
739                break;
740            };
741            if next == self.sentinel {
742                return Ok(());
743            }
744            let next_obj = next.deref_alloc(alloc);
745            if !pred(next, next_obj) {
746                continue;
747            }
748            next.detach(alloc)?;
749            other.push_back(next, alloc)?;
750            on_move(next);
751        }
752        Err(EntityListError::ListBroken)
753    }
754
755    pub fn clean(&self, alloc: &EntityAlloc<I::ObjectT, I::PolicyT>) {
756        let mut count = 0;
757        let err = loop {
758            match self.pop_front(alloc) {
759                Ok(_) => count += 1,
760                Err(EntityListError::EmptyList) => return,
761                Err(e) => break e,
762            };
763        };
764        panic!("Broken ring list detected after removing {count} nodes: {err}");
765    }
766
767    pub fn iter<'a>(
768        &self,
769        alloc: &'a EntityAlloc<I::ObjectT, I::PolicyT>,
770    ) -> EntityRingListIter<'a, I> {
771        EntityRingListIter {
772            alloc,
773            curr: self
774                .sentinel
775                .get_next_id(alloc)
776                .expect("Broken ring list detected in iter()"),
777        }
778    }
779}
780
781#[derive(Clone, Copy)]
782pub struct EntityRingListIter<'alloc, I: IEntityRingListNodeID> {
783    alloc: &'alloc EntityAlloc<I::ObjectT, I::PolicyT>,
784    curr: I,
785}
786impl<'alloc, I: IEntityRingListNodeID> Iterator for EntityRingListIter<'alloc, I>
787where
788    I::ObjectT: 'alloc,
789{
790    type Item = (I, &'alloc I::ObjectT);
791
792    fn next(&mut self) -> Option<Self::Item> {
793        let curr = self.curr;
794        if curr.is_sentinel(self.alloc) {
795            return None;
796        }
797        let obj = curr.deref_alloc(self.alloc);
798        let Some(next) = curr.get_next_id(self.alloc) else {
799            panic!("Broken ring list detected during iteration");
800        };
801        self.curr = next;
802        Some((curr, obj))
803    }
804}
mtb_entity_slab/container/ptrlist.rs

mtb_entity_slab/container/
ptrlist.rs
