mm___2.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  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 number(void *result);

/* $begin mallocmacros */

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

/* Basic constants and macros */
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

#define WSIZE 4          /* word size (bytes) */  

#define DSIZE 8          /* doubleword size (bytes) */

#define CHUNKSIZE (1<<12)   /* initial heap size (bytes) */

#define MAX(x,y)  ((x) > (y)? (x):(y))   /* overhead of header and footer (bytes) */

/* Pack a size and allocated bit into a word */
#define PACK(size,alloc)  ((size) | (alloc))

/* overhead byte size */
#define OVERHEAD 8

/* Read and write a word at address p */
#define GET(p)       (*(size_t *)(p))

#define PUT(p,val)   (*(size_t *)(p) =(val))

/* Read the size and allocated fields from address p */
#define GET_SIZE(p)  (GET(p) & ~0x7)

#define GET_ALLOC(p)  (GET(p) & 0x1)

/* Given block ptr bp, compute address of its header and footer */
#define HDRP(bp)      ((char *)(bp)-WSIZE)

#define FTRP(bp)      ((char *)(bp)+GET_SIZE(HDRP(bp))-DSIZE)

/* Given block ptr bp, compute address of next and previous blocks */
#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)

/* $end mallocmacros */

void *heap_listp=NULL;   /* The global variable is a pointer to the first block */
void *header=NULL;       /* The header of the double linked list */
void *tail;              /* The tail of the double linked list */
int j=0;                 /* The global condition sign */
int length;              /* The length of the list */
void *numberheader;      /* The pointer of the number header */
int factuallength;       /* The facutal length */


/* 
 * mm_init - initialize the malloc package.
 */
int mm_init(void)
{
    /* initialize all the global variables*/
    header=NULL;              
    tail=NULL;
    numberheader=NULL;      /* set all the pointer to be null */
    j=0;
    length=0;
    factuallength=0;        /* set all the integers to 0 */
   
    /* initialize an extra space */
    if((numberheader=mem_sbrk(4*WSIZE+100*4))==NULL)
        return -1;          /* if get null,return due to false */
  
    /* initialize the heap_listp to the the next of the extra space */ 
    heap_listp=numberheader+4*100;
    
    PUT(heap_listp,0);      /* alignment padding */
    
    PUT(heap_listp+WSIZE,PACK(OVERHEAD,1));   /* prologue header */ 
    
    PUT(heap_listp+DSIZE,PACK(OVERHEAD,1));   /* prologue footer */ 
    
    PUT(heap_listp+WSIZE+DSIZE,PACK(0,1));    /* epilogue header */

    heap_listp += DSIZE;   

    /* Extend the empty heap with a free block of CHUNKSIZE bytes */
    if(extend_heap(1<<4)==NULL)
        return -1;         /* If error happens,return -1 */
    
    return 0;	           /* Normally exits */
}

/* Extends the heap with a new free block */
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));

    void* result=NULL;
    result=coalesce(bp);

    number(result);
    
    
    
    return result;
}


