解释这一实施从K＆放的malloc; R书 [英] Explain this implementation of malloc from the K&R book
问题描述
这是从书上C时摘录通过的 Kernighan和Ritchie 的。它显示了如何实现一个版本的malloc 的。虽然很好的注释，我理解它有很大的困难。可有人请解释一下吗？
的typedef长对齐; / *对齐长的边界* /
工会头{/ *块头* /
结构{
工会头* PTR; / *下一块，如果在空闲列表* /
无符号的大小; / *这个块*的大小/
}等;
对齐X; / *力块对齐* /
};
工会的typedef头头;静态头基地;上手/ *空列表* /
静态标题* freep = NULL; / *空闲列表开始* /
/ * malloc的：通用存储分配* /
无效* malloc的（未签名的nbytes）
{
标题* P * preVP;
标题* morecore（符号）;
无符号nunits;
nunits =（为nbytes +的sizeof（头）-1）/的sizeof（头）+ 1;
如果（（preVP = freep）== NULL）{/ *没有免费的名单尚未* /
base.s.ptr = freeptr = prevptr =安培;基地;
base.s.size = 0;
}
为（P = preVP-GT＆; s.ptr; preVP = P，P = P-＆GT; s.ptr）{
如果（对GT; s.size＆GT; = nunits）{/ *足够大* /
如果（对GT; s.size == nunits）/ * *正好/
preVP-GT＆; s.ptr = P-＆GT; s.ptr;
其他{/ *分配尾部* /
P-＆GT; s.size - = nunits;
P + = P-＆GT; s.size;
P-＆GT; s.size = nunits
}
freep = preVP;
返回（无效*）（P + 1）;
}
如果（P == freep）/ *缠空闲列表* /
如果（（P = morecore（nunits））== NULL）
返回NULL; / *都不剩了* /
}
}＃定义NALLOC 1024 / *最小#units要求* /
/ * morecore：要求系统更多的内存* /静态标题* morecore（无符号NU）
{ 字符* CP，* SBRK（INT）;
头*了; 如果（NU＆LT; NALLOC）
NU = NALLOC; CP = SBRK（NU *的sizeof（头））; 如果（CP ==（的char *）-1）/ *完全没有空间* /
返回NULL; UP =（头*）CP;
向上＆GT; s.size = NU;
免费的（（无效*）（高达+ 1））; 返回freep;
}/ *自由：自由列表把块AP * /
无效免费（无效* AP）{
标题*基点，* P;
BP =（头*）AP - 1; / *点块头* /
为（p值= freep;！（bp的指p＆放大器;＆放大器;碱基＆下;对 - ＆GT; s.ptr）; P =对 - ＆GT; s.ptr）
如果（P＆GT =对 - ＆GT; s.ptr＆放大器;及（bp的指p ||碱基＆下;对 - ＆GT; s.ptr））
打破; / *在开始或竞技场年底释放的块* /
如果（BP + BP-GT＆;大小== p型＆GT; s.ptr）{
BP-GT＆; s.size + = P-＆GT; s.ptr-＆GT; s.size;
BP-GT＆; s.ptr = P-＆GT; s.ptr-＆GT; s.ptr;
}其他
BP-GT＆; s.ptr = P-＆GT; s.ptr; 如果第（p +对 - ＆GT;大小== bp）的{
P-＆GT; s.size + = BP-GT＆; s.size;
P-＆GT; s.ptr = BP-GT＆; s.ptr;
}其他
P-＆GT; s.ptr = BP;
freep = P;
}
好吧，我们这里有什么是真正写得不好code的一大块。我将在这篇文章做才能最好地描述为软件考古学。
第1步：修正格式
缩进和紧凑的格式没有做任何人都没有好处。不同的空间和空行需要插入。注释可以写在更易读的方式。我会通过固定的开始。
与此同时，我从K＆安培改变括号风格; R风格 - 请注意，K＆放大器; R梅开二度的风格是可以接受的，这仅仅是我个人的preference。另外个人preference是编写*为指针旁边的类型指向。我不会争论（主观）风格的问题在这里。
同样，标题的类型定义为完全不可读，它需要大幅修正。
和我看到的东西完全模糊：他们似乎已经声明的函数内部函数原型。 标题* morecore（符号）; 。这是非常古老和风格非常差，我不知道如果C甚至允许任何更长的时间。就让我们去掉那行，不管该函数的作用，它必须定义在别处。
的typedef长对齐; / *对齐长的边界* /工会的typedef页眉/ *块头* /
{
结构
{
工会头* PTR; / *下一块，如果在空闲列表* /
无符号的大小; / *这个块*的大小/
}等; 对齐X; / *力块对齐* /}头;
静态头基地;上手/ *空列表* /
静态标题* freep = NULL; / *空闲列表开始* /
/ * malloc的：通用存储分配* /
无效* malloc的（未签名的nbytes）
{
头* P;
头* preVP;
无符号nunits; nunits =（为nbytes +的sizeof（头） - 1）/的sizeof（头）+ 1; 如果（（preVP = freep）== NULL）/ *没有免费的名单尚未* /
{
base.s.ptr = freeptr = prevptr =安培;基地;
base.s.size = 0;
} 为（P = preVP-GT＆; s.ptr; preVP = P，P = P-＆GT; s.ptr）
{
如果（对GT; s.size＆GT; = nunits）/ *足够大* /
{
如果（对GT; s.size == nunits）/ * *正好/
preVP-GT＆; s.ptr = P-＆GT; s.ptr;
否则/ *分配尾部* /
{
P-＆GT; s.size - = nunits;
P + = P-＆GT; s.size;
P-＆GT; s.size = nunits
} freep = preVP;
返回（无效*）（P + 1）;
} 如果（P == freep）/ *缠空闲列表* /
如果（（P = morecore（nunits））== NULL）
返回NULL; / *都不剩了* /
}
}
好吧，现在我们可能实际上是能够读取code。
第二步：剔除掉广泛认可的坏习惯
这code充满了东西，现在被认为是不好的做法。它们需要被去除，因为它们危及code的安全，可读性和维护。如果你想要一个权威$ P $参考paching相同做法，我检查出广泛认可的编码标准的MISRA-C 。
我已经发现并删除下列不良行为：
1）只需输入无符号在code可能会导致出现混乱：这是由程序员一个错字或者是写<$ C $意向C> unsigned int类型？我们应该用 unsigned int类型替换所有无符号。但如我们这样做，我们发现，这是在这样的背景下使用，得到各种二进制数据的大小。正确类型的使用等事项是C标准型<$ C $ C>为size_t 。这本质上只是一个unsigned int为好，但它是保证足够大为特定平台。在的sizeof 运算符返回类型的结果为size_t ，如果我们看一下真正的malloc的C标准的定义，它为的void * malloc的（为size_t大小）; 。因此，为size_t 是最正确的类型使用。
2），这是一个坏主意，使用相同的名称为我们自己的malloc函数为居住在stdlib.h中的之一。如果我们需要包括stdlib.h中，事情会变得混乱。作为一个经验法则，从来没有在自己的code使用的C标准库函数的标识符名称。我将名称更改为kr_malloc。
3）code滥用所有静态变量保证被初始化为零的事实。这是由C标准，而是一个相当微妙的规则，明确定义。让我们明确地初始化所有静态，就表明我们没有忘记意外的init他们。
4）内部的分配情况是危险的，难以阅读。此应尽可能避免的，因为它也可以导致错误，如经典= VS ==错误。
5）在同一行的多个任务是难以阅读，也可能是危险的，因为评估的顺序。
6）在同一行中多次声明是难以阅读和危险的，因为混合数据和指针声明时，它可能会导致错误。始终宣称在其自己的行中的每个变量。
7）每个语句后始终使用大括号。不这样做会导致错误的bug的bug。
8）不要从一个特定的指针类型强制类型转换为void *。这是在C不必要的，可以遁形错误编译器，否则检测。
9）避免使用函数内的多个return语句。有时，他们会导致更清晰的code，但在大多数情况下，它们会导致意大利面条。由于code表示，我们无法改变，如果没有，虽然重写循环，所以以后我会解决这个问题。
10）保持for循环简单。他们应该包含一个初始化语句，一个循环条件和一个迭代，没有别的。这种循环，使用逗号运算符和一切，是非常模糊的。同样，我们发现了一个需要这个循环改写成什么理智。我会做这下，但现在我们有：
的typedef长对齐; / *对齐长的边界* /工会的typedef页眉/ *块头* /
{
结构
{
工会头* PTR; / *下一块，如果在空闲列表* /
为size_t的大小; / *这个块*的大小/
}等; 对齐X; / *力块对齐* /}头;
静态头基地= {0};上手/ *空列表* /
静态标题* freep = NULL; / *空闲列表开始* /
/ * malloc的：通用存储分配* /
无效* kr_malloc（为size_t为nbytes）
{
头* P;
头* preVP;
为size_t nunits; nunits =（为nbytes +的sizeof（头） - 1）/的sizeof（头）+ 1; preVP = freep;
如果（preVP == NULL）/ *没有免费的名单尚未* /
{
base.s.ptr =安培;基地;
freeptr =安培;基地;
prevptr =安培;基地;
base.s.size = 0;
} 为（P = preVP-GT＆; s.ptr; preVP = P，P = P-＆GT; s.ptr）
{
如果（对GT; s.size＆GT; = nunits）/ *足够大* /
{
如果（对GT; s.size == nunits）/ * *正好/
{
preVP-GT＆; s.ptr = P-＆GT; s.ptr;
}
否则/ *分配尾部* /
{
P-＆GT; s.size - = nunits;
P + = P-＆GT; s.size;
P-＆GT; s.size = nunits
} freep = preVP;
返回的p + 1;
} 如果（P == freep）/ *缠空闲列表* /
{
P = morecore（nunits）;
如果（P == NULL）
{
返回NULL; / *都不剩了* /
}
}
} / * *为/
}
第3步：重新编写晦涩环
。有关前面提到的原因。我们可以看到，这个循环下去永远，它终止从函数返回时，无论是当分配完成后，或者当没有留下的记忆。所以让我们创建一个循环条件，并解除了返回功能，它应该是结束。并让摆脱难看的逗号操作的。
我就为大家介绍两个新的变量：一个结果变量来保存结果指针，另一个跟踪的循环是否应该继续。我会吹K＆放大器;通过使用布尔 R型的心目中，这是C语言的一部分，自1999年
（我希望我没有改变这种变化的算法，我相信我有没有）
的#include＆LT; stdbool.h＆GT;长期的typedef对齐; / *对齐长的边界* /工会的typedef页眉/ *块头* /
{
结构
{
工会头* PTR; / *下一块，如果在空闲列表* /
为size_t的大小; / *这个块*的大小/
}等; 对齐X; / *力块对齐* /}头;
静态头基地= {0};上手/ *空列表* /
静态标题* freep = NULL; / *空闲列表开始* /
/ * malloc的：通用存储分配* /
无效* kr_malloc（为size_t为nbytes）
{
头* P;
头* preVP;
为size_t nunits;
void *的结果;
布尔is_allocating; nunits =（为nbytes +的sizeof（头） - 1）/的sizeof（头）+ 1; preVP = freep;
如果（preVP == NULL）/ *没有免费的名单尚未* /
{
base.s.ptr =安培;基地;
freeptr =安培;基地;
prevptr =安培;基地;
base.s.size = 0;
} is_allocating = TRUE;
为（P = preVP-GT＆; s.ptr; is_allocating; P = P-＆GT; s.ptr）
{
如果（对GT; s.size＆GT; = nunits）/ *足够大* /
{
如果（对GT; s.size == nunits）/ * *正好/
{
preVP-GT＆; s.ptr = P-＆GT; s.ptr;
}
否则/ *分配尾部* /
{
P-＆GT; s.size - = nunits;
P + = P-＆GT; s.size;
P-＆GT; s.size = nunits
} freep = preVP;
结果= P + 1;
is_allocating = FALSE; /* 我们完了 */
} 如果（P == freep）/ *缠空闲列表* /
{
P = morecore（nunits）;
如果（P == NULL）
{
结果= NULL; / *都不剩了* /
is_allocating = FALSE;
}
}
preVP = P;
} / * *为/ 返回结果;
}
第四步：让这个垃圾编译
。由于这是从K＆放大器; R它充满了错字。 的sizeof（头）应的sizeof（标题）。有遗漏分号。他们使用不同的名称freep，preVP与freeptr，prevptr，但显然指的是同一个变量。我相信后者实际上是更好的名字，所以让我们使用这些。
的#include＆LT; stdbool.h＆GT;长期的typedef对齐; / *对齐长的边界* /工会的typedef页眉/ *块头* /
{
结构
{
工会头* PTR; / *下一块，如果在空闲列表* /
为size_t的大小; / *这个块*的大小/
}等; 对齐X; / *力块对齐* /}头;
静态头基地= {0};上手/ *空列表* /
静态标题* freeptr = NULL; / *空闲列表开始* /
/ * malloc的：通用存储分配* /
无效* kr_malloc（为size_t为nbytes）
{
头* P;
头* prevptr;
为size_t nunits;
void *的结果;
布尔is_allocating; nunits =（为nbytes +的sizeof（头） - 1）/的sizeof（头）+ 1; prevptr = freeptr;
如果（prevptr == NULL）/ *没有免费的名单尚未* /
{
base.s.ptr =安培;基地;
freeptr =安培;基地;
prevptr =安培;基地;
base.s.size = 0;
} is_allocating = TRUE;
为（P = prevptr-＆GT; s.ptr; is_allocating; P = P-＆GT; s.ptr）
{
如果（对GT; s.size＆GT; = nunits）/ *足够大* /
{
如果（对GT; s.size == nunits）/ * *正好/
{
prevptr-＆GT; s.ptr = P-＆GT; s.ptr;
}
否则/ *分配尾部* /
{
P-＆GT; s.size - = nunits;
P + = P-＆GT; s.size;
P-＆GT; s.size = nunits;
} freeptr = prevptr;
结果= P + 1;
is_allocating = FALSE; /* 我们完了 */
} 如果（P == freeptr）/ *缠空闲列表* /
{
P = morecore（nunits）;
如果（P == NULL）
{
结果= NULL; / *都不剩了* /
is_allocating = FALSE;
}
}
prevptr = P;
} / * *为/ 返回结果;
}
，现在我们有一定程度的可读性，可维护性code，没有无数危险的做法，这将无法编译！所以，现在我们可以真正开始思考什么了code实际上是做什么。
该结构头，正如你可能已经猜到了，一个节点的声明在一个链表。每个这样的节点包含一个指向下一个。我不太明白morecore功能，也不是环绕式，我从来没有使用此功能，也不 SBRK 。但是，我认为在这个结构中指定，也跟随该头的原始数据的一些大块它分配一个标题。如果是这样，这解释了为什么没有实际数据指针：假设数据跟随首标，在相邻存储器。因此，对于每一个节点，我们得到了头，我们得到头后面的原始数据块。
迭代本身是pretty直线前进，他们正在经历一个单链表，一个节点的时间。
在循环结束时，他们设定的指针一点一点过去的块，然后存储在一个静态变量，年底使程序会记住它previously分配的内存，下一时间函数被调用。
他们用了一招，使他们的头，最后变成了一个对齐的存储器地址：他们一起存放所有的开销信息的工会有足够的可变大，对应平台的对齐要求。所以，如果PTR加大小的大小尺寸太小，无法给出确切的定位，工会保证至少的sizeof（对齐）字节分配。我认为，这整个把戏今天已经过时了，因为C标准规定自动结构/联合填充。
This is an excerpt from the book on C by Kernighan and Ritchie. It shows how to implement a version of malloc. Although well commented, I am having great difficulty in understanding it. Can somebody please explain it?
typedef long Align; /* for alignment to long boundary */
union header { /* block header */
struct {
union header *ptr; /* next block if on free list */
unsigned 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 */
/* malloc: general-purpose storage allocator */
void *malloc(unsigned nbytes)
{
Header *p, *prevp;
Header *morecore(unsigned);
unsigned nunits;
nunits = (nbytes+sizeof(Header)-1)/sizeof(header) + 1;
if ((prevp = freep) == NULL) { /* no free list yet */
base.s.ptr = freeptr = prevptr = &base;
base.s.size = 0;
}
for (p = prevp->s.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 { /* allocate tail end */
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 */
}
}
#define NALLOC 1024 /* minimum #units to request */
/* morecore: ask system for more memory */
static Header *morecore(unsigned nu)
{
char *cp, *sbrk(int);
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;
}
/* free: put block ap in free list */
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; /* freed block at start or end of arena */
if (bp + bp->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->size == bp) {
p->s.size += bp->s.size;
p->s.ptr = bp->s.ptr;
} else
p->s.ptr = bp;
freep = p;
}
Ok, what we have here is a chunk of really poorly written code. What I will do in this post could best be described as software archaeology.
Step 1: fix the formatting.
The indention and compact format doesn't do anyone any good. Various spaces and empty rows need to be inserted. The comments could be written in more readable ways. I'll start by fixing that.
At the same time I'm changing the brace style from K&R style - please note that the K&R brace style is acceptable, this is merely a personal preference of mine. Another personal preference is to write the * for pointers next to the type pointed at. I'll not argue about (subjective) style matters here.
Also, the type definition of Header is completely unreadable, it needs a drastic fix.
And I spotted something completely obscure: they seem to have declared a function prototype inside the function. Header* morecore(unsigned);. This is very old and very poor style, and I'm not sure if C even allows it any longer. Lets just remove that line, whatever that function does, it will have to be defined elsewhere.
typedef long Align; /* for alignment to long boundary */
typedef union header /* block header */
{
struct
{
union header *ptr; /* next block if on free list */
unsigned size; /* size of this block */
} s;
Align x; /* force alignment of blocks */
} Header;
static Header base; /* empty list to get started */
static Header* freep = NULL; /* start of free list */
/* malloc: general-purpose storage allocator */
void* malloc (unsigned nbytes)
{
Header* p;
Header* prevp;
unsigned nunits;
nunits = (nbytes + sizeof(Header) - 1) / sizeof(header) + 1;
if ((prevp = freep) == NULL) /* no free list yet */
{
base.s.ptr = freeptr = prevptr = &base;
base.s.size = 0;
}
for (p = prevp->s.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 /* allocate tail end */
{
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 */
}
}
Ok now we might actually be able to read the code.
Step 2: weed out widely-recognized bad practice.
This code is filled with things that are nowadays regarded as bad practice. They need to be removed, since they jeopardize the safety, readability and maintenance of the code. If you want a reference to an authority preaching the same practices as me, check out the widely-recognized coding standard MISRA-C.
I have spotted and removed the following bad practices:
1) Just typing unsigned in the code could lead to be confusion: was this a typo by the programmer or was the intention to write unsigned int? We should replace all unsigned with unsigned int. But as we do that, we find that it is used in this context to give the size of various binary data. The correct type to use for such matters is the C standard type size_t. This is essentially just an unsigned int as well, but it is guaranteed to be "large enough" for the particular platform. The sizeof operator returns a result of type size_t and if we look at the C standard's definition of the real malloc, it is void *malloc(size_t size);. So size_t is the most correct type to use.
2) It is a bad idea to use the same name for our own malloc function as the one residing in stdlib.h. Should we need to include stdlib.h, things will get messy. As a rule of thumb, never use identifier names of C standard library functions in your own code. I'll change the name to kr_malloc.
3) The code is abusing the fact that all static variables are guaranteed to be initialized to zero. This is well-defined by the C standard, but a rather subtle rule. Lets initialize all statics explicitly, to show that we haven't forgotten to init them by accident.
4) Assignment inside conditions is dangerous and hard to read. This should be avoided if possible, since it can also lead to bugs, such as the classic = vs == bug.
5) Multiple assignments on the same row is hard to read, and also possibly dangerous, because of the order of evaluation.
6) Multiple declarations on the same row is hard to read, and dangerous, since it could lead to bugs when mixing data and pointer declarations. Always declare each variable on a row of its own.
7) Always uses braces after every statement. Not doing so will lead to bugs bugs bugs.
8) Never type cast from a specific pointer type to void*. It is unnecessary in C, and could hide away bugs that the compiler would otherwise have detected.
9) Avoid using multiple return statements inside a function. Sometimes they lead to clearer code, but in most cases they lead to spaghetti. As the code stands, we can't change that without rewriting the loop though, so I will fix this later.
10) Keep for loops simple. They should contain one init statement, one loop condition and one iteration, nothing else. This for loop, with the comma operator and everything, is very obscure. Again, we spot a need to rewrite this loop into something sane. I'll do this next, but for now we have:
typedef long Align; /* for alignment to long boundary */
typedef union header /* block header */
{
struct
{
union header *ptr; /* next block if on free list */
size_t size; /* size of this block */
} s;
Align x; /* force alignment of blocks */
} Header;
static Header base = {0}; /* empty list to get started */
static Header* freep = NULL; /* start of free list */
/* malloc: general-purpose storage allocator */
void* kr_malloc (size_t nbytes)
{
Header* p;
Header* prevp;
size_t nunits;
nunits = (nbytes + sizeof(Header) - 1) / sizeof(header) + 1;
prevp = freep;
if (prevp == NULL) /* no free list yet */
{
base.s.ptr = &base;
freeptr = &base;
prevptr = &base;
base.s.size = 0;
}
for (p = prevp->s.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 /* allocate tail end */
{
p->s.size -= nunits;
p += p->s.size;
p->s.size = nunits
}
freep = prevp;
return p+1;
}
if (p == freep) /* wrapped around free list */
{
p = morecore(nunits);
if (p == NULL)
{
return NULL; /* none left */
}
}
} /* for */
}
Step 3: rewrite the obscure loop.
For the reasons mentioned earlier. We can see that this loop goes on forever, it terminates by returning from the function, either when the allocation is done, or when there is no memory left. So lets create that as a loop condition, and lift out the return to the end of the function where it should be. And lets get rid of that ugly comma operator.
I'll introduce two new variables: one result variable to hold the resulting pointer, and another to keep track of whether the loop should continue or not. I'll blow K&R's minds by using the bool type, which is part of the C language since 1999.
(I hope I haven't altered the algorithm with this change, I believe I haven't)
#include <stdbool.h>
typedef long Align; /* for alignment to long boundary */
typedef union header /* block header */
{
struct
{
union header *ptr; /* next block if on free list */
size_t size; /* size of this block */
} s;
Align x; /* force alignment of blocks */
} Header;
static Header base = {0}; /* empty list to get started */
static Header* freep = NULL; /* start of free list */
/* malloc: general-purpose storage allocator */
void* kr_malloc (size_t nbytes)
{
Header* p;
Header* prevp;
size_t nunits;
void* result;
bool is_allocating;
nunits = (nbytes + sizeof(Header) - 1) / sizeof(header) + 1;
prevp = freep;
if (prevp == NULL) /* no free list yet */
{
base.s.ptr = &base;
freeptr = &base;
prevptr = &base;
base.s.size = 0;
}
is_allocating = true;
for (p = prevp->s.ptr; is_allocating; p = p->s.ptr)
{
if (p->s.size >= nunits) /* big enough */
{
if (p->s.size == nunits) /* exactly */
{
prevp->s.ptr = p->s.ptr;
}
else /* allocate tail end */
{
p->s.size -= nunits;
p += p->s.size;
p->s.size = nunits
}
freep = prevp;
result = p+1;
is_allocating = false; /* we are done */
}
if (p == freep) /* wrapped around free list */
{
p = morecore(nunits);
if (p == NULL)
{
result = NULL; /* none left */
is_allocating = false;
}
}
prevp = p;
} /* for */
return result;
}
Step 4: make this crap compile.
Since this is from K&R, it is filled with typos. sizeof(header) should be sizeof(Header). There are missing semi-colons. They use different names freep, prevp versus freeptr, prevptr, but clearly mean the same variable. I believe the latter were actually better names, so lets use those.
#include <stdbool.h>
typedef long Align; /* for alignment to long boundary */
typedef union header /* block header */
{
struct
{
union header *ptr; /* next block if on free list */
size_t size; /* size of this block */
} s;
Align x; /* force alignment of blocks */
} Header;
static Header base = {0}; /* empty list to get started */
static Header* freeptr = NULL; /* start of free list */
/* malloc: general-purpose storage allocator */
void* kr_malloc (size_t nbytes)
{
Header* p;
Header* prevptr;
size_t nunits;
void* result;
bool is_allocating;
nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;
prevptr = freeptr;
if (prevptr == NULL) /* no free list yet */
{
base.s.ptr = &base;
freeptr = &base;
prevptr = &base;
base.s.size = 0;
}
is_allocating = true;
for (p = prevptr->s.ptr; is_allocating; p = p->s.ptr)
{
if (p->s.size >= nunits) /* big enough */
{
if (p->s.size == nunits) /* exactly */
{
prevptr->s.ptr = p->s.ptr;
}
else /* allocate tail end */
{
p->s.size -= nunits;
p += p->s.size;
p->s.size = nunits;
}
freeptr = prevptr;
result = p+1;
is_allocating = false; /* we are done */
}
if (p == freeptr) /* wrapped around free list */
{
p = morecore(nunits);
if (p == NULL)
{
result = NULL; /* none left */
is_allocating = false;
}
}
prevptr = p;
} /* for */
return result;
}
And now we have somewhat readable, maintainable code, without numerous dangerous practices, that will even compile! So now we could actually start to ponder about what the code is actually doing.
The struct "Header" is, as you might have guessed, the declaration of a node in a linked list. Each such node contains a pointer to the next one. I don't quite understand the morecore function, nor the "wrap-around", I have never used this function, nor sbrk. But I assume that it allocates a header as specified in this struct, and also some chunk of raw data following that header. If so, that explains why there is no actual data pointer: the data is assumed to follow the header, adjacently in memory. So for each node, we get the header, and we get a chunk of raw data following the header.
The iteration itself is pretty straight-forward, they are going through a single-linked list, one node at a time.
At the end of the loop, they set the pointer to point one past the end of the "chunk", then store that in a static variable, so that the program will remember where it previously allocated memory, next time the function is called.
They are using a trick to make their header end up on an aligned memory address: they store all the overhead info in a union together with a variable large enough to correspond to the platform's alignment requirement. So if the size of "ptr" plus the size of "size" are too small to give the exact alignment, the union guarantees that at least sizeof(Align) bytes are allocated. I believe that this whole trick is obsolete today, since the C standard mandates automatic struct/union padding.
这篇关于解释这一实施从K＆放的malloc; R书的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
