好的，我们这里有一大块写得很糟糕的代码。我将在这篇文章中所做的最好描述为软件考古学。
第1步：修复格式。
缩进和紧凑的格式对任何人都没有任何好处。需要插入各种空格和空行。评论可以以更易读的方式编写。我将从修复它开始。
同时，我正在从 K&R 风格更改牙套样式 - 请注意，K&R 牙套样式是可以接受的，这只是我的个人喜好。另一个个人偏好是将 * 写在指向的类型旁边的指针。我不会在这里争论（主观）风格问题。
此外， 的类型定义Header完全不可读，需要彻底修复。
而且我发现了一些完全模糊的东西：他们似乎在函数内部声明了一个函数原型。Header* morecore(unsigned);. 这是非常古老且非常糟糕的风格，我不确定 C 是否允许它不再使用。让我们删除该行，无论该函数做什么，都必须在其他地方定义。
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 */
}
}
好的，现在我们实际上可能能够阅读代码。
第 2 步：清除广为人知的不良做法。
这段代码充满了现在被认为是不好的做法。它们需要被删除，因为它们会危害代码的安全性、可读性和维护性。如果您想参考宣扬与我相同做法的权威，请查看广泛认可的编码标准MISRA-C。
我发现并删除了以下不良做法：
1) 只是输入unsigned代码可能会导致混淆：这是程序员的错字还是有意编写的unsigned int？我们应该全部替换unsigned为unsigned int. 但是当我们这样做时，我们发现它在这种情况下被用来给出各种二进制数据的大小。用于此类事务的正确类型是 C 标准类型size_t。这本质上也只是一个无符号整数，但保证对于特定平台来说“足够大”。sizeof运算符返回类型的结果，如果size_t我们查看 C 标准对真正 malloc 的定义，它是void *malloc(size_t size);. size_t使用最正确的类型也是如此。
2) 为我们自己的 malloc 函数使用与位于 stdlib.h 中的函数相同的名称是一个坏主意。如果我们需要包含 stdlib.h，事情就会变得一团糟。根据经验，切勿在您自己的代码中使用 C 标准库函数的标识符名称。我将名称更改为 kr_malloc。
3）代码滥用了所有静态变量都保证初始化为零的事实。这是由 C 标准明确定义的，但这是一个相当微妙的规则。让我们显式地初始化所有静态变量，以表明我们没有意外忘记初始化它们。
4) 内部条件下的作业是危险的且难以阅读。如果可能，应该避免这种情况，因为它也可能导致错误，例如经典的 = vs == 错误。
5) 由于评估的顺序，同一行上的多个作业很难阅读，也可能很危险。
6) 同一行上的多个声明难以阅读，而且很危险，因为在混合数据和指针声明时可能会导致错误。始终在自己的一行中声明每个变量。
7) 在每条语句之后总是使用大括号。不这样做会导致bugs bugs。
8) 切勿将特定指针类型强制转换为 void*。在 C 中它是不必要的，并且可以隐藏编译器本来会检测到的错误。
9) 避免在函数内使用多个返回语句。有时它们会导致代码更清晰，但在大多数情况下它们会导致意大利面条。就代码而言，我们不能在不重写循环的情况下改变它，所以我稍后会修复它。
10) 保持 for 循环简单。它们应该包含一个 init 语句、一个循环条件和一个迭代，仅此而已。这个带有逗号运算符和所有内容的 for 循环非常晦涩难懂。同样，我们发现需要将这个循环重写为合理的东西。接下来我会这样做，但现在我们有：
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 */
}
第三步：重写晦涩的循环。
由于前面提到的原因。我们可以看到这个循环永远持续下去，它通过从函数返回终止，无论是在分配完成时，还是在没有剩余内存时。因此，让我们将其创建为循环条件，并将 return 提升到应该在的函数末尾。让我们摆脱那个丑陋的逗号运算符。
我将介绍两个新变量：一个结果变量用于保存结果指针，另一个用于跟踪循环是否应该继续。我将通过使用类型来让 K&R 大吃一惊bool，这是自 1999 年以来 C 语言的一部分。
（我希望我没有用这个改变改变算法，我相信我没有）
#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;
}
第 4 步：编译这个废话。
由于这是来自 K&R，它充满了错别字。sizeof(header)应该是sizeof(Header)。缺少分号。它们使用不同的名称 freep、prevp 与 freeptr、prevptr，但显然意味着相同的变量。我相信后者实际上是更好的名字，所以让我们使用它们。
#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;
}
现在我们有了一些可读、可维护的代码，没有许多危险的做法，甚至可以编译！所以现在我们实际上可以开始思考代码实际上在做什么。
正如您可能已经猜到的那样，结构“Header”是链接列表中节点的声明。每个这样的节点都包含一个指向下一个节点的指针。我不太了解 morecore 功能，也不是“环绕”，我从来没有使用过这个功能，也没有sbrk. 但我假设它分配了这个结构中指定的标头，以及该标头后面的一些原始数据块。如果是这样，这就解释了为什么没有实际的数据指针：假设数据跟在标头之后，在内存中相邻。因此，对于每个节点，我们都会获得标头，并且我们会在标头之后获得一大块原始数据。
迭代本身非常简单，它们通过一个单链表，一次一个节点。
在循环结束时，他们将指针设置为指向“块”末尾之后的位置，然后将其存储在静态变量中，以便程序在下次调用函数时记住它之前分配内存的位置。
他们正在使用一种技巧来使他们的标头最终位于对齐的内存地址上：他们将所有开销信息与一个足够大的变量一起存储在一个联合中，以对应于平台的对齐要求。因此，如果“ptr”的大小加上“size”的大小太小而无法给出精确的对齐，则联合保证至少分配 sizeof(Align) 个字节。我相信这整个技巧今天已经过时了，因为 C 标准要求自动 struct/union 填充。