6502basiccompiler/arch/6502/__sandbox__/library-asm/_2_converting/alloc.asm

; 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

; ----- 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 freed 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.
#include once <error.asm>
#include once <heapinit.asm>
;
; ---------------------------------------------------------------------
; MEM_ALLOC
;  Allocates a block of memory in the heap.
;
; Parameters
;  BC = Length of requested memory block
;
; Returns:
;  HL = Pointer to the allocated block in memory. Returns 0 (NULL)
;       if the block could not be allocated (out of memory)
; ---------------------------------------------------------------------
;
MEM_ALLOC:
__MEM_ALLOC: ; Returns the 1st free block found of the given length (in BC)
        PROC
        LOCAL __MEM_LOOP
        LOCAL __MEM_DONE
        LOCAL __MEM_SUBTRACT
        LOCAL __MEM_START
        LOCAL TEMP, TEMP0

TEMP EQU TEMP0 + 1
                     ;- ld hl, 0
                     ;- ld (TEMP), hl

__MEM_START:
                     ;- ld hl, ZXBASIC_MEM_HEAP  ; This label point to the heap start
inc z80_c            ;- inc bc
bne *+4
inc z80_b
inc z80_c            ;- inc bc  ; BC = BC + 2 ; block size needs 2 extra bytes for hidden pointer
bne *+4
inc z80_b

__MEM_LOOP:  ; Loads lengh at (HL, HL+). If Lenght >= BC, jump to __MEM_DONE
lda z80_h            ;- ld a,h ;  HL = NULL (No memory available?)
sta z80_a
ora z80_l            ;- or l
#ifdef __MEMORY_CHECK__
                     ;- ld a, ERROR_OutOfMemory
jeq __ERROR          ;- jp z, __ERROR
#else
bne *+3              ;- ret z ; NULL
rts

#endif
; HL = Pointer to Free block
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)
lda (z80_hl),y
sta z80_d
inc z80_l            ;- inc hl          ; DE = Block Length
bne *+4
inc z80_h
lda z80_l            ;- push hl         ; HL = *pointer to -> next block
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
ora z80_a            ;- or a            ; CF = 0
                     ;- sbc hl, bc      ; FREE >= BC (Length)  (HL = BlockLength - Length)
jcs __MEM_DONE       ;- jp nc, __MEM_DONE
pla                  ;- pop hl
sta z80_h
pla
sta z80_l
lda z80_l            ;- ld (TEMP), hl
sta TEMP
lda z80_h
sta TEMP+1
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)
lda (z80_hl),y
sta z80_d
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
jmp __MEM_LOOP       ;- jp __MEM_LOOP

__MEM_DONE:
; A free block has been found.
; Check if at least 4 bytes remains free (HL >= 4)
lda z80_l            ;- push hl
pha
lda z80_h
pha
lda z80_c            ;- exx  ; exx to preserve bc
ldx z80_cp
stx z80_c
sta z80_cp
lda z80_b
ldx z80_bp
stx z80_b
sta z80_bp
lda z80_e
ldx z80_ep
stx z80_e
sta z80_ep
lda z80_d
ldx z80_dp
stx z80_d
sta z80_dp
lda z80_l
ldx z80_lp
stx z80_l
sta z80_lp
lda z80_h
ldx z80_hp
stx z80_h
sta z80_hp
pla                  ;- pop hl
sta z80_h
pla
sta z80_l
lda #<4              ;- ld bc,4
sta z80_c
lda #>4
sta z80_b
ora z80_a            ;- or a
                     ;- sbc hl,bc
lda z80_c            ;- exx
ldx z80_cp
stx z80_c
sta z80_cp
lda z80_b
ldx z80_bp
stx z80_b
sta z80_bp
lda z80_e
ldx z80_ep
stx z80_e
sta z80_ep
lda z80_d
ldx z80_dp
stx z80_d
sta z80_dp
lda z80_l
ldx z80_lp
stx z80_l
sta z80_lp
lda z80_h
ldx z80_hp
stx z80_h
sta z80_hp
jcs __MEM_SUBTRACT    ;- jp nc, __MEM_SUBTRACT
; At this point...
; less than 4 bytes remains free. So we return this block entirely
; We must link the previous block with the next to this one
; (DE) => Pointer to next block
; (TEMP) => &(previous->next)
;
pla                  ;- pop hl     ; Discard current block pointer
sta z80_h
pla
sta z80_l
lda z80_e            ;- push de
pha
lda z80_d
pha
lda z80_e            ;- ex de,hl  ; DE = Previous block pointer; (HL) = Next block pointer
ldx z80_l
stx z80_e
sta z80_l
lda z80_d
ldx z80_h
stx z80_d
sta z80_h
ldy #$00             ;- ld a,(hl)
lda (z80_hl),y
sta z80_a
inc z80_l            ;- inc hl
bne *+4
inc z80_h
ldy #$00             ;- ld h,(hl)
lda (z80_hl),y
sta z80_h
lda z80_a            ;- ld l,a    ; HL = (HL)
sta z80_l
lda z80_e            ;- ex de,hl  ; HL = Previous block pointer; DE = Next block pointer
ldx z80_l
stx z80_e
sta z80_l
lda z80_d
ldx z80_h
stx z80_d
sta z80_h

TEMP0:
lda #<0              ;- ld hl,0   ; Pre-previous block pointer
sta z80_l
lda #>0
sta 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 ; LINKED
ldy #$00
sta (z80_hl),y
pla                  ;- pop hl ; Returning block.
sta z80_h
pla
sta z80_l
rts                  ;- ret

__MEM_SUBTRACT:
; At this point we have to store HL value (Length - BC) into (DE - 2)
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
                     ;- dec hl
lda z80_d            ;- ld (hl),d
ldy #$00
sta (z80_hl),y
                     ;- dec hl
lda z80_e            ;- ld (hl),e ; Store new block length
ldy #$00
sta (z80_hl),y
clc                  ;- add hl,de ; New length + DE => free-block start
lda z80_l
adc z80_e
sta z80_l
lda z80_h
adc z80_d
sta z80_h
pla                  ;- pop de     ; Remove previous HL off the stack
sta z80_d
pla
sta z80_e
lda z80_c            ;- ld (hl),c ; Store length on its 1st word
ldy #$00
sta (z80_hl),y
inc z80_l            ;- inc hl
bne *+4
inc z80_h
lda z80_b            ;- ld (hl),b
ldy #$00
sta (z80_hl),y
inc z80_l            ;- inc hl     ; Return hl
bne *+4
inc z80_h
rts                  ;- ret
                     ;- ENDP