/* -- GC ----------------------------------------------------------------------------------- */

/*
 * All we can do is a conversative garbage collection as we cannot
 * tell pointers from scalar data apart in the C stack.
 *
 * We use a mark and sweep algorithm.
 */

/** Allocation */

/*
 * We allocate from one of a number of what we call segments. A
 * segment is a collection of objects of equal size.
 */

void mark (T node);
T potential_node_pointer_p (void *x);
void mark_phase (void);
void sweep (void);

#define SEGMENT_SIZE (1 << 15)
#define MIN_FREE (SEGMENT_SIZE / 2)

struct segment {
  unsigned size;                /* node count */
  T node;                       /* vector of `size` nodes */
  struct segment *link;         /* link to next segment */
};

struct segment *segments = 0;   /* linked list of all segments */

T freelist = NIL;               /* linked list of all free nodes */

struct segment *alloc_segment (unsigned size)
{
  struct segment *r = malloc (sizeof (struct segment));
  r->size = size;
  r->node = calloc (size, sizeof (struct node));
  r->link = 0;
  nalloc += sizeof (struct node) * size;
  return r;
}

void add_segment (void)
{
  int i;
  struct segment *s = alloc_segment (SEGMENT_SIZE);

  /* Enter all nodes into the free list */
  for (i = s->size - 1; i >= 0; i--)
    {
      s->node[i].mark = 1;
      s->node[i].u.cons.cdr = freelist;
      freelist = s->node + i;
      nfree += sizeof (struct node);
    }

  /* Link into list of segments */
  s->link = segments;
  segments = s;

  /* all done */
}

T alloc_node (type_t type)
{
  T res;

  res = freelist;
  if (eq (res, NIL))
    {
      /* Out of space */
      gc ();
      res = freelist;
    }
  freelist = res->u.cons.cdr;
  nfree -= sizeof (struct node);
  res->mark = 0;
  res->type = type;
  return res;
}


void gc (void)
{
  mark_phase ();
  sweep ();
  if (nfree < MIN_FREE)
    add_segment ();

  if (0)
    {
      T here;

      printf ("nused = %d, %p, %d\n", (int)(nalloc - nfree), stack_start, (int)(stack_start - &here));
    }
  ngc++;
}

void mark_phase (void)
{
  struct cframe *f;
  int k;
  T here;
  T *q;
  jmp_buf buf;

  /* Mark the root set */
  mark (oblist);
  mark (block_marker);
  mark (dot);
  mark (rparen);
  mark (sFIN);
  mark (tag_marker);
  mark (unbound);
  mark (NIL_plist);

  for (f = cstack; f; f = f->link)
    {
      mark (f->binding);
      mark (f->ret);
    }

  for (k = MIN_FIXNUM; k <= MAX_FIXNUM; k++)
    mark (fixnums[k - MIN_FIXNUM]);

  /* ### file_table */

  /* 
   * Walk over the stack. The main function set up `stack_start` for
   * us, which is a pointer to one of its local variables. We take a
   * pointer to our local variable, everthing inbetween is scanned. We
   * assume that the stack grows downwards.
   */

  for (q = &here; q < stack_start; q++)
    mark (potential_node_pointer_p (*q));

  setjmp (buf);
  {
    T *a = (T*) &buf;
    T *e = (T*) (((char*)&buf) + sizeof (buf));
    for (q = a; q < e; q++)
      mark (potential_node_pointer_p (*q));
  }
}

void mark (T node)
{
  if (!node) return;

  if (node->mark)
    return;

  node->mark = 1;

  switch (node->type)
    {
    case TYPE_CONS:
      mark (node->u.cons.car);
      mark (node->u.cons.cdr);
      break;

    case TYPE_SYMBOL:
      mark (node->u.symbol.function);
      mark (node->u.symbol.more);
      break;
    }
}

T potential_node_pointer_p (void *x)
  /* Guess whether `x` is a pointer into one of our segments and if so
     return a pointer to the potential node, otherwise return NIL. */
{
  struct segment *s;

  for (s = segments; s; s = s->link)
    {
      /* Don't look */
      char *p = x;
      char *start = (char*) s->node;
      char *end = (char*) (s->node + s->size);
      if ((p >= start) && (p < end))
        return s->node + ((p - start) / sizeof (struct node));
    }

  /* fall through --- no segment found */
  return NIL;
}

void sweep (void)
{
  struct segment *s;
  int i;
  
  /* We simply traverse all segments and add each unmarked node to the
     free list and remove the mark on the marked ones. */
 
  for (s = segments; s; s = s->link)
    for (i = 0; i < s->size; i++)
      {
        T q = s->node + i;
        if (q->mark)
          q->mark = 0;
        else
          {
            if (q->type == TYPE_STRING)
              {
                // nfree += strlen (q->u.string.s + 1);
                free (q->u.string.s);
              }
            q->mark = 1;
            q->u.cons.car = NIL;
            q->u.cons.cdr = freelist;
            freelist = s->node + i;
            nfree += sizeof (struct node);
          }
      }
}