123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296 |
- ; vim: ts=4:et:sw=4:
- ; Copyleft (K) by Jose M. Rodriguez de la Rosa - (a.k.a. Boriel) - http://www.boriel.com
- ; This ASM library is licensed under the BSD license
- ; you can use it for any purpose (even for commercial closed source programs).
- ; Please read the BSD license on the internet
- #include once <heapinit.asm>
- ; ---------------------------------------------------------------------
- ; MEM_FREE
- ; Frees a block of memory
- ; Parameters:
- ; HL = Pointer to the block to be freed. If HL is NULL (0) nothing
- ; is done
- ; ---------------------------------------------------------------------
- MEM_FREE:
- __MEM_FREE:
- ; Frees the block pointed by HL
- ; HL DE BC & AF modified
- ;- PROC
- ;- LOCAL __MEM_LOOP2
- ;- LOCAL __MEM_LINK_PREV
- ;- LOCAL __MEM_JOIN_TEST
- ;- LOCAL __MEM_BLOCK_JOIN
- lda z80_h ;- ld a,h
- sta z80_a
- ora z80_l ;- or l
- ;- ret z ; Return if NULL pointer
- ;- dec hl
- ;- dec hl
- lda z80_h ;- ld b,h
- sta z80_b
- lda z80_l ;- ld c,l ; BC = Block pointer
- sta z80_c
- ;- ld hl, ZXBASIC_MEM_HEAP ; This label point to the heap start
- __MEM_LOOP2:
- inc z80_l ;- inc hl
- bne *+4
- inc z80_h
- inc z80_l ;- inc hl ; Next block ptr
- bne *+4
- inc z80_h
- ldy #$00 ;- ld e,(hl)
- lda (z80_hl),y
- sta z80_e
- inc z80_l ;- inc hl
- bne *+4
- inc z80_h
- ldy #$00 ;- ld d,(hl) ; Block next ptr
- lda (z80_hl),y
- sta z80_d
- lda z80_e ;- ex de,hl ; DE = &(block->next); HL = block->next
- ldx z80_l
- stx z80_e
- sta z80_l
- lda z80_d
- ldx z80_h
- stx z80_d
- sta z80_h
- ;- ld a, h ; HL == NULL?
- ora z80_l ;- or l
- ;- jp z, __MEM_LINK_PREV; if so, link with previous
- ora z80_a ;- or a ; Clear carry flag
- ;- sbc hl, bc ; Carry if BC > HL => This block if before
- ;- add hl, bc ; Restores HL, preserving Carry flag
- ;- jp c, __MEM_LOOP2 ; This block is before. Keep searching PASS the block
- ;------ At this point current HL is PAST BC, so we must link (DE) with BC, and HL in BC->next
- __MEM_LINK_PREV:
- ; Link (DE) with BC, and BC->next with HL
- lda z80_e ;- ex de,hl
- ldx z80_l
- stx z80_e
- sta z80_l
- lda z80_d
- ldx z80_h
- stx z80_d
- sta z80_h
- lda z80_l ;- push hl
- pha
- lda z80_h
- pha
- ;- dec hl
- lda z80_c ;- ld (hl),c
- ldy #$00
- sta (z80_hl),y
- inc z80_l ;- inc hl
- bne *+4
- inc z80_h
- lda z80_b ;- ld (hl),b ; (DE) <- BC
- ldy #$00
- sta (z80_hl),y
- lda z80_b ;- ld h,b ; HL <- BC (Free block ptr)
- sta z80_h
- lda z80_c ;- ld l,c
- sta z80_l
- inc z80_l ;- inc hl ; Skip block length (2 bytes)
- bne *+4
- inc z80_h
- inc z80_l ;- inc hl
- bne *+4
- inc z80_h
- lda z80_e ;- ld (hl),e ; Block->next = DE
- ldy #$00
- sta (z80_hl),y
- inc z80_l ;- inc hl
- bne *+4
- inc z80_h
- lda z80_d ;- ld (hl),d
- ldy #$00
- sta (z80_hl),y
- ; --- LINKED ; HL = &(BC->next) + 2
- jsr __MEM_JOIN_TEST ;- call __MEM_JOIN_TEST
- pla ;- pop hl
- sta z80_h
- pla
- sta z80_l
- __MEM_JOIN_TEST:
- ; Checks for fragmented contiguous blocks and joins them
- ; hl = Ptr to current block + 2
- ldy #$00 ;- ld d,(hl)
- lda (z80_hl),y
- sta z80_d
- ;- dec hl
- ldy #$00 ;- ld e,(hl)
- lda (z80_hl),y
- sta z80_e
- ;- dec hl
- ldy #$00 ;- ld b,(hl) ; Loads block length into BC
- lda (z80_hl),y
- sta z80_b
- ;- dec hl
- ldy #$00 ;- ld c,(hl)
- lda (z80_hl),y
- sta z80_c
- lda z80_l ;- push hl ; Saves it for later
- pha
- lda z80_h
- pha
- lda z80_l ;- add hl, bc ; Adds its length. If HL == DE now, it must be joined
- clc
- adc z80_c
- sta z80_l
- lda z80_h
- adc z80_b
- sta z80_h
- ora z80_a ;- or a
- ;- sbc hl, de ; If Z, then HL == DE => We must join
- pla ;- pop hl
- sta z80_h
- pla
- sta z80_l
- beq *+3 ;- ret nz
- rts
- __MEM_BLOCK_JOIN: ; Joins current block (pointed by HL) with next one (pointed by DE). HL->length already in BC
- lda z80_l ;- push hl ; Saves it for later
- pha
- lda z80_h
- pha
- lda z80_e ;- ex de,hl
- ldx z80_l
- stx z80_e
- sta z80_l
- lda z80_d
- ldx z80_h
- stx z80_d
- sta z80_h
- ldy #$00 ;- ld e,(hl) ; DE -> block->next->length
- lda (z80_hl),y
- sta z80_e
- inc z80_l ;- inc hl
- bne *+4
- inc z80_h
- ldy #$00 ;- ld d,(hl)
- lda (z80_hl),y
- sta z80_d
- inc z80_l ;- inc hl
- bne *+4
- inc z80_h
- lda z80_e ;- ex de,hl ; DE = &(block->next)
- ldx z80_l
- stx z80_e
- sta z80_l
- lda z80_d
- ldx z80_h
- stx z80_d
- sta z80_h
- lda z80_l ;- add hl,bc ; HL = Total Length
- clc
- adc z80_c
- sta z80_l
- lda z80_h
- adc z80_b
- sta z80_h
- lda z80_h ;- ld b,h
- sta z80_b
- lda z80_l ;- ld c,l ; BC = Total Length
- sta z80_c
- lda z80_e ;- ex de,hl
- ldx z80_l
- stx z80_e
- sta z80_l
- lda z80_d
- ldx z80_h
- stx z80_d
- sta z80_h
- ldy #$00 ;- ld e,(hl)
- lda (z80_hl),y
- sta z80_e
- inc z80_l ;- inc hl
- bne *+4
- inc z80_h
- ldy #$00 ;- ld d,(hl) ; DE = block->next
- lda (z80_hl),y
- sta z80_d
- pla ;- pop hl ; Recovers Pointer to block
- sta z80_h
- pla
- sta z80_l
- lda z80_c ;- ld (hl),c
- ldy #$00
- sta (z80_hl),y
- inc z80_l ;- inc hl
- bne *+4
- inc z80_h
- lda z80_b ;- ld (hl),b ; Length Saved
- ldy #$00
- sta (z80_hl),y
- inc z80_l ;- inc hl
- bne *+4
- inc z80_h
- lda z80_e ;- ld (hl),e
- ldy #$00
- sta (z80_hl),y
- inc z80_l ;- inc hl
- bne *+4
- inc z80_h
- lda z80_d ;- ld (hl),d ; Next saved
- ldy #$00
- sta (z80_hl),y
- rts ;- ret
- ;- ENDP
- ;-------------------------------------------------------------------------------
- ; ----- IMPLEMENTATION NOTES ------
- ; The heap is implemented as a linked list of free blocks.
- ; Each free block contains this info:
- ; +----------------+ <-- HEAP START
- ; | Size (2 bytes) |
- ; | 0 | <-- Size = 0 => DUMMY HEADER BLOCK
- ; +----------------+
- ; | Next (2 bytes) |---+
- ; +----------------+ <-+
- ; | Size (2 bytes) |
- ; +----------------+
- ; | Next (2 bytes) |---+
- ; +----------------+ |
- ; | <free bytes...>| | <-- If Size > 4, then this contains (size - 4) bytes
- ; | (0 if Size = 4)| |
- ; +----------------+ <-+
- ; | Size (2 bytes) |
- ; +----------------+
- ; | Next (2 bytes) |---+
- ; +----------------+ |
- ; | <free bytes...>| |
- ; | (0 if Size = 4)| |
- ; +----------------+ |
- ; <Allocated> | <-- This zone is in use (Already allocated)
- ; +----------------+ <-+
- ; | Size (2 bytes) |
- ; +----------------+
- ; | Next (2 bytes) |---+
- ; +----------------+ |
- ; | <free bytes...>| |
- ; | (0 if Size = 4)| |
- ; +----------------+ <-+
- ; | Next (2 bytes) |--> NULL => END OF LIST
- ; | 0 = NULL |
- ; +----------------+
- ; | <free bytes...>|
- ; | (0 if Size = 4)|
- ; +----------------+
- ; When a block is FREED, the previous and next pointers are examined to see
- ; if we can defragment the heap. If the block to be breed is just next to the
- ; previous, or to the next (or both) they will be converted into a single
- ; block (so defragmented).
- ;-- MEMORY MANAGER
- ; This library must be initialized calling __MEM_INIT with
- ; HL = BLOCK Start & DE = Length.
- ; An init directive is useful for initialization routines.
- ; They will be added automatically if needed.
|