4

此代码来自 K&R 书 - 第 8 章第 7 节：示例 - 存储分配器。至少对我来说，这段代码没有意义。“Header”是一个结构体和一个“最严格的对齐类型”的联合，它是一个长类型。然后，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 是怎么回事？为什么分配的空间少于预期。

4

2 回答 2

10

-1和将+1考虑不是块大小倍数的值。

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

如果您将公式更改为，n / 10 + 1那么它也将是错误的。当 n = 20 时，您只需要 2 个块，但该公式将返回 3。

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

于 2012-05-26T23:43:07.933 回答
3

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

实际的成语更好地表示为(nbytes - 1)/unitSizeInBytes + 1。

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

于 2012-05-26T23:39:36.840 回答