#include "malloc.h"
#include "malloc_private.h"
#include "stdio.h"

heap_ll * _heap_head[NB_TASKS_MAX];

unsigned int _heap_base[NB_TASKS_MAX];
unsigned int _heap_length[NB_TASKS_MAX];

int _first_malloc[NB_TASKS_MAX] = { 0 };


#if MALLOC_SELECTED == 1

#elif MALLOC_SELECTED == 2
    heap_ll * _prev_next_last_allocted[NB_TASKS_MAX] = { 0 };
#else
    #define MAX_SIZE_POW2_TAB 28 
    #define GET_TAB_INDEX(size) (size == 0x00000008) ? 0 :\
                            (size <= 0x00000010) ? 1 :\
                            (size <= 0x00000020) ? 2 :\
                            (size <= 0x00000040) ? 3 :\
                            (size <= 0x00000080) ? 4 :\
                            (size <= 0x00000100) ? 5 :\
                            (size <= 0x00000200) ? 6 :\
                            (size <= 0x00000400) ? 7 :\
                            (size <= 0x00000800) ? 8 :\
                            (size <= 0x00001000) ? 9 :\
                            (size <= 0x00002000) ? 10 :\
                            (size <= 0x00004000) ? 11 :\
                            (size <= 0x00008000) ? 12 :\
                            (size <= 0x00010000) ? 13 :\
                            (size <= 0x00020000) ? 14 :\
                            (size <= 0x00040000) ? 15 :\
                            (size <= 0x00080000) ? 16 :\
                            (size <= 0x00100000) ? 17 :\
                            (size <= 0x00200000) ? 18 :\
                            (size <= 0x00400000) ? 19 :\
                            (size <= 0x00800000) ? 20 :\
                            (size <= 0x01000000) ? 21 :\
                            (size <= 0x02000000) ? 22 :\
                            (size <= 0x04000000) ? 23 :\
                            (size <= 0x08000000) ? 24 :\
                            (size <= 0x10000000) ? 25 :\
                            (size <= 0x20000000) ? 26 :\
                                                   27

    heap_ll * _pow2tab[NB_TASKS_MAX][MAX_SIZE_POW2_TAB] = {{ 0 }};
#endif

/* Todo: meilleure gestion des printf
//#if DEBUG_MALLOC == 1
unsigned int debug_level = 2;
#elif DEBUG_MALLOC == 0

#define giet_printf(level, ...)                 \
({                                           \
if (debug_level < level) {              \
giet_tty_printf(__VA_ARGS__);       \
}                                       \
})
*/


#if MALLOC_SELECTED == 1

heap_ll *get_prev_fit_chunk(unsigned int size) {
    int task_id = giet_global_task_id();
    if (_heap_head[task_id] == 0x0) {
        return ((heap_ll *) 0x01);
    }
    int found = 0;
    heap_ll * ptr_to_chunk_list = _heap_head[task_id];
    heap_ll * tmp = 0x0;
    heap_ll * prev = 0x0;
    heap_ll * prev_tmp = 0x0;
    while (ptr_to_chunk_list != 0x0) {
        if (size <= ptr_to_chunk_list->chunk_length) {
            if (tmp == 0x0 || ptr_to_chunk_list->chunk_length > tmp->chunk_length) {
                prev_tmp = prev;
                tmp = ptr_to_chunk_list;
                found = 1;
            }
        }
        prev = ptr_to_chunk_list;
        ptr_to_chunk_list = ptr_to_chunk_list->next;
    }
    if (found == 1) {
        return prev_tmp; // case when prev_tmp == 0x0 is handled in the calling function
    }
    else {
        return (heap_ll *) 0x1;
    }
}



