root/heap.c

/* [<][>][^][v][top][bottom][index][help] */

DEFINITIONS

This source file includes following definitions.
  1. check_gc
  2. alloc_object
  3. CRB_literal_to_crb_string
  4. CRB_create_crowbar_string
  5. CRB_string_substr
  6. CRB_create_array
  7. CRB_array_resize
  8. CRB_array_add
  9. CRB_array_insert
  10. CRB_array_remove
  11. CRB_create_assoc
  12. CRB_add_assoc_member
  13. CRB_search_assoc_member
  14. crb_create_scope_chain
  15. CRB_create_native_pointer
  16. CRB_check_native_pointer_type
  17. crb_create_stack_trace_line
  18. CRB_create_exception
  19. gc_mark
  20. gc_reset_mark
  21. gc_mark_value
  22. gc_mark_objects
  23. gc_dispose_object
  24. gc_sweep_objects
  25. crb_garbage_collect

#include <stdio.h>
#include <string.h>
#include "MEM.h"
#include "DBG.h"
#include "crowbar.h"

static void
check_gc(CRB_Interpreter *inter)
{
#if 0
    crb_garbage_collect(inter);
#endif
    if (inter->heap.current_heap_size > inter->heap.current_threshold) {
        /* fprintf(stderr, "garbage collecting..."); */
        crb_garbage_collect(inter);
        /* fprintf(stderr, "done.\n"); */

        inter->heap.current_threshold
            = inter->heap.current_heap_size + HEAP_THRESHOLD_SIZE;
    }
}

static CRB_Object *
alloc_object(CRB_Interpreter *inter, ObjectType type)
{
    CRB_Object *ret;

    check_gc(inter);
    ret = MEM_malloc(sizeof(CRB_Object));
    inter->heap.current_heap_size += sizeof(CRB_Object);
    ret->type = type;
    ret->marked = CRB_FALSE;
    ret->prev = NULL;
    ret->next = inter->heap.header;
    inter->heap.header = ret;
    if (ret->next) {
        ret->next->prev = ret;
    }

    return ret;
}

CRB_Object *
CRB_literal_to_crb_string(CRB_Interpreter *inter, char *str)
{
    CRB_Object *ret;

    ret = alloc_object(inter, STRING_OBJECT);
    ret->u.string.string = str;
    ret->u.string.is_literal = CRB_TRUE;

    return ret;
}

CRB_Object *
CRB_create_crowbar_string(CRB_Interpreter *inter, char *str)
{
    CRB_Object *ret;

    ret = alloc_object(inter, STRING_OBJECT);
    ret->u.string.string = str;
    inter->heap.current_heap_size += strlen(str) + 1;
    ret->u.string.is_literal = CRB_FALSE;

    return ret;
}

CRB_Object *
CRB_string_substr(CRB_Interpreter *inter, CRB_LocalEnvironment *env,
                  CRB_Object *str, int from, int len, int line_number)
{
    int org_len = strlen(str->u.string.string);
    char *new_str;

    if (from < 0 || from >= org_len) {
        crb_runtime_error(inter, env, line_number,
                          STRING_POS_OUT_OF_BOUNDS_ERR,
                          CRB_INT_MESSAGE_ARGUMENT, "len", org_len,
                          CRB_INT_MESSAGE_ARGUMENT, "pos", from,
                          CRB_MESSAGE_ARGUMENT_END);
    }
    if (len < 0 || from + len >= org_len) {
        crb_runtime_error(inter, env, line_number, STRING_SUBSTR_LEN_ERR,
                          CRB_INT_MESSAGE_ARGUMENT, "len", len,
                          CRB_MESSAGE_ARGUMENT_END);
    }
    new_str = MEM_malloc(len+1);
    strncpy(new_str, str->u.string.string + from, len);
    new_str[len] = '\0';
    return CRB_create_crowbar_string(inter, new_str);
}

CRB_Object *
CRB_create_array(CRB_Interpreter *inter, int size)
{
    CRB_Object *ret;

    ret = alloc_object(inter, ARRAY_OBJECT);
    ret->u.array.size = size;
    ret->u.array.alloc_size = size;
    ret->u.array.array = MEM_malloc(sizeof(CRB_Value) * size);
    inter->heap.current_heap_size += sizeof(CRB_Value) * size;

    return ret;
}

