#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

#define dim_gestiune 12
#define la_bloc_anterior 4
#define la_dim_bloc 8

uint32_t arena_size, arena_start, block_at_0;
unsigned char* arena;

uint32_t min(uint32_t a, uint32_t b)
{
    if(a<b)return a;
    return b;
}
//Returneaza urmatorul numar >= ca x si divizibil cu align
uint32_t next_aligned_index(uint32_t x, uint32_t align)
{
    if(!x) return 0;
    return ((x - 1) / align + 1) * align;
}

//Prints an int on the allocator
void uint_to_hex(uint32_t index, uint32_t num)
{
    arena [index + 3] = (num >> 24) & 0xFF;
    arena [index + 2] = (num >> 16) & 0xFF;
    arena [index + 1] = (num >> 8) & 0XFF;
    arena [index] = num & 0xFF;
}

//Reads an int from the allocator
uint32_t hex_to_int(uint32_t index)
{
    uint32_t res = 0;
    res = arena[index + 3];
    res = (res << 8) + arena[index + 2];
    res = (res << 8) + arena[index + 1];
    res = (res << 8) + arena[index];
    return res;
}

void INITIALIZE(uint32_t size)
{
    //Creeaza o arena noua de dimensiune size,
    //initializeaza dimensiunea si locul primului bloc
    arena_size = size;
    arena_start = 0;
    block_at_0 = 0;
    arena = calloc(size, sizeof(unsigned char));
}

void FINALIZE()
{
    //Elibereaza arena si modifica dimensiunea la 0
    if(!arena_size) return;
    free (arena);
    arena_size = 0;
}

void DUMP()
{
    uint32_t parse_index;
    for(parse_index = 0; parse_index < arena_size; parse_index++)
    {
        //Printeaza locul din memorie la fiecare bloc de 16 octeti
        if(!(parse_index & 0xF))
            printf("%08X\t",parse_index);
        //Printeaza un spatiu inainte de al 9-lea octet
        else if((parse_index & 0xF) == 8)
            printf(" ");
        printf("%02X ", arena[parse_index]);
        //Trece pe o linie noua dupa al 16-lea octet
        if((parse_index & 0xF) == 0xF)
            printf("\n");
    }
    if(arena_size & 0xF)
            printf("\n");
}

//Aloca un bloc de memorie la free_index, de marime size, cu blocul anterior la prev_index
//si blocul urmator la next_index
void alloc_at(uint32_t free_index, uint32_t size, uint32_t prev_index, uint32_t next_index)
{
    //Updateaza blocurile vecine cu noua forma
    if(prev_index || block_at_0)
        uint_to_hex(prev_index, free_index);
    if(next_index)
        uint_to_hex(next_index + la_bloc_anterior, free_index);
    //Initializeaza blocul nou cu datele necesare
    uint_to_hex(free_index, next_index);
    uint_to_hex(free_index + la_bloc_anterior, prev_index);
    uint_to_hex(free_index + la_dim_bloc, size);
    //Marcheaza atunci cand contruieste un bloc incepand la 0
    if(!free_index) block_at_0 = 1;
}

uint32_t ALLOCALIGNED(uint32_t size, uint32_t align)
{
    uint32_t loc_align;
    //Calculeaza primul loc aliniat
    loc_align = next_aligned_index(dim_gestiune, align);
    //Verifica daca nu exista niciun bloc de memorie alocat
    if(hex_to_int(arena_start + la_dim_bloc)==0)
    {
        //Daca cererea de memorie este mai mica decat arena se poate aloca
        if(size + loc_align <= arena_size)
        {
            arena_start = loc_align - dim_gestiune;
            alloc_at(arena_start, size, 0, 0);
            return loc_align;
        }
        else return 0;
    }
    //Incearca sa aloce memorie la indexul 0
    if(size + loc_align <= arena_start)
    {
        alloc_at(loc_align - dim_gestiune, size, 0, arena_start);
        arena_start = loc_align - dim_gestiune;
        return loc_align;
    }
    //Cauta primul loc unde poate insera blocul de memorie
    uint32_t parse_index, next_index, curr_bloc_len;
    next_index = arena_start;
    do
    {
        parse_index = next_index;
        next_index = hex_to_int(parse_index);
        curr_bloc_len = hex_to_int(parse_index + la_dim_bloc);
        loc_align = next_aligned_index(parse_index + dim_gestiune * 2 + curr_bloc_len, align);
    }while(next_index && loc_align + size > next_index);

    //Trateaza cazul in care se poate aloca memorie intre 2 blocuri existente
    if(next_index)
    {
        alloc_at(loc_align - dim_gestiune, size, parse_index, next_index);
        return loc_align;
    }
    //Trateaza cazul in care aloca memorie la final
    else
    {
        //Daca nu are destul spatiu nu aloca
        if(arena_size< loc_align + size)
            return 0;
        alloc_at(loc_align - dim_gestiune, size, parse_index, 0);
        return loc_align;
    }
}

uint32_t ALLOC(uint32_t size)
{
    return ALLOCALIGNED(size, 1);
}

