free.asm 7.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296
  1. ; vim: ts=4:et:sw=4:
  2. ; Copyleft (K) by Jose M. Rodriguez de la Rosa - (a.k.a. Boriel) - http://www.boriel.com
  3. ; This ASM library is licensed under the BSD license
  4. ; you can use it for any purpose (even for commercial closed source programs).
  5. ; Please read the BSD license on the internet
  6. #include once <heapinit.asm>
  7. ; ---------------------------------------------------------------------
  8. ; MEM_FREE
  9. ; Frees a block of memory
  10. ; Parameters:
  11. ; HL = Pointer to the block to be freed. If HL is NULL (0) nothing
  12. ; is done
  13. ; ---------------------------------------------------------------------
  14. MEM_FREE:
  15. __MEM_FREE:
  16. ; Frees the block pointed by HL
  17. ; HL DE BC & AF modified
  18. ;- PROC
  19. ;- LOCAL __MEM_LOOP2
  20. ;- LOCAL __MEM_LINK_PREV
  21. ;- LOCAL __MEM_JOIN_TEST
  22. ;- LOCAL __MEM_BLOCK_JOIN
  23. lda z80_h ;- ld a,h
  24. sta z80_a
  25. ora z80_l ;- or l
  26. ;- ret z ; Return if NULL pointer
  27. ;- dec hl
  28. ;- dec hl
  29. lda z80_h ;- ld b,h
  30. sta z80_b
  31. lda z80_l ;- ld c,l ; BC = Block pointer
  32. sta z80_c
  33. ;- ld hl, ZXBASIC_MEM_HEAP ; This label point to the heap start
  34. __MEM_LOOP2:
  35. inc z80_l ;- inc hl
  36. bne *+4
  37. inc z80_h
  38. inc z80_l ;- inc hl ; Next block ptr
  39. bne *+4
  40. inc z80_h
  41. ldy #$00 ;- ld e,(hl)
  42. lda (z80_hl),y
  43. sta z80_e
  44. inc z80_l ;- inc hl
  45. bne *+4
  46. inc z80_h
  47. ldy #$00 ;- ld d,(hl) ; Block next ptr
  48. lda (z80_hl),y
  49. sta z80_d
  50. lda z80_e ;- ex de,hl ; DE = &(block->next); HL = block->next
  51. ldx z80_l
  52. stx z80_e
  53. sta z80_l
  54. lda z80_d
  55. ldx z80_h
  56. stx z80_d
  57. sta z80_h
  58. ;- ld a, h ; HL == NULL?
  59. ora z80_l ;- or l
  60. ;- jp z, __MEM_LINK_PREV; if so, link with previous
  61. ora z80_a ;- or a ; Clear carry flag
  62. ;- sbc hl, bc ; Carry if BC > HL => This block if before
  63. ;- add hl, bc ; Restores HL, preserving Carry flag
  64. ;- jp c, __MEM_LOOP2 ; This block is before. Keep searching PASS the block
  65. ;------ At this point current HL is PAST BC, so we must link (DE) with BC, and HL in BC->next
  66. __MEM_LINK_PREV:
  67. ; Link (DE) with BC, and BC->next with HL
  68. lda z80_e ;- ex de,hl
  69. ldx z80_l
  70. stx z80_e
  71. sta z80_l
  72. lda z80_d
  73. ldx z80_h
  74. stx z80_d
  75. sta z80_h
  76. lda z80_l ;- push hl
  77. pha
  78. lda z80_h
  79. pha
  80. ;- dec hl
  81. lda z80_c ;- ld (hl),c
  82. ldy #$00
  83. sta (z80_hl),y
  84. inc z80_l ;- inc hl
  85. bne *+4
  86. inc z80_h
  87. lda z80_b ;- ld (hl),b ; (DE) <- BC
  88. ldy #$00
  89. sta (z80_hl),y
  90. lda z80_b ;- ld h,b ; HL <- BC (Free block ptr)
  91. sta z80_h
  92. lda z80_c ;- ld l,c
  93. sta z80_l
  94. inc z80_l ;- inc hl ; Skip block length (2 bytes)
  95. bne *+4
  96. inc z80_h
  97. inc z80_l ;- inc hl
  98. bne *+4
  99. inc z80_h
  100. lda z80_e ;- ld (hl),e ; Block->next = DE
  101. ldy #$00
  102. sta (z80_hl),y
  103. inc z80_l ;- inc hl
  104. bne *+4
  105. inc z80_h
  106. lda z80_d ;- ld (hl),d
  107. ldy #$00
  108. sta (z80_hl),y
  109. ; --- LINKED ; HL = &(BC->next) + 2
  110. jsr __MEM_JOIN_TEST ;- call __MEM_JOIN_TEST
  111. pla ;- pop hl
  112. sta z80_h
  113. pla
  114. sta z80_l
  115. __MEM_JOIN_TEST:
  116. ; Checks for fragmented contiguous blocks and joins them
  117. ; hl = Ptr to current block + 2
  118. ldy #$00 ;- ld d,(hl)
  119. lda (z80_hl),y
  120. sta z80_d
  121. ;- dec hl
  122. ldy #$00 ;- ld e,(hl)
  123. lda (z80_hl),y
  124. sta z80_e
  125. ;- dec hl
  126. ldy #$00 ;- ld b,(hl) ; Loads block length into BC
  127. lda (z80_hl),y
  128. sta z80_b
  129. ;- dec hl
  130. ldy #$00 ;- ld c,(hl)
  131. lda (z80_hl),y
  132. sta z80_c
  133. lda z80_l ;- push hl ; Saves it for later
  134. pha
  135. lda z80_h
  136. pha
  137. lda z80_l ;- add hl, bc ; Adds its length. If HL == DE now, it must be joined
  138. clc
  139. adc z80_c
  140. sta z80_l
  141. lda z80_h
  142. adc z80_b
  143. sta z80_h
  144. ora z80_a ;- or a
  145. ;- sbc hl, de ; If Z, then HL == DE => We must join
  146. pla ;- pop hl
  147. sta z80_h
  148. pla
  149. sta z80_l
  150. beq *+3 ;- ret nz
  151. rts
  152. __MEM_BLOCK_JOIN: ; Joins current block (pointed by HL) with next one (pointed by DE). HL->length already in BC
  153. lda z80_l ;- push hl ; Saves it for later
  154. pha
  155. lda z80_h
  156. pha
  157. lda z80_e ;- ex de,hl
  158. ldx z80_l
  159. stx z80_e
  160. sta z80_l
  161. lda z80_d
  162. ldx z80_h
  163. stx z80_d
  164. sta z80_h
  165. ldy #$00 ;- ld e,(hl) ; DE -> block->next->length
  166. lda (z80_hl),y
  167. sta z80_e
  168. inc z80_l ;- inc hl
  169. bne *+4
  170. inc z80_h
  171. ldy #$00 ;- ld d,(hl)
  172. lda (z80_hl),y
  173. sta z80_d
  174. inc z80_l ;- inc hl
  175. bne *+4
  176. inc z80_h
  177. lda z80_e ;- ex de,hl ; DE = &(block->next)
  178. ldx z80_l
  179. stx z80_e
  180. sta z80_l
  181. lda z80_d
  182. ldx z80_h
  183. stx z80_d
  184. sta z80_h
  185. lda z80_l ;- add hl,bc ; HL = Total Length
  186. clc
  187. adc z80_c
  188. sta z80_l
  189. lda z80_h
  190. adc z80_b
  191. sta z80_h
  192. lda z80_h ;- ld b,h
  193. sta z80_b
  194. lda z80_l ;- ld c,l ; BC = Total Length
  195. sta z80_c
  196. lda z80_e ;- ex de,hl
  197. ldx z80_l
  198. stx z80_e
  199. sta z80_l
  200. lda z80_d
  201. ldx z80_h
  202. stx z80_d
  203. sta z80_h
  204. ldy #$00 ;- ld e,(hl)
  205. lda (z80_hl),y
  206. sta z80_e
  207. inc z80_l ;- inc hl
  208. bne *+4
  209. inc z80_h
  210. ldy #$00 ;- ld d,(hl) ; DE = block->next
  211. lda (z80_hl),y
  212. sta z80_d
  213. pla ;- pop hl ; Recovers Pointer to block
  214. sta z80_h
  215. pla
  216. sta z80_l
  217. lda z80_c ;- ld (hl),c
  218. ldy #$00
  219. sta (z80_hl),y
  220. inc z80_l ;- inc hl
  221. bne *+4
  222. inc z80_h
  223. lda z80_b ;- ld (hl),b ; Length Saved
  224. ldy #$00
  225. sta (z80_hl),y
  226. inc z80_l ;- inc hl
  227. bne *+4
  228. inc z80_h
  229. lda z80_e ;- ld (hl),e
  230. ldy #$00
  231. sta (z80_hl),y
  232. inc z80_l ;- inc hl
  233. bne *+4
  234. inc z80_h
  235. lda z80_d ;- ld (hl),d ; Next saved
  236. ldy #$00
  237. sta (z80_hl),y
  238. rts ;- ret
  239. ;- ENDP
  240. ;-------------------------------------------------------------------------------
  241. ; ----- IMPLEMENTATION NOTES ------
  242. ; The heap is implemented as a linked list of free blocks.
  243. ; Each free block contains this info:
  244. ; +----------------+ <-- HEAP START
  245. ; | Size (2 bytes) |
  246. ; | 0 | <-- Size = 0 => DUMMY HEADER BLOCK
  247. ; +----------------+
  248. ; | Next (2 bytes) |---+
  249. ; +----------------+ <-+
  250. ; | Size (2 bytes) |
  251. ; +----------------+
  252. ; | Next (2 bytes) |---+
  253. ; +----------------+ |
  254. ; | <free bytes...>| | <-- If Size > 4, then this contains (size - 4) bytes
  255. ; | (0 if Size = 4)| |
  256. ; +----------------+ <-+
  257. ; | Size (2 bytes) |
  258. ; +----------------+
  259. ; | Next (2 bytes) |---+
  260. ; +----------------+ |
  261. ; | <free bytes...>| |
  262. ; | (0 if Size = 4)| |
  263. ; +----------------+ |
  264. ; <Allocated> | <-- This zone is in use (Already allocated)
  265. ; +----------------+ <-+
  266. ; | Size (2 bytes) |
  267. ; +----------------+
  268. ; | Next (2 bytes) |---+
  269. ; +----------------+ |
  270. ; | <free bytes...>| |
  271. ; | (0 if Size = 4)| |
  272. ; +----------------+ <-+
  273. ; | Next (2 bytes) |--> NULL => END OF LIST
  274. ; | 0 = NULL |
  275. ; +----------------+
  276. ; | <free bytes...>|
  277. ; | (0 if Size = 4)|
  278. ; +----------------+
  279. ; When a block is FREED, the previous and next pointers are examined to see
  280. ; if we can defragment the heap. If the block to be breed is just next to the
  281. ; previous, or to the next (or both) they will be converted into a single
  282. ; block (so defragmented).
  283. ;-- MEMORY MANAGER
  284. ; This library must be initialized calling __MEM_INIT with
  285. ; HL = BLOCK Start & DE = Length.
  286. ; An init directive is useful for initialization routines.
  287. ; They will be added automatically if needed.