mm_3.c

ICS 课程的Lab7

                else  if(pre_size+oldsize+next_size>=newsize)
                {
		    /* Set the sign */
                    PUT(HDRP(pre),PACK(pre_size+oldsize+next_size,1));
                    PUT(FTRP(pre),PACK(pre_size+oldsize+next_size,1));

		    char *temp1=(char *)pre;
		    char *temp2=(char *)oldptr;
		    int ii;
		    
		    for(ii=0;ii<oldsize;ii++)   /* Copy the data to the new block */
		    {
			*temp1=*temp2;
			temp1++;
			temp2++;
		    }
		    
		    /* The pre in the list is null and the next is null too */
                    if(pre1==NULL && next2==NULL)    
                        tail=header=NULL; 
		    /* The pre in the list is null and the next is not null */
                    else if(pre1==NULL && next2!=NULL)
                    {
                        PUT(next2,(int)NULL);   /* Set the next of the header */
                        header=next2;           /* Set the header */
                    }
		    /* The pre in the list is not null and the next is null */
                    else if(pre1!=NULL && next2==NULL)
                    {
                        PUT(NEXT(pre1),(int)NULL); /* set the next*/
                        tail=pre1;                 /* set the tail */
                    }
		    /* The pre in the list is not null and the next is not null too */
                    else
                    {
                        PUT(NEXT(pre1),(int)next2);  /* set the next of the pre */
                        PUT(next2,(int)pre1);        /* set the pre of the next */
                    }
                    return pre;                      /* return the pre */
                }
                else      /* All the total size is not big enough */
                { 
		    newptr=mm_malloc(size);   /* malloc a new block */
		    memcpy(newptr,oldptr,oldsize-DSIZE); /* copy the data */
		    mm_free(oldptr);          /* free the old block */
		    return newptr;            /* return the new block pointer */
                }   
            }   
        }   
    }
}


/* 
 * mm_malloc - Allocate a block with at least size bytes of payload 
 */
/* $begin mmmalloc */
void *mm_malloc(size_t size)
{
    size_t asize;               /* adjusted block size */
    size_t extendsize;          /* amount to extend heap if no fit */
    void  *bp;                  /* The return pointer */
    j++;                        /* increase j */
    
    
    if(size<=0)                 /* if size smaller than 0,just return */
        return NULL;

    if(size <= DSIZE)           /* If the size smaller than two word */
        asize = DSIZE + OVERHEAD;
    else                        /* larger than two words */
        asize = DSIZE *((size +(OVERHEAD) + (DSIZE - 1))/DSIZE);

    if((bp = find_fit(asize)) !=NULL)  /* find the apporiate one and place it */        
        return place(bp,asize);

    extendsize = MAX(asize,CHUNKSIZE); /* doesnot find the fit one ,and extend the size */

    if((bp = extend_heap(extendsize/WSIZE)) == NULL)  /* Extend the heap failed */
        return NULL;

    return  place(bp,asize);    /* return the place pointer */
}

/*
 * coalesce - boundary tag coalescing. Return ptr to coalesced block
 */
