在研究K&R第八章第五节的实现之前，不妨先看看其第五章第四节的alloc/afree实现，虽然这段代码主要目的是展示地址运算。
#define ALLOCSIZE 10000 static char allocbuf[ALLOCSIZE]; /*storage for alloc*/ static char *allocp = allocbuf; /*next free position*/
char *alloc(int n) { if(allocbuf+ALLOCSIZE - allocp >= n) { allocp += n; return alloc - n; } else return 0; }
void afree(char *p) { if (p >= allocbuf && ps.ptr; ;prevp = p, p= p->s.ptr) { if(p->s.size >= nunits) { /* big enough */ if (p->s.size == nunits) /* exactly */ 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; /* none left */ } }
malloc()第一次调用时建立一个退化链表base，只有一个大小是0的空间，并指向它自己。freep用于标识空闲链表的某个元素，每次查找时可能发生变化；中间的查找和分配过程是基本的链表操作，在空闲链表中不存在合适大小的空闲空间时调用morecore()获得更多内存空间；最后的返回值是空闲空间的首地址，即Header之后的地址，这个接口与库函数一致。
#define NALLOC 1024 /* minimum #units to request */ static Header *morecore(unsigned nu) { char *cp; Header *up; if(nu < NALLOC) nu = NALLOC; cp = sbrk(nu * sizeof(Header)); if(cp == (char *)-1) /* no space at all*/ return NULL; up = (Header *)cp; up->s.size = nu; free((void *)(up+1)); return freep; }
这里有个让人惊讶的地方：malloc()调用了morecore()，morecore()又调用了free()！第一次看到这里时可能会觉得不可思议，因为按照惯性思维，malloc()和free()似乎应该是相互分开的，各司其职啊？但请再思考一下，free()是把空闲链表进行扩充，而malloc()在空闲链表不足时，从系统申请到更多内存空间后，也要先把它们转化成空闲链表的一部分，再进行利用。这样，malloc()调用free()完成后面的工作也是顺理成章了。根据这个思想，后面是free()的实现。在此之前，还有几个morecore()自身的细节：
1.如果系统也没有空间可以分配，sbrk()返回-1。cp是char *类型，在有的机器上char无符号，这里需要一次强制类型转换。
2.morecore()调用的返回值看上去比较奇怪，别担心，freep会在free()中修改的。使用这个返回值也是为了在malloc()里的判断、p = freep的再次赋值的语句能够紧凑。
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 || bps.ptr)) break; /* freed block at start or end of arena*/ if (bp+bp->s.size==p->s.ptr) { /* join to upper nbr */ 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) { /* join to lower nbr */ p->s.size += bp->s.size; p->s.ptr = bp->s.ptr; } else p->s.ptr = bp; freep = p; }
定位后，根据要释放的空间与附近空间的相邻性，进行合并，也即修改对应空间的Header。两个if并列可以使得bp可以同时与高地址和低地址空闲空间结合（如果都相邻），或者进行二者之一的合并，或者不合并。
完成了这三部分代码后（注意放到同一源文件中,sbrk()需要#include ），就可以使用了。当然要注意，命名和stdlib.h中的同名函数是冲突的，可以自行改名。
第一次审视源码，会发现很多实现可能原先并没有想到：Header的结构和对齐填充、空间的取整、链表的操作和初始化（边界情况）、malloc()对free()的调用、由malloc()和free()暗中保证的链表地址有序等等，确实很值得玩味。另外再附上前文中提到的两个问题还有一些补充问题的简单思考：
1.Header与空闲空间相剥离，Header中包含一个指向其空闲空间的指针
这样做未必不可，相应地算法需要改动。同时，由于Header和空闲空间不再相邻，sbrk()获得的空间也应该包含Header的部分，内存的分布可能会更加琐碎。当然，这也可能带来好处，即用其他数据结构对链表进行管理，比如按大小进行hash，这样查找起来更快。
2.关于sbrk()
sbrk()也是库函数，它能使堆往栈的方向增长，具体可以参考：brk(), sbrk() 用法详解。
3.可以改进的方
空闲空间的寻找是线性的，查找过程在内存分配中可以看作是循环首次适应算法，在某些情况下可能很慢；如果再建立一个数据结构，如hash表，对不同大小的空间进行索引，肯定可以加快查找本身，并且能实现一些算法，比如最佳匹配。但查找加快的代价是，修改这个索引会占用额外的时间，这是需要权衡的。
morecore()中的最小分配空间是宏定义，在实际使用中完全可以作为参数传递，根据需要设定最小分配下限。