void * malloc(unsigned int size) {
    int task_id = giet_global_task_id();

#if DEBUG_MALLOC == 1
    giet_tty_printf("############ MALLOC ############\n\n");
#endif
    if (size == 0) {
#if DEBUG_MALLOC == 1
        giet_tty_printf(" SIZE = 0 \n");
#endif
        return 0x0;
    }

    /****** First call to malloc ******/
    if (_first_malloc[task_id] == 0) {
        giet_heap_info(&_heap_base[task_id], &_heap_length[task_id]);

        if (_heap_length[task_id] == 0) {
            giet_tty_printf("*** Error: Malloc called in task %d while no heap was defined.\n", task_id);
            return 0x0;
        }
        _heap_head[task_id] = (heap_ll *) _heap_base[task_id];
        _heap_head[task_id]->chunk_length = _heap_length[task_id];
        _heap_head[task_id]->next = 0x0;


        _first_malloc[task_id] = 1;
    }

    /****** Size align ******/
    int size_align = size;
    if (size % 4 != 0) {
        size_align = ((size / 4) + 1) * 4;
    }


#if DEBUG_MALLOC == 1
    giet_tty_printf("Looking for size : %d\n", size_align + 4);
#endif
    /****** Get prev victim from the chunks list ******/
    heap_ll *victim;
    heap_ll *prev_victim;
    //// WORST

    if ((prev_victim = get_prev_fit_chunk(size_align + 4)) == (heap_ll *) 0x1) {
        return 0x0;		// no chunk of this size avaiable, 0x1 : no suitable chunk found
    }
    else {
        if (prev_victim != 0x0)	{
            // victim != HEAD
            victim = prev_victim->next;
        }
        else {
            victim = _heap_head[task_id];
        }
    }
    /****** Get Victim Base ******/
    unsigned int victim_vbase = (unsigned int) victim;	// overhead

    /****** update the chunks list ******/
    if (victim->chunk_length == size_align + 4) {
        // if it is an exact match
        if (prev_victim == 0x0)	{
            // if victim == head
            _heap_head[task_id] = victim->next;
        }
        else {
            prev_victim->next = victim->next;
        }
    } 
    else {
        // if its not an exact match then update chunk base and length
        heap_ll * tmp_chunk = victim;
        victim = (heap_ll *) (((unsigned int) victim) + (size_align + 4));
#if DEBUG_MALLOC == 1
        giet_tty_printf("NEXT CHUNK is at @ : 0x%x + 0x%x = 0x%x\n",
                (unsigned int) tmp_chunk,
                (unsigned int) ((size_align + 4) / 4),
                (unsigned int) victim);
#endif

        victim->chunk_length = tmp_chunk->chunk_length - (size_align + 4);
        victim->next = tmp_chunk->next;
        if (prev_victim == 0x0) {
            _heap_head[task_id] = victim;
        }
        else {
            prev_victim->next = victim;
        }
    }

    /****** Write Overhead ******/
    *((unsigned int *) victim_vbase) = size_align;	// writing overhead on the first word
#if DEBUG_MALLOC == 1
    giet_tty_printf("BLOCK SUCCESSFULLY ALLOCATED at @ 0x%x user will write at @ 0x%x\n\n"\
            ,(unsigned int)(victim_vbase),(unsigned int) (victim_vbase + 4));
#endif
    return (unsigned int *) (victim_vbase + 4);
}



/* this function tries to merge the block to free with chunks in the list if
 * they are contiguous
 * the block can be merged two times.
 */
void update_chunk_list(unsigned int block_base, unsigned int block_length) {
    /* entire heap is allocated : create a new block of size block_length and give it to the head  */
    int task_id = giet_global_task_id();
    if (_heap_head[task_id] == 0x0) {
        ((heap_ll *) block_base)->chunk_length = block_length;
        ((heap_ll *) block_base)->next = 0x0;
        _heap_head[task_id] = ((heap_ll *) block_base);
#if DEBUG_MALLOC == 1
        giet_tty_printf("****** NEW BLOCK ******\n"
                "@ : %x\n"
                "Length : %d o\n"
                "***********************\n",
                block_base,
                (unsigned int) (((heap_ll *) block_base)->chunk_length));
#endif
        return;
    }


    /* Test for each Chunk in my list if the block can be merged with */
    heap_ll *ptr_to_chunk_list = _heap_head[task_id]; // move through the list
    heap_ll *prev = 0x0; // pointer on the previous visited chunk in the list
    heap_ll *prev_block_base = 0x0; // pointer on the previous chunk of the chunk that contains the merged block in the list
    unsigned int chunk_length;
    int block_merged = 0; // =1 when the block has already been merged with a chunk in the list
    while (ptr_to_chunk_list != 0x0) {
        chunk_length = ptr_to_chunk_list->chunk_length;
        /*  [.....|ptr|block|.....] */
        if ((unsigned int) (ptr_to_chunk_list) + chunk_length == block_base) {
#if DEBUG_MALLOC == 1
            giet_tty_printf("****** BLOCK MERGED ******\n"
                    "CHUNK : %x of size %d o\n"
                    "merged with \n"
                    "BLOCK : %x of size %d o\n"
                    "***********************\n",
                    (unsigned int) ptr_to_chunk_list,
                    ptr_to_chunk_list->chunk_length, block_base,
                    block_length);
#endif

            /* update the size */
            ptr_to_chunk_list->chunk_length = chunk_length + block_length;

            /* [.....|ptr|[block|old_ptr]|.....]
             *  remove ptr from the list
             *  update next pointer
             *  update the previous chunk of block base to point to ptr
             */
            if (block_merged == 1) {
                prev->next = ptr_to_chunk_list->next;
                ptr_to_chunk_list->next = ((heap_ll *) block_base)->next;
                if (prev_block_base != 0x0) {
                    prev_block_base->next = ptr_to_chunk_list;
                }
                else {
                    _heap_head[task_id] = ptr_to_chunk_list;
                }
            }
            /****** for next turn ******/
            block_base = (unsigned int) ptr_to_chunk_list;
            block_length = ptr_to_chunk_list->chunk_length;
#if DEBUG_MALLOC == 1
            giet_tty_printf("****** NEW BLOCK ******\n"
                    "@ : %x\n"
                    "Length : %d o\n"
                    "***********************\n",
                    (unsigned int) ptr_to_chunk_list,
                    (unsigned int) (ptr_to_chunk_list->chunk_length));
#endif
            prev_block_base = prev;
            prev = ptr_to_chunk_list;
            ptr_to_chunk_list = ptr_to_chunk_list->next;
            block_merged = 1;
            continue;

        } // end [.....|ptr|block|.....]
        /*  [......|block|ptr|.....] */
        if (block_base + block_length == (unsigned int) ptr_to_chunk_list) {
#if DEBUG_MALLOC == 1
            giet_tty_printf("****** BLOCK MERGED ******\n"
                    "BLOCK : %x of size %d o\n"
                    "merged with \n"
                    "CHUNK : %x of size %d o\n"
                    "***********************\n",
                    block_base, block_length,
                    (unsigned int) ptr_to_chunk_list,
                    ptr_to_chunk_list->chunk_length);
#endif

            /* update the size */
            ((heap_ll *) block_base)->chunk_length = block_length + chunk_length;

            /* [.....|block|ptr|......] */
            if (block_merged == 0) {
                /* update next pointer
                 *  update the previous chunk of ptr to point to block_base
                 */
                ((heap_ll *) block_base)->next = ptr_to_chunk_list->next;
                if (prev == 0x0) {
                    _heap_head[task_id] = ((heap_ll *) block_base);
                }
                else {
                    prev->next = ((heap_ll *) block_base);
                }
            }
            /* [.....[old_ptr|block]|ptr|......] */
            else {
                /* remove ptr from the list */
                prev->next = ptr_to_chunk_list->next;
            }

            ptr_to_chunk_list = ((heap_ll *) block_base);
            block_length = ptr_to_chunk_list->chunk_length;
#if DEBUG_MALLOC == 1
            giet_tty_printf("****** NEW BLOCK ******\n"
                    "@ : %x\n"
                    "Length : %d o\n"
                    "***********************\n",
                    (unsigned int) ptr_to_chunk_list,
                    (unsigned int) (ptr_to_chunk_list->chunk_length));
#endif
            prev_block_base = prev;
            block_merged = 1;
        } // end [......|block|ptr|.....]
        prev = ptr_to_chunk_list;
        ptr_to_chunk_list = ptr_to_chunk_list->next;
    } // end while
    if (block_merged == 1) {
        return;
    }
    /* if the block cant be merge
     *  create new block and add it to the end of the list 
     */
    ((heap_ll *) block_base)->chunk_length = block_length;
    ((heap_ll *) block_base)->next = 0x0;
    prev->next = ((heap_ll *) block_base);
#if DEBUG_MALLOC == 1
    giet_tty_printf("****** NEW BLOCK ******\n"
            "@ : %x\n"
            "Length : %d o\n"
            "***********************\n",
            block_base,
            (unsigned int) (((heap_ll *) block_base)->chunk_length));
#endif
    return;

}


