static void place(void *bp, size_t size){
    size_t totalsize = GET_SIZE(HDRP(bp));                                               

    if((totalsize - size) >= OVERHEAD){                                                  
        PUT(HDRP(bp), PACK(size, 1));                                                    
        PUT(FTRP(bp), PACK(size, 1));                                                    
        mm_remove(bp);                                                                   
        bp = NEXT_BLKP(bp);                                                               
        PUT(HDRP(bp), PACK(totalsize - size, 0));                                         
        PUT(FTRP(bp), PACK(totalsize - size, 0));                                         
        coalesce(bp);                                                                     
    }

    else{                                                                                 
        PUT(HDRP(bp), PACK(totalsize, 1));                                                
        PUT(FTRP(bp), PACK(totalsize, 1));                                                
        mm_remove(bp);                             
    }
}

/*my helper functions*/
static void *extend_heap(size_t words)
{
    void *bp;
    size_t size;
    /* Allocate an even number of words to maintain alignment. */
    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
    if ((bp = mem_sbrk(size)) == (void *)-1)
    {
	return (NULL);
    }
    /* Initialize free block header/footer and the epilogue header. */
    PUT(HDRP(bp), PACK(size, 0));         /* Free block header */
    PUT(NEXT(bp), 0);  /*next address is null*/
    PUT(PREV(bp), 0);  /*prev address is null*/
    PUT(FTRP(bp), PACK(size, 0));         /* Free block footer */
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */
    /* Coalesce if the previous block was free. */
    return (coalesce(bp));
}

static void place(void *bp, size_t asize)
{
    size_t csize = GET_SIZE(HDRP(bp));

    if((csize - asize) >= (3*DSIZE))
    {
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize , 1));
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp), PACK(csize-asize, 0));
        PUT(FTRP(bp), PACK(csize-asize, 0));
        add_to_group(bp);
    }
    else
    {
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
    }
}

/*
 * find_fit - Find a fit for a block with asize bytes
 */
static void *find_fit(size_t asize)
{
    /* First-fit search */
    void *bp;

    /* Free list is empty */
    if (free_list_header == NULL) {
       return NULL;
    }

    /* Stop at prologue, while prologue is allocted */
    for (bp = free_list_header;
        GET_ALLOC(HDRP(bp)) == 0; bp = GET_SUCC_FREE_BLKP(bp)) {
        if (asize <= GET_SIZE(HDRP(bp))) {
            return bp;
        }
    }
    return NULL; /* No fit */
}

//将空闲位标志为分配位
static void place(void *bp, size_t asize)
{
	size_t csize=GET_SIZE(HDRP(bp));

	//如果一个块儿不够
	if((csize-asize) >= (2*DSIZE)){

		PUT(HDRP(bp), PACK(asize, 1));
		PUT(FTRP(bp), PACK(asize, 1));
		bp=NEXT_BLKP(bp);

		//占用下一个块儿一些空间
		PUT( HDRP(bp), PACK(csize-asize, 0) );	
		PUT( FTRP(bp), PACK(csize-asize, 0) );	
	}else{
		PUT(HDRP(bp), PACK(csize, 1));
		PUT(FTRP(bp), PACK(csize, 1));
	}
}

/*
 * extend_heap - Extend heap with free block and return its block pointer
 */
static void *extend_heap(size_t words) /* TODO */
{

    char *bp;
    size_t size;

    /* Allocate an even number of words to maintain alignment */
    size = (words % 2) ? (words+1) * WSIZE : words * WSIZE;
    if ((long)(bp = mem_sbrk(size)) == -1)
      return NULL;

    /* Initialize free block header/footer and the epilogue header */
    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 */

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

/* Extends the heap by asking for more space, and reassigning pointers
accordingly. */
static void *extend_heap(size_t words) {
    char *bp;
    size_t size;

    size = (words % 2) ? (words+1) * WSIZE : words * WSIZE;

    if (size < MIN_BLOCK_SIZE) {
        size = MIN_BLOCK_SIZE;
    }
    if ((long)(bp = mem_sbrk(size)) == -1)
        return NULL;

    /* Initialize free block header/footer and the epilogue header */
    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));

    return coalesce(bp);
}