void
CRB_array_resize(CRB_Interpreter *inter, CRB_Object *obj, int new_size)
{
    int new_alloc_size;
    CRB_Boolean need_realloc;
    int i;

    check_gc(inter);
    
    if (new_size > obj->u.array.alloc_size) {
        new_alloc_size = obj->u.array.alloc_size * 2;
        if (new_alloc_size < new_size) {
            new_alloc_size = new_size + ARRAY_ALLOC_SIZE;
        } else if (new_alloc_size - obj->u.array.alloc_size
                   > ARRAY_ALLOC_SIZE) {
            new_alloc_size = obj->u.array.alloc_size + ARRAY_ALLOC_SIZE;
        }
        need_realloc = CRB_TRUE;
    } else if (obj->u.array.alloc_size - new_size > ARRAY_ALLOC_SIZE) {
        new_alloc_size = new_size;
        need_realloc = CRB_TRUE;
    } else {
        need_realloc = CRB_FALSE;
    }
    if (need_realloc) {
        check_gc(inter);
        obj->u.array.array = MEM_realloc(obj->u.array.array,
                                         new_alloc_size * sizeof(CRB_Value));
        inter->heap.current_heap_size
            += (new_alloc_size - obj->u.array.alloc_size) * sizeof(CRB_Value);
        obj->u.array.alloc_size = new_alloc_size;
    }
    for (i = obj->u.array.size; i < new_size; i++) {
        obj->u.array.array[i].type = CRB_NULL_VALUE;
    }
    obj->u.array.size = new_size;
}

void
CRB_array_add(CRB_Interpreter *inter, CRB_Object *obj, CRB_Value *v)
{
    DBG_assert(obj->type == ARRAY_OBJECT, ("bad type..%d\n", obj->type));

    CRB_array_resize(inter, obj, obj->u.array.size + 1);
    obj->u.array.array[obj->u.array.size-1] = *v;
}

void
CRB_array_insert(CRB_Interpreter *inter, CRB_LocalEnvironment *env,
                 CRB_Object *obj, int pos,
                 CRB_Value *new_value, int line_number)
{
    int i;
    DBG_assert(obj->type == ARRAY_OBJECT, ("bad type..%d\n", obj->type));

    if (pos < 0 || pos > obj->u.array.size) {
        crb_runtime_error(inter, env, line_number,
                          ARRAY_INDEX_OUT_OF_BOUNDS_ERR,
                          CRB_INT_MESSAGE_ARGUMENT, "size", obj->u.array.size,
                          CRB_INT_MESSAGE_ARGUMENT, "index", pos,
                          CRB_MESSAGE_ARGUMENT_END);
    }
    CRB_array_resize(inter, obj, obj->u.array.size + 1);
    for (i = obj->u.array.size-2; i >= pos; i--) {
        obj->u.array.array[i+1] = obj->u.array.array[i];
    }
    obj->u.array.array[pos] = *new_value;
}

void
CRB_array_remove(CRB_Interpreter *inter, CRB_LocalEnvironment *env,
                 CRB_Object *obj, int pos, int line_number)
{
    int i;

    DBG_assert(obj->type == ARRAY_OBJECT, ("bad type..%d\n", obj->type));
    if (pos < 0 || pos > obj->u.array.size-1) {
        crb_runtime_error(inter, env, line_number,
                          ARRAY_INDEX_OUT_OF_BOUNDS_ERR,
                          CRB_INT_MESSAGE_ARGUMENT, "size", obj->u.array.size,
                          CRB_INT_MESSAGE_ARGUMENT, "index", pos,
                          CRB_MESSAGE_ARGUMENT_END);
    }
    for (i = pos+1; i < obj->u.array.size; i++) {
        obj->u.array.array[i-1] = obj->u.array.array[i];
    }
    CRB_array_resize(inter, obj, obj->u.array.size - 1);
}

CRB_Object *
CRB_create_assoc(CRB_Interpreter *inter)
{
    CRB_Object *ret;

    ret = alloc_object(inter, ASSOC_OBJECT);
    ret->u.assoc.member_count = 0;
    ret->u.assoc.member = NULL;

    return ret;
}