static void print_all_heap(void) {
    int task_id = giet_global_task_id();
    heap_ll * ptr_to_chunk_list = _heap_head[task_id];
    giet_tty_printf("################### PRINT ALL HEAP ######################\n");
    while (ptr_to_chunk_list != 0x0) {
        giet_tty_printf("CHUNK at @ : %x\n"
                "OVERHEAD : %d\n"
                "NEXT : %x\n\n",
                (unsigned int) ptr_to_chunk_list,
                ptr_to_chunk_list->chunk_length,
                (unsigned int) ptr_to_chunk_list->next);
        ptr_to_chunk_list = ptr_to_chunk_list->next;
    }
    giet_tty_printf("#########################################################\n");
}


/* Warning: the division doesn't seem to work well in the giet/soclib ? */
static void frag(int turn) {
    int task_id = giet_global_task_id();
    int nb_blocks = 0;
    int size = 0;
    heap_ll * ptr_to_chunk;
    ptr_to_chunk = _heap_head[task_id];
    while(ptr_to_chunk != 0x0) {
        size += ptr_to_chunk->chunk_length;
        nb_blocks += 1;
        ptr_to_chunk = ptr_to_chunk->next;
    }
    if (size != 0) {
        giet_tty_printf("%.3f\t%d\n", size / ((double) nb_blocks), turn);
    }
}

// End WORST_FIT
#elif MALLOC_SELECTED == 2 // Next Fit 

heap_ll * get_prev_fit_chunk(unsigned int size) {
    int task_id = giet_global_task_id();
    if (_heap_head[task_id] == 0x0) {
        return ((heap_ll *) 0x1);
    }

    heap_ll * ptr_to_chunk_list;
    heap_ll * prev = 0x0;
    heap_ll * tmp_turn = 0x0;

    if (_prev_next_last_allocted[task_id] == 0x0 || _prev_next_last_allocted[task_id]->next == 0x0) {
        ptr_to_chunk_list = _heap_head[task_id];
    }
    else
    {
        ptr_to_chunk_list = _prev_next_last_allocted[task_id]->next;
    }

    tmp_turn = (ptr_to_chunk_list == 0x0)?_heap_head[task_id]:ptr_to_chunk_list;
    do {
        if (ptr_to_chunk_list == 0x0) {
            // simulate circular list
            ptr_to_chunk_list = _heap_head[task_id];
            if (ptr_to_chunk_list == tmp_turn) break;
        }

        if (size <= ptr_to_chunk_list->chunk_length) {
            return prev;
        }
        prev = ptr_to_chunk_list;
        ptr_to_chunk_list = ptr_to_chunk_list->next;
    } while (ptr_to_chunk_list != tmp_turn);

    return (heap_ll *) 0x1;
}


