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

    } 
} 

이 코드의 이상한 부분은 헤더의 크기면에서 단위 충분히 큰 공간을 찾기 위해 비교 if (p->s.size >= nunits)에서 사용되는 문 nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1;입니다. 전자가 nunits = (nbytes+sizeof(Header))/sizeof(Header)일까요? 원래의 코드는해야 할 것보다 적은 값으로 평가됩니다. + -1은 무엇입니까? 왜 원하는 것보다 적은 공간을 할당해야 하는가?

Answer 1

-1 및 +1은 블록 크기의 배수가 아닌 값을 고려해야합니다.

예를 들어

, 당신은 당신이 잘못 15. 당신이 필요 = n은 1 개 블록을 얻을 것입니다 필요한 블록 수를 얻을 수있는 공식 n/10를 사용하려고하면 블록 크기는 10입니다 가정 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)의 사용은 부서의 양쪽에서 다릅니다. 배당금의 용도는 Header 및 Nbytes에 대해 바이트를 할당해야하기 때문입니다. 제수에서 사용하는 것은 할당되는 블록의 크기이기 때문입니다. 이 경우 동일한 값인 sizeof(Header)이 발생합니다.