main.c

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

#define STACK_MAX_CAP 256
#define INIT_OBJECT_THRESHOLD 8

typedef enum
{
    OBJ_INT,
    OBJ_PAIR
} ObjectType;

typedef struct Object
{
    ObjectType type;
    int marked;
    struct Object *next;
    union
    {
        int value;

        struct
        {
            struct Object *head;
            struct Object *tail;
        };
    };

} Object;

typedef struct
{
    Object *stack[STACK_MAX_CAP];
    int stackSize;

    // 제일 마지막에 생성된 객체를 가리킴.
    Object *firstObject;

    int numberOfObjects;

    int maxObjects;
} VM;

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

VM *createVM()
{
    VM *vm = malloc(sizeof(VM));
    vm->stackSize = 0;
    vm->firstObject = NULL;
    vm->numberOfObjects = 0;
    vm->maxObjects = INIT_OBJECT_THRESHOLD;

    return vm;
}

void mark(Object *object)
{
    if (object->marked)
        return;

    object->marked = 1;

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

// stack을 순회하며 모두 1로 mark
void markAll(VM *vm)
{
    for (int i = 0; i < vm->stackSize; i++)
    {
        mark(vm->stack[i]);
    }
}

void sweep(VM *vm)
{
    Object **obj = &vm->firstObject;
    while (*obj)
    {
        if (!(*obj)->marked)
        {
            Object *dead = *obj;
            *obj = dead->next;
            free(dead);

            vm->numberOfObjects--;
        }
        else
        {
            (*obj)->marked = 0; // 다음 GC 사이클을 위해 0으로 초기화
            obj = &(*obj)->next;
        }
    }
}

// GC cycle : 매 GC 사이클 마다, stack에 있는 지를 기준으로 죽은 (0) 객체를 판별함. - markAll
// cycle이 끝날 때 살아있는(1) 객체는 다음 사이클을 위해 다시 0 으로 초기화 하여야함 - sweep 에서 진행
// -> 1로 냅둔 상태로 stack 에서 사라지면, 새로 죽었는지 살았는지 체크를 할 수 없음
// -> mark() 함수에서 이미 marked = 1 인 Object인 경우 바로 return 이 되도록 설계되었기 때문에. (무한 재귀 호출 방지)
// gc 함수에서 현재 상황에 맞게 maxObjects(threshold)를 조절해야함.
void gc(VM *vm)
{
    int numObjectsBefore = vm->numberOfObjects;
    markAll(vm);
    sweep(vm);

    vm->maxObjects = vm->numberOfObjects == 0 ? INIT_OBJECT_THRESHOLD : vm->numberOfObjects * 2;

    printf("Colleted %d objects, %d remaining\n", numObjectsBefore - vm->numberOfObjects, vm->numberOfObjects);
}

// Object를 새로 만들 때, 현재 객체 수가 maxObjects 에 도달했다면 garbage collecting 진행.
Object *createObject(VM *vm, ObjectType type)
{
    if (vm->numberOfObjects == vm->maxObjects)
        gc(vm);

    Object *newObject = malloc(sizeof(Object));
    newObject->type = type;
    newObject->marked = 0;
    newObject->next = vm->firstObject;
    vm->firstObject = newObject;

    vm->numberOfObjects++;

    return newObject;
}

Object *pop(VM *vm)
{
    assert(vm->stackSize > 0, "Stack is Empty\n");
    // ex) size == 1 이면 0번째 index 하나 있으니까 --vm->stackSize (o) , vm->stackSize-- (x)
    return vm->stack[--vm->stackSize];
}

// stack에 삽입
void push(VM *vm, Object *object)
{
    assert(vm->stackSize < STACK_MAX_CAP, "Stack Overflow\n");
    vm->stack[vm->stackSize++] = object;
}

// Object에 대한 설정은 createObject에서 다 하고 value만 push에서 설정
void pushInt(VM *vm, int data)
{
    Object *newObject = createObject(vm, OBJ_INT);
    newObject->value = data;
    push(vm, newObject);
}

Object *pushPair(VM *vm)
{
    Object *first = pop(vm);
    Object *second = pop(vm);

    Object *newObject = createObject(vm, OBJ_PAIR);
    newObject->head = first;
    newObject->tail = second;

    push(vm, newObject);

    return newObject;
}

void freeVM(VM *vm)
{
    printf("--Free VM--\n");
    vm->stackSize = 0;
    gc(vm);
    free(vm);
}

void test1()
{
    printf("Test 1: Objects on stack are preserved.\n");
    VM *vm = createVM();

    pushInt(vm, 1);
    pushInt(vm, 2);

    gc(vm);
    assert(vm->numberOfObjects == 2, "Should have 2 preserved objects.");
    freeVM(vm);

    printf("\n");
}

void test2()
{
    printf("Test 2: Dead objects are collected.\n");
    VM *vm = createVM();
    pushInt(vm, 1);
    pushInt(vm, 2);
    pop(vm);
    pop(vm);

    gc(vm);
    assert(vm->numberOfObjects == 0, "Should have 2 collected objects.");
    freeVM(vm);

    printf("\n");
}

void test3()
{
    printf("Test 3: Reach nested objects.\n");
    VM *vm = createVM();
    pushInt(vm, 1);
    pushInt(vm, 2);
    pushPair(vm);
    pushInt(vm, 3);
    pushInt(vm, 4);
    pushPair(vm);
    pushPair(vm);

    gc(vm);
    assert(vm->numberOfObjects == 7, "Should have reached objects.");
    freeVM(vm);

    printf("\n");
}

void test4()
{
    printf("Test 4: Handle cycles.\n");
    VM *vm = createVM();
    pushInt(vm, 1);
    pushInt(vm, 2);
    Object *a = pushPair(vm);
    pushInt(vm, 3);
    pushInt(vm, 4);
    Object *b = pushPair(vm);

    a->tail = b;
    b->tail = a;

    // 2, 4 더 이상 참조되지 않으므로 collect 될 예정
    gc(vm);
    assert(vm->numberOfObjects == 4, "Should have collected objects.");
    freeVM(vm);

    printf("\n");
}

int main(int argc, char const *argv[])
{
    test1();
    test2();
    test3();
    test4();
    return 0;
}