; --------------------------------------------------------
;		Dynamische Speicherverwaltung
; --------------------------------------------------------

; Externe Aufrufe:
;	abort_oomem


; Mit diesem Modul kann der freie Speicher dynamisch verwaltet werden.
;
; Zugeteilter Speicher wird immer über ein ortsfestes Handle referenziert.
; Pro Block werden zusätzlich 4 Bytes für Verwaltungsinformationen belegt.
;
; 0-Byte-Blocks werden nicht abgespeichert, Als Handle wird 0 zurückgegeben.
;
; Die maximale Größe für einen einzelnen Block ist $6000 = 24576 Bytes. 
; Dieses Limit wird für die Garbage Collection-Routine benötigt, die eine 
; Grenze zur Unterscheidung von Handle-Adressen und Blockgrößen benötigt.
;
; Sobald eine Speicheranforderung nicht mehr sofort befriedigt werden kann,
; wird automatisch eine Garbage Collection durchgeführt. Diese hat einen
; linearen Zusammenhang zwischen Anzahl angelegter Speicherblöcke plus
; Gesamtgröße aller belegten Blöcke und Zeitverbrauch.
;
; Alle Routinen benutzen nur die Register AF bis HL.
; Alle Register, bis auf AF, werden von allen Routinen nicht verändert,
; wenn darin keine Werte zurückgegeben werden.


; von mem_start bis mem_free_start
;	liegen die datenblöcke.
;	jeder Datenblock beginnt mit 2 Byte Längenangabe.
;	Auch wieder frei gegebene Speicherbereiche sind noch so verwaltet.
;
; von mem_free_start bis mem_handles_start
;	ist freies Ram.
;
; von mem_handles_start bis mem_end
;	sind die handles abgelegt.
;	unbenutzte handles sind = 0.
;	sonst zeigen sie auf die zugehörigen daten
;
; mem_last_handle
;	zeigt auf das zuletzt vergebene Handle.
;	Bei der nächsten Anforderung wird ab dieser Stelle abwärts
;	nach einem neuen freien Handle gesucht.
;
; mem_error_handler
;	enthält die Adresse für den Aussprung aus einer
;	Memory-Routine nach einem Fehler, insbesondere auch 
;	out-of-memory, um evtl. die Daten noch sichern zu können.


mem_start	data	2
mem_data_start	equ	mem_start

mem_data_end	data	2
mem_free_start	equ	mem_data_end

mem_free_end	data	2
mem_handles_start equ	mem_free_end

mem_handles_end	data	2
mem_end		equ	mem_handles_end

mem_last_handle	data	2

lo		equ	0	; offset of low byte in word
hi		equ	1	; offset of high byte in word

mem_max_size	equ	$6000	; darunter auch bei 16K-Modell sicher keine Handles
mem_max_hi	equ	$60



; init_mem			hl de	--
; mem_get_free_total			-- bc z
; mem_get_free				-- bc z
; mem_test_free_total		bc	-- cy
; mem_test_free			bc	-- cy
; mem_alloc			bc	-- hl de z
; mem_dup			hl	-- hl
; mem_dealloc			hl	--
; mem_get_address		hl	-- hl
; mem_get_size			hl	-- bc z
; mem_save_data			hl bc	-- hl de
; mem_restore_data		hl de	--
; mem_compact				--



; --------------------------------------------------------
; Initialize Memory Handler
;
; in:	hl -> first usable byte
;	de -> behind last usable byte
; out:	--
; mod:	af, bc, de, hl

init_mem:
	ld	(mem_start),hl
	ld	(mem_free_start),hl

	ex	hl,de
	ld	(mem_end),hl
	ld	(mem_free_end),hl
	ld	(mem_last_handle),hl

	ld	bc,1			; minimalen Speicherblock im Speicher anlegen.
	jr	mem_alloc		; => es ist immer ein Block in der Verwaltung.
					; -> Verwendung als Stopper zB. in mem_compact.