/* $begin mmfree */
static void *coalesce(void *bp)
{
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));   /* WHether the pre block allocated*/
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));   /* Whether the next block allocated*/
    size_t size       = GET_SIZE(HDRP(bp));    /* Get size of the current one */

    void *temp1;      /* Two temporary variables */
    void *temp2;
    
   
    /* Address order double linked list */
    if(prev_alloc && next_alloc)             /* case 1 */ /*pre allocated and next allocated*/
    {
     	if(header==NULL)               /* header is null in the beginning */
    	{
	       PUT(bp,(int)NULL);
	       PUT(NEXT(bp),(int)NULL);
	       tail=header=bp;
    	}
	else                          /* header is not null in the beginning */
	{
	    if(bp<header)             /* The bp is less then header */
	    {
		PUT(bp,(int)NULL);
		PUT(NEXT(bp),(int)header);
		PUT(header,(int)bp);
		header=bp;
	    }
	    
	    /* Look forward to find the next free list */
	    for(temp1=header;temp1!=NULL;temp1=(void *)(GET(NEXT(temp1))))
	    {
		temp2=(void *)(GET(NEXT(temp1)));
		if(temp2!=NULL)          /* Not null */
		{
		    if(bp>temp1 &&bp<temp2) /* bp is between them */
		    {
			PUT(NEXT(temp1),(int)(bp));   /* add bp to them */
			PUT(bp,(int)temp1);
			
			PUT(NEXT(bp),(int)temp2);     /* change the list */
			PUT(temp2,(int)bp);

			return bp;                    /* return bp */
		    }
		}
		else
		{
		    if(bp>temp1)        /* temp2 is null ,bp is the tail */
		    {
                        PUT(NEXT(temp1),(int)bp);     /* add bp to the list */
                        PUT(bp,(int)temp1);
                        PUT(NEXT(bp),(int)NULL);
                        tail=bp;                      /* set bp to be tail */
		    }
		}
	    }        
	}
        return bp;       /* return bp */
    }
    else if(prev_alloc && !next_alloc)             /* Case 2 */
    {
    	void *nextBp=NEXT_BLKP(bp);             /* The next block */
     
        size += GET_SIZE(HDRP(nextBp));         /* Add the size to it */
        PUT(HDRP(bp),PACK(size,0));
        PUT(FTRP(bp),PACK(size,0));
	
        temp1=(void *)(GET(nextBp));           /* The next */
        temp2=(void *)(GET(NEXT(nextBp)));     /* The next of next in the list */
      	
        PUT(nextBp,(int)NULL);                 /* set the next */
        PUT(NEXT(nextBp),(int)NULL);           /* set the next in the list */
	
	if(temp1==NULL && temp2==NULL)         /* the pre and next is both null */
	{ 
	    PUT(bp,(int)NULL);                 /* set the list*/ 
	    PUT(NEXT(bp),(int)NULL);
	    tail=header=bp;                    /* set the header and tail both to be bp*/
	    
	}else if(temp1!=NULL && temp2==NULL)   /* after temp1 and be the tail */
        {
	    PUT(NEXT(temp1),(int)bp);          /* Set the list*/
	    PUT(bp,(int)temp1);
	    PUT(NEXT(bp),(int)NULL);
	    tail=bp;                           /* Set bp to be tail */
	}else if(temp1==NULL && temp2!=NULL)   /* before the temp1 and temp2 and is the header*/
	{	 
	    PUT(NEXT(bp),(int)temp2);          /* Set the list */
	    PUT(temp2,(int)bp);
	    PUT(bp,(int)NULL);
	    header=bp;                         /* Set bp to be header */	    
	}else                                  /* between temp1 and temp2*/
	{	   
	    PUT(NEXT(temp1),(int)bp);         /* set the pre*/
	    PUT(bp,(int)temp1);           
	    PUT(temp2,(int)bp);               /* set the next*/
	    PUT(NEXT(bp),(int)temp2);	  	    
	}	      
        return bp;
    }
    else if(!prev_alloc && next_alloc)         /* Case  3 */
    {
        size += GET_SIZE(HDRP(PREV_BLKP(bp))); /* add the size of the pre to the total size*/
        PUT(FTRP(bp),PACK(size,0));
        PUT(HDRP(PREV_BLKP(bp)),PACK(size,0));

        return PREV_BLKP(bp);                  /* return the prev block pointer */        
    }else                                      /* Case 4*/
    {       
	void *pre=PREV_BLKP(bp);               /* Set the list */
	void *next=NEXT_BLKP(bp);
	void *next1=(void *)(GET(NEXT(next)));
	PUT(next,(int)NULL);
	PUT(NEXT(next),(int)NULL);             /* add it into the list*/

	/* Get the total size with the neighbour ones */
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));

	/* Set the block sign */
        PUT(HDRP(PREV_BLKP(bp)),PACK(size,0));

        PUT(FTRP(NEXT_BLKP(bp)),PACK(size,0));
       
        if(next1==NULL)                /* in the last of the list */
	{
	    PUT(NEXT(pre),(int)NULL);
            tail=pre;                  /* to be the new tail */
	}
	else                           /* not in the last */
	{
	    PUT(NEXT(pre),(int)next1);
	    PUT(next1,(int)pre);       /* add to the list */	    
	}

	return pre;                      /* return the pre block pointer */        
    }                    
}
/* $end mmfree */


