Initial commit

1 files changed, 235 insertions, 0 deletions

diff --git a/garbage_collector/garbage_collect.c b/garbage_collector/garbage_collect.c
new file mode 100644
index 0000000..6559182
--- /dev/null
+++ b/garbage_collector/garbage_collect.c
@@ -0,0 +1,235 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+
+#define STACK_MAX 256
+#define INITIAL_GC_THRESHOLD 8
+
+
+typedef enum {
+    OBJ_INT,
+    OBJ_PAIR
+} ObjectType;
+
+typedef struct sObject {
+    /* The next object in the list of all objects */
+    struct sObject* next;
+    unsigned char marked;
+    ObjectType type;
+
+    union {
+        /* OBJ_INT */
+        int value;
+
+        /* OBJ_PAIR */
+        struct {
+            struct sObject* head;
+            struct sObject* tail;
+        };
+    };
+} Object;
+
+
+typedef struct {
+    /* The total number of currently allocated objects. */
+    int numObjects;
+    /* The number of objects required to trigger a GC. */
+    int maxObjects;
+    /* The first object in the list of all objects. */
+    Object* firstObject;
+    Object* stack[STACK_MAX];
+    int stackSize;
+} VM;
+
+VM* newVM() {
+    VM* vm = malloc(sizeof(VM));
+    vm->stackSize = 0;
+    vm->numObjects = 0;
+    vm->maxObjects = INITIAL_GC_THRESHOLD;
+    vm->firstObject = NULL;
+    return vm;
+}
+
+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 sweep(VM* vm) {
+    Object** object = &vm->firstObject;
+    while (*object) {
+        if (!(*object)->marked) {
+            /* Remove unmarked object. */
+            Object* unreached = *object;
+            *object = unreached->next;
+            free(unreached);
+            vm->numObjects--;
+        } else {
+            /* Reset mark for next traversal */
+            (*object)->marked = 0;
+            object = &(*object)->next;
+        }
+    }
+}
+
+
+void assert(int condition, const char* message) {
+  if (!condition) {
+    printf("%s\n", message);
+    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];
+}
+
+
+void gc(VM* vm) {
+    int numObjects = vm->numObjects;
+
+    markAll(vm);
+    sweep(vm);
+
+    vm->maxObjects = vm->numObjects * 2;
+}
+
+Object* newObject(VM* vm, ObjectType type) {
+    if (vm->numObjects == vm->maxObjects) gc(vm);
+
+    Object* object = malloc(sizeof(Object));
+    object->type = type;
+
+    /* Insert into list of all objects. */
+    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;
+}
+
+void freeVM(VM *vm) {
+  vm->stackSize = 0;
+  gc(vm);
+  free(vm);
+}
+
+void test1() {
+  printf("Test 1: Objects on stack are preserved.\n");
+  VM* vm = newVM();
+  pushInt(vm, 1);
+  pushInt(vm, 2);
+
+  gc(vm);
+  assert(vm->numObjects == 2, "Should have preserved objects.");
+  freeVM(vm);
+}
+
+void test2() {
+  printf("Test 2: Unreached objects are collected.\n");
+  VM* vm = newVM();
+  pushInt(vm, 1);
+  pushInt(vm, 2);
+  pop(vm);
+  pop(vm);
+
+  gc(vm);
+  assert(vm->numObjects == 0, "Should have collected objects.");
+  freeVM(vm);
+}
+
+void test3() {
+  printf("Test 3: Reach nested objects.\n");
+  VM* vm = newVM();
+  pushInt(vm, 1);
+  pushInt(vm, 2);
+  pushPair(vm);
+  pushInt(vm, 3);
+  pushInt(vm, 4);
+  pushPair(vm);
+  pushPair(vm);
+
+  gc(vm);
+  assert(vm->numObjects == 7, "Should have reached objects.");
+  freeVM(vm);
+}
+
+static void test4() {
+  printf("Test 4: Handle cycles.\n");
+  VM* vm = newVM();
+  pushInt(vm, 1);
+  pushInt(vm, 2);
+  Object* a = pushPair(vm);
+  pushInt(vm, 3);
+  pushInt(vm, 4);
+  Object* b = pushPair(vm);
+
+  /* Set up a cycle, and also make 2 and 4 unreachable and collectible. */
+  a->tail = b;
+  b->tail = a;
+
+  gc(vm);
+  assert(vm->numObjects == 4, "Should have collected objects.");
+  freeVM(vm);
+}
+
+static void perfTest() {
+  printf("Performance Test.\n");
+  VM* vm = newVM();
+
+  for (int i = 0; i < 1000; i++) {
+    for (int j = 0; j < 20; j++) {
+      pushInt(vm, i);
+    }
+
+    for (int k = 0; k < 20; k++) {
+      pop(vm);
+    }
+  }
+  freeVM(vm);
+}
+
+int main(int argc, const char * argv[]) {
+  test1();
+  test2();
+  test3();
+  test4();
+  perfTest();
+
+  return 0;
+}