research/malloc.txt: New incomplete notes

1 files changed, 178 insertions, 0 deletions

diff --git a/research/malloc.txt b/research/malloc.txt
new file mode 100644
index 0000000..6335486
--- /dev/null
+++ b/research/malloc.txt
@@ -0,0 +1,178 @@
+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