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)]
9#[repr(transparent)]
10pub(crate) 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    #[inline(always)]
45    pub fn is_empty(&self) -> bool {
46        self.link_head.is_some()
47    }
48
49    /// Remove the given node from the link chain.
50    ///
51    /// Returns `true` if the node was found and removed, `false` otherwise.
52    pub fn remove(&mut self, target: NonNull<GcHead>) -> bool {
53        let mut current = self.link_head;
54        let mut prev: Option<NonNull<GcHead>> = None;
55
56        while let Some(node) = current {
57            unsafe {
58                if node == target {
59                    let next = node.as_ref().next;
60                    if let Some(mut prev_node) = prev {
61                        prev_node.as_mut().next = next;
62                    } else {
63                        self.link_head = next;
64                    }
65                    return true;
66                } else {
67                    prev = Some(node);
68                    current = node.as_ref().next;
69                }
70            }
71        }
72
73        false
74    }
75
76    pub fn filter_remove_with(
77        &mut self,
78        mut predicate: impl FnMut(&GcHead) -> bool,
79        mut remove_fn: impl FnMut(NonNull<GcHead>),
80    ) {
81        let mut current = self.link_head;
82        let mut prev: Option<NonNull<GcHead>> = None;
83
84        while let Some(node) = current {
85            unsafe {
86                let node_ref = node.as_ref();
87                if predicate(node_ref) {
88                    // predicate returns true, so remove the node
89                    let next = node_ref.next;
90                    if let Some(mut prev_node) = prev {
91                        // It's not the head of the list
92                        prev_node.as_mut().next = next;
93                    } else {
94                        // It's the head of the list
95                        self.link_head = next;
96                    }
97                    current = next;
98                    remove_fn(node);
99                } else {
100                    // predicate returns false, keep the node and move to the next
101                    prev = Some(node);
102                    current = node_ref.next;
103                }
104            }
105        }
106    }
107}
108
109/// Iterate along node link chain
110#[repr(transparent)]
111pub struct NodeLinkIter<'a> {
112    current: Option<NonNull<GcHead>>,
113    _marker: std::marker::PhantomData<&'a ()>,
114}
115
116impl<'a> NodeLinkIter<'a> {
117    /// Create iterator from starting node
118    pub fn new(starting: Option<NonNull<GcHead>>) -> Self {
119        Self {
120            current: starting,
121            _marker: std::marker::PhantomData,
122        }
123    }
124}
125
126impl<'a> Iterator for NodeLinkIter<'a> {
127    type Item = NonNull<GcHead>;
128
129    fn next(&mut self) -> Option<Self::Item> {
130        if let Some(current) = self.current {
131            self.current = unsafe { current.as_ref().next };
132            Some(current)
133        } else {
134            None
135        }
136    }
137}
138
139impl GcHeap {
140    #[inline]
141    pub fn nodes(&self, partition_id: GcPartitionId) -> NodeLinkIter<'_> {
142        NodeLinkIter::new(
143            self.partitions
144                .get(&partition_id)
145                .and_then(|p| p.nodes.head()),
146        )
147    }
148}
149
150pub struct NodeLinkIterMut<'a> {
151    current: Option<NonNull<GcHead>>,
152    _marker: std::marker::PhantomData<&'a mut GcHead>,
153}
154
155impl<'a> NodeLinkIterMut<'a> {
156    pub fn new(head: Option<NonNull<GcHead>>) -> Self {
157        Self {
158            current: head,
159            _marker: std::marker::PhantomData,
160        }
161    }
162}
163
164impl<'a> Iterator for NodeLinkIterMut<'a> {
165    type Item = &'a mut GcHead;
166
167    fn next(&mut self) -> Option<Self::Item> {
168        if let Some(current) = self.current {
169            unsafe {
170                self.current = current.as_ref().next;
171                Some(&mut *current.as_ptr())
172            }
173        } else {
174            None
175        }
176    }
177}
178
179impl GcPartition {
180    pub fn nodes_mut(&mut self) -> NodeLinkIterMut<'_> {
181        NodeLinkIterMut::new(self.nodes.head())
182    }
183}
184
185#[cfg(test)]
186mod tests {
187    use super::*;
188
189    #[test]
190    fn test_gc_node_link_empty() {
191        let link = GcNodeLink::new(None);
192        let mut iter = link.iter();
193        assert!(iter.next().is_none());
194    }
195
196    #[test]
197    fn test_gc_node_link_single() {
198        let mut node = GcHead {
199            attrs: 0,
200            partition: 0,
201            weak_id: crate::weak::GcWeakRawId::NULL,
202            next: None,
203            #[cfg(debug_assertions)]
204            dbg_scope_depth: 0,
205            #[cfg(debug_assertions)]
206            dbg_string: "".into(),
207        };
208        let node_ptr = NonNull::from(&mut node);
209        let link = GcNodeLink::new(Some(node_ptr));
210        let mut iter = link.iter();
211        assert_eq!(iter.next(), Some(node_ptr));
212        assert!(iter.next().is_none());
213    }
214
215    #[test]
216    fn test_gc_node_link_multiple() {
217        let mut node3 = GcHead {
218            attrs: 0,
219            partition: 0,
220            weak_id: crate::weak::GcWeakRawId::NULL,
221            next: None,
222            #[cfg(debug_assertions)]
223            dbg_scope_depth: 0,
224            #[cfg(debug_assertions)]
225            dbg_string: "node3".into(),
226        };
227        let node3_ptr = NonNull::from(&mut node3);
228
229        let mut node2 = GcHead {
230            attrs: 0,
231            partition: 0,
232            weak_id: crate::weak::GcWeakRawId::NULL,
233            next: Some(node3_ptr),
234            #[cfg(debug_assertions)]
235            dbg_scope_depth: 0,
236            #[cfg(debug_assertions)]
237            dbg_string: "node2".into(),
238        };
239        let node2_ptr = NonNull::from(&mut node2);
240
241        let mut node1 = GcHead {
242            attrs: 0,
243            partition: 0,
244            weak_id: crate::weak::GcWeakRawId::NULL,
245            next: Some(node2_ptr),
246            #[cfg(debug_assertions)]
247            dbg_scope_depth: 0,
248            #[cfg(debug_assertions)]
249            dbg_string: "node1".into(),
250        };
251        let node1_ptr = NonNull::from(&mut node1);
252
253        let link = GcNodeLink::new(Some(node1_ptr));
254        let mut iter = link.iter();
255
256        assert_eq!(iter.next(), Some(node1_ptr));
257        assert_eq!(iter.next(), Some(node2_ptr));
258        assert_eq!(iter.next(), Some(node3_ptr));
259        assert!(iter.next().is_none());
260    }
261
262    fn create_nodes(count: usize) -> (Vec<GcHead>, GcNodeLink) {
263        let mut nodes: Vec<GcHead> = (0..count)
264            .map(|i| GcHead {
265                attrs: i as u32,
266                partition: 0,
267                weak_id: crate::weak::GcWeakRawId::NULL,
268                next: None,
269                #[cfg(debug_assertions)]
270                dbg_scope_depth: 0,
271                #[cfg(debug_assertions)]
272                dbg_string: format!("node{}", i).into(),
273            })
274            .collect();
275
276        let mut link = GcNodeLink::new(None);
277        // Iterate backwards over the vector to prepend correctly, building a list like (n-1)->(n-2)->...->0
278        for node in nodes.iter_mut().rev() {
279            let node_ptr = NonNull::from(node);
280            link.prepend(node_ptr);
281        }
282
283        (nodes, link)
284    }
285
286    #[test]
287    fn test_filter_remove_from_empty_list() {
288        let mut link = GcNodeLink::new(None);
289        let mut removed_count = 0;
290        link.filter_remove_with(|_| true, |_| removed_count += 1);
291        assert_eq!(removed_count, 0);
292        assert!(link.iter().next().is_none());
293    }
294
295    #[test]
296    fn test_filter_remove_none() {
297        let (_nodes, mut link) = create_nodes(3);
298        let mut removed_count = 0;
299        link.filter_remove_with(|_| false, |_| removed_count += 1);
300        assert_eq!(removed_count, 0);
301        assert_eq!(link.len(), 3);
302    }
303
304    #[test]
305    fn test_filter_remove_all() {
306        let (_nodes, mut link) = create_nodes(3);
307        let mut removed_count = 0;
308        link.filter_remove_with(|_| true, |_| removed_count += 1);
309        assert_eq!(removed_count, 3);
310        assert!(link.iter().next().is_none());
311    }
312
313    #[test]
314    fn test_filter_remove_first() {
315        let (_nodes, mut link) = create_nodes(3);
316        let mut removed_count = 0;
317        link.filter_remove_with(|node| node.attrs == 0, |_| removed_count += 1);
318        assert_eq!(removed_count, 1);
319        assert_eq!(link.len(), 2);
320        let mut iter = link.iter();
321        assert_eq!(unsafe { iter.next().unwrap().as_ref().attrs }, 1);
322        assert_eq!(unsafe { iter.next().unwrap().as_ref().attrs }, 2);
323    }
324
325    #[test]
326    fn test_filter_remove_last() {
327        let (_nodes, mut link) = create_nodes(3);
328        let mut removed_count = 0;
329        link.filter_remove_with(|node| node.attrs == 2, |_| removed_count += 1);
330        assert_eq!(removed_count, 1);
331        assert_eq!(link.len(), 2);
332        let mut iter = link.iter();
333        assert_eq!(unsafe { iter.next().unwrap().as_ref().attrs }, 0);
334        assert_eq!(unsafe { iter.next().unwrap().as_ref().attrs }, 1);
335    }
336
337    #[test]
338    fn test_filter_remove_middle() {
339        let (_nodes, mut link) = create_nodes(3);
340        let mut removed_count = 0;
341        link.filter_remove_with(|node| node.attrs == 1, |_| removed_count += 1);
342        assert_eq!(removed_count, 1);
343        assert_eq!(link.len(), 2);
344        let mut iter = link.iter();
345        assert_eq!(unsafe { iter.next().unwrap().as_ref().attrs }, 0);
346        assert_eq!(unsafe { iter.next().unwrap().as_ref().attrs }, 2);
347    }
348
349    #[test]
350    fn test_filter_remove_every_other() {
351        let (_nodes, mut link) = create_nodes(5);
352        let mut removed_count = 0;
353        link.filter_remove_with(|node| node.attrs % 2 != 0, |_| removed_count += 1);
354        assert_eq!(removed_count, 2);
355        assert_eq!(link.len(), 3);
356        let mut iter = link.iter();
357        assert_eq!(unsafe { iter.next().unwrap().as_ref().attrs }, 0);
358        assert_eq!(unsafe { iter.next().unwrap().as_ref().attrs }, 2);
359        assert_eq!(unsafe { iter.next().unwrap().as_ref().attrs }, 4);
360    }
361}
gc_lite/node_link.rs

gc_lite/
node_link.rs