; --------------------------------------------------------
; Get total amount of ultimately available memory
; runs the garbage collection and 
; then returns the total amount of free ram
;
; return bc>0 & nz: the returned amount is > 0.
; return bc=0 & z:  no more ram available.
;
; in:	--
; out:	bc = free memory size (total)
;	f: nz: bc > 0
;	   z:  bc = 0
; mod:	af, bc

mem_get_free_total:	
	call	mem_compact
	;jr	mem_get_free
	


; --------------------------------------------------------
; Get amount of immediately available memory
; which will not trigger a garbage collection.
;
; return bc>0 & nz: the returned amount is > 0.
; return bc=0 & z:  no more ram immediately available.
;
; in:	--
; out:	bc = free memory size (immediately available)
;	f: nz: bc > 0
;	   z:  bc = 0
; mod:	f, bc

mem_get_free:
	push	hl
	push	de
	call	up_mem_get_free
	ld	bc,hl
	pop	de
	pop	hl
	ret



; --------------------------------------------------------
; UP:	return immediately free memory size in hl
;	preserve bc
;
; in:	--
; out:	hl = free memory size
;	f: nc
;	   nz: hl > 0
;	   z:  hl = 0
; mod:	f, de, hl

up_mem_get_free:
	ld	hl,(mem_free_end)
	ld	de,(mem_free_start)

	dec	hl		; -2 for size
	dec	hl		
	dec	hl		; -2 for handle
	scf			

	sbc	hl,de
	ret	nc		; z or nz 

	inc	h		; h = 0 & z
	ld	l,h		; hl = 0
	and	a		; z & nc
	ret			; z & nc

	

; --------------------------------------------------------
; Test whether BC bytes are available
; runs the garbage collection if required
;
; in:	bc = requested size
; out	f: nc: available
;	   c:  oomem
; mod:	af

mem_test_free_total:
	call	mem_test_free
	ret	nc		; passt ohne garbage collection
	call	mem_compact	
	;jr	mem_test_free

	

; --------------------------------------------------------
; Test whether BC bytes are immediately available
; and will not trigger a garbage collection.
;
; the maximum size for BC is mem_max_size
;
; in:	bc = requested size
; out	f: nc: available
;	   c:  oomem
; mod:	af

mem_test_free:

; check size:
	ld	a,mem_max_hi
	cp	b
	ret	c			; bc > $3FFF => error => cy => not available

	push	hl
	push	de
	
	call	up_mem_get_free		; -> nc, z/nz, hl >= 0
	;and	a
	sbc	hl,bc			; -> nc/cy
	
	pop	de
	pop	hl
	ret	
	


; --------------------------------------------------------
; Get data address from handle.
;
; If the passed handle is nil, 
; then the returned address is 0.
;
; in:	hl -> handle
; out:	hl -> data
; mod:	af, hl

mem_get_address:
	ld	a,h
	and	a
	ret	z		; nil -> address = 0

mem_get_address_quick:	
	ld	a,(hl)
	inc	hl
	ld	h,(hl)
	add	2
	ld	l,a
	ret	nc
	inc	h
	ret

	

; --------------------------------------------------------
; Get data size from handle.
;
; If the passed handle is nil, 
; then the returned size is 0.
;
; note: damit das z-flag stimmt, dürfen niemals 0-byte-chunks 
; angelegt werden. Für 0-Byte-Blöcke muss immer nil als Handle 
; zurückgegeben werden!
;
; in:	hl -> handle
; out:	bc = size
;	f: nz: bc>0
;	   z:  bc=0
; mod:	af, bc

mem_get_size:
	push	hl
	ld	a,(hl)
	inc	hl
	ld	h,(hl)
	ld	l,a
	ld	c,(hl)
	inc	hl
	ld	b,(hl)
	pop	hl		; handle

	ld	a,h
	and	a		; null handle?
	ret	nz		; nein

	ld	b,a
	ld	c,a		; handle = 0 => size = 0
	ret



; --------------------------------------------------------
; Allocate memory.
;
; triggers a garbage collection if requested size is not immediately available.
; jumps to oomem handler, if after garbage collection is still not enough memory free.
;
; the memory is not cleared
; the maximum size for BC is $3FFF
; if 0 bytes are requested, then a null pointer is returned for handle and data.
; 
; in:	bc = requested size
; out:	f: z:  bc=0 => hl=de=0
;	   nz: bc>0 => hl!=0, de!=0
;	hl -> handle
;	de -> data
;	bc = size (pres.)
; mod:	af, de, hl

