CareerCup

Khoa,
what did you answer? it seems like you should have the memory management data structure.
it might be a heap or a link list or any other tree.

Do you remember what was the right answer?

THX,
Eila

code can be found in K & R book for C...in 8th chapter

All dynamically allocated data are stored in the heap. These are the data created by malloc in C or new in C++. You can imagine the heap as a vector of bytes (characters) and end_of_heap a pointer to the first available byte in the heap:

char heap[heap_size];
int end_of_heap = 0;

A trivial implementation of malloc in C is:
void* malloc ( int size ) {
void* loc = (void*) &heap[end_of_heap];
end_of_heap += size;
return loc;
};

Google "implement malloc". Look at the lambda site.

<<The C Programming Language>>, chapter 8.7.
=================================================
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;
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 */
}
}

============================================
/* free: put block ap in free list */
void free(void *ap)
{
Header *bp, *p;
bp = (Header *)ap - 1; /* point to block header */
for (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 at start or end of arena */
if (bp + bp->size == p->s.ptr) { /* join to 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->size == bp) { /* join to lower nbr */
p->s.size += bp->s.size;
p->s.ptr = bp->s.ptr;
} else
p->s.ptr = bp;
freep = p;
}

what is freeptr and prevptr