void * malloc(unsigned int size) {

    int task_id = giet_global_task_id();
#if DEBUG_MALLOC == 1
    giet_tty_giet_tty_printf("############ MALLOC ############\n\n");
#endif
    if (size == 0) {
#if DEBUG_MALLOC == 1
        giet_tty_giet_tty_printf(" SIZE = 0 \n");
#endif
        return 0x0;
    }

    /****** First call to malloc ******/
    if (_first_malloc[task_id] == 0) {
        giet_heap_info(&_heap_base[task_id], &_heap_length[task_id]);

        if (_heap_length[task_id] == 0) {
            giet_tty_printf("*** Error: Malloc called in task %d while no heap was defined.\n", task_id);
            return 0x0;
        }

        _heap_head[task_id] = (heap_ll *) _heap_base[task_id];
        _heap_head[task_id]->chunk_length = _heap_length[task_id];
        _heap_head[task_id]->next = 0x0;

        _prev_next_last_allocted[task_id] = 0x0;

        _first_malloc[task_id] = 1;
    }

    /****** Size align ******/
    int size_align = size;
    if (size % 4 != 0) {
        size_align = ((size / 4) + 1) * 4;
    }


#if DEBUG_MALLOC == 1
    giet_tty_giet_tty_printf("Looking for size : %d\n", size_align + 4);
#endif
    /****** Get prev victim from the chunks list ******/
    heap_ll *victim;
    heap_ll *prev_victim;

    if ((prev_victim = get_prev_fit_chunk(size_align + 4)) == (heap_ll *) 0x1) {
        return 0x0;		// no chunk of this size avaiable, 0x1 : no suitable chunk found
    }
    else {
        if (prev_victim != 0x0) {
            // victim != _next_last_allocted
            if (prev_victim->next == 0x0) {
                // victim == HEAD
                victim = _heap_head[task_id];
            }
            else {
                victim = prev_victim->next;
            }
        }
        else
        {
            if (_prev_next_last_allocted[task_id] == 0x0 || _prev_next_last_allocted[task_id]->next == 0x0) {
                victim =_heap_head[task_id];
            }
            else {
                victim = _prev_next_last_allocted[task_id]->next;
            }
        }
    }

    /****** Get Victim Base ******/
    unsigned int victim_vbase = (unsigned int) victim; // overhead

    /****** update the chunks list ******/
    if (victim->chunk_length - (size_align + 4) < 8) {
        // if it is an exact match
        size_align = size_align + (victim->chunk_length - (size_align + 4));

        if (prev_victim == 0x0)	{
            // if victim == head
            if (_prev_next_last_allocted[task_id] == 0x0 || _prev_next_last_allocted[task_id]->next == 0x0) {
                _heap_head[task_id] = victim->next;
            }
            else {
                _prev_next_last_allocted[task_id]->next = victim->next;
            }
            _prev_next_last_allocted[task_id] = victim->next;
        }
        else {
            if (prev_victim->next == 0x0) {
                _heap_head[task_id] = victim->next;
            }
            else {
                prev_victim->next = victim->next;
            }
            _prev_next_last_allocted[task_id] = prev_victim;
        }
    } 
    else {
        // if its not an exact match then update chunk base and length
        heap_ll * tmp_chunk = victim;
        victim = (heap_ll *) (((unsigned int) victim) + (size_align + 4));
#if DEBUG_MALLOC == 1
        giet_tty_giet_tty_printf("NEXT CHUNK is at @ : 0x%x + 0x%x = 0x%x\n",
                (unsigned int) tmp_chunk,
                (unsigned int) ((size_align + 4) / 4),
                (unsigned int) victim);
#endif

        victim->chunk_length = tmp_chunk->chunk_length - (size_align + 4);
        victim->next = tmp_chunk->next;
        if (prev_victim == 0x0) {
            if (_prev_next_last_allocted[task_id] == 0x0 || _prev_next_last_allocted[task_id]->next == 0x0) {
                _heap_head[task_id] = victim;
            }
            else {
                _prev_next_last_allocted[task_id]->next = victim;
            }
            _prev_next_last_allocted[task_id] = victim->next;
        }
        else {
            if (prev_victim->next == 0x0) {
                _heap_head[task_id] = victim;
            }
            else {
                prev_victim->next = victim;
            }
            _prev_next_last_allocted[task_id] = prev_victim;
        }
    }

    /****** Write Overhead ******/
    *((unsigned int *) victim_vbase) = size_align;	// writing overhead on the first word
#if DEBUG_MALLOC == 1
    giet_tty_giet_tty_printf("BLOCK SUCCESSFULLY ALLOCATED at @ 0x%x user will write at @ 0x%x\n\n"\
            ,(unsigned int)(victim_vbase),(unsigned int )(victim_vbase + 4));
#endif
    return (unsigned int *) (victim_vbase + 4);
}



/* this function tries to merge the block to free with chunks in the list if they are contiguous
 * the block can be merged two times.
 */

