储存分配

存储分配

malloc 从上一次找到空闲块的地方(freep)开始搜索，如果找到的块太大，则将尾部返回给用户，头部只需修改size字段。
malloc 返回的指引将指向空闲空间，而不是块的头部。
free 从freep指向的地址开始，逐个扫描空闲块链表，插入或合并空闲块。
morecore 不太懂，尤其最后两句，不能理解。
typedef long Align;/* for alignment to long boundary */union header {struct {union header *ptr;/* next block if on free list */unsigned int size;/* size of this block */} s;Align x;/* force alignment of blocks */};typedef union header Header;static Header base;/* empty list to get started */static Header *freep = NULL;/* start of free list */void *malloc(unsigned int nbytes){Header *p, *prevp;Header *morecore(unsigned int);unsigned int nunits;nunits = (nbytes + sizeof(Header) - 1)/sizeof(Header) + 1;if ((prevp = freep) == NULL) {/* no free list yet */base.s.ptr = freep = prevp = &base;base.s.size = 0;}for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {if (p->s.size >= nunits) {if (p->s.size == nunits) {prevp->s.ptr = p->s.ptr;} else {p->s.size -= nunits;p += p->s.size;p->s.size = nunits;}freep = prevp;return (void *)(p+1);}if (p == freep)/* wrapped around free list */if ((p = morecore(nunits)) == NULL)return NULL;}}void free(void *ap){Header *bp, *p;bp = (Header *)ap - 1;/* point to block header */for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))break;if (bp + bp->s.size == p->s.ptr) {bp->s.size += p->s.ptr->s.size;bp->s.ptr = p->s.ptr->s.ptr;} else {bp->s.ptr = p->s.ptr;}if (p + p->s.size == bp) {p->s.size += bp->s.size;p->s.ptr = bp->s.ptr;} else {p->s.ptr = bp;}freep = p;}// morecore用于向OS请求存储空间#define NALLOC 1024/*minimum units to request */static Header *morecore(unsigned int nu){char *cp, *sbrk(int);Header *up;if (nu < NALLOC)nu = NALLOC;cp = sbrk(nu * sizeof(Header));if (cp == (char *)-1)/* no space */return NULL;up = (Header *)cp;up->s.size = nu;free(up+1);return freep;}

来自《The C Programming Language》 Chapter 8