[TI ASM] Good yet uncomplicated memory allocator?

[King Harold]

It can be, in that case no new block will be allocated in between them
Otherwise there may - if the gap is big enough

[Timendus]

Ah, I see.. Perhaps you could post your code as well? See if I can perhaps improve mine with your data structure?

I'll be gone for a few weeks, by the way. I know I've hardly been on this forum lately, but I thought I should let you know

[King Harold]

It's not really optimized or anything.. in fact, it may not even work (only done some basic tests)
Also, all addresses are hardcoded.. but have a look

Code: Select all

.module mem
;
;
; .dw size, .dw next, .dw prev, [data bytes], [free space], .dw size, .dw next, .dw prev etc
;
;
;
;
init:
	;front guard
	ld hl,0
	ld ($C008),hl
	ld ($C00C),hl
	ld hl,$F400-6
	ld ($C00A),hl
	;
	
	;end guard
	ld hl,0
	ld ($F400-6),hl
	ld ($F400-4),hl
	ld hl,$C008
	ld ($F400-2),hl
	;
	
	ret
realloc:
	;Input: HL -> block to realloc
	;	 BC = new size
	ld de,-5
	add hl,de
	ld a,(hl)
	dec hl
	cp b
	jr c,{+}	;grow
	jr nz,{++}	;shrink
	ld a,(hl)
	cp c
	jr c,{+}	;grow
	jr nz,{++}	;shrink
	ret	;same size as first
	
	;hl -> .dw size
+:	;grow
	
	;first test if it can grow in-place
	inc hl
	inc hl
	ld e,(hl)
	inc hl
	push hl
	ld d,(hl)
	inc hl
	ex de,hl
	scf
	sbc hl,de
	;hl = sizeof([data bytes] + [free space])
	or a
	sbc hl,bc
	jr c,{+}	;no fit
	; fits inplace
	pop hl
	dec hl
	dec hl
	ld (hl),c
	dec hl
	ld (hl),b
	ld de,5
	add hl,de
	ret
+:	push bc
	call alloc
	pop bc
	pop de
	ret c
	inc de
	inc de
	inc de
	push de
	ldir
	pop hl
	call free
	ret
++:	;shrink
	;allways in-place of course
	;hl -> .dw size
	;bc = new size
	ld (hl),c
	inc hl
	ld (hl),b
	ld de,5
	add hl,de
	ret
	
	
	
free:
	;Input: HL -> block to free
	ld a,h
	or l
	ret z
	dec hl
	ld d,(hl)
	dec hl
	ld e,(hl)
	dec hl
	ld b,(hl)
	dec hl
	ld c,(hl)
	ex de,hl
	inc hl
	inc hl
	ld (hl),e
	inc hl
	ld (hl),d
	ret


_err1:
	pop hl
	ret
alloc:
	;Input: BC = length
	;Output: C -> Error
	;	 NC, HL = pointer to block, no error
	ld a,b
	or c
	ret z
	ld hl,6
	add hl,bc
	ld ($C002),hl
	ld hl,$C008
	ld de,($C00A)
	
-:
	;hl -> prev
	;de -> next
	push hl
	push de
	ld c,(hl)
	inc hl
	ld b,(hl)
	inc hl
	inc hl
	ex de,hl
	scf
	sbc hl,de
	;hl = sizeof(data bytes + empty space) + 2
	scf
	sbc hl,bc
	;hl = sizeof(empty space) + 1
	ld bc,($C002)
	scf
	sbc hl,bc	;sizeof(empty space) - reqsize
	pop de
	pop hl
	jr nc,{+}
	push de
	ex de,hl
	inc hl
	inc hl
	ld e,(hl)
	inc hl
	ld d,(hl)
	ld a,e
	or d
	jr z,{++}
	pop hl
	jr {-}
+:	
	;place found
	;hl -> prev
	;de -> next
	push hl
	ld c,(hl)
	inc hl
	ld b,(hl)
	add hl,bc
	ld bc,5
	add hl,bc
	;hl -> node
	push hl
	ld bc,-6
	ld hl,($C002)
	add hl,bc
	ld b,h
	ld c,l
	pop hl
	push hl
	ld (hl),c
	inc hl
	ld (hl),b
	inc hl
	ld (hl),e
	inc hl
	ld (hl),d
	inc hl
	pop bc
	pop de
	ld (hl),e
	inc hl
	ld (hl),d
	inc hl
	ex de,hl
	inc hl
	inc hl
	ld (hl),c
	inc hl
	ld (hl),b
	ex de,hl
	or a
	ret
++:	;error, no space
	pop hl
	scf
	ret
	
	
.endmodule

[King Harold]

I guess I'll explain it a bit..
Usually a free-list is used, which has the benefit of keeping most overhead in ram that is not used anyway.
The downside of that, is that you must avoid getting a free block of less than the space it takes to add it to the list at all cost, or have an alternative way to store very small blocks - otherwise those bytes will be leaked and will be hard to find again (finding them would require scanning the entire heap and in some implementations may even be impossible)
I just described the opposite of the memory manager I posted - because that one keeps a list of blocks that are in use. No matter how big or small a block is, if you free it - the bytes are back and ready to be used. Of course, if somehow you manage to get a gap of less than 6 bytes it can not be used, but it will be known they are free (because they are not in use and there is nothing in between) so they can be used when some neighbouring bytes are also freed.
That way, bytes that are freed are always freed without needing a separate list for very small pieces.
There are of course also downsides:
A front and an end guard are needed (so the heap is fixed size unless you mess with the end guard)
It takes 6 bytes of overhead per allocated block

note: it was about 4 am when I posted this, so the post is probably filled with nonsense, bad grammar, lies and spelling mistakes. It's not intentional..

[Timendus]

I see what you did now... I find it hard to compare the two approaches to determine which one would be better...

I think I'll stick to my implementation for now, for the sake of simplicity and the fact that it is more extensively documented. But I'll keep an eye on yours in case my use case gets more complex.