K&R Storage Allocator是一种从C编程语言中分配内存的方法。在使用K&R Storage Allocator的过程中,存在指针在分配内存时出现错误的问题。主要原因在于当一个已分配的内存块被释放后,指针可能指向一个随机的地址。
为了解决这个问题,可以使用一个指向自身的结构体来表示内存块的头部,其包含了一个指针作为前一个内存块的地址。这个指针可以让我们知道该内存块前面的内存块的长度。
下面是一个基于K&R Storage Allocator的解决方案的代码示例:
typedef long Align; // 调整块的边界
union header { // 块的头部换成了一个联合体
struct {
union header *ptr; // 指向下一个块的指针
unsigned size; // 该块的大小
} s;
Align x;
};
typedef union header Header;
static Header base; // 基础块,作为程序的起始地址
static Header *freep = NULL; // 指向空闲块列表的指针
// K&R的_malloc: 返回大小为n的块
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