/* 
 * find_fit - Find a fit for a block with asize bytes 
 */
/* $begin mmfirstfit */
/* $begin mmfirstfit-proto */
static void *find_fit(size_t asize)
{
    void *bp;      /* The return block pointer */

    if(header==NULL)    /* If the header is null ,return null */
    	return NULL;    
   
    if(j%2==1)    /* whether start from beginning or the end */
    {                             
	/* Search a fit block from the header */
        for(bp=header;bp!=NULL;bp=(void *)(GET(NEXT(bp))))	    
	    if(asize<=GET_SIZE(HDRP(bp)))    	/* Find a fit one */	    
		return bp;    
    }	                          
    else         /* search from the end of the list */
    {
        if(tail==NULL)        /*If tail is null ,return null */
            return NULL;                    
        
	/* Search a fit block from the tail */
	for(bp=tail;bp!=NULL;bp=(void *)(GET(bp)))      
	    if(asize<=GET_SIZE(HDRP(bp)))    	/* Find a fit one */	    
		return bp;    	              
    }                                                                  
    return NULL;         
}
/* $end mmfirstfit */


/* 
 * place - Place block of asize bytes at start of free block bp 
 *         and split if remainder would be at least minimum block size
 */
/* $begin mmplace */
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)));

    /* Whether the block can be splitted into two smaller ones */
    if((csize - asize) >= (DSIZE + OVERHEAD))
    {	
	if(j%2==1)                     /* Case 1 */
	{	    	
	    PUT(bp,(int)NULL);               /* Set the list */
	    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)     /* The pre and next are both null */
	    {
		PUT(bp,(int)NULL);
           	PUT(NEXT(bp),(int)NULL);
	        tail=header=bp;		
	    }else if(pre!=NULL && next==NULL) /* The pre is not null and next is null */
	    {		
		PUT(NEXT(pre),(int)bp);      /* Set the list */
		PUT(bp,(int)pre);
         	PUT(NEXT(bp),(int)NULL);
	        tail=bp;			    
	    }
	    else if(pre==NULL && next!=NULL)  /* The pre is null and next is not  null */
	    {		
		PUT(bp,(int)NULL);            /* Set the list */
		PUT(NEXT(bp),(int)next);
		PUT(next,(int)bp);
		header=bp;		
	    }else                             /* Both are not null */ 
	    {
		PUT(NEXT(pre),(int)bp);       /* Set the list */
		PUT(bp,(int)pre);		
		PUT(NEXT(bp),(int)next);
		PUT(next,(int)bp);	    
	    }

	    return bp;
	}
	else	       /* Case 2 */
	{
            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));            
	}                       
    }
    else   /* The left is not big enough for a new block */
    {        
	PUT(HDRP(bp),PACK(csize,1));    /* Set the block mark*/
    	PUT(FTRP(bp),PACK(csize,1));
	
        if(pre==NULL && next==NULL)     /* The pre and next are both null */
	    tail=header=NULL;	    
	else if(pre==NULL && next!=NULL) /* The pre is null and next is not null */
	{
	    PUT(next, (int)NULL);
	    header=next;	    
	}else if(pre!=NULL && next==NULL) /* The pre is not null and next is null */
	{	    
	    PUT(NEXT(pre),(int)NULL);
	    tail=pre;
	}else                            /* The pre and next are both not null */
	{
	    PUT(NEXT(pre),(int)next);
	    PUT(next,(int)pre);
	}
    }                  
    return bp;                           /* return the block pointer */
}
/* $end mmplace */