/* Decides whether we can split the block, and if so performs the split
by computing leftover block space, deleting shortened allocated block, 
and then labeling split free block and coalescing. 
Otherwise, just resets size and allocation tags of block and deletes
it from free list. */
static void place(void *bp, size_t asize) {
    size_t csize = GET_SIZE(HDRP(bp));

    if ((csize - asize) >= MIN_BLOCK_SIZE) {
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));
        deleteBlk(bp);
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp), PACK(csize-asize, 0));
        PUT(FTRP(bp), PACK(csize-asize, 0));
        coalesce(bp);
    }
    /* Not enoough room to split, simple allocation and free list deletion */
    else {
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
        deleteBlk(bp);
    }
}

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

    /* Allocate an even number of words to maintain alignment */
    size = (words % 2) ? (words+1) * SWORD : words * SWORD;
    if ((long)(ptr = mem_sbrk(size)) == -1)
        return NULL;

    /* Initialize free block header/footer and the epilogue header */
    PUT(HDRP(ptr), PACK(size, 0));           /* Free block header */
    PUT(FTRP(ptr), PACK(size, 0));           /* Free block footer */
    PUT(HDRP(NEXT_BLKP(ptr)), PACK(0, 1));   /* New epilogue header */

    /* Coalesce if the previous block was free */
    printf("Before coalesce\n");
    return coalesce(ptr);
}

static void printblock(void *bp) 
{
    size_t hsize, halloc, fsize, falloc;

    checkheap(0);
    hsize = GET_SIZE(HDRP(bp));
    halloc = GET_ALLOC(HDRP(bp));  
    fsize = GET_SIZE(FTRP(bp));
    falloc = GET_ALLOC(FTRP(bp));  

    if (hsize == 0) {
        printf("%p: EOL\n", bp);
        return;
    }

    /*  printf("%p: header: [%p:%c] footer: [%p:%c]\n", bp, 
	hsize, (halloc ? 'a' : 'f'), 
	fsize, (falloc ? 'a' : 'f')); */
}

static void printblock(void *bp) 
{
  size_t hsize, halloc, fsize, falloc;

  hsize = GET_SIZE(HDRP(bp));
  halloc = GET_ALLOC(HDRP(bp));  
  fsize = GET_SIZE(FTRP(bp));
  falloc = GET_ALLOC(FTRP(bp));  
    
  if (hsize == 0) {
    printf("%p: EOL\n", bp);
    return;
  }

  printf("%p: header: [%d:%c] footer: [%d:%c]\n",
	 bp, 
	 (int) hsize, (halloc ? 'a' : 'f'), 
	 (int) fsize, (falloc ? 'a' : 'f')); 
}

static void Exam_list(int asize){
    void *bp;
    int csize;
    if(!asize){
        printf("\n-------mem list----------\n");
        for(bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)){
            printf("block %x:%x of realsize:%d %d \n",bp,bp+GET_SIZE(HDRP(bp)),GET_SIZE(HDRP(bp)),GET_ALLOC(HDRP(bp)));
        }
    }else{
        printf("\n------mem size[%d]----------\n",asize);
        for(bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)){
            csize = GET_SIZE(HDRP(bp));
            if(!GET_ALLOC(HDRP(bp))){
                if(csize<asize)printf("%d \t",csize);
                else printf("\033[42;30m%d\033[0m \t",csize);
            }
        }
    }
}

static void printblock(void *bp)
{
    size_t hsize, halloc, fsize, falloc;

    // checkheap(0);
    hsize = GET_SIZE(HDRP(bp));
    halloc = GET_ALLOC(HDRP(bp));
    fsize = GET_SIZE(FTRP(bp));
    falloc = GET_ALLOC(FTRP(bp));

    if (hsize == 0) {
        dbg_printf("%p: EOL\n", bp);
        return;
    }

    dbg_printf("%p: header: [%u:%c] footer: [%u:%c]\n", bp,
               (uint32_t)	hsize, (halloc ? 'a' : 'f'),
               (uint32_t)fsize, (falloc ? 'a' : 'f'));
}

