Yhc/RTS/PointerReversal
| Part of Yhc |
Marking the heap is a recursive process but a naive recursive implementation of this can quickly exhaust the C stack. So a common trick here is 'pointer reversal' whereby the heap itself is used as a stack.
The following diagram explains how it works. We mark the root node by taking this heap layout:
+-- Current Node
|
root V node A
+--------+ +---------+---------+---------+
| --------------->| XXX | | |
+--------+ +---------+----|----+----|----+
| |
+-----------------+ |
V V
+---------+---------+ +----------+
node B | YYY | --------->| ZZZ |
+---------+---------+ +----------+
node C
and changing it to (the hashes indicate the word is marked).
Current Node-+
|
root V node A
+--------+ ###########---------+---------+
| XXX |<--------------- # | |
+--------+ ###########----|----+----|----+
| |
+-----------------+ |
V V
+---------+---------+ +----------+
node B | YYY | --------->| ZZZ |
+---------+---------+ +----------+
node C
We then mark all the arguments of node a, starting from the right most one:
root node A
+--------+ ###########---------+---------+
| XXX |<--------------- # | ZZZ |
+--------+ ###########----|----+---------+
| ^ Current Node
+-----------------+ | |
V | |
+---------+---------+ ###|######## |
node B | YYY | ---------># #<----+
+---------+---------+ ############
node C
There are no more arguments to mark so we 'return'
Current Node ------+
|
root node A V
+--------+ ###########---------+---------+
| XXX |<--------------- # | |
+--------+ ###########----|----+----|----+
| |
+-----------------+ |
V V
+---------+---------+ ############
node B | YYY | ---------># ZZZ #
+---------+---------+ ############
node C
We now decrement current node to the first argument of node A and mark that node.
root node A
+--------+ ###########---------+---------+
| XXX |<--------------- # YYY | |
+--------+ ###########---------+----|----+
^ |
+-----------------+ |
| V
#####|#####---------+ ############
node B # # ---------># ZZZ #
###########---------+ ############
^ node C
Current Node ------+
And descend into the first argument of node B.
root node A
+--------+ ###########---------+---------+
| XXX |<--------------- # YYY | |
+--------+ ###########---------+----|----+
| | Current Node
+-----------------+ | |
| V |
#####|#####---------+ ############ |
node B # # ZZZ |<--------- #<----+
###########---------+ ############
node C
This node is already marked, so we return.
root node A
+--------+ ###########---------+---------+
| XXX |<--------------- # YYY | |
+--------+ ###########---------+----|----+
| |
+-----------------+ |
| V
#####|#####---------+ ############
node B # # ----------># ZZZ #
###########---------+ ############
^ node C
Current Node------+
We can now decrement current node, however this takes us to the head of node B (we can tell it's the head of a node because it's marked). There are no more arguments in node B, so we return.
+--- Current Node
root node A V
+--------+ ###########---------+---------+
| XXX |<--------------- # | |
+--------+ ###########----|----+----|----+
| |
+-----------------+ |
V V
###########---------+ ############
node B # YYY # ----------># ZZZ #
###########---------+ ############
node C
We now decrement current node, again we're at the head of node A. No more arguments left so we return.
+--- Current Node
|
root V node A
+--------+ ###########---------+---------+
| ---------------># XXX # | |
+--------+ ###########----|----+----|----+
| |
+-----------------+ |
V V
###########---------+ ############
node B # YYY # ----------># ZZZ #
###########---------+ ############
node C
We're back at our starting point so we can stop.