implementing malloc

[tubby123]

Guys, this is the code from KnR

I dont understand this line
nunits = (nbytes+sizeof(Header)-1)/sizeof(header) + 1;

The entire code is as follows

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 *moreroce(unsigned);
unsigned nunits;
[B]nunits = (nbytes+sizeof(Header)-1)/sizeof(header) + 1;[/B]
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 */

[L7Sqr]

Assume that sizeof(Header) is 20. You call malloc(100) and nunits is evaluated as:

nunits = (100 + 20 - 1) / 20 + 1
nunits = (119) / 20 + 1
nunits = 5 + 1
nunits = 6

That is the amount of space (in terms of header blocks) required to satisfy the requested size.

The nbytes + sizeof(Header) - 1 , because of integer arithmetic properly adjusts of partial blocks. For example

Size = # of Blocks
 99 = 6
100 = 6
101 = 7
102 = 7
103 = 7

[tubby123]

Thank you for the quick response,
but if you want to malloc 100 bytes, then what is 6 ?
1)I mean, i am getting confused cuz i feel like only 6 bytes is getting calculated.
2)What exactly does the morecore function do ? Is this right, it calls sbrk which allocates memory ????

[L7Sqr]

... but if you want to malloc 100 bytes, then what is 6 ?...

See my original response:

That is the amount of space (in terms of header blocks) required to satisfy the requested size.

2)What exactly does the morecore function do ? Is this right, it calls sbrk which allocates memory ????

It is pretty hard to comment on that without seeing the implementation of morecore

[rubberman]

My guess is that morecore() is using sbrk() under the covers. In many cases, malloc() implements the allocated heap (locally) as a linked list of allocated parts. When one is freed, then the allocator either merges the freed part with an adjacent free segment in the free list, or it links it into the free list.