programs/sub-suite/free-new.s


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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143


.include "declare.s"

.org 0

; free: Free allocated memory.
; Input: D = Pointer to allocated memory.
; Output: none.
; Caller preserved registers: D.
; Callie preserved registers: A, B, X, Y, E.

free:
	pha.q			; Preserve A.
	phb.q			; Preserve B.
	phx.q			; Preserve X.
	phy.q			; Preserve Y.
	phe.q			; Preserve E.
	and #0			; Reset A.
	tab			; Reset B.
	tax			; Reset X.
	tay			; Reset Y.
	mov a, d		; Get the passed pointer.
	bne @getrealblk		; The pointer isn't NULL, so get the real block.
	bra @end		; The pointer is NULL, so we're done.
@getrealblk:
	sub #8			; Get the start of the used block.
	mov.q a, (a)		; Get the start of the real block.
	mov.q b, (a+ublk.size)	; Get the size of the real block.
	lea e, (a+b)		; Add the size of the real block with the start of the real block.
	cmp.q e, heapptr	; Is this block on top of the heap?
	bne @heapadd		; No, so add it to the free block list.
@dectop:
	mov.q heapptr, (a)	; Set the top of the heap to the start of the previous real block.
@chklastblk:
	mov.q b, heapl		; Get the last free list entry.
	beq @end		; The free list is empty, so we're done.
	ldy #fblk.size		; Get the size of the block.
	mov.q a, (b+fblk.size)	; Get the size of the block.
	lea e, (a+b)		; Add the size of the block, with the address of the block entry.
	cmp.q e, heapptr	; Is the last block on top of the heap?
	bne @end		; No, so we're done.
@delblk:
	mov.q heapptr, b	; Yes, so remove the last block.
@correctblk:
	mov.q a, (b+fblk.prev)	; Get the previous block.
	sta.q heapl		; Set the last block to the previous block.
	bne @delnxtblk		; The previous block isn't NULL, so delete the next block.
	sta.q heapf		; The previous block is NULL, so empty the free list.
	bra @end		; We are done.
@delnxtblk:
	lea e, (a+fblk.next)	; Delete the next block.
	stz.q (e)		;
@end:
	ple.q			; Restore E.
	ply.q			; Restore Y.
	plx.q			; Restore X.
	plb.q			; Restore B.
	pla.q			; Restore A.
	rts			; End of free.


@heapadd:
	mov.q y, heapf		; Get the first block.
	bne @srchflst		; The Free list isn't empty, so start searching the free list.
@empty:
	mov.q (a+fblk.next), y	; Clear the next block.
	mov.q (a+fblk.prev), y	; Clear the previous block.
	sta.q heapf		; Set the first block entry to the current block.
	sta.q heapl		; Set the last block entry to the current block.
	bra @end		; We are done.
@srchflst:
@loop:
	cmp y, a		; Is the right pointer at, or below the current block?
	beq @nextright		; Yes, so get the next right pointer.
	bcs @chkrmerge		; No, so do the right block merge.
@nextright:
	tyx			; Set the left pointer, to the right pointer.
	mov.q y, (y+fblk.next)	; Set the current right pointer to the next right pointer.
	bne @loop		; The next right pointer isn't NULL, so keep looping.
@st_lmerge2:
	mov.q (a+fblk.next), y	; Clear the next block.
	sta.q heapl		; Set the last free block entry to it.
	bra @chklmerge2		; Do the left block merge.
@chkrmerge:
	lea e, (a+b)		; Add the size of the current block, to the current block.
	cmp e, y		; Is the current block the same as the right block?
	bne @normerge		; No, so don't merge the right block.
@rmerge:
	mov e, b		; Get the size of the current block.
	add.q e, (y+fblk.size)	; Add the size of the current block, with the size of the right pointer.
	mov.q (a+fblk.size), e	; Set the size of the current block, to the new size.
@rmerge2:
	lea fblk.next		; Get the next right pointer.
	mov.q (a+e), (y+e)	; Set the next block, to the next right pointer.
	mov.q b, (y+e)		; Save the next block.
	beq @setheapl		; The next block is NULL, so set the last block.
@setprev:
	mov.q (b+fblk.prev), a	; Set the previous block to the current block.
	bra @chklmerge		; Do the left block merge.
@setheapl:
	sta.q heapl		; Set the last block to the current block.
	bra @chklmerge		; Do the left block merge.
@normerge:
	mov.q (a+fblk.next), y	; Set the next block to the right pointer.
	mov.q (y+fblk.prev), a	; Set the previous right pointer to the current block.
@chklmerge:
	and x, x		; Is the left pointer NULL?
	bne @chklmerge2		; No, so keep checking.
@newstart:
	mov.q (a+fblk.prev), x	;
	sta.q heapf		; Set the first block, to the current block.
	bra @end2		; We are done.
@chklmerge2:
	mov.q e, (x+fblk.size)	; Get the size of the left block.
	add e, x		; Add the size of the left block, to the left pointer.
	cmp e, a		; Is the left block adjacent?
	bne @nolmerge		; No, so don't merge the left block.
@lmerge:
	lea fblk.size		; Set the offset to the block size.
	add.q (x+e), (a+e)	; Add the size of the left block, with the size of the current block.
@lmerge2:
	lea fblk.next		; Set the offset to the next block.
	mov.q (x+e), (a+e)	; Set the next left pointer, to the next block.
	mov.q b, (a+e)		; Get the next block.
	beq @newlast		; The next block is NULL, so set the last block.
@lprev:
	mov.q (b+fblk.prev), x	; Set the next left pointer's previous pointer to the left pointer.
	bra @end2		; We are done.
@newlast:
	stx.q heapl		; Set the last block, to the left pointer.
	bra @end2		; We are done.
@nolmerge:
	mov.q (x+fblk.next), a	; Set the next left pointer, to the current block.
@nolmerge2:
	mov.q (a+fblk.prev), x	; Set the previous block, to the left pointer.
@end2:
	ple.q			; Restore E.
	ply.q			; Restore Y.
	plb.q			; Restore B.
	pla.q			; Restore A.
	rts			; End of free.

a
q