Designing Malloc:

Technical challenges:
* how to track which chunks are free?
* free only supplies a pointer, what's the corresponding size?
* which of the free chunk to allocate?

Linked list is promising, can we embed the linked list in the chunks themselves?

   draw a block:   size, status, payload
   No need for explicit pointers, we know the start of the next chunk from the size of the current chunk.

typedef struct {
  size_t size; //including header size
  char allocated;
} hdr_t;

#define HSZ sizeof(hdr_t)

void *
init()
{
  hdr_t *h = (hdr_t *)heap_start;
  h->size = (heap_end - heap_start); //assuming size is sufficiently large
  h->allocated = 0;
}

void *
malloc(size_t size)
{
  hdr_t *h = (hdr_t *)heap_start;
  //if cannot find a large enough free chunk, 
  //ask the OS for more heap space
  while ((void *)h < heap_end) {
     if (h->size > (size + HSZ)) {
	allocate(h, size);
	break;
     }
     h = (hdr_t *)((void *)h + h->size;
  }

}

//allocate size bytes from free chunk h;
void *
allocate(hdr_t *h, int size) {
  int remaining = h->size - size - HSZ;
  if (remaining > HSZ) {
    h->size = size + HSZ;
    h->allocated = 1;
    hdr_t *next = (void *)h + h->size;
    next->size = remaining;
    next->allocated = 0;
  } else {
    h->allocated = 1;
  }
  return (void *)h + HSZ; 
}

void
free(void *p)
{
   hdr_t *h;
   h = (hdr_t *)((void *)p - HSZ); 
   h->allocated = 0;
   coalesce_with_right(h);
}

// combine a newly freed block with its righthand-side free block
void
colaesce_with_right(hdr_t *h)
{
   hdr_t *next = (hdr_t *)((void *)h + h->size);
   while ((void *)next < heap_end && !next->allocated) {
          h->size  += next->size;
   	  next = (hdr_t *)((void *)next + next->size);
   }
}

This implementation is called *implicit list*