LARA

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