/*
 * malloc
 */
void *malloc (size_t size) {
    size_t asize;      /* Adjusted block size */
    size_t extendsize; /* Amount to extend heap if no fit */
    char *bp;      

    if (heap_listp == 0){
        mm_init();
    }
    /* Ignore spurious requests */
    if (size == 0)
        return NULL;

    asize = ALIGN(size + 4); /* the overhead is payload + header(4 byte) + padding(optional) */
    asize = MAX(asize, MINSIZE * WSIZE); /* require minimum size */

    /* Search the free list for a fit */
    if ((bp = find_fit(asize)) != NULL) {  
#ifdef DEBUG    
        printf("malloc: before alloc.\n");
        mm_checkheap(1);
#endif            
        place(bp, asize);                  
#ifdef DEBUG
        printf("malloc: after alloc.\n");        
        mm_checkheap(1);
        printf("\n\n");
#endif        
        return bp;
    }

    /* No fit found. Get more memory and place the block */
    int tail_free = 0; // the free space we have in the tail of heap
    if (heap_tailp && !GET_ALLOC(HDRP(heap_tailp))) {
        tail_free = GET_SIZE(HDRP(heap_tailp));
    }
    extendsize = MAX(asize - tail_free,CHUNKSIZE);
    bp = extend_heap(extendsize/WSIZE);
    if (bp == NULL) 
        return NULL;
    place(bp, asize);
    return bp;
}

/*
 * printBlock - prentar ut staka blokk
 */
void printBlock(void *bp) {
    if(GET_ALLOC(HDRP(bp)))
        printf("%p | hdr: %p | ftr: %p | Size %d | Alloc: %d\n" ,
               bp, HDRP(bp), FTRP(bp), GET_SIZE(HDRP(bp)), GET_ALLOC(HDRP(bp)));
    else
        printf("%p | hdrp %p | ftr: %p | prevfre: %p | nextfre: %p | Size: %d | Alloc: %d\n",
               bp, HDRP(bp), FTRP(bp), NEXT_FREE_BLKP(bp), PREV_FREE_BLKP(bp),
               GET_SIZE(HDRP(bp)), GET_ALLOC(HDRP(bp)));
}

void merge(void *bp , size_t size, int state)
{
//	void *prev_block = PREV_BLKP(bp);
//	void *next_block = NEXT_BLKP(bp);
//	dbg_printf("merge\n");
	switch (state)		//X means current blcok
	{
	case 1:		//AXA
		{
//			dbg_printf("case : AXA\n");
			PUT(HDRP(bp),PACK(size,0));
			PUT(FTRP(bp),PACK(size,0));
			merge_case(bp,1);
			return;
		}
	case 2:		//AXF
		{
//			dbg_printf("case2 : AXF\n");
			PUT(HDRP(bp),PACK(size,0));
			PUT(FTRP(bp),PACK(size,0));
			merge_case(bp,2);
			return ;
		}
	case 3:		//FXA
		{
//			dbg_printf("case3 : FXA\n");
			PUT(HDRP(bp),PACK(size,0));
			PUT(FTRP(bp),PACK(size,0));
			merge_case(bp,3);
			return ;
		}
	case 4:		//FXF
		{
//			dbg_printf("case4 : FXF\n");
			PUT(HDRP(bp),PACK(size,0));
			PUT(FTRP(bp),PACK(size,0));
			merge_case(bp,4);
			return ;
		}
	}
	
}

