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

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

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