research/heap.sh: New file

1 files changed, 42 insertions, 0 deletions

diff --git a/research/heap.sh b/research/heap.sh
new file mode 100644
index 0000000..54ce1e3
--- /dev/null
+++ b/research/heap.sh
@@ -0,0 +1,42 @@
+__malloc()
+{
+	__heap=${1}
+
+	if eval "\${${__heap}_size:+true}"; then
+		# Empty heap
+		__mr="${__heap}0"
+		eval "${__heap}_size=1"
+	elif eval "\${${__heap}_free_head:+false}"; then
+		# No free blocks, grow heap
+		eval "__mr=\${__heap}\${${__heap}_size}"
+		eval "${__heap}_size=\$((\${${__heap}_size} + 1))"
+	else
+		# Free block(s) available, allocate
+		eval "__mr=\${${__heap}_free_head}"
+		if eval "\${${__mr}_next_free:+false}"; then
+			# Last free block, clear heap's free list
+			eval "${__heap}_free_head="
+			eval "${__heap}_free_tail="
+		else
+			# Multiple free blocks, move heap's free list head
+			eval "${__heap}_free_head=\${${__mr}_next_free}"
+		fi
+	fi
+}
+
+__free()
+{
+	__heap=${1}
+	__ptr=${2}
+
+	if eval "\${${__heap}_free_tail:+false}"; then
+		# Empty free list
+		eval "${__heap}_free_head=\${__ptr}"
+		eval "${__heap}_free_tail=\${__ptr}"
+	else
+		# Non-empty free list, push to tail
+		eval "__free_tail=\${${__heap}_free_tail}"
+		eval "${__free_tail}_next_free=\${__ptr}"
+		eval "${__heap}_free_tail=\${__ptr}"
+	fi
+}