// Stack of root nodes.
typedef struct RootNodes {
    Object **buf;
    size_t size;
    size_t cap;
} RootNodes;

typedef struct GC {
    RootNodes roots;
    Object *obj_list;
    // Free list keeps track of the offset numbers from the obj_list
    size_t *free_list;
    size_t obj_cap;
    size_t fl_pos;
    size_t available_slots;
} GC;

// FIXME: small value for testing purposes
#define GC_INITIAL_HEAP 16
#define GC_ROOTS_CAP 8

static GC gc;

void
push_root(Object *obj) {
    if (gc.roots.size == gc.roots.cap) {
        gc.roots.cap *= 2;
        gc.roots.buf = realloc(gc.roots.buf, gc.roots.cap * sizeof(Object *));
    }
    gc.roots.buf[gc.roots.size++] = obj;
}

Object *
pop_root(void) {
    return gc.roots.buf[gc.roots.size--];
}

void
init_gc(void) {
    gc = (GC){
        .obj_cap = GC_INITIAL_HEAP,
        .available_slots = GC_INITIAL_HEAP,
    };
    gc.free_list = malloc(GC_INITIAL_HEAP * sizeof(size_t));
    gc.obj_list = malloc(GC_INITIAL_HEAP * sizeof(Object));
    gc.roots.buf = malloc(GC_ROOTS_CAP * sizeof(Object*));
    gc.roots.cap = GC_ROOTS_CAP;

    // The free list stores the offset from the initial position for all
    // available slots.
    for (size_t i = 0; i < gc.obj_cap; i++) {
        gc.free_list[i] = i;
    }
}

Object *
get_obj(size_t offset) {
    return gc.obj_list + offset;
}

void
mark_obj(Object *obj) {
    if (obj->marked) {
        return;
    }
    obj->marked = true;
    if (obj->type == OBJ_TYPE_PAIR) {
        mark_obj(obj->car);
        mark_obj(obj->cdr);
    }
}

void
mark_and_sweep(void) {
    // Mark.
    for (size_t i = 0; i < gc.roots.size; i++) {
        if (gc.roots.buf[i]->marked) {
            continue;
        }
        mark_obj(gc.roots.buf[i]);
    }

    // Reset the free list.
    gc.fl_pos = 0;
    gc.available_slots = 0;

    // Sweep.
    for (size_t i = 0; i < gc.obj_cap; i++) {
        if (!gc.obj_list[i].marked) {
            // Free heap allocated memory for this object if needed.
            Object obj = gc.obj_list[i];
            if (obj.type == OBJ_TYPE_SYMBOL) {
                free(obj.symbol);
            } else if (obj.type == OBJ_TYPE_STRING) {
                free(obj.string);
            }

            gc.free_list[gc.available_slots++] = i;
        }
        gc.obj_list[i].marked = false;
    }
}

Object *
alloc_object(ObjectType type) {
    if (gc.available_slots == 0) {
        printf("triggering GC\n");
        mark_and_sweep();
        if (gc.available_slots == 0) {
            printf("NOT MORE MEMORY AVAILABLE\n");
            printf("-------------- ROOTS -------------- \n");
            for (size_t i = 0; i < gc.roots.size; i++) {
                display(gc.roots.buf[i]);
                printf("\n");
            }
            printf("------------- OBJECTS ------------- \n");
            for (size_t i = 0; i < gc.obj_cap; i++) {
                printf("i: %ld -> ", i);
                Object *obj = &gc.obj_list[i];
                display(obj);
                printf("\n");
            }
            exit(EXIT_FAILURE);
            // TODO: grow heap tables.
            // NOTE: When growing the tables, we WILL lose the pointer
            // references! Should we work with offsets all the way?  That is for
            // cdr and car? Should we have a utility function? All in all, we
            // need to refactor the codebase first to work with pointer offsets
            // rather than objects.  This issue is very important, if we are in
            // the middle of an operation that tries to allocate memory but we
            // had saved pointers to some object, the pointer references may be
            // invalidated, crashing or worse, silently returning garbage! Let's
            // move on for now implementing the GC and we will revisit this part
            // later.
        }
    }
    size_t slot = gc.free_list[gc.fl_pos++];
    gc.available_slots--;
    Object *obj = get_obj(slot);
    obj->type = type;
    return obj;
}