Malloc

/*
 * mm_alloc.c
 *
 * Stub implementations of the mm_* routines.
 */

#include "mm_alloc.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define METADATA_SIZE (sizeof(struct block))
#define _GET_METADATA(ptr) ((struct block *)(ptr - METADATA_SIZE))

void *_get_memory(size_t size, struct block *prev);
void *_find_free_block(size_t size, struct block **prev);

void _split_block(struct block *block, size_t size);
void _merge_free_blocks(struct block *block);

int DBG = 0;

void *mm_malloc(size_t size)
{
    if (size <= 0)
        return NULL;

    // first allocation
    if (!head)
    {
        head = _get_memory(size, NULL);
        _mm_print("HEAD");
        return head->data;
    }

    struct block *prev;
    struct block *allocated = _find_free_block(size, &prev);
    if (!allocated) // if need to allocate new data
    {
        allocated = _get_memory(size, prev);
        _mm_print("MALLOC | ALLOCATED");
    }
    else // if found enough free space within free data
    {
        allocated->free = 0;
        memset(allocated->data, 0, size);

        _split_block(allocated, size);
        _mm_print("MALLOC | FOUND");
    }

    return allocated->data;
}

void *mm_realloc(void *ptr, size_t size)
{
    if (!ptr)
        return mm_malloc(size);
    if (!size)
    {
        mm_free(ptr);
        return NULL;
    }

    struct block *to_realloc = _GET_METADATA(ptr);

    if (to_realloc->size >= size)
    {
        to_realloc->size = size;
        _split_block(to_realloc, size);
        _mm_print("REALLOC | STAY IN SAME");
        return to_realloc->data;
    }
    else
    {
        void *new_mem = mm_malloc(size);
        if (!new_mem)
            return NULL;
        memmove(new_mem, ptr, to_realloc->size);
        mm_free(ptr);
        _mm_print("REALLOC | NEED MALLOC");
        return new_mem;
    }
}

void mm_free(void *ptr)
{
    if (!ptr)
        return;

    struct block *to_free = _GET_METADATA(ptr);
    if (to_free->free)
        return;

    to_free->free = 1;
    _merge_free_blocks(to_free);

    _mm_print("FREE");
}

void *_get_memory(size_t size, struct block *prev)
{
    struct block *allocated = sbrk(size + METADATA_SIZE);
    if (!allocated)
    {
        perror("malloc");
        return NULL;
    }

    memset(allocated, 0, size + METADATA_SIZE);
    allocated->next = NULL;
    allocated->prev = prev;
    if (prev)
        prev->next = allocated;
    allocated->size = size;
    allocated->free = 0;

    return allocated;
}

void *_find_free_block(size_t size, struct block **prev)
{
    struct block *ptr = head;
    *prev = NULL;
    while (ptr && (!ptr->free || ptr->size < size))
    {
        *prev = ptr;
        ptr = ptr->next;
    }
    if ((*prev) && (*prev)->free)
    {
        sbrk(size - (*prev)->size);
        (*prev)->size = size;
        return (*prev);
    }
    return ptr;
}

void _split_block(struct block *block, size_t size)
{
    if (block->size - size > METADATA_SIZE) // NEED TO SPLIT
    {
        struct block *new_block = ((void *)block->data + size);
        int old_size = block->size;

        if (block->next)
            block->next->prev = new_block;
        new_block->next = block->next;

        block->next = new_block;
        new_block->prev = block;

        block->size = size;
        new_block->free = 1;
        new_block->size = old_size - METADATA_SIZE - block->size;
    }
}

void _merge_free_blocks(struct block *block)
{
    if (block->next && block->next->free)
    {
        block->size += block->next->size + METADATA_SIZE;
        block->next = block->next->next;
        if (block->next)
            block->next->prev = block;
    }
    if (block->prev && block->prev->free)
    {
        _merge_free_blocks(block->prev);
    }
}

void _mm_print(char *s)
{
    if (!DBG)
        return;
    struct block *ptr = head;
    int counter = 0;

    printf("\n$$$$$ %s $$$$$\n", s);
    printf("!!! MEMORY !!!\n");
    while (ptr)
    {
        printf("###  %d\n", ++counter);
        printf("Cur        : %p\n", ptr);
        printf("Alloc Size : %ld\n", ptr->size);
        printf("Free       : %d\n", ptr->free);
        printf("Prev       : %p\n", ptr->prev);
        printf("Next       : %p\n", ptr->next);
        ptr = ptr->next;
    }
}