void update_chunk_list(unsigned int block_base, unsigned int block_length) {
    int task_id = giet_global_task_id();
    /* entire heap is allocated : create a new block of size block_length and give it to the head  */
    if (_heap_head[task_id] == 0x0) {
        ((heap_ll *) block_base)->chunk_length = block_length;
        ((heap_ll *) block_base)->next = 0x0;
        _heap_head[task_id] = ((heap_ll *) block_base);
#if DEBUG_MALLOC == 1
        giet_tty_giet_tty_printf("****** NEW BLOCK ******\n"
                "@ : %x\n"
                "Length : %d o\n"
                "***********************\n",
                block_base,
                (unsigned int) (((heap_ll *) block_base)->chunk_length));
#endif
        return;
    }

    /* Test for each Chunk in my list if the block can be merged with */
    heap_ll * ptr_to_chunk_list = _heap_head[task_id]; // move through the list
    heap_ll * prev = 0x0; // pointer on the previous visited chunk in the list
    heap_ll * prev_block_base = 0x0; // pointer on the previous chunk of the chunk that contains the merged block in the list
    unsigned int chunk_length;
    int block_merged = 0; // =1 when the block has already been merged with a chunk in the list
    while (ptr_to_chunk_list != 0x0) {
        chunk_length = ptr_to_chunk_list->chunk_length;
        /*  [.....|ptr|block|.....] */
        if ((unsigned int) (ptr_to_chunk_list) + chunk_length == block_base) {
#if DEBUG_MALLOC == 1
            giet_tty_giet_tty_printf("****** BLOCK MERGED ******\n"
                    "CHUNK : %x of size %d o\n"
                    "merged with \n"
                    "BLOCK : %x of size %d o\n"
                    "***********************\n",
                    (unsigned int) ptr_to_chunk_list,
                    ptr_to_chunk_list->chunk_length, block_base,
                    block_length);
#endif
            if (_prev_next_last_allocted[task_id] == ptr_to_chunk_list) {
                _prev_next_last_allocted[task_id] = ptr_to_chunk_list->next;
            }

            /* update the size */
            ptr_to_chunk_list->chunk_length = chunk_length + block_length;

            /* [.....|ptr|[block|old_ptr]|.....]
             *  remove ptr from the list
             *  update next pointer
             *  update the previous chunk of block base to point to ptr
             */
            if (block_merged == 1) {
                prev->next = ptr_to_chunk_list->next;
                ptr_to_chunk_list->next = ((heap_ll *) block_base)->next;

                if (prev_block_base != 0x0) {
                    prev_block_base->next = ptr_to_chunk_list;
                }
                else {
                    _heap_head[task_id] = ptr_to_chunk_list;
                }
            }
            /****** for next turn ******/
            block_base = (unsigned int) ptr_to_chunk_list;
            block_length = ptr_to_chunk_list->chunk_length;
#if DEBUG_MALLOC == 1
            giet_tty_giet_tty_printf("****** NEW BLOCK ******\n"
                    "@ : %x\n"
                    "Length : %d o\n"
                    "***********************\n",
                    (unsigned int) ptr_to_chunk_list,
                    (unsigned int) (ptr_to_chunk_list->chunk_length));
#endif
            prev_block_base = prev;
            prev = ptr_to_chunk_list;
            ptr_to_chunk_list = ptr_to_chunk_list->next;
            block_merged = 1;
            continue;

        } // end [.....|ptr|block|.....]
        /*  [......|block|ptr|.....] */
        if (block_base + block_length == (unsigned int) ptr_to_chunk_list) {
#if DEBUG_MALLOC == 1
            giet_tty_giet_tty_printf("****** BLOCK MERGED ******\n"
                    "BLOCK : %x of size %d o\n"
                    "merged with \n"
                    "CHUNK : %x of size %d o\n"
                    "***********************\n",
                    block_base, block_length,
                    (unsigned int) ptr_to_chunk_list,
                    ptr_to_chunk_list->chunk_length);
#endif

            if (_prev_next_last_allocted[task_id] == ptr_to_chunk_list) {
                _prev_next_last_allocted[task_id] = ptr_to_chunk_list->next;
            }

            /* update the size */
            ((heap_ll *) block_base)->chunk_length = block_length + chunk_length;

            /* [.....|block|ptr|......] */
            if (block_merged == 0) {
                /* update next pointer
                 *  update the previous chunk of ptr to point to block_base
                 */
                ((heap_ll *) block_base)->next = ptr_to_chunk_list->next;
                if (prev == 0x0) {
                    _heap_head[task_id] = ((heap_ll *) block_base);
                }
                else {
                    prev->next = ((heap_ll *) block_base);
                }
            }
            /* [.....[old_ptr|block]|ptr|......] */
            else {
                /* remove ptr from the list */
                prev->next = ptr_to_chunk_list->next;
                if (prev_block_base != 0x0) {
                    prev_block_base->next = ((heap_ll *)block_base);
                }
                else {
                    _heap_head[task_id] = ((heap_ll *)block_base);
                }
            }

            ptr_to_chunk_list = ((heap_ll *) block_base);
            block_length = ptr_to_chunk_list->chunk_length;
#if DEBUG_MALLOC == 1
            giet_tty_giet_tty_printf("****** NEW BLOCK ******\n"
                    "@ : %x\n"
                    "Length : %d o\n"
                    "***********************\n",
                    (unsigned int) ptr_to_chunk_list,
                    (unsigned int) (ptr_to_chunk_list->chunk_length));
#endif
            prev_block_base = prev;
            block_merged = 1;
        } // end [......|block|ptr|.....]

        prev = ptr_to_chunk_list;
        ptr_to_chunk_list = ptr_to_chunk_list->next;
    } // end while

    if (block_merged == 1) {
        return;
    }

    /* if the block cant be merge
     *  create new block and add it to the end of the list 
     */
    ((heap_ll *) block_base)->chunk_length = block_length;
    ((heap_ll *) block_base)->next = 0x0;
    prev->next = ((heap_ll *) block_base);

#if DEBUG_MALLOC == 1
    giet_tty_giet_tty_printf("****** NEW BLOCK ******\n"
            "@ : %x\n"
            "Length : %d o\n"
            "***********************\n",
            block_base,
            (unsigned int) (((heap_ll *) block_base)->chunk_length));
#endif
    return;
}


