# 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
}
}
}```