void
CRB_add_assoc_member(CRB_Interpreter *inter, CRB_Object *assoc,
                     char *name, CRB_Value *value)
{
    AssocMember *member_p;

    check_gc(inter);
    member_p = MEM_realloc(assoc->u.assoc.member,
                           sizeof(AssocMember)
                           * (assoc->u.assoc.member_count+1));
    member_p[assoc->u.assoc.member_count].name = name;
    member_p[assoc->u.assoc.member_count].value = *value;
    assoc->u.assoc.member = member_p;
    assoc->u.assoc.member_count++;
    inter->heap.current_heap_size += sizeof(AssocMember);
}

CRB_Value *
CRB_search_assoc_member(CRB_Object *assoc, char *member_name)
{
    CRB_Value *ret = NULL;
    int i;

    if (assoc->u.assoc.member_count == 0)
        return NULL;

    for (i = 0; i < assoc->u.assoc.member_count; i++) {
        if (!strcmp(assoc->u.assoc.member[i].name, member_name)) {
            ret = &assoc->u.assoc.member[i].value;
            break;
        }
    }

    return ret;
}

CRB_Object *
crb_create_scope_chain(CRB_Interpreter *inter)
{
    CRB_Object *ret;

    ret = alloc_object(inter, SCOPE_CHAIN_OBJECT);
    ret->u.scope_chain.frame = NULL;
    ret->u.scope_chain.next = NULL;

    return ret;
}

CRB_Object *
CRB_create_native_pointer(CRB_Interpreter *inter, void *pointer,
                          CRB_NativePointerInfo *info)
{
    CRB_Object *ret;

    ret = alloc_object(inter, NATIVE_POINTER_OBJECT);
    ret->u.native_pointer.pointer = pointer;
    ret->u.native_pointer.info = info;

    return ret;
}

CRB_Boolean
CRB_check_native_pointer_type(CRB_Object *native_pointer,
                              CRB_NativePointerInfo *info)
{
    return native_pointer->u.native_pointer.info == info;
}

CRB_Object *
crb_create_stack_trace_line(CRB_Interpreter *inter,
                            CRB_LocalEnvironment *env, int line_number)
{
    char        *func_name;
    CRB_Object  *new_line;
    CRB_Value   new_line_value;
    CRB_Value   value;
    int         stack_count = 0;

    new_line = CRB_create_assoc(inter);
    if (env) {
        if (env->current_function_name) {
            func_name = env->current_function_name;
        } else {
            func_name = "anonymous closure";
        }
    } else {
        func_name = "top level";
    }
    
    new_line_value.type = CRB_ASSOC_VALUE;
    new_line_value.u.object = new_line;
    CRB_push_value(inter, &new_line_value);
    stack_count++;

    value.type = CRB_STRING_VALUE;
    value.u.object = CRB_literal_to_crb_string(inter, func_name);
    CRB_push_value(inter, &value);
    stack_count++;
    
    CRB_add_assoc_member(inter, new_line, EXCEPTION_MEMBER_FUNCTION_NAME,
                         &value);

    value.type = CRB_INT_VALUE;
    value.u.int_value = line_number;
    CRB_add_assoc_member(inter, new_line, EXCEPTION_MEMBER_LINE_NUMBER,
                         &value);

    CRB_shrink_stack(inter, stack_count);

    return new_line;
}

#if 0
CRB_Object *
CRB_create_exception(CRB_Interpreter *inter, CRB_LocalEnvironment *env,
                     CRB_Object *message, int line_number)
{
    CRB_Object  *ret;
    CRB_Value   value;
    CRB_Object  *stack_trace; /* CRB_Array */

    ret = CRB_create_assoc(inter);

    value.type = CRB_STRING_VALUE;
    value.u.object = message;
    CRB_add_assoc_member(inter, ret, EXCEPTION_MEMBER_MESSAGE, &value);
   
    stack_trace = CRB_create_array(inter, 0);
    value.type = CRB_ASSOC_VALUE;
    value.u.object = crb_create_stack_trace_line(inter, env, line_number);
    CRB_array_add(inter, stack_trace, &value);

    value.type = CRB_ARRAY_VALUE;
    value.u.object = stack_trace;
    CRB_add_assoc_member(inter, ret, EXCEPTION_MEMBER_STACK_TRACE, &value);

    return ret;
}
#endif

