# Pointer Reversal

Suppose we write depth-first search in mark and sweep using a stack

What is the maximal stack size?

How can we represent the stack?

- same stack we use for procedures
- explicit stack data structure on the heap
- pointer reversal: store information within nodes

## Explicit Stack

function DFS(x) if (x is a pointer and record x is not marked) { mark(x) t = 1 stack(t) = x while (t > 0) { x = stack(t) t = t - 1 for each field f_i of record x if (x.f_i is a pointer and x.f_i is not marked) { mark(x.f_i) t = t + 1 stack(t) = x.f_i } } }

## Deutsch-Shorr-Waite algorithm

A 'done' field keeps track which fields we have traversed in a node

Simpler version:

- add an extra “parent” field to each node
- use it instead of stack pop to go back to the node

Avoiding the parent field:

- store parent in the field that we are following
- indeed, they are inverse of the other, so one is redundant
- when going back, restore the field

function DFS(x) if (x is a pointer and record x is not marked) { t = nil mark(x) x.done = 0 while (true) { // t - parent node // x - current node // y - node we descend into i = x.done if (i < numberOfFields(xType)) { y = x.f_i if (y is a pointer and record y is not marked) { x.f_i = t t = x x = y mark(x) x.done = 0 } else { x.done = i + 1 } } else { y = x x = t if (x = nil) return i = x.done t = x.f_i x.f_i = y x.done = i + 1 } } }