mem_alloc:
	
; check size:
	ld	a,b
	cp	mem_max_hi
	jp	nc,abort_oomem		; bc > $3FFF
	or	c
	jr	z,ma_0			; bc = 0
			
; check free space:	
	call	up_mem_get_free		; -> hl >= 0
	xor	a			; nc & a=0
	sbc	hl,bc
	jp	c,abort_oomem

; find a free handle:
	ld	de,(mem_handles_start)
	dec	de
	ld	(de),a		; stopper.hi: finales handle löschen
	dec	de		; de -> stopper = mem_handles_start -2
	;ld	(de),a		; stopper.lo egal, wenn stopper.hi=0 => frei

	ld	hl,(mem_last_handle)

ma1	dec	hl		; hl -> prev_handle.hi
	cp	(hl)		
	dec	hl		; hl -> handle.lo
	jp	nz,ma1		; handle.hi != 0 => belegt
	
; free handle found: hl
	ld	(mem_last_handle),hl	
	;and	a
	sbc	hl,de	
	add	hl,de		; note: setzt kein z!!
	jr	nz,ma2
	ld	(mem_handles_start),hl	; new handle = stopper => update mem_handles_start
	
; allocate data
ma2	ld	de,(mem_data_end) ; de -> my_data.size
	ld	(hl),e		  ; store data address in handle
	inc	hl
	ld	(hl),d		
	dec	hl		; hl -> handle
	
	ex	hl,de		; hl -> data.size; de->handle
	ld	(hl),c		; store size in data.size
	inc	hl
	ld	(hl),b		
	inc	hl		; hl->data.data
	
	add	hl,bc		; hl->data.end
	ld	(mem_data_end),hl
	sbc	hl,bc		; hl->data.data
		
	ex	hl,de		; hl -> handle; de -> data
	ret  ;	nz

; return nil for a 0-byte-request

ma_0:	ld	hl,bc		; hl -> handle = 0
	ld	de,bc		; de -> data = 0
	ret  ;	z		; bc = 0
	


; --------------------------------------------------------
; Duplicate data and return new handle for it.
; 
; If nil is duplicated, then the result is nil as well.
;
; in:	hl -> handle
; out:	hl -> new handle
; mod:	af, hl

mem_dup:
	ld	a,h
	or	l
	ret	z			; copy of nil = nil
	
	push	de
	push	bc
	
	call	mem_get_size		; bc = size != 0
	call	mem_get_address		; hl -> source 
	push	hl			; sp: -> source
	call	mem_alloc		; hl -> handle; de -> dest buffer
	ex	hl,(sp)			; sp: -> handle; hl->source	
	ldir
	pop	hl			; hl -> new handle

	pop	bc
	pop	de
	ret



; ---------------------------------------
; Reserviere Speicher und speichere Daten darin
;
; in:	hl -> source data
;	bc =  data size
; out:	hl -> handle
;	de -> data
; mod:	af, de, hl

mem_save_data:
	push	hl			; sp: -> source
	
	call	mem_alloc		; -> hl = handle, de = ziel, bc=size 
	ex	hl,(sp)			; sp: -> handle; hl->source; de->ziel	
	jr	z,msd1			; save 0 bytes => LDIR would move 64k ...

	push	bc
	push	de
	ldir
	pop	de
	pop	bc

msd1	pop	hl			; hl = handle
	ret



; ------------------------------------------------------------
; Restore data from memory block
; All parameters are extracted from the data block.
; Finally the data block is deallocated.
;
; in:	hl -> handle
;	de -> dest.
; out:	--
; mod:	af

mem_restore_data:
	ld	a,h			; null handle -> data size = 0 -> nop
	and	a
	ret	z			; even dealloc is a nop...
	
	push	bc
	push	de
	push	hl

	call	mem_get_size		; bc = size
	call	mem_get_address		; hl -> source buffer
	
	ldir

	pop	hl
	pop	de
	pop	bc
	;jp	mem_dealloc



