4

このコードは、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)前者だけではいけません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です。これが、整数除算で切り上げる方法です。これとあなたが尋ねた式との唯一の違いは、余分なsizeof(Header)ものです。これは、ヘッダー自体に必要な余分なスペースです。

于 2012-05-26T23:43:07.933 に答える
3

(nbytes+sizeof(Header)-1)/sizeof(Header) + 1は、正しい切り上げで何かのユニット数を取得するためのコードのかなり標準的なイディオムです。いくつかの値で試してみると、正しく機能することがわかります。

実際のイディオムは、としてより適切に表現され(nbytes - 1)/unitSizeInBytes + 1ます。

明確にするために、受け入れられた回答の最後の段落に基づいてsizeof(Header)、部門の両側で使用法が異なります。配当で使用されるのは、ヘッダーとnバイトにバイトを割り当てる必要があるためです。除数で使用されるのは、割り当てられるブロックのサイズだからです。この場合、それらは同じ値であることが起こりますsizeof(Header)。

于 2012-05-26T23:39:36.840 に答える