Simple GC

gc.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef enum _Type Type;
enum _Type {
  TYPE_INT,
  TYPE_PAIR,
};

typedef struct _Object Object;
struct _Object {
  bool marked;
  Object *next;
  Type type;
  union {
    int value;
    struct {
      Object *head;
      Object *tail;
    };
  };
};

static const int STACK_MAX = 256;
static const int INITIAL_GC_THRESHOLD = 8;

typedef struct _Machine Machine;
struct _Machine {
  Object *stack[STACK_MAX];
  Object *origin;
  int size;
  int number;
  int max;
};

Machine *machine_new()
{
  Machine *machine;
  machine = (Machine *) malloc(sizeof(Machine));
  machine->size = 0;
  machine->origin = NULL;
  machine->number = 0;
  machine->max = INITIAL_GC_THRESHOLD;
  return machine;
}

void machine_free(Machine *machine)
{
  free(machine);
}

void machine_push(Machine *machine, Object *object)
{
  if (machine->size >= STACK_MAX) {
    exit(1);
  }
  machine->stack[machine->size++] = object;
}

Object *machine_pop(Machine *machine)
{
  if (machine->size <= 0) {
    exit(1);
  }
  return machine->stack[--(machine->size)];
}

void object_mark(Object *object)
{
  if (object->marked) {
    return;
  }
  object->marked = true;
  if (object->type == TYPE_PAIR) {
    object_mark(object->head);
    object_mark(object->tail);
  } else {
    printf("%d marked\n", object->value);
  }
}

void machine_mark_all(Machine *machine)
{
  for (int i = 0; i < machine->size; ++i) {
    object_mark(machine->stack[i]);
  }
}

void object_free(Object *object)
{
  free(object);
}

int machine_sweep(Machine *machine)
{
  int count = 0;
  Object **object = &machine->origin;
  while (*object) {
    if (!(*object)->marked) {
      Object *unreached = *object;
      *object = unreached->next;
      object_free(unreached);
      ++count;
    } else {
      (*object)->marked = false;
      object = &(*object)->next;
    }
  }
  return count;
}

void machine_collect_garbage(Machine *machine)
{
  int number, count;
  number = machine->number;
  machine_mark_all(machine);
  count = machine_sweep(machine);
  machine->max = number * 2;
  printf("GC: %d %d\n", number, count);
}

Object *object_new(Machine *machine, Type type)
{
  if (machine->number >= machine->max) {
    machine_collect_garbage(machine);
  }

  Object *object;
  object = (Object *) malloc(sizeof(Object));
  object->marked = false;
  object->type = type;

  object->next = machine->origin;
  machine->origin = object;
  ++(machine->number);
  return object;
}

Object *machine_push_int(Machine *machine, int value)
{
  Object *object;
  object = object_new(machine, TYPE_INT);
  object->value = value;
  machine_push(machine, object);
  return object;
}

Object *machine_push_pair(Machine *machine)
{
  Object *object;
  object = object_new(machine, TYPE_PAIR);
  object->tail = machine_pop(machine);
  object->head = machine_pop(machine);
  machine_push(machine, object);
  return object;
}

int main()
{
  Machine *machine = machine_new();
  machine_push_int(machine, 1);
  machine_push_int(machine, 2);
  machine_pop(machine);
  machine_pop(machine);
  machine_collect_garbage(machine);
  machine_free(machine);
  return 0;
}