; --------------------------------------------------------
; Release handle
;
; If a nil pointer is released, 
; then the first 2 bytes of the Rom are "overwritten".
; only the high byte is cleared.
;
; in:	hl -> handle
; out:	--
; mod:	--

mem_dealloc:
	inc	hl
	ld	(hl),0		; handle.hi := 0
	dec	hl
	ret



; --------------------------------------------------------
; Release handle in DE
;
; in:	de -> handle
; out:	--
; mod:	--

mem_dealloc_de:
	ex	hl,de
	inc	hl
	ld	(hl),0		; handle.hi := 0
	dec	hl
	ex	hl,de
	ret



; --------------------------------------------------------
; Garbage Collection
;
; in der ersten Schleife über alle Handles wird in allen
; belegten data.size ein rptr auf das handle und in das handle 
; die länge aus data.size eingetragen.
;
; in der zweiten schleife über alle data chunks werden leere chunks,
; erkennbar daran, dass in ihr size-feld kein rptr eingetragen wurde,
; übersprungen. alle belegten blöcke, erkennbar daran, dass sie jetzt im size-feld 
; einen rptr auf ein handle enthalten, erkennbar daran, dass die blockgröße
; extrem groß ist, werden bündig nach vorne geschoben, in das size-feld 
; wieder die länge eingetragen und in das handle wieder ein zeiger auf die neue 
; position des blocks.
;
; in:	--
; out:	--
; mod:	af

mem_compact:
	push	hl
	push	de
	push	bc
	push	iy

; -----	Handles: -----
	
; handle-allocation-pointer zurücksetzen:
	ld	hl,(mem_handles_end)
	ld	(mem_last_handle),hl
	
; freie Handles am Anfang des Handles-Bereiches entfernen:
	ex	hl,de			; de = mem_handles_end
	ld	hl,(mem_handles_start)
	sub	a
	dec	hl			; -> before_first_handle.hi

mc0	inc	hl
	inc	hl
	cp	(hl)			; handle.hi
	jr	z,mc0			; der ist auch noch frei

	dec	hl			; handle.lo
	ld	(mem_handles_start),hl	; hl -> 1st used handle

; -----	Datenblocks -----

; Schleife über alle handles:

; in der ersten Schleife über alle Handles wird in allen
; belegten data.size ein rptr auf das handle und in das handle 
; die länge aus data.size eingetragen.

;	hl -> current handle
	ld	iy,(mem_handles_end)	; for loop end test

; loop 1 start:
; hole Längenangabe:
mc1	xor	a
mc11	ld	e,(hl)		
	inc	hl
	ld	d,(hl)		; de -> data.size
	inc	hl		; hl -> next handle
; handle frei? -> loop
	cp	d
	jr	z,mc1	; freies handle => end-of-loop test nicht nötig; finales handle aus init_mem ex. immer
	dec	hl
	dec	hl		; hl -> handle

; get data length BC from data.size (DE)
; store handle HL in data.size 
	ex	hl,de		; hl -> data.size.lo; de -> handle; bc=size (not yet)
	ld	c,(hl)
	ld	(hl),e
	inc	hl		; hl -> data.size.hi
	ld	b,(hl)		; bc = size
	ld	(hl),d

; speichere im handle die länge
	ex	hl,de		; hl -> handle
	ld	(hl),c
	inc	hl		; hl -> handle.hi
	ld	(hl),b
	inc	hl		; hl -> next handle
	
; loop end test:
mc1e	ld	a,yl		; mem_handles_end.lo
	cp	l
	jr	nz,mc1
	ld	a,yh		; mem_handles_end.hi
	cp	h
	jr	nz,mc1
	

; schleife über alle datenblöcke:	

; in der zweiten schleife über alle data chunks werden leere chunks,
; erkennbar daran, dass in ihrem size-feld kein rptr eingetragen wurde,
; übersprungen. alle belegten blöcke, erkennbar daran, dass sie jetzt im size-feld 
; einen rptr auf ein handle enthalten, erkennbar daran, dass die blockgröße
; > $3FFF ist, werden bündig nach vorne geschoben, in das size-feld 
; wieder die länge eingetragen und in das handle wieder ein zeiger auf die neue 
; position des blocks.

	ld	hl,(mem_data_start)	; hl -> old data
	ld	de,hl			; de -> new data
	ld	iy,(mem_data_end)	; for loop end test