void print_all_heap(void) {
    int task_id = giet_global_task_id();
    heap_ll * ptr_to_chunk_list = _heap_head[task_id];
    giet_tty_printf("################### PRINT ALL HEAP ######################\n");
    while (ptr_to_chunk_list != 0x0) {
        giet_tty_printf("CHUNK at @ : %x\n"
                "OVERHEAD : %d\n"
                "NEXT : %x\n\n",
                (unsigned int) ptr_to_chunk_list,
                ptr_to_chunk_list->chunk_length,
                (unsigned int) ptr_to_chunk_list->next);
        ptr_to_chunk_list = ptr_to_chunk_list->next;
    }
    giet_tty_printf("#########################################################\n");
}


void frag(int turn) {
    int task_id = giet_global_task_id();
    int nb_blocks = 0;
    int size = 0;
    heap_ll * ptr_to_chunk;
    ptr_to_chunk = _heap_head[task_id];
    while (ptr_to_chunk != 0x0) {
        size += ptr_to_chunk->chunk_length;
        nb_blocks += 1;
        ptr_to_chunk = ptr_to_chunk->next;
    }
    //   assert(size != 0 || nb_blocks == 0);
    if (size != 0) {
        giet_tty_printf("%.3f\t%d\n", size / ((double) nb_blocks), turn);
    }
}




#else // Default case : New Fit


int get_prev_fit_chunk(unsigned int size) {
    int task_id = giet_global_task_id();
    int index = GET_TAB_INDEX(size);
    while (index != MAX_SIZE_POW2_TAB) {
        if (_pow2tab[task_id][index] != 0x0) {
            return index;
        }
        index++;
    }
    return -1;
}



void * malloc(unsigned int size) {
    int task_id = giet_global_task_id();
#if DEBUG_MALLOC == 1
    giet_tty_printf("############ MALLOC ############\n\n");
#endif
    if(size == 0) {
#if DEBUG_MALLOC == 1
        giet_tty_printf(" SIZE = 0 \n");
#endif
        return 0x0;
    }
    if (size > 0x20000000) {
#if DEBUG_MALLOC == 1
        giet_tty_printf("ERROR max size = %d\n",0x20000000); 
#endif
        return 0x0;
    }
    if (size < 8) {
        size = 8;
    }

    /****** First call to malloc ******/
    if (_first_malloc[task_id] == 0) {
        giet_heap_info(&_heap_base[task_id], &_heap_length[task_id]);

        if (_heap_length[task_id] == 0) {
            giet_tty_printf("*** Error: Malloc called in task %d while no heap was defined.\n", task_id);
            return 0x0;
        }

        int index = GET_TAB_INDEX(_heap_length[task_id]);

        _pow2tab[task_id][index] = (heap_ll *) _heap_base[task_id];
        _pow2tab[task_id][index]->chunk_length = _heap_length[task_id];
        _pow2tab[task_id][index]->next = 0x0;

        *((unsigned int *) ((_heap_base[task_id] +_heap_length[task_id]) - 4))     = _heap_length[task_id];

        _first_malloc[task_id] = 1;
    }

    /****** Size align ******/
    int size_align = size;
    if (size % 4 != 0) {
        size_align = ((size / 4) + 1) * 4;
    }

#if DEBUG_MALLOC == 1
    giet_tty_printf("Looking for size : %d %d = %d\n", size_align, 4,size_align+4);
#endif


    /****** Get tab index of the victim from the chunks list ******/
    heap_ll * victim;
    int index;
    if ((index = get_prev_fit_chunk(size_align + 4)) == -1) {
        return 0x0;
    }
    victim = _pow2tab[task_id][index];

    /****** Get Victim Base ******/
    unsigned int victim_vbase = (unsigned int) victim;	// overhead


    /****** update the chunks list ******/
    _pow2tab[task_id][index] = _pow2tab[task_id][index]->next;

    if ((victim->chunk_length - (size_align + 4)) < 12) {
        size_align = size_align + (victim->chunk_length - (size_align + 4)); 
    } 
    else {
        // if its not an exact match then update chunk base and length
        unsigned int new_size = victim->chunk_length - (size_align + 4); // get the new size;
        unsigned int new_index = GET_TAB_INDEX(new_size);                 // get the new index;
        heap_ll * new_chunk = (heap_ll *) (((unsigned int) victim) + (size_align + 4)); //update new_chunk @
        new_chunk->chunk_length = new_size;                                // write new size
        *((unsigned int *) ((unsigned int) new_chunk + new_size - 4)) = new_size;                                // on both side of the block
        new_chunk->next = _pow2tab[task_id][new_index];                     // insert new_chunk @ the new index
        _pow2tab[task_id][new_index] = new_chunk;

#if DEBUG_MALLOC == 1
        giet_tty_printf("NEXT CHUNK is at @ : 0x%x + 0x%x = 0x%x : @ of size over the block : %x\n",
                (unsigned int) victim,
                (unsigned int) ((size_align + 4) / 4),
                (unsigned int) new_chunk,
                ((unsigned int) new_chunk + new_chunk->chunk_length) - 4);
#endif
    }

    /****** Write Overhead ******/
    *((unsigned int *) victim_vbase) = size_align;	// writing overhead on the first word
#if DEBUG_MALLOC == 1
    giet_tty_printf("BLOCK SUCCESSFULLY ALLOCATED at @ 0x%x user will write at @ 0x%x\n\n",\
            (unsigned int)(victim_vbase), (unsigned int ) (victim_vbase + 4));
#endif

    return (unsigned int *) (victim_vbase + 4);
}