//对空闲块进行合并
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)
	{
		;
	}
	else if (prev_alloc && !next_alloc)
	{
		//将要合并的的块从空闲队列中取出
		fetchFromList(NEXT_BLKP(bp));

		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)
	{
		//将要合并的的块从空闲队列中取出
		fetchFromList(PREV_BLKP(bp));

		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
	{
		//将要合并的的块从空闲队列中取出
		fetchFromList(NEXT_BLKP(bp));
		fetchFromList(PREV_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);
	}

	//将新释放的块放在空闲队列头部
	PUT(bp, &head);
	PUT((char*)bp + (1 * WSIZE), head.next);
	if (head.next != NULL)
		PUT(head.next, bp);
	head.next = bp;


	return bp;
}

/* 
 * Requires:
 *   words: the number of words to increase the heap by
 *   next: next pointer at the end of the linked list, to be set to the 
 	   header of the new block
 * Effects:
 *   Extend the heap with a free block and return that block's address.
 */
static void *
extend_heap(size_t words) 
{
	size_t size;
	void *bp;

	/* Allocate an even number of words to maintain alignment. */
	size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;

	if ((bp = mem_sbrk(size)) == (void *)-1)  
		return (NULL);
	printf("Before extended block is added to the free list\n");
	checkheap(1);
	/* Initialize the new node pointers, next precedes previous */
	/* The previous point points to the header of the previous block*/	
	
	/*PUT(bp, NULL);
	PUT(bp + WSIZE, HDRP(next));*/

	/* Initialize free block header/footer and the epilogue header. */
	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 */
	
	/* If list start is NULL, initialize the start to the pointer to the
	 * added block
	 */
	if (list_start == NULL) {
		list_start = (struct node *)bp;
		list_start->next = list_start;
		list_start->previous = list_start;
	}

	printf("For isolation\n");

	add_to_front(bp);
	printf("After extended block is added to the free list\n");
	checkheap(1);
	printf("Entering coalesce from extend_heap\n");
	/* Coalesce if the previous block was free. */
	return (coalesce(bp));
}

/**
 * checkblock - check the current block for consistency
 * @param bp Block to be checked
 */
static void checkblock(void *bp) 
{
    /**
     * Checks-
     * 1) Check for alignment
     * 2) Check for Header and Footer Match
     * 3) Check for the block to be in heap
     * 4) Check coalescing- no previous/next free blocks if current is free.
     */
    
    /*Check Block for alignment*/
    if ((size_t)bp % 8) {
       printf("ERROR: %p is not doubleword aligned\n", bp);
    }

    /*Check Block Header matching Footer*/
    if (GET(HDRP(bp)) != GET(FTRP(bp))) {
        printf("ERROR: header does not match footer\n");
        dbg_printf("**Debug Info \n");
        dbg_printf("Heap_listp = %p \n", heap_listp );
        dbg_printf("Block %p \n", bp );
    } 

    /* Check for if the block is in the heap */       
    if( !in_heap(bp)) {
        printf("ERROR: %p is not in heap \n", bp);        
    }

    /**
     * Concept : As all the blocks are iteratively checked, just checking
     *           next block for coalescing will suffice next/previous block
     *           checks.
     */    
    /* Check Coalescing with Next Block */
    if( GET_ALLOC(HDRP(bp)) ==0 && NEXT_BLKP(bp)!=NULL 
        && GET_ALLOC(HDRP(NEXT_BLKP(bp))) ==0 ) {
        printf("ERROR: %p is not coalesced with next block\n", bp);        
        print_all();
        exit(1);
    }

}

/**********************************************************
 * extend_heap
 * Extend the heap by "words" words, maintaining alignment
 * requirements of course. Free the former epilogue block
 * and reallocate its new header
 **********************************************************/
void *extend_heap(size_t words) {
	intptr_t *bp;
	size_t size;

	/* Allocate an even number of words to maintain alignments */
	size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
	if ((bp = mem_sbrk(size)) == (void *) -1)
		return NULL;

	/* Initialize free block header/footer and the epilogue header */
	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

	/* Coalesce if the previous block was free */
	// Trade-off between util and thru
//    bp = coalesce(bp);

	return bp;
}