/*
 * 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 <sys/mman.h>
#include <errno.h>

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

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

  /* single word (4) or double word (8) alignment */
#define ALIGNMENT 8

/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)

#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

// Basic constants and macros
#define WSIZE 4 
#define DSIZE 8 
#define CHUNKSIZE (1<<12) 

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

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

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

#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)))

#define PRED_FREEP(bp) (*(void**)(bp)) //이전 free block pointer
#define SUCC_FREEP(bp) (*(void**)(bp + WSIZE)) //다음 free block pointer

static void* heap_listp = NULL; // heap 시작주소 pointer
static void* free_listp = NULL; // free list head pointer

static void* coalesce(void* bp);
static void* extend_heap(size_t words);
static void* first_fit(size_t a_size);
static void place(void* bp, size_t a_size);

void rmFreeBlock(void* bp); // delete free block from free list
void putFreeBlock(void* bp); // input free block to free list

int mm_init(void)
{
    // Create the initial empty heap
    if ((heap_listp = mem_sbrk(6 * WSIZE)) == (void*)-1) {
        return -1;
    }

    PUT(heap_listp, 0);                             // Alignment padding
    PUT(heap_listp + (1 * WSIZE), PACK(2 * DSIZE, 1)); // Prologue header
    PUT(heap_listp + (2 * WSIZE), NULL);            // PRED pointer NULL로 초기화
    PUT(heap_listp + (3 * WSIZE), NULL);            // SUCC pointer NULL로 초기화
    PUT(heap_listp + (4 * WSIZE), PACK(2 * DSIZE, 1));  // Prologue footer
    PUT(heap_listp + (5 * WSIZE), PACK(0, 1));      // Epilogue header

    free_listp = heap_listp + (2 * WSIZE); // free_listp를 PRED 포인터 가리키게 초기화

    if (extend_heap(CHUNKSIZE / WSIZE) == NULL) //extend heap
        return -1;

    return 0;
}

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) { // next free
        rmFreeBlock(NEXT_BLKP(bp)); // 합쳐질거기때문에 -> free block list에서 제거

        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp), PACK(size, 0));   // hd, ft update
        PUT(FTRP(bp), PACK(size, 0));
    }

    else if (!prev_alloc && next_alloc) {   // prev free
        rmFreeBlock(PREV_BLKP(bp)); // 합쳐질거기때문에 -> free block list에서 제거

        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); // bp를 prev로 옮겨줌

    }

    else if (!prev_alloc && !next_alloc) { // prev next all free

        rmFreeBlock(PREV_BLKP(bp)); // 합쳐질거기때문에 -> free block list에서 제거
        rmFreeBlock(NEXT_BLKP(bp));

        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); //bp를 prev로 옮겨줌
    }

    putFreeBlock(bp); // 연결이 된 블록을 free list 에 추가, 
    // prev next 모두 할당되어있는경우 원래 블록을 free list에 넣어주게됨

    return bp;
}

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

    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE; //짝수로 할당 -> double word alignment
    if ((long)(bp = mem_sbrk(size)) == -1) {
        return NULL;
    }

    PUT(HDRP(bp), PACK(size, 0)); // Free block header
    PUT(FTRP(bp), PACK(size, 0)); // Free block footer
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); // New epilogue header

    return coalesce(bp); // coalesce if the previous block was free
}

static void* first_fit(size_t a_size) {
    void* bp;

    // free list에서 유일하게 할당된 블록(= 리스트의 끝)을 만나면 종료
    for (bp = free_listp; GET_ALLOC(HDRP(bp)) != 1; bp = SUCC_FREEP(bp)) {
        if (GET_SIZE(HDRP(bp)) >= a_size) {
            return bp;
        }
    }
    return NULL;
}

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

    rmFreeBlock(bp); // 할당된 것이므로 지움

    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));

        putFreeBlock(bp); // free list 에 분할된 블럭을 넣는다.
    }
    else { // 그냥 할당
        PUT(HDRP(bp), PACK(c_size, 1));
        PUT(FTRP(bp), PACK(c_size, 1));
    }
}

/*
 * 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; // adjusted block size
    size_t extend_size; // amount to extend heap if no fit
    char* bp;

    if (size == 0) { //no use
        return NULL;
    }

    //adjusted block size 조정
    if (size <= DSIZE) { //최소 블록조건 충족 (for overhead and alignment reqs)
        a_size = 2 * DSIZE;
    }

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

    // search free block
    if ((bp = first_fit(a_size)) != NULL) {
        place(bp, a_size); //가능하면 분할
        return bp;
    }

    // free block 못찾음
    extend_size = MAX(a_size, CHUNKSIZE);
    if ((bp = extend_heap(extend_size / WSIZE)) == NULL) { //heap 확장
        return NULL;
    }
    place(bp, a_size);
    return bp;
}

// LIFO(후입선출) 방식, free한 블럭을 free list에 추가
void putFreeBlock(void* bp) {
    SUCC_FREEP(bp) = free_listp; // 연결 : $ -> bp -> free_listp
    PRED_FREEP(bp) = NULL; // 연결 해제 : bp -> free_listp
    PRED_FREEP(free_listp) = bp; // 연결 : bp <-> free_listp

    free_listp = bp; // free listp update
}

void rmFreeBlock(void* bp) { // free list에서 제거
    // ex. bp <-> a
    if (bp == free_listp) { // 가장 마지막에 들어온 블록 = 가장 먼저 제거됨
        PRED_FREEP(SUCC_FREEP(bp)) = NULL; // 연결 해제 : bp -> a
        free_listp = SUCC_FREEP(bp); // free listp update : a
    }

    else { // ex. b <-> bp <-> a
        SUCC_FREEP(PRED_FREEP(bp)) = SUCC_FREEP(bp); // b -> a
        PRED_FREEP(SUCC_FREEP(bp)) = PRED_FREEP(bp); // b <-> a
    }
}

/*
 * 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)); //free
    PUT(FTRP(bp), PACK(size, 0));

    coalesce(bp); //연결
}

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
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;

}