虽然malloc()函数和free()函数是C语言中最常用的函数之一,但是可能大多数人只是用它,却没有去查看它的原型。记得有一次听一个学长说他去面试,面试官让他写出malloc()函数的原型,他当时不知所措就悲剧了。今天看了一篇文章,给出了malloc()函数的源代码,特转载于此与大家共享。
原文地址:http://blog.sina.com.cn/s/blog_642bb6110100k144.html
该实现使用大容量的静态数组作为堆,但也可使用操作系统调用分配堆。定义了一个数据类型Header保存每个存储器块的簿记信息,定义了具有Header类型元素的堆数组,这样就可以很容易地将簿记信息保存在存储器块中。类型Header包含了3块信息:指向列表的下一个块的指针,当前分配空间的长度,后面的自由空间的长度。另外,类型Header的定义还使用了一个union声明和Align数据类型,这是将存储器元素排在合理的字节边界上,根据系统的不同,这有时是需要的,有时是不需要的。
#define NULL 0 #define MEMSEZE 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* malloc(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->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 free(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->next); if(p!=bp) return; prev->s.freesize+=p->s.usedsize+p->s.freesize; prev->s.next=p->s.next; memptr=prev; }