c语言 - K & R malloc 代码没有意义？

Question

此代码来自K&R书籍-第8章第7节：示例-存储分配器。这段代码，至少对我来说，没有意义。"标题"是结构和"最严格的对齐类型"的并集，后者是长类型。然后，Malloc 将找到一个足够大的可用空间，其大小是标头大小的倍数。

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 */
  }
}

此代码的奇怪部分是语句nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1;，然后在比较if (p->s.size >= nunits)中使用它来查找足够大的空间，其中包含 Header 大小的单位。前者不应该只nunits = (nbytes+sizeof(Header)) / sizeof(Header)吗？原始代码的计算值将小于应有的值。 +-1 是怎么回事？为什么要分配的空间少于所需的空间。

Answer 1

-1和+1是要考虑不是块大小乘以的值。

例如，假设块大小为 10。如果您尝试使用公式n / 10来获取所需块的数量，那么当 n = 15 时，您将获得 1 个块。这是错误的，你需要 2。

如果将公式更改为n / 10 + 1则也会出错。当 n = 20 时，您只需要 2 个块，但该公式将返回 3。

正确的公式是 (n - 1) / 10 + 1 .这就是整数除法四舍五入的方式。与此和您询问的公式的唯一区别是 额外的sizeof(Header) ，这只是标题本身所需的额外空间。

Answer 2

(nbytes+sizeof(Header)-1)/sizeof(Header) + 1 是一个非常标准的代码习语，用于通过正确的四舍五入来获取某物的单位数。如果您尝试使用某些值，您会发现它工作正常。

实际成语最好用(nbytes - 1)/unitSizeInBytes + 1来表达。

澄清一下，根据接受答案的最后一段，sizeof(Header)的使用在划分的双方是不同的。它在股息中的使用是因为它需要为标头和 nbytes 分配字节。它在除数中的使用是因为这是分配的块的大小。在这种情况下，它们的值相同，sizeof(Header) .