C语言中malloc函数实现

C语言中malloc函数实现

  该实现使用大容量的静态数组作为堆，但也可使用操作系统调用分配堆。

定义了一个数据类型Header保存每个存储器块的簿记信息，定义了具有Header类型元素的堆数组，

这样就可以很容易地将簿记信息保存在存储器块中。

 

  类型Header包含了3块信息：指向列表的下一个块的指针，当前分配空间的长度，后面的自由空间的长度。

 

       另外，类型Header的定义还使用了一个union声明和Align数据类型，这是将存储器元素排在合理的字节边界上，

       根据系统的不同，这有时是需要的，有时是不需要的。

 

//在malloc函数中，当申请空间时，至少要分配两个Header元素节点，有什么原因吗？

当然有，因为每个空间块都包含两部分：空间头和空间体。

 

  空间头是为维护堆而设计的，说到底就是维护已用空间链表，为搜索空闲空间和释放已用空间服务。

 

       空间体是供用户读写的，当malloc函数返回给用户一个指针时，用户就可以设定自己的规格，

       比如强制转换成int或double类型，接下来就可以按照这种规格进行读写了。

 

       需要注意一点，空间头是不能被用户访问的，它是用来维护堆的，不是为用户服务的，所以malloc函数返回的指针是指向空间体的,

 

       而不是指向空间头的，理所当然free函数得到的指针也是指向空间体的。

 

       可是为了释放空间，free函数需要得到该空间的空间头信息，所以实现时需要把指针调整一下，改为指向空间头，

       此情形下，加一即可。另外一点，空间头和空间体同为Header类型，用union声明再合适不过。

 

       下面就是malloc函数和free函数的实现代码：

*/

#include "stdio.h"

#include <iostream>

using namespace std;

 

#define NULL 0

#define MEMSIZE 8096

 

typedef double Align;

typedef union header

{

       struct

       {

              union header* next;

              unsigned usedsize;

              unsigned freesize;

       }s;

       Align a;

} Header;

static Header mem[MEMSIZE];

static Header* memptr=NULL;

 

void* mymalloc(unsigned nbytes)

{

       Header *p,*newp;

       unsigned nunits;

       nunits=(nbytes+sizeof(Header)-1)/sizeof(Header)+1;

      

       if(memptr==NULL)

       {

              memptr->s.next=memptr=mem;

              memptr->s.usedsize=1;

              memptr->s.freesize=MEMSIZE-1;

       }

 

       for(p=memptr;(p->s.next!=memptr) && (p->s.freesize<nunits);p=p->s.next);

       if(p->s.freesize < nunits) return NULL;

      

       newp=p+p->s.usedsize;

       newp->s.usedsize=nunits;

       newp->s.freesize=p->s.freesize-nunits;

       newp->s.next=p->s.next;

       p->s.freesize=0;

       p->s.next=newp;

       memptr=newp;

      

       return (void*)(newp+1);

}

void myfree(void* ap)

{

       Header *bp,*p,*prev;

       bp=(Header*)ap-1;

      

       for(prev=memptr,p=memptr->s.next;

       (p!=bp) && (p!=memptr);prev=p,p=p->s.next);

      

       if(p!=bp) return;

      

       prev->s.freesize+=p->s.usedsize+p->s.freesize;

       prev->s.next=p->s.next;

       memptr=prev;

}

 

void main()

{

       /*测试*/

    int i;

    int *arry=(int *)mymalloc(100*sizeof(int));

    for(i=0;i<100;i++)

              arry[i]=i+1;

    for(i=0;i<100;i++)

              printf("%d ",*arry++);

    getchar();

}