K＆R malloc代碼沒有意義嗎？

此代碼來自K & R書 - 第8章第7節：示例 - 存儲分配器。這段代碼至少對我來說沒有意義。「Header」是一個結構體和一個「限制性最強的對齊類型」的聯合，這是一種長類型。然後，Malloc將找到一個足夠大的可用空間，其大小爲標題大小的倍數。K＆R 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)？原始代碼將評估爲比它應該低的值。什麼是+ -1s？爲什麼分配空間比想要的少。

來源

2012-05-26 1der

保持運營商的優先考慮，並再次分析... –

@duffymo：而不是告訴我，你不能告訴我代碼如何工作？順便說一句，你讀過那本書嗎？注意到很多錯別字？但沒有人對此說過任何話。 – 1der

假設這是第一次調用'malloc'，並且您已經請求了1個字節，即'malloc（1）'，並且看到了哪些'nunits'返回了您的建議修正和書中的代碼。 – dirkgently

-1和+1將計算不與塊大小相乘的值。

例如，假設塊大小爲10。如果嘗試使用公式n/10獲得所需的塊的數目，那麼你將得到對於n 1個塊= 15。這是錯誤的，就需要2

如果您更改公式爲n/10 + 1那麼它也將是錯誤的。當n = 20時，只需要2個塊，但該公式將返回3.

正確的公式是(n - 1)/10 + 1。這就是你用整數除法的方法。唯一與此不同的是，您詢問的公式是額外的sizeof(Header)，這只是標題本身所需的額外空間。

來源

2012-05-26 23:43:07

謝謝這真的有幫助。其實這個混淆是由於我把分割符號'/'作爲一個整體單元后的表達式。 – 1der

使用'（n + 9）/ 10'會不會更簡單？ –

@JoshuaGreen：是的，這就是我通常使用的。 –

(nbytes+sizeof(Header)-1)/sizeof(Header) + 1在代碼中是一個非常標準的習慣用法，用正確的四捨五入得到某些東西的單位數。它用一些值來嘗試它，你會發現它能正常工作。

實際成語最好表示爲(nbytes - 1)/unitSizeInBytes + 1。

爲了澄清，根據接受的答案的最後一段，sizeof(Header)的使用是不同的兩個部門。它在分紅中的用途是因爲它需要爲Header和nbytes分配字節。它在除數中的用途是因爲這是分配塊的大小。發生在這種情況下，它們是相同的值，sizeof(Header)。

來源

2012-05-26 23:39:36

是的，正如K-ballo所說的，考慮運營商的優先級。 –

這是否意味着我應該閱讀別人的代碼以熟悉這些標準習語？ – 1der

是的，並且提出這樣的問題也是一個好主意，但在你做之前要仔細研究。閱讀好的開源代碼。然後工作。讓世界變得更美好。 :) –

K＆R malloc代碼沒有意義嗎？

回答

相關問題