/* this function tries to merge the block to free with chunks in the list if they are contiguous
 * the block can be merged two times.
 */
void update_chunk_list(unsigned int block_base, unsigned int block_length) {
    int task_id = giet_global_task_id();

    int left_merging               = 0;
    unsigned int left_block_size   = 0;
    unsigned int left_block_index  = 0;
    heap_ll * left_block_addr      = 0x0;

    int right_merging              = 0;
    unsigned int right_block_size  = 0; 
    unsigned int right_block_index = 0;
    heap_ll * right_block_addr     = 0x0;

    if (block_base - 4 >= _heap_base[task_id]) {

#if DEBUG_MALLOC == 1
        giet_tty_printf("############# LEFT MERGE #############\n\n");
#endif
        left_block_size = *((unsigned int *) (block_base - 4));
        left_block_index = GET_TAB_INDEX(left_block_size);
        left_block_addr = (heap_ll *)(block_base - left_block_size);
        left_merging = 1;
    }

    if ((block_base + block_length) <= (_heap_base[task_id] + _heap_length[task_id]) - 8) {
#if DEBUG_MALLOC == 1
        giet_tty_printf("############# RIGHT MERGE #############\n\n");
#endif
        right_block_size = ((heap_ll *)(block_base + block_length))->chunk_length;
        right_block_index = GET_TAB_INDEX(right_block_size);
        right_block_addr = (heap_ll *) (block_base + block_length);
        right_merging = 1;
    }

#if DEBUG_MALLOC == 1
    giet_tty_printf("############# END PREP MERGE #############\n\n");
#endif

    heap_ll * ptr_to_chunk = 0x0;
    heap_ll * prev_ptr_to_chunk = 0x0;

    heap_ll * ptr_to_chunk_right = 0x0;
    heap_ll * prev_ptr_to_chunk_right = 0x0;

    unsigned int new_size = block_length;
    unsigned int new_index = 0;
    int merged_left = 0;
    heap_ll * new_addr = 0x0;



    /* try to merge with left block */
    if (left_merging == 1 &&
            (unsigned int) left_block_addr >= _heap_base[task_id] &&
            (unsigned int) left_block_addr <= block_base - 12) {
        ptr_to_chunk = _pow2tab[task_id][left_block_index];
        while (ptr_to_chunk != 0x0) {
            if (ptr_to_chunk == left_block_addr && ptr_to_chunk->chunk_length == left_block_size) {
                new_size = new_size + left_block_size;
                if (prev_ptr_to_chunk == 0x0) {
                    _pow2tab[task_id][left_block_index] = ptr_to_chunk->next;
                }
                else {
                    prev_ptr_to_chunk->next = ptr_to_chunk->next;
                }
                merged_left = 1;
                break;
            }
            else if (ptr_to_chunk == right_block_addr && ptr_to_chunk->chunk_length == right_block_size) {
                ptr_to_chunk_right = ptr_to_chunk;
                prev_ptr_to_chunk_right = prev_ptr_to_chunk;
            }
            prev_ptr_to_chunk = ptr_to_chunk;
            ptr_to_chunk = ptr_to_chunk->next;
        }
    }

    if (right_block_index != left_block_index) {
        prev_ptr_to_chunk = 0x0;
        ptr_to_chunk = _pow2tab[task_id][right_block_index];
    }
    else {
        ptr_to_chunk = ptr_to_chunk_right;
        prev_ptr_to_chunk = prev_ptr_to_chunk_right;
    }

    /* try to merge with right block */
    if (right_merging == 1 &&
            (unsigned int) right_block_addr >= block_base + block_length &&
            (unsigned int) right_block_addr <= (_heap_base[task_id] + _heap_length[task_id]) - 12) {
        while (ptr_to_chunk != 0x0) {
            if (ptr_to_chunk == right_block_addr && ptr_to_chunk->chunk_length == right_block_size) {
                new_size = new_size + right_block_size;
                if (prev_ptr_to_chunk == 0x0) {
                    _pow2tab[task_id][right_block_index] = ptr_to_chunk->next;
                }
                else {
                    prev_ptr_to_chunk->next = ptr_to_chunk->next;
                }
                break;
            }
            prev_ptr_to_chunk = ptr_to_chunk;
            ptr_to_chunk = ptr_to_chunk->next;
        }
    }
    new_index = GET_TAB_INDEX(new_size);
    if (merged_left == 1) {
        new_addr = (heap_ll *) (block_base - left_block_size);
    }
    else {
        new_addr = (heap_ll *) block_base;
    }
    new_addr->chunk_length = new_size;
    *((unsigned int *) ((unsigned int) new_addr + (new_addr->chunk_length - 4))) = new_size;
    new_addr->next = _pow2tab[task_id][new_index];
    _pow2tab[task_id][new_index] = new_addr;

    return;
}


