mm_6.c

ICS 课程的Lab7

    if((bp = extend_heap(extendsize/WSIZE)) == NULL)
    {
        return NULL;
    }
    //   printf("exit malloc\n");
   return  place(bp,asize);
    
}
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));

    void *temp1;
    void *temp2;
    
   
    
    if(prev_alloc && next_alloc)
    {
     	if(header==NULL)
    	{
	       PUT(bp,(int)NULL);
	       PUT(NEXT(bp),(int)NULL);
	       tail=header=bp;
    	}
	else
	{
	    if(bp<header)
	    {
            PUT(bp,(int)NULL);
            PUT(NEXT(bp),(int)header);
            PUT(header,(int)bp);
            header=bp;
		
	    }
        
	    for(temp1=header;temp1!=NULL;temp1=(void *)(GET(NEXT(temp1))))
	    {
             
		temp2=(void *)(GET(NEXT(temp1)));
		if(temp2!=NULL)
		{
		    if(bp>temp1 &&bp<temp2)
		    {
			PUT(NEXT(temp1),(int)(bp));
			PUT(bp,(int)temp1);
			
			PUT(NEXT(bp),(int)temp2);
			PUT(temp2,(int)bp);

			return bp;
		    }
		}
		else
		{
		    if(bp>temp1)
		    {
                        PUT(NEXT(temp1),(int)bp);
                        PUT(bp,(int)temp1);
                        PUT(NEXT(bp),(int)NULL);
                        tail=bp;
		    }


                  }
	    }
        
	    
	}
	large(GET_SIZE(HDRP(bp)),bp);
	
	/* if (largest_size < GET_SIZE(HDRP(bp)))
	 {
	     if (largest_num > 0){
		 second_size = largest_size;
		 second_num = largest_num;
	     }
	     largest_size = GET_SIZE(HDRP(bp));
	     largest_num = 1;
	 }
	 else if (largest_size == GET_SIZE(HDRP(*/
        return bp;
    }
    else if(prev_alloc && !next_alloc)
    {

	
    	void *nextBp=NEXT_BLKP(bp);
     
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp),PACK(size,0));
        PUT(FTRP(bp),PACK(size,0));
	
        temp1=(void *)(GET(nextBp));
        temp2=(void *)(GET(NEXT(nextBp)));

	if (GET_SIZE(HDRP(nextBp)) == largest_size )
	    largest_num --;
	else if (GET_SIZE(HDRP(nextBp)) == second_size )
	    second_num --;
       
	
        PUT(nextBp,(int)NULL);
        PUT(NEXT(nextBp),(int)NULL);
	
	if(temp1==NULL && temp2==NULL)
	{ 
	    PUT(bp,(int)NULL);
	    PUT(NEXT(bp),(int)NULL);
	    tail=header=bp;
	    
	}else if(temp1!=NULL && temp2==NULL)

        {
	    PUT(NEXT(temp1),(int)bp);
	    PUT(bp,(int)temp1);
	    PUT(NEXT(bp),(int)NULL);
        tail=bp;
	    
	}else if(temp1==NULL && temp2!=NULL)

	  {	 
	    PUT(NEXT(bp),(int)temp2);
	    PUT(temp2,(int)bp);
	    PUT(bp,(int)NULL);
	    
	    header=bp;
	    
	}else
	{
	   
	     PUT(NEXT(temp1),(int)bp);
	     PUT(bp,(int)temp1);
             PUT(temp2,(int)bp);
	     PUT(NEXT(bp),(int)temp2);

	  
	    
	}
	
	large(GET_SIZE(HDRP(bp)),bp);
	/*   if (largest_size < GET_SIZE(HDRP(bp)))
    {
	largest_size = GET_SIZE(HDRP(bp));
	largest_changed = 0;
	largest_ptr = bp;
	}*/
        return bp;
    }
    else if(!prev_alloc && next_alloc)
    {
	
	if (GET_SIZE(HDRP(PREV_BLKP(bp))) == largest_size )
	    largest_num --;
	else if (GET_SIZE(HDRP(PREV_BLKP(bp))) == second_size )
	    second_num --;
	
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(FTRP(bp),PACK(size,0));
        PUT(HDRP(PREV_BLKP(bp)),PACK(size,0));
	large(GET_SIZE(HDRP(PREV_BLKP(bp))),PREV_BLKP(bp));
	/* if (largest_size < GET_SIZE(HDRP(PREV_BLKP(bp))))
	 {
	largest_size = GET_SIZE(HDRP(PREV_BLKP(bp)));
	largest_changed = 0;
	largest_ptr = PREV_BLKP(bp);
	}*/

        return PREV_BLKP(bp);
        
    }else
    {
       
            void *pre=PREV_BLKP(bp);
            void *next=NEXT_BLKP(bp);
            void *next1=(void *)(GET(NEXT(next)));
            PUT(next,(int)NULL);
	    PUT(NEXT(next),(int)NULL);
	    if (GET_SIZE(HDRP(pre)) == largest_size )
		largest_num --;
	    else if (GET_SIZE(HDRP(pre)) == second_size )
		second_num --;
	    	if (GET_SIZE(HDRP(next)) == largest_size )
		    largest_num --;
		else if (GET_SIZE(HDRP(next)) == second_size )
		    second_num --;
	 
        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));

       
        if(next1==NULL)
	{
	    PUT(NEXT(pre),(int)NULL);
            tail=pre;
	}
	else
	{
	    PUT(NEXT(pre),(int)next1);
	    PUT(next1,(int)pre);
	    
	}
	large(GET_SIZE(HDRP(pre)),pre);
	return pre;
        
    }
    
    
    
    
    
}

