Garbage Collection

Routine for Garbage Collection

# include"stdio.h"
# include"conio.h"
# include"iostrem.h"
struct cell
{
int mark:1;
struct cell *c[2];}
struct cell *free;
struct cell heap[HEAPSIZE];
struct cell *roots[ROOTS];

/* Initially all cells are on free list. Use c[0] to link members of free list. */
void init_heap()
{
for (i=0; i < HEAPSIZE-1; i++)
heap[i].c[0] = &(heap[i+1]);
heap[HEAPSIZE-1].c[0] = 0;
free = &(heap[0]);
}

struct cell *allocate()
{
struct cell *a;
if (!free) { /* no more room => */
gc(); /* try gc */
if (!free) /* still no more room */
die();
};
a = free;
free = free->c[0];
return a;


void gc()
{
for (i = 0; i < ROOTS; i++)
mark(roots[i]);
sweep();
}

void mark(struct cell *cell)
{
if (!cell->mark)
{
cell->mark = 1;
mark(cell->c[0]);
mark(cell->c[1]);
}
}

void sweep()
{
for (i = 0; i < HEAPSIZE; i++)
if (heap[i].mark)
heap[i].mark = 0;
else
{
heap[i].c[0] = free;
free = &(heap[i]);
}
}