/**********************************************************
 * place
 * Mark the block as allocated.
 * Also create a new free block of the size difference if possible.
 **********************************************************/
void place(void* bp, size_t asize)
{
    remove_free_block(bp);
    /* Get the current block size */
    size_t bsize = GET_SIZE(HDRP(bp));

    // Create a block of the size difference and insert it into the free list.
    if (bsize - asize > 8*DSIZE) {
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));
        PUT(HDRP(NEXT_BLKP(bp)), PACK(bsize-asize, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(bsize-asize, 0));
        add_free_block(NEXT_BLKP(bp));
    } else {
        PUT(HDRP(bp), PACK(bsize, 1));
        PUT(FTRP(bp), PACK(bsize, 1));
    }
}

static void *match( size_t asize )
{
    if(asize == 8 && list_for_8 != NULL_POINTER) return list_for_8;
    if(asize <= 16 && list_for_16 != NULL_POINTER) return list_for_16;
	/* the most fit block */
	void *fit = NULL_POINTER;
	/* temporary location of the search */
	void *temp = root;
	/* use tree to implement a comparative best fit search */
	while(temp != NULL_POINTER){
		if( asize <= GET_SIZE(temp) ){
			fit = temp;
			temp = (void *)GET_LEFT(temp);
		} else
			temp = (void *)GET_RIGHT(temp);
	}
	return fit;
}

/**********************************************************
 * mm_free
 * Free the block and coalesce with neighbouring blocks
 **********************************************************/
void mm_free(void *bp)
{
    logg(3, "\n============ mm_free() starts ==============");
    if (LOGGING_LEVEL>0)
        mm_check();
	logg(1, "mm_free() with bp: %p; header: %zx(h); footer: %zx(h)", bp, GET(HDRP(bp)), GET(FTRP(bp)));
    if(bp == NULL){
      return;
    }

    // Mark the current block as free and do coalescing.
    size_t size = GET_SIZE(HDRP(bp));
    PUT(HDRP(bp), PACK(size,0));
    PUT(FTRP(bp), PACK(size,0));
    coalesce(bp);

    logg(3, "============ mm_free() ends ==============\n");
}

static void place(void *bp,size_t asize)
{
	size_t csize = GET_SIZE(bp);
	delete_node( bp );
	if((csize-asize) >= ALIGN_REQ){
	    size_t sign = 1 | GET_PRE_ALLOC_INFO(bp) | GET_PRE_8_INFO(bp);
		PUT_HDRP( bp,PACK(asize,sign) );

		void * temp = GET_NEXT(bp);
		PUT_HDRP( temp, PACK(csize-asize,2) );
		PUT_FTRP( temp, PACK(csize-asize,2) );
		
		insert_node( coalesce(temp) );
	} else{
	    size_t sign = 1 | GET_PRE_ALLOC_INFO(bp) | GET_PRE_8_INFO(bp);
		PUT_HDRP(bp,PACK(csize, sign) );
	}
}

/**********************************************************
 * free_list_marked_as_free
 * check if there are two consecutive free blocks in the
 * heap
 * we start at second block and check if previous one is
 * free, if current block is free
 *********************************************************/
int find_two_free_blocks(void){

    void *bp;

    if (heap_listp == NULL) return 1; //no blocks
    if (NEXT_BLKP(heap_listp) == NULL) return 1; //only one block

    for (bp = NEXT_BLKP(heap_listp); GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp))
    {
        if (!GET_ALLOC(HDRP(bp))) {
            if (!GET_ALLOC(PREV_BLKP(bp))) {
                return 0;
            }
        }
    }
    return 1;

}

/*
  Place block of asize bytes at start of free block bp and split if remainder would be at least minimum block size
  the requested size of free block
 */
static void place(void *bp, size_t asize){
    size_t csize = GET_SIZE(bp);

    if ((csize - asize) >= BLKSIZE) {
        SET_HDRP(bp, PACK(asize, 1));
        SET_FTRP(bp, PACK(asize, 1));
        mm_delete(bp);
        bp = NEXT_BLKP(bp);
        SET_HDRP(bp, PACK(csize-asize, 0));
        SET_FTRP(bp, PACK(csize-asize, 0));
        coalesce(bp);
    }
    else {
        SET_HDRP(bp, PACK(csize, 1));
        SET_FTRP(bp, PACK(csize, 1));
        mm_delete(bp);
    }
}

