K & R malloc code doesn't make sense?
c, kernighan-and-ritchie, malloc
Solution
The `-1` and `+1` are to account for values that aren't multiplies of the block size.
For example, suppose the block size is 10. If you try to use the formula `n / 10` to get the number of required blocks then you would get 1 block for n = 15. This is wrong, you need 2.
If you change the formula to be `n / 10 + 1` then it will also be wrong. When n = 20 you only need 2 blocks, but that formula will return 3.
The correct formula is `(n - 1) / 10 + 1`. That's how you round up with integer division. The only difference with this and the formula you asked about is the extra `sizeof(Header)`, which is just the extra space needed for the header itself.
Problem
This code is from the K & R book - Chapter 8 Section 7: Example - Storage Allocator. This code, at least for me, doesn't make sense. "Header" is a union of a struct and a "most restrictive alignment type", which is a long type. Malloc will then find a big enough free space with size of a multiple of the header size. ``` 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 */ } } ``` The odd part of this code is the statement `nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1;` which is then used in the comparison `if (p->s.size >= nunits)` to find a big enough space with units in terms of the size of Header. Shouldn't the former be `nunits = (nbytes+sizeof(Header)) / sizeof(Header)` only? The original code would evaluate to a value less than it ought to be. What is with the +-1s? Why allocate space less than the desired.