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;
  char allocated;
} header_t;

void *
malloc_init()
{
  header_t *h = (header_t *)heap_start;
  h->size = (heap_end - heap_start);
  h->allocated = 0;
}

void *
malloc(size_t size)
{
  header_t *h = (header_t *)heap_start;
  while (h < heap_end) {
     if (h->size > (size + sizeof(header_t))) {
	allocate;
	break;
     }
     h = (header_t *)((char *)h + h->size;
  }

}

void *
allocate(header_t *h, int size) {
  int remaining = h->size - size - sizeof(header_t);
  if remaining > 2*sizeof(header_t) {
    h->size = size + sizeof(header_t);
    h->allocated = 1;
    header_t *next = (char *)h + h->size;
    next->size = remaining;
    next->allocated = 0;
  } else {
    h->allocated = 1;
  }
  return (char *)h + sizeof(header_t); 
}

void
free(void *p)
{
   header_t *h;
   h = (header_t *)((char *)p - sizeof(header_t)); 
   h->allocated = 0;
   while (coalesc()) {
   };
}

int
colaesce(header_t *h)
{
   header_t *next = (header_t *)((char *)h + h->size);
   if (next->allocated) {
	return 0;
   }
   h->size += next->size;
   return 1;
}

Question: how do we colaesce with both previous and next block?
* Add a footer 

Draw picture and explain how do I get the pointer to the previous block

This implementation is called *implicit list* 

Notes on our strawman implementation: 
* we did first-fit to find the block 
  - other choices include next-fit (start where the previous search left off) and best-fit (find the block with the fewest bytes left)
* we did not obey alignment rules
* we did not pack header information to save space


Limitations of implicit list?
* Hint: what's the most expensive operation? How expensive?
* the problem is that the list contains both allocated and free blocks

How about making a list of just free blocks?

typedef struct {
  size_t size;
  char allocated;
  char *next;
  char *prev; 
} header_t;

typedef footer {
  size_t size;
  char allocated;
} footer_t;

Draw picture of free block format
size
allocated
next
..
..
size
allocated

next, prev fields only exist for free blocks

char *heap_start;
char *heap_end;
header_t *flist;

void
init()
{
  flist = (header_t *)heap_start;
  flist->prev = flist->next = NULL;
  flist->size = heap_end-heap_start;
  flist->allocated = 0;

  footer = heap_start + size - sizeof(footer_t);
  footer->size = flist->size;
  footer->allocated = 0;
}
void
set_block(header_t *p, size_t size, int allocated)
{
       p->size = size;
       p->allocated = allocated;
       //set footer info
       footer_t *f = (footer_t *)((char *)p+ size + HSZ);
       f->allocated = 1;
       f->size = curr->size;
}

void
malloc(size_t size)
{
    header_t *curr = flist;
    while (curr && curr->size < size + HSZ + FSZ ) {
    	curr = curr->next; 
    }
    if (curr) { //found, allocate
        header_t *leftover = (header_t *)((char *)curr + size + HSZ + FSZ);
	set_block(leftover, curr->size - size - HSZ - FSZ, 0);
        //detach curr from list
        if (curr->prev) { 	
	   curr->prev = curr->next
	}else{
	   flist = curr->next
        }
        if (curr->next) {
	   curr->next->prev = curr->prev
	}
        //insert leftover to freelist
 	leftover->next = flist
	leftover->prev = NULL
        flist = leftover

	set_block(curr, size + HSZ + FSZ, 1);
	return (char *)curr + HSZ;
    } else {
	return NULL
    }
}

void
free(void *p)
{
    if prev block is free
        detach from linked list
    if next block is free
        detach from linked list
    maybe merge with prev and/or next block
    insert into linked list
}