marwood 0.3.1

Scheme R5RS Virtual Machine
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146

/// GcMap
///
/// GcMap is a map used to track the disposition of objects on a
/// heap during mark&sweep garbage collection.
///
/// The map tracks three possible states for each element in a heap:
/// * Free
/// * Allocated
/// * Used
///
/// The initial state for a vcell is free (0x0, and then when allocated
/// the state is transitioned to Allocated.
#[derive(Debug)]
pub struct Map {
    size: usize,
    map: Vec<u8>,
}

/// State
///
/// State represents the disposition of an object on the heap in regards
/// to garbage collection.
///
/// Free: The object is not in use, and is on the free list ready to be
///       allocated.
///
/// Allocated: The object is allocated and believed to be in use. It is
///       subject to garbage collection checks.
///
/// Used: The object has been marked during garbage collection. This is an
///       ephemeral state used during GC before the object is either marked
///       allocated again, or free.
#[derive(Debug, Eq, PartialEq, Clone)]
#[repr(u8)]
pub enum State {
    Free,
    Allocated,
    Used,
}

impl State {
    pub fn bits(&self) -> u8 {
        match self {
            State::Free => 0b00,
            State::Allocated => 0b01,
            State::Used => 0b10,
        }
    }
}

impl From<u8> for State {
    fn from(val: u8) -> State {
        match val {
            0b00 => State::Free,
            0b01 => State::Allocated,
            0b10 => State::Used,
            _ => panic!("invalid gc state"),
        }
    }
}

impl Map {
    /// New
    ///
    /// Construct a new GcMap of len elements, initializing every element
    /// to the value 0 (free).
    pub fn new(size: usize) -> Map {
        Map {
            size,
            map: vec![0; size],
        }
    }

    /// Get
    ///
    /// Given the index into the map, retrieve the state of the object,
    /// or None if the index was out of bounds.
    ///
    /// # Arguments
    /// `index` - The index to retrieve the state for.
    pub fn get(&self, index: usize) -> Option<State> {
        self.map
            .get(index / 4)
            .map(|it| (it >> ((index % 4) * 2)) & 0b11)
            .map(|it| it.into())
    }

    /// Set
    ///
    /// Given the index into the map, set the state to the value given.
    ///
    /// Panic if the index is invalid.
    ///
    /// # Arguments
    /// `index` - The index to mutate
    /// `state` - The state to set at the index
    pub fn set(&mut self, index: usize, state: State) {
        match self.map.get_mut(index / 4) {
            Some(byte) => {
                let mask: u8 = 0b11 << ((index % 4) * 2);
                let flag: u8 = state.bits() << ((index % 4) * 2);
                *byte &= !mask;
                *byte |= flag;
            }
            None => panic!("invalid gc index"),
        }
    }

    pub fn mark(&mut self, index: usize) {
        self.set(index, State::Used);
    }

    pub fn is_marked(&self, index: usize) -> bool {
        matches!(self.get(index), Some(State::Used))
    }

    pub fn capacity(&self) -> usize {
        self.size
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn initial_state_is_free() {
        let gcmap = Map::new(8);
        assert_eq!(gcmap.size, 8);
        for it in 0..32 {
            assert_eq!(gcmap.get(it), Some(State::Free));
        }
        assert_eq!(gcmap.get(32), None);
    }

    #[test]
    fn mutation() {
        let mut gcmap = Map::new(8);
        gcmap.set(0, State::Used);
        gcmap.set(1, State::Allocated);
        gcmap.set(15, State::Used);
        assert_eq!(gcmap.get(0), Some(State::Used));
        assert_eq!(gcmap.get(15), Some(State::Used));
        assert_eq!(gcmap.get(1), Some(State::Allocated));
        assert_eq!(gcmap.get(2), Some(State::Free));
    }
}