From 8ab1fe3d9f123be7856a5538909a8965c0ab2aa6 Mon Sep 17 00:00:00 2001
From: P. J. McDermott <pj@pehjota.net>
Date: Fri, 10 Feb 2017 01:02:23 -0500
Subject: research/heap.sh: New file

---
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
+}
--
cgit v0.9.1