/* $begin mmfree */
void mm_free(void *bp)
{
/* $end mmfree */
    if(bp == 0) 
	return;

/* $begin mmfree */
    size_t size = GET_SIZE(HDRP(bp));
/* $end mmfree */
    if (heap_listp == 0){
	mm_init();
    }
/* $begin mmfree */

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

/* $begin mmfree */
void mm_free(void *bp)
{
    /*
     * mm_free(NULL) is now a no-op.  Previously _malloc(5); _free(0);
     * resulted in a page fault.
     *
     *  -- Mike Kasick <[email protected]>  Fri, 16 Feb 2007 14:51:36 -0500
     */
    if (bp != NULL) {
        int size;

        size = GET_SIZE(HDRP(bp));

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

/**********************************************************
 * mm_free
 * Free the block and coalesce with neighbouring blocks
 **********************************************************/
void mm_free(void *bp) {

	// If ptr is NULL, do nothing
	if (bp == NULL)
		return;

	// Coalesce with the neighboring block if possible
	bp = coalesce(bp);

	// Mark the header and footer of the current/coalesced block
	size_t size = GET_SIZE(HDRP(bp));
	PUT(HDRP(bp), PACK(size,0));
	PUT(FTRP(bp), PACK(size,0));

	// Insert this free block to the list
	insert_freelist(bp);

}

/**********************************************************
 * mm_free
 * Free the block and coalesce with neighbouring blocks
 **********************************************************/
void mm_free(void *bp)
{
	//	printf("IN FREE\n");
	//	printf("freeing block ptr %p\n",bp);

	if(bp == NULL){
		return;
	}

	size_t size = GET_SIZE(HDRP(bp));
	PUT(HDRP(bp), PACK(size,0));
	PUT(FTRP(bp), PACK(size,0));
	//print_fl();
	//printf("FROM MM_FREE\n");
	coalesce(bp);

	//print_fl();
}

//
// mm_realloc -- implemented for you
//
void *mm_realloc(void *ptr, size_t size)
{
  void *newp;
  size_t copySize;

  newp = mm_malloc(size);
  if (newp == NULL) {
    printf("ERROR: mm_malloc failed in mm_realloc\n");
    exit(1);
  }
  copySize = GET_SIZE(HDRP(ptr));
  if (size < copySize) {
    copySize = size;
  }
  memcpy(newp, ptr, copySize);
  mm_free(ptr);
  return newp;
}

void place(void* bp, size_t size){
    size_t oldsize = GET_SIZE(HDRP(bp));
    //If enough minimum space to split the block
    if(oldsize - size >= (DSIZE)){ //Splitting block to better utilize memory
        PUT(HDRP(bp), PACK(size, 1));
        PUT(FTRP(bp), PACK(size, 1));
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp), PACK(oldsize - size, 0));
        PUT(FTRP(bp), PACK(oldsize - size, 0));
        //coalesce(bp);
    }

    //Internal fragmentation could occur... if its not exactly equal
    else{
        PUT(HDRP(bp), PACK(oldsize, 1));
        PUT(FTRP(bp), PACK(oldsize, 1));
    }
}

void omtTestFree(omMemCell cell)
{
  void* addr = cell->addr;
  unsigned long spec = cell->spec;
  omBin bin = cell->bin;
  omBin orig_bin = cell->orig_bin;
  size_t size = GET_SIZE(spec);

  omtTestDebug(cell);

  if (IS_FREE_SIZE(spec))
  {
    if (IS_SLOPPY(spec))
      omfreeSize(addr, size);
    else
      omFreeSize(addr, size);
  }
  else if (bin != NULL && IS_FREE_BIN(spec))
    omFreeBin(addr, bin);
  else if (IS_FREE_BINADDR(spec) && (bin != NULL) && (size <= OM_MAX_BLOCK_SIZE))
  {
    omFreeBinAddr(addr);
  }
  else
  {
    if (IS_SLOPPY(spec))
      omfree(addr);
    else
      omFree(addr);
  }

  if (bin != NULL && IS_SPEC_BIN(spec))
  {
    if (orig_bin != NULL)
      omUnGetSpecBin(&orig_bin);
    else
      omUnGetSpecBin(&bin);
  }

  cell->addr = NULL;
  cell->spec = 0;
  cell->bin = NULL;
  cell->orig_bin = NULL;
}

/**********************************************************
 * mm_free
 * Free the block and coalesce with neighbouring blocks
 **********************************************************/
void mm_free(void *bp)
{

#if DEBUG >= 3
    printf("\nmm_free\n");

#endif
    //printf(" list before freeing..\n");
    //print_free_list();

    if(bp == NULL){
        printf("null found..");
        return;
    }

    size_t size = GET_SIZE(HDRP(bp));
    printf(" size %zu\n", size);
    PUT(HDRP(bp), PACK(size,0));

    PUT(FTRP(bp), PACK(size,0));

    if (bp == flhead){
        if (getNext(flhead) != NULL ){
            flhead = getNext(flhead);
        }
        else {
            flhead = NULL;
        }
    }
    if (bp == fltail){
        if (getPrev(fltail) != NULL){
            fltail = getPrev(fltail);
        } 
        else {
            fltail = NULL;    
        }
        
    }

    coalesce(bp);

    //printf("list after freeing\n");
    //print_free_list();
}

/*
* insert_node - Insert a block pointer into a segregated list. Lists are
* segregated by byte size, with the n-th list spanning byte
* sizes 2^n to 2^(n+1)-1. Each individual list is sorted by
* pointer address in ascending order.
*/
static void insert_node(void *ptr, size_t size) {
int list = 0;
void *search_ptr = ptr;
void *insert_ptr = NULL;
/* Select segregated list */
while ((list < LISTS - 1) && (size > 1)) {
size >>= 1;
list++;
}
/* Select location on list to insert pointer while keeping list
organized by byte size in ascending order. */
search_ptr = free_lists[list];
while ((search_ptr != NULL) && (size > GET_SIZE(HEAD(search_ptr)))) {
insert_ptr = search_ptr;
search_ptr = PRED(search_ptr);
}
/* Set predecessor and successor */
if (search_ptr != NULL) {
if (insert_ptr != NULL) {
SET_PTR(PRED_PTR(ptr), search_ptr);
SET_PTR(SUCC_PTR(search_ptr), ptr);
SET_PTR(SUCC_PTR(ptr), insert_ptr);
SET_PTR(PRED_PTR(insert_ptr), ptr);
} else {
SET_PTR(PRED_PTR(ptr), search_ptr);
SET_PTR(SUCC_PTR(search_ptr), ptr);
SET_PTR(SUCC_PTR(ptr), NULL);
/* Add block to appropriate list */
free_lists[list] = ptr;
}
} else {
if (insert_ptr != NULL) {
SET_PTR(PRED_PTR(ptr), NULL);
SET_PTR(SUCC_PTR(ptr), insert_ptr);
SET_PTR(PRED_PTR(insert_ptr), ptr);
} else {
SET_PTR(PRED_PTR(ptr), NULL);
SET_PTR(SUCC_PTR(ptr), NULL);
/* Add block to appropriate list */
free_lists[list] = ptr;
}
}
return;
}

//将空闲位标志为分配位
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));
	}
}