static void print_all_heap(void) {
    int task_id = giet_global_task_id();
    int i = 0;
    int nb_blocks = 0;
    heap_ll * ptr_to_chunk_list;
    giet_tty_printf("################### PRINT ALL HEAP ######################\n");
    while (i != MAX_SIZE_POW2_TAB) {
        ptr_to_chunk_list = _pow2tab[task_id][i];

        if (ptr_to_chunk_list != 0x0) {
            giet_tty_printf("###################### %d ####################\n", i);
        }
        while (ptr_to_chunk_list != 0x0) {
            giet_tty_printf("CHUNK at @ : %x\n"
                    "OVERHEAD : %d\n"
                    "NEXT : %x\n\n",
                    (unsigned int) ptr_to_chunk_list,
                    ptr_to_chunk_list->chunk_length,
                    (unsigned int) ptr_to_chunk_list->next);
            ptr_to_chunk_list = ptr_to_chunk_list->next;
            nb_blocks++;
        }
        i++;
    }
    giet_tty_printf("####################### ##%d## ##########################\n", nb_blocks);
}


static void frag(int turn) {
    int task_id = giet_global_task_id();
    int i = 0;
    int nb_blocks = 0;
    int size = 0;
    heap_ll * ptr_to_chunk;
    while (i != MAX_SIZE_POW2_TAB) {
        ptr_to_chunk = _pow2tab[task_id][i];
        while (ptr_to_chunk != 0x0) {
            size += ptr_to_chunk->chunk_length;
            nb_blocks += 1;
            ptr_to_chunk = ptr_to_chunk->next;
        }
        i++;
    }
    if (size != 0) {
        giet_tty_printf("%.3f\t%d\n",size / ((double) nb_blocks), turn);
    }
}



#endif // New Fit


void free(void * ptr) {
    int task_id = giet_global_task_id();
    unsigned int * to_free = ptr;
    unsigned int heapB = _heap_base[task_id];
    unsigned int heapL = _heap_length[task_id];
    unsigned int overhead;
    unsigned int block_base;
    unsigned int block_length;

#if DEBUG_MALLOC == 1
    giet_tty_printf("############# FREE  #############\n\n");
#endif
    /****** CHECK PTR ******/
    if (to_free == 0x0) {
#if DEBUG_MALLOC == 1
        giet_tty_printf("free == 0x0\n");
#endif
        return;
    }
    // check alignement of ptr
    if (((unsigned int) to_free) % 4 != 0) {
#if DEBUG_MALLOC == 1
        giet_tty_printf("allignement of ptr  %x = %d\n", (unsigned int) to_free, (unsigned int) to_free % 4);
#endif
        return;
    }
    // check if the @ of ptr matches the range of the heap
    if (!((unsigned int) to_free >= heapB && (unsigned int) to_free < heapB + heapL)) {
#if DEBUG_MALLOC == 1
        giet_tty_printf("check if it matches the range of the heap\n");
#endif
        return;
    }

    // get the 4 bytes before the ptr that contains the size of the block 
    overhead = *(to_free - 1);
    // check alignement of overhead
    if (overhead % 4 != 0) {
#if DEBUG_MALLOC == 1
        giet_tty_printf("check alignement of overhead\n");
#endif
        return;
    }
    // check if (overhead + to_free) matches the range of the heap
    if ((((unsigned int) (to_free) + overhead) - 4) > heapB + heapL) {
#if DEBUG_MALLOC == 1
        giet_tty_printf ("check if (overhead + to_free) matches the range of the heap\n");
#endif
        return;
    }

    block_base = (unsigned int) (to_free - 1);
    block_length = overhead + 4;

#if DEBUG_MALLOC == 1
    giet_tty_printf("############# UPDATE CL :  FREE %x of size %d #############\n\n",block_base, block_length);
#endif
    update_chunk_list(block_base, block_length);

#if DEBUG_MALLOC == 1
    giet_tty_printf("BLOCK SUCCESSFULLY FREED\n\n");
#endif

    return;
}






// Local Variables:
// tab-width: 4
// c-basic-offset: 4
// c-file-offsets:((innamespace . 0)(inline-open . 0))
// indent-tabs-mode: nil
// End:
// vim: filetype=c:expandtab:shiftwidth=4:tabstop=4:softtabstop=4