c - Explain this implementation of free from the K&R book -
this excerpt malloc/free implementation on k&r book. having great difficulty in understanding free function, if statement in loop: if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
. if p >= p->s.ptr
true, p must last node in free list, since circular list, p->s.ptr
must point base header (remember therer list header defined static header base;
). how can bp < p->s.ptr
true? can please explain it?
/* free: put block ap in free list */ void free(void *ap) { header *bp, *p; bp = (header *)ap - 1; /* point block header */ (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr) if (p >= p->s.ptr && (bp > p || bp < p->s.ptr)) break; /* freed block @ start or end of arena */ if (bp + bp->s.size == p->s.ptr) { /* join upper nbr */ bp->s.size += p->s.ptr->s.size; bp->s.ptr = p->s.ptr->s.ptr; } else bp->s.ptr = p->s.ptr; if (p + p->s.size == bp) { /* join lower nbr */ p->s.size += bp->s.size; p->s.ptr = bp->s.ptr; } else p->s.ptr = bp; freep = p; }
the first loop trying find free block before block freed. traversing through blocks have been freed, not blocks.
there 2 cases consider. either next free block comes after current free block (the usual case), or next block wraps around beginning.
if next free block comes after current free block, need check see if block freeing between current block , next. if, however, next free block wraps around, due circular nature of list, have see whether block freeing comes after current block or before next.
note free list list of free blocks, if
talking checking see if block freed (but isn't freed yet!) before first block has been freed, entirely possible.
Comments
Post a Comment