summaryrefslogtreecommitdiffstats
path: root/research/heap.sh
diff options
context:
space:
mode:
Diffstat (limited to 'research/heap.sh')
-rw-r--r--research/heap.sh42
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
+}