research/heap.sh


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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
}