; loop 2 start:
; get data.size:
mc2	ld	c,(hl)
	inc	hl
	ld	b,(hl)			; bc = size  or  ptr -> handle
	inc	hl			; hl -> old_data.data

; data.size < mem_max ? data.size = still the block size => this block is free
	ld	a,b
	cp	mem_max_hi
	jr	c,mc2ee			; => bc = size => free block => skip & loop

; block is in use:			; => bc -> handle
; => move block from hl to de 

; read bc = size from handle
; write de = new data address into handle
	push	hl			; sp: -> old_data.data
	ld	hl,bc			; hl -> handle.lo
	ld	c,(hl)	
	ld	(hl),e			
	inc	hl			; hl -> handle.hi
	ld	b,(hl)			; bc = size
	ld	(hl),d			; store de -> new_data.size
	pop	hl			; hl -> old_data.data

; write bc = size to new_data.size
	ex	hl,de			; hl -> new_data.size; de->old_data.data
	ld	(hl),c
	inc	hl
	ld	(hl),b			; new_data.size := size
	inc	hl			; hl -> new_data.data
	ex	hl,de			; de -> new_data.data; hl -> old_data.data; bc = size > 0

		; note: bc = size is guaranteed > 0 because we do not store 0-byte chunks
		; note: we also ldir the first chunks up to the first free chunk, though this is a nop.
		;       but test for hl==de and adding bc to hl and de instead of ldir adds too much 
		;       overhead to each loop.
	ldir				; bc=0; de->new_data.end; hl->old_data.end
	;jr	mc2e  ((add hl,bc=0 is a nop))
	
mc2ee	add	hl,bc			; skip old data for free block

; loop end test				; hl -> old data
					; de -> new data
mc2e	ld	a,yh	; mem_data_end.hi
	cp	h
	jr	nz,mc2
	ld	a,yl	; mem_data_end.lo
	cp	l
	jr	nz,mc2
	
; finished: update sysvar & exit
	ld	(mem_data_end),de

	pop	iy
	pop	bc
	pop	de
	pop	hl
	ret	



; ----------------------------------------------------
; Get address for index
;
; in:	hl = handle
;	de = index
; out:	hl = address
; mod:	af, hl

mem_get_address_for_index:
	call	mem_get_address
	add	hl,de
	ret


; ----------------------------------------------------
; Get index for address
;
; in:	hl = handle
;	de = address
; out:	de = index
; mod:	af, de

mem_get_address_for_index:
	push	hl
	call	mem_get_address
	ex	hl,de
	and	a
	sbc	hl,de
	pop	hl
	ret
	
	

; ----------------------------------------------------
; Data manipulation
;
; mem_cat	concatenate 2 memory blocks
; mem_shrink	shrink block size, left-aligned
; mem_rshrink	shrink block size, right-aligned
; mem_split	split block into two blocks
; mem_extract	extract subrange from block



; ------------------------------------------------
; validate position de
;
; in:	hl = position
;	bc = size
; out:	hl = adjusted:  [0..de..size]
; mod:	af, hl

up_validate_hl_and_de
	ex	hl,de
	call	up_validate_hl
	ex	hl,de
	
up_validate_hl
	bit	7,h
	jr	nz,vd1		; hl < 0

	and	a
	sbc	hl,bc		; cp hl,bc
	add	hl,bc
	ret	c		; hl<bc
	ld	hl,bc		; hl>=bc => hl:=bc
	ret
	
ss1	pop	hl
	pop	hl
	call	mem_dealloc
	
vd1	ld	hl,0
	ret



; ---------------------------------------------
; extract subrange from block
;
; the original block is preserved
;
; in:	hl = handle
;	de = start index
;	bc = end index+1
; out:	hl = new handle
; mod:	af, bc, de

