Aizu Advent Calendar 2013 - 3.c

void* malloc(size_t size_byte) {
    size_t size = size_byte * 8;

    Dlinked_list_node lst = mem_manager->mem_lst;
    Memory_info* mi = lst->data;

    while (lst->tail != DUMMY) {
        if (mi->state == MEM_INFO_STATE_FREE && size < mi->size) {
            break;
        }

        lst = lst->tail;
        mi = lst->data;
    }

    Dlinked_list_node new = get_new_memory_list_node();
    if (new == NULL) {
        return NULL;
    }
    Memory_info* new_mi = new->data;
    new_mi->base_addr = mi->base_addr + size;
    new_mi->size = mi->size - size;
    new_mi->state = MEM_INFO_STATE_FREE;

    mi->size = size;
    mi->state = MEM_INFO_STATE_ALLOC;

    insert_tail(lst, new);

    return (void*)(mi->base_addr);
}


void free(void* object) {
    uint32_t allocated_addr = (uint32_t)object;
    Dlinked_list_node lst = mem_manager->mem_lst;
    Memory_info* mi = lst->data;

    while (lst->tail != DUMMY) {
        if (mi->base_addr == allocated_addr) {
            break;
        }

        lst = lst->tail;
        mi = lst->data;
    }

    Dlinked_list_node head = lst->head, tail = lst->tail;
    Memory_info *head_mi = (Memory_info*)head->data, *tail_mi = (Memory_info*)tail->data;

    if (head_mi->state == MEM_INFO_STATE_FREE) {
        // merge head
        head_mi->size += mi->size;
        delete_node(lst);
    } else if (tail_mi->state == MEM_INFO_STATE_FREE) {
        if (lst == mem_manager->mem_lst) {
           mem_manager->mem_lst = lst->tail;
        }

        // merge tail
        tail_mi->base_addr -= mi->size;
        tail_mi->size += mi->size;
        delete_node(lst);
    } else {
        mi->state = MEM_INFO_STATE_FREE;
    }
}