void FREE(uint32_t free_index)
{
    //Seteaza free_index la inceputul blocului si citeste urmatorul si anteriorul bloc
    free_index -= dim_gestiune;
    if(free_index == 0) block_at_0 = 0;
    uint32_t next_index = hex_to_int(free_index);
    uint32_t prev_index = hex_to_int(free_index + la_bloc_anterior);
    //Daca free_index e primul bloc trece urmatorul bloc ca friind primul
    if(free_index == arena_start)
        arena_start = next_index;
    //Updateaza blocurile vecine
    if(prev_index >= arena_start)
        uint_to_hex(prev_index,next_index);
    if(next_index)
        uint_to_hex(next_index + la_bloc_anterior, prev_index);
    //Sterge memoria
    memset(arena + free_index, 0, (dim_gestiune + hex_to_int(free_index + la_dim_bloc)) * sizeof(unsigned char));
}

void FILL(uint32_t index, uint32_t size, unsigned char value)
{
    index -= dim_gestiune;
    uint32_t block_fill, next_index;
    while(size)
    {
        //Umple blocul curent cu numarul maxim de octeti disponibili
        block_fill = min(size, hex_to_int(index + la_dim_bloc));
        next_index = hex_to_int(index);
        for(uint32_t i = 0; i < block_fill; i++)
            arena[index + dim_gestiune + i] = value;
        //Scade din numarul total de octeti cati a umplut si trece la urmatorul bloc
        size -= block_fill;
        index = next_index;
        //Daca nu mai are loc sa completeze se opreste
        if(!index) return;
    }
}

uint32_t REALLOC(uint32_t index, uint32_t size)
{
    //Calculeaza punctul de inceput al blocului si dimensiunea memoriei din el
    index -= dim_gestiune;
    uint32_t dim_mem = min(size, hex_to_int(index + la_dim_bloc));
    //Salveaza intr-un sir de caractere temporal valorile din bloc
    unsigned char* tmp;
    tmp = calloc(dim_mem, sizeof(unsigned char));
    memcpy(tmp, arena + index + dim_gestiune, dim_mem * sizeof(unsigned char));
    //Goleste zona de inlocuit si cauta un loc nou
    FREE(index + dim_gestiune);
    uint32_t free_pos = ALLOC(size);
    //Daca gaseste un loc nou copiaza ce se afla in memoria blocului sters
    if(!free_pos)
    {
        free(tmp);
        return 0;
    }
    memcpy(arena + free_pos, tmp, dim_mem * sizeof(unsigned char));
    free(tmp);
    return free_pos;
}

void parse_command(char* cmd)
{
    const char* delims = " \n";

    char* cmd_name = strtok(cmd, delims);
    if (!cmd_name) {
        goto invalid_command;
    }

    if (strcmp(cmd_name, "INITIALIZE") == 0) {
        char* size_str = strtok(NULL, delims);
        if (!size_str) {
            goto invalid_command;
        }
        uint32_t size = atoi(size_str);
        INITIALIZE (size);

    } else if (strcmp(cmd_name, "FINALIZE") == 0) {
        FINALIZE ();

    } else if (strcmp(cmd_name, "DUMP") == 0) {
        DUMP ();

    } else if (strcmp(cmd_name, "ALLOC") == 0) {
        char* size_str = strtok(NULL, delims);
        if (!size_str) {
            goto invalid_command;
        }
        uint32_t size = atoi(size_str);
        printf("%d\n",ALLOC (size));

    } else if (strcmp(cmd_name, "FREE") == 0) {
        char* index_str = strtok(NULL, delims);
        if (!index_str) {
            goto invalid_command;
        }
        uint32_t index = atoi(index_str);
        FREE (index);

    } else if (strcmp(cmd_name, "FILL") == 0) {
        char* index_str = strtok(NULL, delims);
        if (!index_str) {
            goto invalid_command;
        }
        uint32_t index = atoi(index_str);
        char* size_str = strtok(NULL, delims);
        if (!size_str) {
            goto invalid_command;
        }
        uint32_t size = atoi(size_str);
        char* value_str = strtok(NULL, delims);
        if (!value_str) {
            goto invalid_command;
        }
        uint32_t value = atoi(value_str);
        FILL(index, size, value);

    } else if (strcmp(cmd_name, "ALLOCALIGNED") == 0) {
        char* size_str = strtok(NULL, delims);
        if (!size_str) {
            goto invalid_command;
        }
        uint32_t size = atoi(size_str);
        char* align_str = strtok(NULL, delims);
        if (!align_str) {
            goto invalid_command;
        }
        uint32_t align = atoi(align_str);
        printf("%d\n",ALLOCALIGNED(size, align));

    } else if (strcmp(cmd_name, "REALLOC") == 0) {
        char* index_str = strtok(NULL, delims);
        if (!index_str) {
            goto invalid_command;
        }
        uint32_t index = atoi(index_str);
        char* size_str = strtok(NULL, delims);
        if (!size_str) {
            goto invalid_command;
        }
        uint32_t size = atoi(size_str);
        printf("%d\n",REALLOC(index, size));

    } else {
        goto invalid_command;
    }

    return;

invalid_command:
    printf("Invalid command: %s\n", cmd);
    exit(1);
}

int main(void)
{
    ssize_t read;
    char* line = NULL;
    size_t len;

    /* parse input line by line */
    while ((read = getline(&line, &len, stdin)) != -1) {
        /* print every command to stdout */
        printf("%s", line);

        parse_command(line);
    }

    free(line);

    return 0;
}