It can be, in that case no new block will be allocated in between them
Otherwise there may - if the gap is big enough
[TI ASM] Good yet uncomplicated memory allocator?
Moderator: MaxCoderz Staff
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
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
http://clap.timendus.com/ - The Calculator Link Alternative Protocol
http://api.timendus.com/ - Make your life easier, leave the coding to the API
http://vera.timendus.com/ - The calc lover's OS
http://api.timendus.com/ - Make your life easier, leave the coding to the API
http://vera.timendus.com/ - The calc lover's OS
-
- Calc King
- Posts: 1513
- Joined: Sat 05 Aug, 2006 7:22 am
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
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
-
- Calc King
- Posts: 1513
- Joined: Sat 05 Aug, 2006 7:22 am
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..
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..
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.
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.
http://clap.timendus.com/ - The Calculator Link Alternative Protocol
http://api.timendus.com/ - Make your life easier, leave the coding to the API
http://vera.timendus.com/ - The calc lover's OS
http://api.timendus.com/ - Make your life easier, leave the coding to the API
http://vera.timendus.com/ - The calc lover's OS