本文共 4031 字，大约阅读时间需要 13 分钟。

这章举例实现了一个内存管理函数malloc 将系统以来的部分和非系统依赖的部分进行分离

malloc内部管理的内存区块实际上是一个环链表，用一个全局指针纪录上一次操作的节点，用户遍历时判断是否已经遍历一周。

每个链表节点又一个头部组成，纪录了下一个区块的地址和整个区块的尺寸

定义如下

typedef long Align;union header{    struct {        union header * ptr;        unsigned size;    } s;    Align x; };typedef union header Header;

Align是使得申明出来的区块具有字节对齐属性

接下来是malloc函数的实现

首先需要一个base 节点提供初始化使用

和一个全局指针指向上一次操作的节点

static Header * freep = NULL;static Header base;

如果遍历一周没有找到合适的尺寸就调用morecore函数像操作系统申请内存（该函数具有系统依赖）

void * malloc(unsigned nbytes){    Header *p, *prevp;    Header *morecore(unsigned);    unsigned nunits;    nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;    if((prevp = freep) == NULL){        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)            if((p = morecore(nunits)) == NULL)                return NULL;    }}

#define NALLOC  1024Header * morecore(unsigned nunits){    char *cp, *sbrk(int);    Header *up;    void free(void *p);    if(nunits < NALLOC)        nunits = NALLOC;    cp = sbrk(nunits * sizeof(Header));    if(cp == (char *)-1)        return NULL;    up = (Header *)cp;    up->s.size = nunits;    free((void *)(up + 1));    return freep;}

void free(void *ap){    Header *bp, *p;    bp = (Header *)ap - 1;    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;}

完整代码如下

#define NULL    (0)typedef long Align;union header{    struct {        union header * ptr;        unsigned size;    } s;    Align x; };typedef union header Header;static Header * freep = NULL;static Header base;void * malloc(unsigned nbytes){    Header *p, *prevp;    Header *morecore(unsigned);    unsigned nunits;    nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;    if((prevp = freep) == NULL){        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)            if((p = morecore(nunits)) == NULL)                return NULL;    }}#define NALLOC  1024Header * morecore(unsigned nunits){    char *cp, *sbrk(int);    Header *up;    void free(void *p);    if(nunits < NALLOC)        nunits = NALLOC;    cp = sbrk(nunits * sizeof(Header));    if(cp == (char *)-1)        return NULL;    up = (Header *)cp;    up->s.size = nunits;    free((void *)(up + 1));    return freep;}void free(void *ap){    Header *bp, *p;    bp = (Header *)ap - 1;    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;}