/*
 * mm-naive.c - The fastest, least memory-efficient malloc package.
 *
 * In this naive approach, a block is allocated by simply incrementing
 * the brk pointer.  A block is pure payload. There are no headers or
 * footers.  Blocks are never coalesced or reused. Realloc is
 * implemented directly using mm_malloc and mm_free.
 *
 * NOTE TO STUDENTS: Replace this header comment with your own header
 * comment that gives a high level description of your solution.
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include <stdint.h>

#include "mm.h"
#include "memlib.h"

team_t team = {
    /* Team name */
    "MA",
    /* First member's full name */
    "Marvin Aleksa",
    /* First member's email address */
    "marvin.aleksa@stud.uni-due.de",
    /* Second member's full name (leave blank if none) */
    "",
    /* Second member's email address (leave blank if none) */
    ""
};

typedef uint32_t t4; // 4 byte wide unsigned data type
typedef uint64_t t8; // 8 byte wide unsigned data type

/* single word (4) or double word (8) alignment */
#define AL 8       // word length to align to
#define BS AL*1    // target block size

/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (AL-1)) & ~0x7)
#define ALIGN_ADDR(addr) (void *)ALIGN((int)addr)
#define SIZE_T_SIZE (ALIGN(sizeof(t8)))

#define SET_ALL0(x) ((x) & ~1)
#define SET_ALL1(x) ((x) | 1)
#define GET_LENG(x) ((x) & ~1)
#define GET_ALLC(x) ((x) & 1)

void *heap = NULL;
void *epil = NULL;

void *find_unused(size_t size) {
    // Start traversing from the beginning of the heap
    t8 *current = (t8 *)heap;

    while (current < (t8 *)mem_heap_hi()) {
        size_t block_size = GET_LENG(*current);

        // Check if the block is free and large enough
        if (!GET_ALLC(*current) && block_size >= size) {
            return (void *)(current + 1); // Return pointer to payload
        }

        // Move to the next block
        current = (t8 *)((char *)current + block_size);
    }

    // No suitable block found
    return NULL;
}

/* mm_init - initialize the malloc package. */
int mm_init(void) {
    // printf("\n");
    heap = mem_sbrk(3*AL);
    if (heap == (void *)-1) {
        return 0;
    }

    // printf("heap start: %p - %p\n", heap, ALIGN_ADDR(heap));
    t8 *plhd = heap;
    *plhd = (t8)SET_ALL1(2*AL);
    // printf("plhd start: %p - %p\n", plhd, ALIGN_ADDR(plhd));
    // printf("plhd value: %llu\n", GET_LENG(*plhd));
    // printf("plhd alloc: %llu\n", GET_ALLC(*plhd));

    t8 *plft = heap+8;
    *plft = (t8)(2*AL);
    // printf("plft start: %p - %p\n", plft, ALIGN_ADDR(plft));
    // printf("plft value: %llu\n", GET_LENG(*plft));
    // printf("plft alloc: %llu\n", GET_ALLC(*plft));

    t8 *elhd = heap+16;
    *elhd = SET_ALL1(0*AL);
    // printf("elhd start: %p - %p\n", elhd, ALIGN_ADDR(elhd));
    // printf("elhd value: %llu\n", GET_LENG(*elhd));
    // printf("elhd alloc: %llu\n", GET_ALLC(*elhd));

    epil = elhd;
    // printf("epil start: %p - %p\n", epil, ALIGN_ADDR(epil));
    // printf("epil value: %llu\n", GET_LENG(*(t8 *)epil));
    // printf("epil alloc: %llu\n", GET_ALLC(*(t8 *)epil));

    // printf("\n");
    return 0;
}

/* mm_malloc - Allocate a block by incrementing the brk pointer. Always allocate a block whose size is a multiple of the alignment. */
void *mm_malloc(size_t size) {
    // printf("malloc: request for %u\n", size);
    int alsize = ALIGN(size);
    // printf("malloc: aligned to  %lli\n", ALIGN((t8)size));
    int fbsize = alsize+(2*AL);
    // printf("malloc: full block size %i - %i\n", fbsize, ALIGN(fbsize));

    void *chk = mem_sbrk(fbsize);
    if (chk == (void *)-1) {
        return NULL;
    }

    t8   *newblock_hd = epil;
    *newblock_hd = (t8)SET_ALL1(fbsize);
    // printf("malloc: new block header starts  %p - %p\n", newblock_hd, ALIGN_ADDR(newblock_hd));

    void *newblock_pl = epil+8;
    // printf("malloc: new block payload starts %p - %p\n", newblock_pl, ALIGN_ADDR(newblock_pl));

    t8   *newblock_ft = epil+8+alsize;
    *newblock_ft = (t8)SET_ALL0(fbsize);
    // printf("malloc: new block footer         %p - %p\n", newblock_ft, ALIGN_ADDR(newblock_ft));

    epil = epil+fbsize;
    t8 *nepil = epil;
    *nepil = (t8)(SET_ALL1(0));
    // printf("malloc: new epilogue             %p - %p\n", epil, ALIGN_ADDR(epil));

    // printf("\n");
    return newblock_pl;
    // int newsize = ALIGN(size + SIZE_T_SIZE);
    // void *p = mem_sbrk(newsize);
    // if (p == (void *)-1)
    //     return NULL;
    // else {
    //     *(size_t *)p = size;
    //     return (void *)((char *)p + SIZE_T_SIZE);
    // }
}

/* mm_free - Freeing a block does nothing. */
void mm_free(void *ptr) {
    if (ptr == NULL) {
        return;
    }

    // Adjust pointer to get the header of the block
    t8 *block_header = (t8 *)ptr - 1;

    // Mark the block as free
    *block_header = SET_ALL0(*block_header);

    // Get the footer for the block
    size_t block_size = GET_LENG(*block_header);
    t8 *block_footer = (t8 *)((char *)block_header + block_size - sizeof(t8));
    *block_footer = *block_header;

    // Try coalescing with previous block if it's free
    t8 *prev_footer = (t8 *)((char *)block_header - sizeof(t8));
    if (prev_footer >= (t8 *)mem_heap_lo() && !GET_ALLC(*prev_footer)) {
        size_t prev_size = GET_LENG(*prev_footer);
        t8 *prev_header = (t8 *)((char *)block_header - prev_size);

        size_t new_size = prev_size + block_size;
        *prev_header = SET_ALL0(new_size);
        *block_footer = *prev_header;

        block_header = prev_header;
        block_size = new_size;
    }

    // Try coalescing with next block if it's free
    t8 *next_header = (t8 *)((char *)block_header + block_size);
    if (next_header < (t8 *)mem_heap_hi() && !GET_ALLC(*next_header)) {
        size_t next_size = GET_LENG(*next_header);
        t8 *next_footer = (t8 *)((char *)next_header + next_size - sizeof(t8));

        size_t new_size = block_size + next_size;
        *block_header = SET_ALL0(new_size);
        *next_footer = *block_header;
    }
}

/* mm_realloc - Implemented simply in terms of mm_malloc and mm_free */
void *mm_realloc(void *ptr, size_t size) {
    void *oldptr = ptr;
    void *newptr;
    size_t copySize;

    newptr = mm_malloc(size);
    if (newptr == NULL)
        return NULL;
    copySize = *(size_t *)((char *)oldptr - SIZE_T_SIZE);
    if (size < copySize)
        copySize = size;
    memcpy(newptr, oldptr, copySize);
    mm_free(oldptr);
    return newptr;
}