bsr 0.11.0

Tracing garbage collector for Amsel
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

//! Contains the main heap struct and implementation for the garbage collector.

use std::collections::HashSet;
use std::pin::Pin;
use crate::gc::Gc;
use crate::heap_entry::{EntryLike, HeapEntry};
use crate::trace::Trace;


/// A heap that manages garbage-collected memory.
#[derive(Debug, Default)]
pub struct Heap {
    objects: Vec<Pin<Box<dyn EntryLike>>>,
    roots: HashSet<*const dyn Trace>,
}

impl Heap {
    /// Give a value to the heap to manage.
    pub fn manage<T: Trace + 'static>(&mut self, value: T) -> Gc<T> {
        let entry = HeapEntry::pin(value);
        let gc = entry.as_ref().get_gc();
        self.objects.push(entry);
        gc
    }

    /// Add a managed object to the root set.
    /// This object and all its children will not be collected.
    /// Returns whether the object was not already in the root set.
    pub fn add_root<T: Trace + 'static>(&mut self, object: Gc<T>) -> bool {
        if object.entry().mark_root() {
            return false;
        }

        // Deref the reference to the [Gc], then deref the [Gc] to get the [T] and finally get the
        // reference to the [Trace] object.
        let object = &*object as *const dyn Trace;
        self.roots.insert(object)
    }

    /// Remove a managed object from the root set.
    /// This object and all its children may be collected.
    /// Returns whether the object was in the root set.
    pub fn remove_root<T: Trace + 'static>(&mut self, object: Gc<T>) -> bool {
        if !object.entry().unmark_root() {
            return false;
        }

        let object = &*object as *const dyn Trace;
        self.roots.remove(&object)
    }

    /// Add a new unmanaged object to the root set.
    /// # Safety
    /// The object must not be managed by the heap and must remain valid until removed or the heap
    /// is dropped.
    /// Returns whether the object was not already in the root set.
    pub unsafe fn add_unmanaged_root<T: Trace + 'static>(&mut self, object: Pin<&T>) -> bool {
        let object = object.as_ref().get_ref() as *const dyn Trace;
        self.roots.insert(object)
    }

    /// Remove an unmanaged object from the root set.
    /// Returns whether the object was in the root set.
    pub fn remove_unmanaged_root<T: Trace + 'static>(&mut self, object: Pin<&T>) -> bool {
        let object = object.as_ref().get_ref() as *const dyn Trace;
        self.roots.remove(&object)
    }

    /// Start a collection cycle.
    /// All objects not reachable from the root set will be collected.
    /// Returns the number of objects collected.
    pub fn collect(&mut self) -> usize {
        // Unmark all objects.
        for object in &self.objects {
            object.unmark_reachable();
        }

        // Mark all reachable objects.
        for root in &self.roots {
            // Safety: The root set consists of managed and unmanaged objects.
            // Unmanaged objects are guaranteed to be valid for the lifetime of the heap.
            // Managed objects are marked as roots will not be collected.
            unsafe {
                let root = *root;
                (*root).mark_children();
            }
        }

        // Collect unreachable objects.
        let before = self.objects.len();
        self.objects.retain(|object| object.is_root() || object.unmark_reachable());
        let after = self.objects.len();
        
        before - after
    }

    /// Get the number of objects managed by the heap.
    pub fn object_count(&self) -> usize {
        self.objects.len()
    }
}