static void *find_fit(size_t asize)
{
    void *bp;

    if(header==NULL)
    {
	return NULL;
    }
   

	  for(bp=header;bp!=NULL;bp=(void *)(GET(NEXT(bp))))
      {
    	if(asize<=GET_SIZE(HDRP(bp)))
    	{
	    
             return bp;
    	}
    


      }
	
      
    
    
   
   
  
    

    return NULL;
    
    
}

static void *place(void *bp,size_t asize)
{
    size_t csize = GET_SIZE(HDRP(bp));
    
    void *pre=(void *)(GET(bp));
    void *next=(void *)(GET(NEXT(bp)));
    
    
    if (GET_SIZE(HDRP(bp)) >= largest_size)
	largest_size --;
    // printf("after place,largest size: %d\n",largest_size);
    

    if((csize - asize) >= (DSIZE + OVERHEAD))
    {
             
	//if(random()%2==0)
	//	{
	    
	
	// PUT(bp,(int)NULL);
	// PUT(NEXT(bp),(int)NULL);
	     
	// 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));


	
	// if(pre==NULL && next==NULL)
	// {
	//  PUT(bp,(int)NULL);
	// PUT(NEXT(bp),(int)NULL);
	// tail=header=bp;
	    
	// }else if(pre!=NULL && next==NULL)
	// {
	  
	// PUT(NEXT(pre),(int)bp);
	// PUT(bp,(int)pre);
	// PUT(NEXT(bp),(int)NULL);
	// tail=bp;
	    
	    
	// }
	//  else if(pre==NULL && next!=NULL)
	//	{
	    
	// PUT(bp,(int)NULL);
	// PUT(NEXT(bp),(int)next);
	// PUT(next,(int)bp);
	//  header=bp;
	    
	//	}else
	//{

	// PUT(NEXT(pre),(int)bp);
	// PUT(bp,(int)pre);
	    
	// PUT(NEXT(bp),(int)next);
	// PUT(next,(int)bp);
	    
	//	}
	//	}
	//	else
	//	{
	// PUT(HDRP(bp),PACK(csize-asize,0));
	// PUT(FTRP(bp),PACK(csize-asize,0));
	// bp=NEXT_BLKP(bp);

	// PUT(HDRP(bp),PACK(asize ,1));
	// PUT(FTRP(bp),PACK(asize ,1));

	    
	//	}
                PUT(HDRP(bp),PACK(csize-asize,0));
        	PUT(FTRP(bp),PACK(csize-asize,0));
		//	printf("free place size : %d\n",GET_SIZE(HDRP(bp)));
		large(GET_SIZE(HDRP(bp)),bp);
        	bp=NEXT_BLKP(bp);

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

       
	 }
	 else
	{
	 PUT(HDRP(bp),PACK(csize,1));
	PUT(FTRP(bp),PACK(csize,1));
	
        if(pre==NULL && next==NULL)
	{
	    tail=header=NULL;
	    
	}else if(pre==NULL && next!=NULL)
	{

	    PUT(next, (int)NULL);
	    header=next;
	    
	}else if(pre!=NULL && next==NULL)
	{
	    
	    PUT(NEXT(pre),(int)NULL);
        tail=pre;
	}else
	{
	    PUT(NEXT(pre),(int)next);
	    PUT(next,(int)pre);
	}
    }
    // printf("after place,largest size: %d\n",largest_size);
   return bp;
    
}

static void large(int num,void *ptr)
{
    if (largest_size < num)
    {
	if (largest_num > 0){
	    second_size = largest_size;
	    second_ptr = largest_ptr;
	    second_num = largest_num;
	}
	largest_num = 1;
	largest_size = num;
	largest_ptr = ptr;
    }
    else if(largest_size == num)
    {
	if (largest_num <= 0)
	    largest_num = 1 ;
	else
	    largest_num ++;
    }
    else if(largest_num <= 0)
    {
	if (second_size < num || second_num < 0)
	{
	    largest_num = 1;
	    largest_size = num;
	    largest_ptr = ptr;
	}
    }
    else if(second_size < num)
    {
	second_num = 1;
	second_size = num;
	second_ptr = ptr;
    }
    else if(second_size == num)
    {
	if (second_num <= 0)
	    second_num = 1;
	else
	    second_num ++;
    }
}

static void checkblock(void *bp) 
{
    if ((size_t)bp % 8)
	printf("Error: %p is not doubleword aligned\n", bp);
    if (GET(HDRP(bp)) != GET(FTRP(bp)))
	printf("Error: header does not match footer\n");
}

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, 
	   hsize, (halloc ? 'a' : 'f'), 
	   fsize, (falloc ? 'a' : 'f')); 
}

/* 
 * mm_checkheap - Check the heap for consistency 
 */
void mm_check(void) 
{
    char *bp = heap_listp;

    /*if (verbose)
      printf("Heap (%p):\n", heap_listp);*/

    if ((GET_SIZE(HDRP(heap_listp)) != DSIZE) || !GET_ALLOC(HDRP(heap_listp)))
	printf("Bad prologue header\n");
    checkblock(heap_listp);

    for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
	//if (verbose) 
	    printblock(bp);
	checkblock(bp);
    }
     
    //if (verbose)
	printblock(bp);
    if ((GET_SIZE(HDRP(bp)) != 0) || !(GET_ALLOC(HDRP(bp))))
	printf("Bad epilogue header\n");
}

/* The remaining routines are internal helper routines */