up_dup_range:
	push	bc		; sp: end idx
	call	mem_get_size	; bc = old size
	call	mem_get_addr	; hl = old addr
	ex	hl,(sp)		; sp: old addr, hl=end idx, de=start idx, bc=old size

	call	up_validate_hl_and_de	; hl: end; de: start; bc=size

	and	a
	sbc	hl,de		; hl: end-start
	jr	c,ss1		; start < end => return null handle

; start and end checked.
; resulting string is > 0 bytes
;	sp: old handle
;	sp: old addr
;	de: start idx in old data
;	hl: new size

	ld	bc,hl		; bc = new size
	pop	hl		; hl = old data addr
	add	hl,de		; hl -> source
	push	hl		; sp: -> source; bc=size
	call	mem_alloc	; hl = new handle; de -> new data
	ex	sp,(hl)		; hl -> source, de -> dest, bc=len; sp:new handle
	ldir
	
	pop	hl		; new handle
	ret


; ---------------------------------------------
; shrink block to subrange of block
;
; in:	hl = handle
;	de = start index
;	bc = end index+1
; out:	hl = handle
; mod:	af, bc, de

up_sub_range:
	push	bc		; sp: end idx
	call	mem_get_size	; bc = old size
	call	mem_get_addr	; hl = old addr
	ex	hl,(sp)		; sp: old addr, hl=end idx, de=start idx, bc=old size

	call	up_validate_hl_and_de	; hl: end; de: start; bc=size

	and	a
	sbc	hl,de		; hl: end-start
	jr	c,ss1		; start < end => return null handle

; start and end checked.
; resulting string is > 0 bytes
;	sp: old handle
;	sp: old addr
;	de: start idx in old data
;	hl: new size

	ld	bc,hl		; bc = new size
	pop	hl		; hl = old data addr
	add	hl,de		; hl -> source
	push	hl		; sp: -> source; bc=size
	call	mem_alloc	; hl = new handle; de -> new data
	ex	sp,(hl)		; hl -> source, de -> dest, bc=len; sp:new handle
	ldir
	
	pop	hl		; new handle
	ret







; ----------------------------------------------------
; Split a memory block in two
;
; in:	hl -> handle 
;	de = split position (index)
; out:	hl -> handle1
;	de -> handle2
; mod:	af,de,hl

mem_split:
	bit	7,d
	jr	nz,ms1		; split position < 0
	call	mem_get_size	; bc=size
	ex	hl,de		; hl=size1; de=handle
	and	a
	sbc	hl,bc
	jr	nc,ms2		; split position >= block size
	add	hl,bc
	
	push	bc		; sp:size
	push	de		; sp:handle
	ld	bc,hl		; bc=size1
	call	mem_alloc	; hl:handle1; de:data1; bc:size1
	push	hl		; sp:handle1
	ldir			; 
	
	

	



; ----------------------------------------------------
; Concatenate two memory blocks
;
; the data from the 2nd block is appended to the first block.
; the two blocks are deallocated and the resulting block is returned.
;
; in:	hl -> handle 1
;	de -> handle 2
; out:	hl -> handle
; mod:	af,hl

mem_cat:
	sub	a	
	cp	d
	ret	z		; 2nd data block is empty
	ex	hl,de
	cp	d
	ret	z		; 1st data block is empty

	push	bc

	push	hl		; handle2
	push	de		; handle1

	push	hl		; handle2
	push	de		; handle1

	call	mem_get_size	; bc:len2
	ld	hl,bc
	ex	hl,de
	call	mem_get_size	; bc:len1
	add	hl,bc
	ld	bc,hl
	call	mem_alloc	; hl:handle3; de:data3; bc:len3

	ex	hl,(sp)		; hl:handle1
	call	mem_get_size	
	call	mem_get_address
	ldir
	
	pop	hl		; handle3
	ex	hl,(sp)		; hl:handle2
	call	mem_get_size	
	call	mem_get_address
	ldir
	
	pop	hl		; hl:handle3
	pop	de		; de:handle1
	call	mem_dealloc_de
	pop	de		: de:handle2
	pop	bc		; bc
	jp	mem_dealloc_de