void print_free_list() {
	int i;
	unsigned int fsize, falloc;
	for (i = 0; i < FREE_LIST_SIZE; i++) {
		printf("free_list[%d]: ",i);
		void *cur = (void *)free_lists[i];
		while(cur != NULL) {
			fsize = GET_SIZE(HDRP(cur));
			// confirm that it is not allocated
			falloc = GET_ALLOC(HDRP(cur));
			printf("[addr = %p, size = %u]", cur, fsize);
			if(falloc)
				printf(", ERROR: ALLOCATED!!");
			printf("-->");
			cur = NEXT_FREE_BLKP(cur);
		}
		printf("\n");
	}
}

/* used in realloc */
static void *replace(void *bp, size_t asize)
{
    size_t csize = GET_SIZE(HDRP(bp));

    if((csize - asize) >= (2 * DSIZE))
    {
        //contain old block data
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));

        void *p = NEXT_BLKP(bp);
        PUT(HDRP(p), PACK((csize - asize), 0));
        PUT(FTRP(p), PACK((csize - asize), 0));
    	add_free(p);
        return bp;
    }
    else return bp; //no action

}

void place(void *bp, size_t asize)
     /* $end mmplace-proto */
{
    size_t csize = GET_SIZE(HDRP(bp));   
int k=in_heap(bp);
printf("some %d useless\n",k);
    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));
    }

}

/**********************************************************
 * insert_freelist
 * Place the free block ptr bp on the appropriated
 * segregated free list
 * Insert at the first element of the list
 **********************************************************/
void insert_freelist(intptr_t * bp) {
	// Find out which list should the free block insert to
	int index = size_to_index(GET_SIZE(HDRP(bp)));

	// Head of the list
	intptr_t * listp = seg_free_list[index];

	// Set the prev_ptr and next_ptr of the current block
	PUT(bp, GET(seg_free_list[index]));	// next
	PUTP(PREVP(bp), listp);             // prev

	// If the list previously has elements inside
	if (GET(listp) != 0) {
		// Set the next element to point to the current bp
		PUTP(PREVP(*listp), bp);
	}
	//Set head to point to the current bp
	PUTP(listp, bp);
}