/*
 * Lisp garbage collector
 * Don Hopkins
 */

#include "lisp.h"

/*
 * Perform garbage collection. The objects car and cdr are passed to
 * gc by cons for protection. Mark car, cdr, Input_Stack,
 * Output_Stack, Ob_List, Ob_Stack, Back_Trace, and the value of each
 * atom. Add all unmarked cons nodes to the free list, and increase
 * the size of the cons space. Return the number of nodes freed.
 */

int gc(car, cdr)
     object car, cdr;
{
  int free = Cons_Free;
  object atom;

  fputs("\n<* Garbage collection *>\n", Output_File);

  mark(car);
  mark(cdr);
  mark(Input_Stack);
  mark(Output_Stack);
  mark(Ob_List);
  mark(Ob_Stack);
  mark(Back_Trace);
  for (atom = 0; atom < Atom_Free; atom++)
    mark(Atom_Value(atom));

  sweep();

  return(Cons_Free - free);
}

/*
 * Lisp interface to gc.
 */

object lgc(args)
     object args;
{
  return(make_number((double)gc(Nil, Nil)));
}

/* 
 * Mark an object in cons space, and all objects in cons space it
 * points too. Cons, user function, user special, built-in function,
 * built-in special, macro, stream, and funarg objects are all stored
 * in cons space. Only cons, user function, user special, macro, and
 * funarg objects have car and cdr fields that can point to other
 * objects in cons space.
 */

mark(obj)
     object obj;
{
  while (1) {
    switch (Object_Type(obj)) {

/*
 * Mark a cons that may point to others, and follow its links.
 */

    case cons_object:
    case user_function_object:
    case user_special_object:
    case macro_object:
    case funarg_object:
      if (Cons_Car(obj) & GC_MARK)
	return;
      Cons_Car(obj) |= GC_MARK;
      mark(Cons_Car(obj));
      obj = Cons_Cdr(obj);
      continue;

/*
 * Mark a cons that doesn't point to others, and return.
 */

    case stream_object:
      Cons_Car(obj) |= GC_MARK;

/*
 * For all other objects, just return.
 */

    default:
      return;
    }
  }
}

/*
 * Sweep up all unmarked cons cells onto the free list. Remove marks from 
 * marked cells.
 */

sweep()
{
  object cons;

  Free_List = Nil;
  Cons_Free = 0;

  for (cons = 0; cons < Cons_Count; cons++) {
    if (!(Cons_Car(cons) & GC_MARK)) {
      Cons_Cdr(cons) = Free_List;
      Free_List = cons;
      Cons_Free++;
    }
    else
      Cons_Car(cons) &= ~GC_MARK;
  }
}