//malloc.c 

#define NULL 0  

union Node{  
      
    struct{  
        union Node *next;  
        unsigned int size;  
    }s; 

    long a;      /*内存对齐*/ 
};  

typedef union Node Header;  

static Header *startup = NULL;   /*空闲链表开始指针*/ 

extern unsigned int _heapstart;  

const int E = 5;  

void *malloc(unsigned int nunits)  
{ 
    Header *p, *prevp; 
    Header *morecore(unsigned int); 
      
    if((prevp = startup) == NULL) 
    { 
        startup = (Header *)(_heapstart - 16); 
        startup->s.size = 0; 
        startup->s.next = startup; 
    }  

    nunits = (nunits + 3) & ~3;    /*内存对齐*/ 

    for(p = startup->s.next; ; prevp = p, p = p->s.next) 
    { 
        if(p->s.size >= nunits) 
        { 
            if(p->s.size <= nunits + E) 
            { 
                prevp->s.next = p->s.next; 
            } 
            else 
            { 
                p->s.size -= (nunits + sizeof(Header)); 
                (char *)p += (p->s.size + sizeof(Header)); 
                p->s.size = nunits; 
            } 

            startup = prevp; 
            return (void *)(p + 1); 
        } 

        if(p == startup) 
        { 
            if((p = morecore(nunits)) == NULL) 
            { 
                return NULL; 
            } 
        } 
    }      
}  

Header *morecore(unsigned int num)  
{  
    Header *up;  
    unsigned int temp;  
    unsigned int former;      
    void free(void *); 

    former = _heapstart;  
    temp = _heapstart + sizeof(Header) + num;  
      
    if(temp < 65535) 
    {  
        _heapstart = temp; 
        up = (Header *)former; 
        up->s.size = num; 
        free((void *)(up + 1)); 
        return startup; 
    } 
    else 
    { 
        return NULL; 
    } 
} 

void free(void *ptr) 
{ 
    Header *p; 

    Header *freep = (Header *)ptr; 

    for(p = startup; ;p = p->s.next) 
    { 
        if((freep - 1) > p && (freep - 1) < p->s.next)  /*在两个空闲块之间*/ 
        { 
            break; 
        } 
        if(p >= p->s.next && ((freep - 1) > p))         /*在空闲链表的末尾*/ 
        { 
            break; 
        } 
    } 
             
        if(((char *)(freep - 1) + (freep - 1)->s.size + sizeof(Header)) == p->s.next) 
        { 
        (freep - 1)->s.size += p->s.next->s.size + sizeof(Header); 
        (freep - 1)->s.next = p->s.next->s.next; 
        } 
        else 
        { 
                (freep - 1)->s.next = p->s.next; 
        } 

         
    if(((char *)p + p->s.size + sizeof(Header)) ==  (freep - 1)) 
    { 
        p->s.size += (freep - 1)->s.size + sizeof(Header); 
        p->s.next = (freep - 1)->s.next; 
    } 
    else 
       { 
               p->s.next = (freep - 1);     
        } 
         
        startup = p; 
}