gc_lite/
node_link.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright (c) 2025-2026 John Ray <996351336@qq.com>
3
4use std::ptr::NonNull;
5
6use crate::{GcPartition, GcPartitionId, heap::GcHeap, node::GcHead};
7
8#[derive(Debug, Default, Clone)]
9#[repr(transparent)]
10pub struct GcNodeLink {
11    link_head: Option<NonNull<GcHead>>,
12}
13
14impl GcNodeLink {
15    pub fn new(head: Option<NonNull<GcHead>>) -> Self {
16        Self { link_head: head }
17    }
18
19    pub fn into_inner(self) -> Option<NonNull<GcHead>> {
20        self.link_head
21    }
22
23    pub fn head(&self) -> Option<NonNull<GcHead>> {
24        self.link_head
25    }
26
27    /// Prepend node to the head of the link, link head is updated
28    pub fn prepend(&mut self, node: NonNull<GcHead>) {
29        unsafe {
30            (*node.as_ptr()).next = self.link_head;
31        }
32        self.link_head = Some(node);
33    }
34
35    #[inline(always)]
36    pub fn iter(&self) -> NodeLinkIter<'_> {
37        NodeLinkIter::new(self.link_head)
38    }
39
40    pub fn len(&self) -> usize {
41        self.iter().count()
42    }
43
44    pub fn filter_remove_with(
45        &mut self,
46        mut predicate: impl FnMut(&GcHead) -> bool,
47        mut remove_fn: impl FnMut(NonNull<GcHead>),
48    ) {
49        let mut current = self.link_head;
50        let mut prev: Option<NonNull<GcHead>> = None;
51
52        while let Some(node) = current {
53            unsafe {
54                let node_ref = node.as_ref();
55                if predicate(node_ref) {
56                    // predicate returns true, so remove the node
57                    let next = node_ref.next;
58                    if let Some(mut prev_node) = prev {
59                        // It's not the head of the list
60                        prev_node.as_mut().next = next;
61                    } else {
62                        // It's the head of the list
63                        self.link_head = next;
64                    }
65                    current = next;
66                    remove_fn(node);
67                } else {
68                    // predicate returns false, keep the node and move to the next
69                    prev = Some(node);
70                    current = node_ref.next;
71                }
72            }
73        }
74    }
75}
76
77/// Iterate along node link chain
78#[repr(transparent)]
79pub struct NodeLinkIter<'a> {
80    current: Option<NonNull<GcHead>>,
81    _marker: std::marker::PhantomData<&'a ()>,
82}
83
84impl<'a> NodeLinkIter<'a> {
85    /// Create iterator from starting node
86    pub fn new(starting: Option<NonNull<GcHead>>) -> Self {
87        Self {
88            current: starting,
89            _marker: std::marker::PhantomData,
90        }
91    }
92}
93
94impl<'a> Iterator for NodeLinkIter<'a> {
95    type Item = NonNull<GcHead>;
96
97    fn next(&mut self) -> Option<Self::Item> {
98        if let Some(current) = self.current {
99            self.current = unsafe { current.as_ref().next };
100            Some(current)
101        } else {
102            None
103        }
104    }
105}
106
107impl GcHeap {
108    #[inline]
109    pub fn nodes(&self, partition_id: GcPartitionId) -> NodeLinkIter<'_> {
110        NodeLinkIter::new(self.partitions[partition_id.0 as usize].nodes.head())
111    }
112}
113
114pub struct NodeLinkIterMut<'a> {
115    current: Option<NonNull<GcHead>>,
116    _marker: std::marker::PhantomData<&'a mut GcHead>,
117}
118
119impl<'a> NodeLinkIterMut<'a> {
120    pub fn new(head: Option<NonNull<GcHead>>) -> Self {
121        Self {
122            current: head,
123            _marker: std::marker::PhantomData,
124        }
125    }
126}
127
128impl<'a> Iterator for NodeLinkIterMut<'a> {
129    type Item = &'a mut GcHead;
130
131    fn next(&mut self) -> Option<Self::Item> {
132        if let Some(current) = self.current {
133            unsafe {
134                self.current = current.as_ref().next;
135                Some(&mut *current.as_ptr())
136            }
137        } else {
138            None
139        }
140    }
141}
142
143impl GcPartition {
144    pub fn nodes_mut(&mut self) -> NodeLinkIterMut<'_> {
145        NodeLinkIterMut::new(self.nodes.head())
146    }
147}
148
149#[cfg(test)]
150mod tests {
151    use super::*;
152
153    #[test]
154    fn test_gc_node_link_empty() {
155        let link = GcNodeLink::new(None);
156        let mut iter = link.iter();
157        assert!(iter.next().is_none());
158    }
159
160    #[test]
161    fn test_gc_node_link_single() {
162        let mut node = GcHead {
163            attrs: 0,
164            partition: 0,
165            weak_id: crate::weak::GcWeakRawId::NULL,
166            next: None,
167            #[cfg(debug_assertions)]
168            dbg_string: "".into(),
169        };
170        let node_ptr = NonNull::from(&mut node);
171        let link = GcNodeLink::new(Some(node_ptr));
172        let mut iter = link.iter();
173        assert_eq!(iter.next(), Some(node_ptr));
174        assert!(iter.next().is_none());
175    }
176
177    #[test]
178    fn test_gc_node_link_multiple() {
179        let mut node3 = GcHead {
180            attrs: 0,
181            partition: 0,
182            weak_id: crate::weak::GcWeakRawId::NULL,
183            next: None,
184            #[cfg(debug_assertions)]
185            dbg_string: "node3".into(),
186        };
187        let node3_ptr = NonNull::from(&mut node3);
188
189        let mut node2 = GcHead {
190            attrs: 0,
191            partition: 0,
192            weak_id: crate::weak::GcWeakRawId::NULL,
193            next: Some(node3_ptr),
194            #[cfg(debug_assertions)]
195            dbg_string: "node2".into(),
196        };
197        let node2_ptr = NonNull::from(&mut node2);
198
199        let mut node1 = GcHead {
200            attrs: 0,
201            partition: 0,
202            weak_id: crate::weak::GcWeakRawId::NULL,
203            next: Some(node2_ptr),
204            #[cfg(debug_assertions)]
205            dbg_string: "node1".into(),
206        };
207        let node1_ptr = NonNull::from(&mut node1);
208
209        let link = GcNodeLink::new(Some(node1_ptr));
210        let mut iter = link.iter();
211
212        assert_eq!(iter.next(), Some(node1_ptr));
213        assert_eq!(iter.next(), Some(node2_ptr));
214        assert_eq!(iter.next(), Some(node3_ptr));
215        assert!(iter.next().is_none());
216    }
217
218    fn create_nodes(count: usize) -> (Vec<GcHead>, GcNodeLink) {
219        let mut nodes: Vec<GcHead> = (0..count)
220            .map(|i| GcHead {
221                attrs: i as u32,
222                partition: 0,
223                weak_id: crate::weak::GcWeakRawId::NULL,
224                next: None,
225                #[cfg(debug_assertions)]
226                dbg_string: format!("node{}", i).into(),
227            })
228            .collect();
229
230        let mut link = GcNodeLink::new(None);
231        // Iterate backwards over the vector to prepend correctly, building a list like (n-1)->(n-2)->...->0
232        for node in nodes.iter_mut().rev() {
233            let node_ptr = NonNull::from(node);
234            link.prepend(node_ptr);
235        }
236
237        (nodes, link)
238    }
239
240    #[test]
241    fn test_filter_remove_from_empty_list() {
242        let mut link = GcNodeLink::new(None);
243        let mut removed_count = 0;
244        link.filter_remove_with(|_| true, |_| removed_count += 1);
245        assert_eq!(removed_count, 0);
246        assert!(link.iter().next().is_none());
247    }
248
249    #[test]
250    fn test_filter_remove_none() {
251        let (_nodes, mut link) = create_nodes(3);
252        let mut removed_count = 0;
253        link.filter_remove_with(|_| false, |_| removed_count += 1);
254        assert_eq!(removed_count, 0);
255        assert_eq!(link.len(), 3);
256    }
257
258    #[test]
259    fn test_filter_remove_all() {
260        let (_nodes, mut link) = create_nodes(3);
261        let mut removed_count = 0;
262        link.filter_remove_with(|_| true, |_| removed_count += 1);
263        assert_eq!(removed_count, 3);
264        assert!(link.iter().next().is_none());
265    }
266
267    #[test]
268    fn test_filter_remove_first() {
269        let (_nodes, mut link) = create_nodes(3);
270        let mut removed_count = 0;
271        link.filter_remove_with(|node| node.attrs == 0, |_| removed_count += 1);
272        assert_eq!(removed_count, 1);
273        assert_eq!(link.len(), 2);
274        let mut iter = link.iter();
275        assert_eq!(unsafe { iter.next().unwrap().as_ref().attrs }, 1);
276        assert_eq!(unsafe { iter.next().unwrap().as_ref().attrs }, 2);
277    }
278
279    #[test]
280    fn test_filter_remove_last() {
281        let (_nodes, mut link) = create_nodes(3);
282        let mut removed_count = 0;
283        link.filter_remove_with(|node| node.attrs == 2, |_| removed_count += 1);
284        assert_eq!(removed_count, 1);
285        assert_eq!(link.len(), 2);
286        let mut iter = link.iter();
287        assert_eq!(unsafe { iter.next().unwrap().as_ref().attrs }, 0);
288        assert_eq!(unsafe { iter.next().unwrap().as_ref().attrs }, 1);
289    }
290
291    #[test]
292    fn test_filter_remove_middle() {
293        let (_nodes, mut link) = create_nodes(3);
294        let mut removed_count = 0;
295        link.filter_remove_with(|node| node.attrs == 1, |_| removed_count += 1);
296        assert_eq!(removed_count, 1);
297        assert_eq!(link.len(), 2);
298        let mut iter = link.iter();
299        assert_eq!(unsafe { iter.next().unwrap().as_ref().attrs }, 0);
300        assert_eq!(unsafe { iter.next().unwrap().as_ref().attrs }, 2);
301    }
302
303    #[test]
304    fn test_filter_remove_every_other() {
305        let (_nodes, mut link) = create_nodes(5);
306        let mut removed_count = 0;
307        link.filter_remove_with(|node| node.attrs % 2 != 0, |_| removed_count += 1);
308        assert_eq!(removed_count, 2);
309        assert_eq!(link.len(), 3);
310        let mut iter = link.iter();
311        assert_eq!(unsafe { iter.next().unwrap().as_ref().attrs }, 0);
312        assert_eq!(unsafe { iter.next().unwrap().as_ref().attrs }, 2);
313        assert_eq!(unsafe { iter.next().unwrap().as_ref().attrs }, 4);
314    }
315}
gc_lite/node_link.rs

gc_lite/
node_link.rs
