Friday, March 13, 2009

My Life with a Linked List

I meant to spend today working on my computer science homework in hopes of having it done before spring break. That way I could spend my week working on real work, house work, and assorted other tasks that have nothing to do with classes that I'm teaching or taking. Didn't work out as planned, and administrative tasks kept me away from the assignment for most of the day.

The task at hand is to write malloc and free (as well as calloc and realloc). The lecture notes go on in great detail about how to manage the free list and how to give away bits of memory and how to allow them to be returned to the list. We're urged to use a doubly-linked list, and the notes go through great contortions to make sure that when you return (or add) free memory to the list that all the nodes are in order by memory location.

This is all well and good if one's free is required to behave decently with respect to memory fragmentation. If you go and malloc(1) until you run out of memory and then go back and free all of those, ideally you should have a nice expanse of free memory. But in our assignment we're explicitly told that it's OK if we leave the memory in stupidly small chunks. We're told that we don't get any more points for coalescing the memory than if we leave it fragmented.

Therefore, I'm just tossing every bit of free'd memory on one end of the list. Doesn't matter what's it's next to.

With this simplification, I think I'm much closer to completing the assignment in a timely way. If I can just figure out a few things about pointer arithmetic and type casting, I should be able to wrap this up well before the due date.