static void gc_mark_value(CRB_Value *v);

static void
gc_mark(CRB_Object *obj)
{
    if (obj == NULL)
        return;

    if (obj->marked)
        return;

    obj->marked = CRB_TRUE;

    if (obj->type == ARRAY_OBJECT) {
        int i;
        for (i = 0; i < obj->u.array.size; i++) {
            gc_mark_value(&obj->u.array.array[i]);
        }
    } else if (obj->type == ASSOC_OBJECT) {
        int i;
        for (i = 0; i < obj->u.assoc.member_count; i++) {
            gc_mark_value(&obj->u.assoc.member[i].value);
        }
    } else if (obj->type == SCOPE_CHAIN_OBJECT) {
        gc_mark(obj->u.scope_chain.frame);
        gc_mark(obj->u.scope_chain.next);
    }
}

static void
gc_reset_mark(CRB_Object *obj)
{
    obj->marked = CRB_FALSE;
}


static void
gc_mark_value(CRB_Value *v)
{
    if (crb_is_object_value(v->type)) {
        gc_mark(v->u.object);
    } else if (v->type == CRB_CLOSURE_VALUE) {
        if (v->u.closure.environment) {
            gc_mark(v->u.closure.environment);
        }
    } else if (v->type == CRB_FAKE_METHOD_VALUE) {
        gc_mark(v->u.fake_method.object);
    }
}

static void
gc_mark_objects(CRB_Interpreter *inter)
{
    CRB_Object *obj;
    Variable *v;
    CRB_LocalEnvironment *lv;
    int i;

    for (obj = inter->heap.header; obj; obj = obj->next) {
        gc_reset_mark(obj);
    }
    
    for (v = inter->variable; v; v = v->next) {
        gc_mark_value(&v->value);
    }
    
    for (lv = inter->top_environment; lv; lv = lv->next) {
        gc_mark(lv->variable);
    }

    for (i = 0; i < inter->stack.stack_pointer; i++) {
        gc_mark_value(&inter->stack.stack[i]);
    }

    gc_mark(inter->current_exception);
}

static void
gc_dispose_object(CRB_Interpreter *inter, CRB_Object *obj)
{
    switch (obj->type) {
    case ARRAY_OBJECT:
        inter->heap.current_heap_size
            -= sizeof(CRB_Value) * obj->u.array.alloc_size;
        MEM_free(obj->u.array.array);
        break;
    case STRING_OBJECT:
        if (!obj->u.string.is_literal) {
            inter->heap.current_heap_size -= strlen(obj->u.string.string) + 1;
            MEM_free(obj->u.string.string);
        }
        break;
    case ASSOC_OBJECT:
        inter->heap.current_heap_size
            -= sizeof(AssocMember) * obj->u.assoc.member_count;
        MEM_free(obj->u.assoc.member);
        break;
    case SCOPE_CHAIN_OBJECT:
        break;
    case NATIVE_POINTER_OBJECT:
        if (obj->u.native_pointer.info->finalizer) {
            obj->u.native_pointer.info->finalizer(inter, obj);
        }
        break;
    case OBJECT_TYPE_COUNT_PLUS_1:
    default:
        DBG_assert(0, ("bad type..%d\n", obj->type));
    }
    inter->heap.current_heap_size -= sizeof(CRB_Object);
    MEM_free(obj);
}

static void
gc_sweep_objects(CRB_Interpreter *inter)
{
    CRB_Object *obj;
    CRB_Object *tmp;

    for (obj = inter->heap.header; obj; ) {
        if (!obj->marked) {
            if (obj->prev) {
                obj->prev->next = obj->next;
            } else {
                inter->heap.header = obj->next;
            }
            if (obj->next) {
                obj->next->prev = obj->prev;
            }
            tmp = obj->next;
            gc_dispose_object(inter, obj);
            obj = tmp;
        } else {
            obj = obj->next;
        }
    }
}

void
crb_garbage_collect(CRB_Interpreter *inter)
{
    gc_mark_objects(inter);
    gc_sweep_objects(inter);
}

/* [<][>][^][v][top][bottom][index][help] */