**Broken/incomplete!  See heap.txt.**

A heap is a set of slots.  Contiguous sets of slots with the same status (free
or allocated) are grouped into blocks.

Example Heap Activity
=====================

	|
	|
	
	malloc
	 ___
	|   |
	|___|
	
	malloc
	 _______
	|   .   |
	|_______|
	
	malloc
	 ___________
	|   .   .   |
	|___________|
	
	free 1
	 ___ ___ ___
	|   | F |   |
	|___|___|___|
	
	malloc
	 ___________
	|   .   .   |
	|___________|
	
	malloc
	 _______________
	|   .   .   .   |
	|_______________|
	
	malloc
	 ___________________
	|   .   .   .   .   |
	|___________________|
	
	malloc
	 _______________________
	|   .   .   .   .   .   |
	|_______________________|
	
	malloc
	 ___________________________
	|   .   .   .   .   .   .   |
	|___________________________|
	
	malloc
	 _______________________________
	|   .   .   .   .   .   .   .   |
	|_______________________________|
	
	free 1
	 ___ ___ _______________________
	|   | F |   .   .   .   .   .   |
	|___|___|_______________________|
	
	free 2
	 ___ _______ ___________________
	|   | F .   |   .   .   .   .   |
	|___|_______|___________________|
	
	free 6
	 ___ _______ ___________ ___ ___
	|   | F .   |   .   .   | F |   |
	|___|_______|___________|___|___|
	
	free 4
	 ___ _______ ___ ___ ___ ___ ___
	|   | F .   |   | F |   | F |   |
	|___|_______|___|___|___|___|___|
	
	free 5
	 ___ _______ ___ ___________ ___
	|   | F .   |   | F .   .   |   |
	|___|_______|___|___________|___|
	
	malloc
	 _______ ___ ___ ___________ ___
	|   .   | F |   | F .   .   |   |
	|_______|___|___|___________|___|
	
	malloc
	 _______________ ___________ ___
	|   .   .   .   | F .   .   |   |
	|_______________|___________|___|
	
	malloc
	 ___________________ _______ ___
	|   .   .   .   .   | F .   |   |
	|___________________|_______|___|

Superpseudocode
===============

	malloc
		if no top
			set heap->top
			set heap[heap->top] size=1 prev=null, next=null
			return top

	malloc
		if no top
			set and return top
		else if no free head
			grow and return top
		else (free blocks exist)
			if free head size == 1
				move free head to next block
				return old block
			else
				move free block start to head+1, --size
				return old block
	free
		if ptr+1 free
			if heap[ptr+1]->prev + size = ptr
				merge prev with ptr+1
			else
				merge ptr with ptr+1
		elif ptr-1 free
			merge ptr-1 with ptr (just ++size)
		else
			mark ptr free

Pseudocode
==========

`__malloc(heap)`:

	if heap->top = null
		# Empty heap, grow
		heap->top = 0
		return 0
	elif heap->free_head = null
		# No free blocks, grow heap
		return ++heap->top
	else
		# Free blocks exist, reallocate
		if heap[heap->free_head]->size == 1
			# Take whole block, point to next block
			new = heap->free_head
			heap->free_head = heap[heap->free_head]->next
			heap[heap->free_head]->prev = null
			return new
		else
			# Shrink block
			new = heap->free_head
			++heap->free_head
			heap[heap->free_head]->size = heap[new]->size - 1
			heap[heap->free_head]->prev = null
			heap[heap->free_head]->next = heap[new]->next
			unset heap[new]->size
			unset heap[new]->prev
			unset heap[new]->next
			return new

`__free(heap, ptr)`:

	if ptr < heap->top and heap[ptr + 1]->size != null
		
	elif ptr > 0 and heap[ptr - 1]->size != null
		++heap[ptr - 1]->size
	else
		heap->ptr

	if ptr > 0 and heap[ptr - 1]->size != null
		++heap[ptr - 1]->size
	elif ptr < heap->top and heap[ptr + 1]->size != null
		heap[ptr]->size = heap[ptr + 1]->size + 1
		heap[ptr]->prev = heap[ptr + 1]->prev
		heap[ptr]->next = heap[ptr + 1]->next