/*
 * 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));
    void *result= coalesce(ptr);
    number(result);
}


/*
 * 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;
    size_t newsize;
    void *pre=PREV_BLKP(ptr);
    void *next=NEXT_BLKP(ptr);
    size_t next_size;
    size_t pre_size;

    size_t prev_alloc=GET_ALLOC(FTRP(pre));
    size_t next_alloc=GET_ALLOC(HDRP(next));

    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(oldptr));
        size=((size+7)/8)*8;
	
        newsize=size+8;

        if(oldsize>=newsize)
        {
            return oldptr;
            
        }
        else
        {
            if(prev_alloc && next_alloc)
            {
                newptr=mm_malloc(size);
                memcpy(newptr,oldptr,oldsize-DSIZE);
                mm_free(oldptr);
		
                return newptr;
                
            }else if(!prev_alloc && next_alloc)
            {
                void *pre1=(void *)(GET(pre));
                
                void *next1=(void *)(GET(NEXT(pre)));
                
                pre_size=GET_SIZE(HDRP(pre));
                
                if(pre_size+oldsize>=newsize)
                {
                    
                    PUT(HDRP(pre),PACK(pre_size+oldsize,1));
                    PUT(FTRP(pre),PACK(pre_size+oldsize,1));
		    
		    char *temp1=(char *)pre;
		    char *temp2=(char *)oldptr;
		    int ii;
		    for(ii=0;ii<oldsize;ii++)
		    {
			*temp1=*temp2;
			 temp1++;
			 temp2++;
			
		    }
		    
                    if(pre1==NULL && next1==NULL)
                    {
                        tail=header=NULL;
                        
                        
                    }else if(pre1!=NULL && next1==NULL)
                    {
                        PUT(NEXT(pre1),(int)NULL);
                        tail=pre1;
                        
                    }
                    else if(pre1==NULL && next1!=NULL)
                    {
                        PUT(next1,(int)NULL);
                        header=next1;
                        
                    }
                    else if(pre1!=NULL && next1!=NULL)
                    {
                        
                        PUT(NEXT(pre1),(int)next1);
                        PUT(next1,(int)pre1);
                              
                    }
                    
                  return pre;  
                    
                }
                else
                {
                     newptr=mm_malloc(size);
                     memcpy(newptr,oldptr,oldsize-DSIZE);
                     mm_free(oldptr);
                     return newptr;
                     
                    
                }
                
                
                
                
            }else if(prev_alloc && !next_alloc)
            {
                void *pre2=(void *)(GET(next));
                void *next2=(void *)(GET(NEXT(next)));
                
                next_size=GET_SIZE(HDRP(next));

                
                if(next_size+oldsize>=newsize)
                {
                    PUT(HDRP(oldptr),PACK(next_size+oldsize,1));
                    PUT(FTRP(oldptr),PACK(next_size+oldsize,1));
                    if(pre2==NULL && next2==NULL)
                    {
                        tail=header=NULL;
                        
                        
                    }else if(pre2!=NULL && next2==NULL)
                    {
                        PUT(NEXT(pre2),(int)NULL);
                        tail=pre2;
                        
                    }
                    else if(pre2==NULL && next2!=NULL)
                    {
                        PUT(next2,(int)NULL);
                        header=next2;
                        
                    }
                    else if(pre2!=NULL && next2!=NULL)
                    {
                        PUT(NEXT(pre2),(int)next2);
                        PUT(next2,(int)pre2);
                              
                    }
                    return oldptr;
                    
                    
                }else
                    
                {
                     newptr=mm_malloc(size);
                     memcpy(newptr,oldptr,oldsize-DSIZE);
                     mm_free(oldptr);
                     return newptr;
                    
                }
                    
                   
                
            }
            else
            {
		

                pre_size=GET_SIZE(HDRP(pre));
                next_size=GET_SIZE(HDRP(next));
		
                void *pre1=(void *)(GET(pre));
                void *next2=(void *)(GET(NEXT(next)));

                if((oldsize+pre_size)>=newsize)
                {
                    PUT(HDRP(pre),PACK(pre_size+oldsize,1));
                    PUT(FTRP(pre),PACK(pre_size+oldsize,1));
		    
		              char *temp1=(char *)pre;
		              char *temp2=(char *)oldptr;
		              int ii;
		             for(ii=0;ii<oldsize;ii++)
		          {
			         *temp1=*temp2;
		        	 temp1++;
			          temp2++;
			
		           }

                     if(pre1==NULL)
                     {
                         PUT(next,(int)NULL);
                         header=next;
                         
                     }
                     else
                     {
                         PUT(NEXT(pre1),(int)next);
                         PUT(next,(int)pre1);
                         
                     }
                     

                     return pre;
                    
                    
                }
                
                        

                else if((oldsize+next_size)>=newsize)
                { 
                    PUT(HDRP(oldptr),PACK(next_size+oldsize,1));
                    PUT(FTRP(oldptr),PACK(next_size+oldsize,1));
                    if(next2==NULL)
                    {
                        PUT(NEXT(pre),(int)NULL);
                        tail=pre;
                        
                    }else
                    {
                        PUT(NEXT(pre),(int)next2);
                        PUT(next2,(int)pre);
                        
                    }
                    
                    return oldptr;
                    
                }
                
                
                else  if(pre_size+oldsize+next_size>=newsize)
                {

                    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++)
		          {
		        	*temp1=*temp2;
			        temp1++;
			       temp2++;
			
		           }
                    if(pre1==NULL && next2==NULL)
                    {
                        tail=header=NULL;
                        
                    }
                    else if(pre1==NULL && next2!=NULL)
                    {
                        PUT(next2,(int)NULL);
                        header=next2;
                        
                    }
                    else if(pre1!=NULL && next2==NULL)
                    {
                        PUT(NEXT(pre1),(int)NULL);
                        tail=pre1;
                        
                    }
                    else
                    {
                        PUT(NEXT(pre1),(int)next2);
                        PUT(next2,(int)pre1);