A root set separates reachable objects from unused allocations.
An explicit heap graph can be traced from roots, marking every referenced object once and classifying allocations that no root can reach.
Which allocations must a storage manager preserve when references form a graph?
- Represent heap objects as identifiers with outgoing references
- Trace every path starting from an explicit root set
- Stop revisiting marked objects when the graph contains a cycle
- Distinguish unreachable allocations without reclaiming them in this model
mark adds an object identifier before following its children. mark-list carries the growing marked set across sibling references, so an object reached through several paths appears once. The first heap leaves garbage and orphan allocated but unreachable from root a.
The second heap contains a cycle from a through b and c back to a. contains? stops the revisit, while mark-roots starts a second traversal from x. unreachable then scans every allocation and classifies only dead outside the marked set. This lesson models tracing and classification, not memory reclamation itself.
- Output
- —
- Value
- —
- Diagnostic
- —
The first program returns ((a b d c) (garbage orphan)). The second returns ((a b c x y) (dead)).
In the first run, follow the root through b to d before returning to c, then watch the heap scan reject marked IDs. In the second run, find the contains? hit that stops the c-to-a cycle and the later traversal from root x.
Change the program and compare the result.
Add a reference from orphan to a while keeping root a. Predict whether garbage and orphan become reachable.
Show hint
Reachability follows references outward from roots. A reference from an unreachable object toward a root does not make that object reachable.