mm_5.c

ICS 课程的Lab7

/*
 * 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.
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>

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

/* declare mm_check as static */
static int mm_check(void);


static void *extend_heap(size_t words);
static void *coalesce(void *bp);
static void *find_fit(size_t asize);
static void place(void *bp,size_t asize);
static void copy(void *aim,void *from,size_t size);

/* 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)))

#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 OVERHEAD 8

#define GET(p)   (*(size_t *)(p))

#define PUT(p,val)   (*(size_t *)(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 NEXT(bp)      ((char *)(bp)+WSIZE)

void *heap_listp;
void *header=NULL;
void *largest_ptr = NULL;
size_t largest_size = 0;
int  largest_changed = 0;
void *current_ptr = NULL;

/* 
 * mm_init - initialize the malloc package.
 */
int mm_init(void)
{
    header=NULL;
    largest_ptr = NULL;
    largest_size = 0;
    largest_changed = 0;
    current_ptr = NULL;
    
    if((heap_listp=mem_sbrk(4*WSIZE))==NULL)
    {
        return -1;
    }
    PUT(heap_listp,0);
    
    PUT(heap_listp+WSIZE,PACK(OVERHEAD,1));
    
    PUT(heap_listp+DSIZE,PACK(OVERHEAD,1));
    
    PUT(heap_listp+WSIZE+DSIZE,PACK(0,1));

    heap_listp += DSIZE;
    if(extend_heap(CHUNKSIZE/WSIZE)==NULL)
    {
        return -1;
    }
    
    
    return 0;	 
}

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

    size=(words%2) ? (words+1)*WSIZE:words*WSIZE;
    if((int)(bp=mem_sbrk(size))<0)
        return NULL;

    PUT(HDRP(bp),PACK(size,0));
    PUT(FTRP(bp),PACK(size,0));
    PUT(HDRP(NEXT_BLKP(bp)),PACK(0,1));

    return coalesce(bp);
}


/*
 * mm_free
 - Freeing a block does nothing.
 */
void mm_free(void *ptr)
{
    size_t size=GET_SIZE(HDRP(ptr));

    PUT(HDRP(ptr),PACK(size,0));
    PUT(FTRP(ptr),PACK(size,0));

    coalesce(ptr);
}


/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
void *mm_realloc(void *ptr, size_t size)
{

    void *oldptr=ptr;
    void *newptr;
    size_t oldsize;

    if(size < 0)
    {
        return NULL;
        
    }

    if(ptr == NULL)
    {
       return  mm_malloc(size); 
        
    }else if(size == 0)
    {
        mm_free(ptr);
        
        return NULL;
    }
    else 
    {
        oldsize=GET_SIZE(HDRP(ptr));
	mm_free(oldptr);
        newptr = mm_malloc(size);

        size =  GET_SIZE(HDRP(newptr));
        
        if (oldsize <size)
        {
            //memcpy(newptr,oldptr,oldsize-DSIZE);
	    copy(newptr,oldptr,oldsize-DSIZE);
            
        }else
        {
            
            //memcpy(newptr,oldptr,size-DSIZE);
	    copy(newptr,oldptr,oldsize-DSIZE);
        }

	//mm_free(oldptr);

           return newptr;
        
    }
}

/*
 * mm_check - Does not currently check anything
 */
//static int mm_check(void)
//{
// printf("You have no hopes!"); 
// return 1;
//}

void *mm_malloc(size_t size)
   {
    size_t asize;
    size_t extendsize;
    void  *bp;
    if(size<=0)
    {
        return NULL;
    }

    if(size <= DSIZE)
    {
        asize = DSIZE + OVERHEAD;
        
    }else
    {
        asize = DSIZE *((size +(OVERHEAD) + (DSIZE - 1))/DSIZE);
    }

    if(!largest_changed && asize > largest_size){
	 extendsize = MAX(asize,CHUNKSIZE);

	 if((bp = extend_heap(extendsize/WSIZE )) == NULL)
	 {

	     return NULL;
	 }
	  place(bp,asize);
	  return bp;
	
    }
    if( (bp = find_fit(asize)) !=NULL)
    {
        place(bp,asize);
	if (GET_SIZE(HDRP(bp)) >= largest_size) {
	    largest_changed = 1;
	}
        return bp;
    }

   
    extendsize = MAX(asize,CHUNKSIZE);

    if((bp = extend_heap(extendsize/WSIZE )) == NULL)
    {

        return NULL;
    }
    
     place(bp,asize);
    
    return bp;
}
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 *current;
    void *pre;
    void *next;
    
    
    //the previous and the next are both allocated
    if(prev_alloc && next_alloc)
    {
        //judge whether the header is null or not 
        if(header==NULL)
        {
            
             PUT(bp,(int)NULL);
             PUT(NEXT(bp),(int)NULL);
            
            header=bp;
           
        }
        //the header is not null
        else
        {
            //insert the newheader;
            PUT(header,(int)bp);
            PUT(NEXT(bp),(int)header);
            
            PUT(bp,(int)NULL);
            
            header=bp;
            
        }    
        //return header;
    }

    //the previous is allocated ,the next is not.
    else if(prev_alloc && !next_alloc)
    {
        
        current = NEXT_BLKP(bp);
        pre = (void *)(GET(current));
        next=(void *)(GET(NEXT(current)));
        
        PUT(current,(int)NULL);
        PUT(NEXT(current),(int)NULL);

        //increase the length
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp),PACK(size,0));
        PUT(FTRP(bp),PACK(size,0));

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

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

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

            
            PUT(header ,(int)bp);
            PUT(NEXT(bp),(int)header);
            PUT(bp,(int)NULL);

            header=bp;
                
        }
	// return header;      
    }
    //the previous is not allocated and the next is allocated
    else if(!prev_alloc && next_alloc)
    {
        
        current=PREV_BLKP(bp);
        pre = (void *)(GET(current));
        next=(void *)(GET(NEXT(current)));

        PUT(current,(int)NULL);
        PUT(NEXT(current),(int)NULL);

        
        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);
        
        if(pre==NULL && next==NULL)
        {
          
            PUT(bp,(int)NULL);
            PUT(NEXT(bp),(int)NULL);
            header=bp;
           
        }