#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>

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

 /*********************************************************
  * NOTE TO STUDENTS: Before you do anything else, please
  * provide your team information in the following struct.
  ********************************************************/

// Basic constants and macors
#define WSIZE       4           // Word and header/footer size(bytes)
#define DSIZE       8           // Double word size (btyes)
#define CHUNKSIZE   (1 << 12)   // Extend heap by this amount (bytes)

#define MAX(x, y)   ((x) > (y) ? (x) : (y))   

#define PACK(size, alloc)   ((size) | (alloc))

// Read and wirte a word at address

#define GET(p)  (*(unsigned int *)(p))
#define PUT(p, val)  (*(unsigned int *)(p) = (val))

// Read the size and allocated field from address p
#define GET_SIZE(p)    (GET(p) & ~0x7)  
#define GET_ALLOC(p)   (GET(p) & 0x1)  

#define HDRP(bp)    ((char *)(bp) - WSIZE)
#define FTRP(bp)    ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

#define NEXT_BLKP(bp)   (((char *)(bp) + GET_SIZE((char *)(bp) - WSIZE)))   
#define PREV_BLKP(bp)   (((char *)(bp) - GET_SIZE((char *)(bp) - DSIZE)))

// Declaration
static void* heap_listp;
static char* last_bp; // last block pointer
static void* extend_heap(size_t words);
static void* coalesce(void* bp);
static void* next_fit(size_t a_size);
static void place(void* bp, size_t a_size);

/*
 * mm_init - initialize the malloc package.
 */
int mm_init(void)
{
    // Create the initial empty heap
    if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void*)-1) {  
        return -1;
    }

    PUT(heap_listp, 0);                             // Alignment padding
    PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1));    // Prologue header
    PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1));    // Prologue footer
    PUT(heap_listp + (3 * WSIZE), PACK(0, 1));        // Epilogue header
    heap_listp += (2 * WSIZE);

    if (extend_heap(CHUNKSIZE / WSIZE) == NULL) {
        return -1;
    }
    last_bp = (char*)heap_listp; //포인터 저장 
    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) {
    size_t a_size;       
    size_t extend_size;        
    char* bp;

    if (size == 0) {
        return NULL;
    }

   
    if (size <= DSIZE) {    
        a_size = 2 * DSIZE;
    }
    else {                 
        a_size = DSIZE * ((size + (DSIZE)+(DSIZE - 1)) / DSIZE);
    }

 
    if ((bp = next_fit(a_size)) != NULL) {  
        place(bp, a_size);                  
        last_bp = bp; // 포인터 저장
        return bp;
    }

 
    extend_size = MAX(a_size, CHUNKSIZE);
    if ((bp = extend_heap(extend_size / WSIZE)) == NULL) {  //확장
        return NULL;
    }
    place(bp, a_size); // 분할
    last_bp = bp; // 포인터 저장
    return bp;
}

static void* next_fit(size_t a_size) {
    char* bp;

    for (bp = last_bp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) { //next fit
        if (!GET_ALLOC(HDRP(bp)) && GET_SIZE(HDRP(bp)) >= a_size) {
            return bp;
        }
    }
    /*
    bp = heap_listp;
    while (bp < last_bp) {
        bp = NEXT_BLKP(bp);
        if (!GET_ALLOC(HDRP(bp)) && GET_SIZE(HDRP(bp)) >= a_size) {
            last_bp = bp;
            return bp;
        }
    }
    */
    return NULL;
}

/*
 * mm_free - Freeing a block does nothing.
 */
void mm_free(void* bp)
{
    size_t size = GET_SIZE(HDRP(bp));

    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    coalesce(bp); //연결
}

static void* extend_heap(size_t words) { //확장
    char* bp;
    size_t size;

    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE; //짝수로

    if ((long)(bp = mem_sbrk(size)) == -1) { //확장
        return NULL;
    }

    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); //new epilogue header

    return coalesce(bp); //연결
}

static void* coalesce(void* bp) {
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); //할당여부
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
    size_t size = GET_SIZE(HDRP(bp));

    if (prev_alloc && next_alloc) { // 둘 다 할당됨
        return bp;
    }

    else if (prev_alloc && !next_alloc) { // next 만 free
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    }

    else if (!prev_alloc && next_alloc) { // prev만 free
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(FTRP(bp), PACK(size, 0));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }

    else { //prev , next all free
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }
    last_bp = bp; //update
    return bp;
}

static void place(void* bp, size_t a_size) { //분할
    size_t c_size = GET_SIZE(HDRP(bp)); //current size 

    if ((c_size - a_size) >= (2 * (DSIZE))) {
        PUT(HDRP(bp), PACK(a_size, 1));
        PUT(FTRP(bp), PACK(a_size, 1));

        bp = NEXT_BLKP(bp);

        PUT(HDRP(bp), PACK(c_size - a_size, 0)); // adjust next block size
        PUT(FTRP(bp), PACK(c_size - a_size, 0));
    }
    else {     // 그냥 할당
        PUT(HDRP(bp), PACK(c_size, 1));
        PUT(FTRP(bp), PACK(c_size, 1));
    }
}

void* mm_realloc(void* bp, size_t size)
{
    void* old_bp = bp;
    void* new_bp;
    size_t copySize;

    new_bp = mm_malloc(size); //새로 할당

    if (new_bp == NULL) return NULL;

    copySize = GET_SIZE(HDRP(old_bp));

    if (size < copySize) // 이전 블록보다 요구되는 크기가 작으면 크기 줄이기
        copySize = size;

    //  old_bp 메모리 영역에서 new_bp 메모리 영역으로 copySize byte 만큼 복사
    memcpy(new_bp, old_bp, copySize);

    mm_free(old_bp);

    return new_bp;
}