Implementation of Baby's first Garbage Collector from http://journal.stuffwithstuff.com/2013/12/08/babys-first-garbage-collector

gc.c

// http://journal.stuffwithstuff.com/2013/12/08/babys-first-garbage-collector/
//

#define STACK_MAX 256
#define INITIAL_GC_THRESHOLD 2

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

void gc(); // Pre-Declared for co-recursive usage

typedef enum {
  OBJ_INT,
  OBJ_PAIR
} ObjectType;

typedef struct sObject {
  unsigned char marked;

	struct sObject* next;

  ObjectType type;

  union {
    /* OBJ_INT */
    int value;

    /* OBJ_PAIR */
    struct {
      struct sObject* head;
      struct sObject* tail;
    };
  };
} Object;

typedef struct {
  Object* stack[STACK_MAX];
  int stackSize;
  int numObjects;
  int maxObjects;

	Object* firstObject;
} VM;

VM* newVM() {
  VM* vm = malloc(sizeof(VM));
  vm->stackSize = 0;
  vm->firstObject = NULL;
	vm->numObjects = 0;
  vm->maxObjects = INITIAL_GC_THRESHOLD;

  return vm;
}

void assert(int b, char* msg) {
	if(! b) {
		printf("%s\n", msg);
		exit(1);
	}
}

void push(VM* vm, Object* value) {
  assert(vm->stackSize < STACK_MAX, "Stack overflow!");
  vm->stack[vm->stackSize++] = value;
}

Object* pop(VM* vm) {
  assert(vm->stackSize > 0, "Stack underflow!");
  return vm->stack[--vm->stackSize];
}

Object* newObject(VM* vm, ObjectType type) {
	if (vm->numObjects >= vm->maxObjects) {
		printf("running gc\n");
		gc(vm);
	}

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

	object->next = vm->firstObject;
  vm->firstObject = object;

  vm->numObjects++;
  return object;
}

void pushInt(VM* vm, int intValue) {
  Object* object = newObject(vm, OBJ_INT);
  object->value = intValue;
  push(vm, object);
}

Object* pushPair(VM* vm) {
  Object* object = newObject(vm, OBJ_PAIR);
  object->tail = pop(vm);
  object->head = pop(vm);

  push(vm, object);
  return object;
}

char* showType(Object* object) {
	switch( object->type ) {
		case OBJ_INT:  return "Int";
		case OBJ_PAIR: return "Pair";
	}
}

void showIndent(int indent) {
	for(int i = 0; i < indent; i++) {
		printf(" ");
	}
}

void showValue(int indent, int details, Object* object) {
	showIndent(indent);
	printf("%p -> [%c] %s",
			object,
			" * "[object->marked],
			showType(object)
	);
	if(! details) {
		printf("\n");
	} else {
		switch( object->type ) {
			case OBJ_INT:
				printf(" (%d)", object->value);
				printf("\n");
				break;
			case OBJ_PAIR:
				printf("\n");
				showValue(indent + 2, details, object->head);
				showValue(indent + 2, details, object->tail);
				break;
		}
	}
}

void sweep(VM* vm)
{
	printf("sweeping\n");
  Object** object = &vm->firstObject;
	Object*  previous = NULL;
  while (*object) {
    if ((*object)->marked) {
      /* This object was reached, so unmark it (for the next GC) and move on to the next. */
			previous = *object;
      (*object)->marked = 0;
      object = &(*object)->next;
		} else {
      /* This object wasn't reached, so remove it from the list and free it. */
      Object* unreached = *object;

      *object = unreached->next;
			if(previous) {
				previous->next = *object;
			} else {
				vm->firstObject = *object;
			}

      free(unreached);
			vm->numObjects--;
    }
  }
}

void showVM(int indent, VM* vm) {
	printf("VM (%p) [Stack Size: %d] [Count: %d/%d]\n\n",
			vm,
			vm->stackSize,
			vm->numObjects,
			vm->maxObjects
	);

	printf("Heap:\n");
	for(int p = 0;  p < vm->stackSize; p++) {
		showValue(0, 1, vm->stack[p]);
	}

	printf("\nMemory:\n");
  Object* object = vm->firstObject;
	while(object != NULL) {
		showValue(0, 0, object);
		object = object->next;
	}
}

void mark(Object* object) {
  /* If already marked, we're done. Check this first
     to avoid recursing on cycles in the object graph. */
  if (object->marked) return;

  object->marked = 1;

  if (object->type == OBJ_PAIR) {
    mark(object->head);
    mark(object->tail);
  }
}

void markAll(VM* vm)
{
  for (int i = 0; i < vm->stackSize; i++) {
    mark(vm->stack[i]);
  }
}

void gc(VM* vm) {
  markAll(vm);
  sweep(vm);

  vm->maxObjects = vm->numObjects * 2;
}

int valadd(Object* object) {
	if(object->type == OBJ_INT) {
		return object->value;
	} else {
		return valadd(object->head) + valadd(object->tail);
	}
}

int addx(VM* vm) {
	Object* object1 = pop(vm);
	Object* object2 = pop(vm);
	return valadd(object1) + valadd(object2);
}

void add(VM* vm) {
	pushInt(vm, addx(vm));
}

void repl(VM* vm) {
	while(1) {
		char str[100];
		printf("Enter an int, or p\n");
		scanf("%s", str);
		if(str[0] == 'p') {
			pushPair(vm);
		} else if(str[0] == '+') {
			add(vm);
		} else {
			pushInt(vm, atoi(str));
		}
		showVM(0, vm);
	}
}

int main() {

	printf("creating a vm\n");
	VM* vm = newVM();
	showVM(0, vm);
	printf("\n\n");

	printf("pushing an int\n");
	Object* object = newObject(vm, OBJ_INT);
	object->value = 5;
	push(vm, object);
	showVM(0, vm);
	printf("\n\n");

	printf("pushing some pairs\n");
	pushInt(vm, 1);
	pushInt(vm, 2);
	pushInt(vm, 3);
	pushPair(vm);
	pushPair(vm);
	showVM(0, vm);
	printf("\n\n");

	printf("marking objects\n");
	markAll(vm);
	showVM(0, vm);
	printf("\n\n");

	printf("sweeping objects\n");
	sweep(vm);
	showVM(0, vm);
	printf("\n\n");

	printf("truncating stack\n");
	vm->stackSize--;
	showVM(0, vm);
	printf("\n\n");

	printf("running gc\n");
	gc(vm);
	showVM(0, vm);
	printf("\n\n");

	printf("running repl\n");
	repl(vm);
	printf("\n\n");

}