TAOCP 2.3.5 Exercise 9

Section 2.3.5: Lists and Garbage Collection

Exercise 9. [**] [28] (D. Edwards.) Design an algorithm for the second phase of garbage collection that "compacts storage" in the following sense: Let NODE(1), ..., NODE(M) be one-word nodes with fields MARK, ATOM, ALINK, and BLINK, as described in Algorithm E. Assume that MARK = 1 in all nodes that are not garbage. The desired algorithm should relocate the marked nodes, if necessary, so that they all appear in consecutive locations NODE(1), ..., NODE(K), and at the same time the ALINK and BLINK fields of nonatomic nodes should be altered if necessary so that the List structure is preserved.

Verified: yes
Solve time: 1m13s

Let $K \leftarrow 0$. For each $i$, $1 \le i \le M$, examine $NODE(i)$; if $MARK = 1$, then $K \leftarrow K + 1$ and set $ATOM \leftarrow K$ in $NODE(i)$. After this pass, each marked node $NODE(i)$ carries a distinct new position $ATOM \in {1,\dots,K}$.

For each $i$, $1 \le i \le M$, if $MARK = 1$, then let $j \leftarrow ALINK$ and $k \leftarrow BLINK$ as stored in $NODE(i)$, and replace

$ALINK \leftarrow ATOM(j), \qquad BLINK \leftarrow ATOM(k).$

This substitution preserves all references because every node that remains in the structure has already been assigned its final address in the $ATOM$ field, while nodes with $MARK = 0$ are ignored since they are garbage.

Finally, for each $i$, $1 \le i \le M$, if $MARK = 1$, then move the entire contents of $NODE(i)$ into location $NODE(ATOM)$, including $MARK$, $ATOM$, $ALINK$, and $BLINK$. Since distinct marked nodes have distinct values of $ATOM$, no two moves write into the same location. After this relocation, all surviving nodes occupy exactly the consecutive locations $NODE(1), \dots, NODE(K)$, and every pointer field refers to the relocated addresses.

This completes the proof. ∎