Pooled memory allocation

Got a brilliant program idea? Let us know!

Moderator: MaxCoderz Staff

Post Reply
User avatar
driesguldolf
Extreme Poster
Posts: 395
Joined: Thu 17 May, 2007 4:49 pm
Location: $4080
Contact:

Pooled memory allocation

Post by driesguldolf »

Long time no see :D

I made some macros (which will inline the code since it's so small) to handle allocation in pooled memory and I thought I'd share it.

Code: Select all

; Lib project
; Copyright (C) 2009, Cryzbl
; 
; File pool.inc
; Easily create pooled memory
; 
; This program is free software: you can redistribute it and/or modify
; it under the terms of the GNU General Public License as published by
; the Free Software Foundation, either version 3 of the License, or
; (at your option) any later version.
;
; This program is distributed in the hope that it will be useful,
; but WITHOUT ANY WARRANTY; without even the implied warranty of
; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
; GNU General Public License for more details.
; 
; You should have received a copy of the GNU General Public License
; along with this program. If not, see <http://www.gnu.org/licenses/>.

#ifndef _POOL_INC
#define _POOL_INC

#include "lib/macros.inc"

;; ==== POOL_INIT ====
;; Initializes the pool, number of elements known at runtime
;; pre:
;;  bc = number of elements to store, has to be larger then 2
;; post:
;;  Pool is initialized
INLINE      POOL_INIT(base, elem)
INLINE_PRE      ld hl, base+2
INLINE_PRE      ld (base), hl   ; Initialize firstfree pointer
INLINE_PRE      MOV_DE_HL
INLINE_PRE      dec bc          ; We manually initialize the last element 
INLINE_PRE      LOOPBC_INIT
INLINE_PRE  _loop:
INLINE_PRE      ld a, elem
INLINE_PRE      ADD_DE_A
INLINE_PRE      MOV_IHL_DE      ; Write ptr to current element
INLINE_PRE      MOV_HL_DE       ; Advance to next element
INLINE_PRE      LOOPBC(_loop)
INLINE_PRE      MOV_IHL_BC      ; Zero the last element to signal end of pool
INLINE_END

;; ==== POOL_INIT ====
;; Initializes the pool, number of elements known at assemble time
;; post:
;;  Pool is initialized
INLINE      POOL_INIT(base, elem, total)
INLINE_PRE      ld hl, base+2
INLINE_PRE      ld (base), hl   ; Initialize firstfree pointer
INLINE_PRE      MOV_DE_HL
INLINE_PRE      LOOPBC_INIT(total-1)
INLINE_PRE  _loop:
INLINE_PRE      ld a, elem
INLINE_PRE      ADD_DE_A
INLINE_PRE      MOV_IHL_DE      ; Write ptr to current element
INLINE_PRE      MOV_HL_DE       ; Advance to next element
INLINE_PRE      LOOPBC(_loop)
INLINE_PRE      ld (base+2+((total-1)*elem)), bc
INLINE_END

;; ==== POOL_ALLOC_SAFE ====
;; Allocates a resource in the pool, checks if there's enough memory
;; post:
;;  carry = set means fail, reset means successful
;;  hl = if successful this points to the allocated data
;;  Destroys af, bc
INLINE      POOL_ALLOC_SAFE(base)
INLINE_PRE      ld hl, (base)   ; Ptr to firstfree
INLINE_PRE      OR_HL           ; Zero indicates end of pool
INLINE_PRE      scf
INLINE_PRE      jr z, _done
INLINE_PRE      MOV_DE_IHL
INLINE_PRE      dec hl
INLINE_PRE      ld (base), de   ; Store next element from the free list in firstfree
INLINE_PRE      ccf
INLINE_PRE  _done:
INLINE_END

;; ==== POOL_ALLOC ====
;; Allocates a resource in the pool, does not check if there is enough memory
;; post:
;;  hl = if successful this points to the allocated data
;;  Destroys bc
INLINE      POOL_ALLOC(base)
INLINE_PRE      ld hl, (base)   ; Ptr to firstfree
INLINE_PRE      MOV_DE_IHL
INLINE_PRE      dec hl
INLINE_PRE      ld (base), de   ; Store next element from the free list in firstfree
INLINE_END

;; ==== POOL_FREE ====
;; Frees allocated data from a pool
;; pre:
;;  hl = pointer to allocated data
;; post:
;;  Data deallocated
;;  Destroys de
INLINE      POOL_FREE(base)
INLINE_PRE      ld de, (base)   ; Ptr to firstfree
INLINE_PRE      MOV_IHL_DE      ; Make the current element point to the firstfree element
INLINE_PRE      dec hl
INLINE_PRE      ld (base), hl   ; Make current element the firstfree
INLINE_END

#endif

; -----------------------------
; End of file
; -----------------------------
For the macros used refer to this file:
http://paste.krus.dk/index.php?id=825252018

Example usage would be

Code: Select all

    POOL_INIT(mypool, 4, 50) ; NEVER MAKE A POOL WITH ELEMENT SIZE 1.
    ; We created a pool for 50 elements of each 4 bytes in size. Total size required is 2+4*50 = 202
    ; Now we can allocate stuff in it
    POOL_ALLOC(mypool)
    ; hl now points to a 4 byte resource, do whatever you want
    push hl
    ; Let's alloc some more
    POOL_ALLOC(mypool)
    POOL_ALLOC(mypool)
    ; It's a bad idea to delete the handles but this is just an example, so let's just ignore them
    pop hl
    ; Now we free the first resource we allocated.
    POOL_FREE(mypool)
    ret
mypool:
.fill 202, 0; 202 bytes filled with zeros
User avatar
driesguldolf
Extreme Poster
Posts: 395
Joined: Thu 17 May, 2007 4:49 pm
Location: $4080
Contact:

Re: Pooled memory allocation

Post by driesguldolf »

So eh, no comments?
King Harold
Calc King
Posts: 1513
Joined: Sat 05 Aug, 2006 7:22 am

Re: Pooled memory allocation

Post by King Harold »

So... no explanation? Like, what makes it better than other memory management things?
We're probably supposed to understand it all just by looking at it, but I'm not feeling so pro at the moment :)
User avatar
driesguldolf
Extreme Poster
Posts: 395
Joined: Thu 17 May, 2007 4:49 pm
Location: $4080
Contact:

Re: Pooled memory allocation

Post by driesguldolf »

I assumed everyone knows what pooled memory allocation is :P
( if you don't, it means that you can dynamically allocate any resource, however each resource has to have the same fixed size which is decided upon initialization: wiki)

Afaik there isn't any sort of easy to use dynamic memory allocation released (or I can't find it) so I made one and posted it :P


It works pretty simple:
The initialization routine creates a single linked list of pointers (hence the minimum size is 2 bytes per block) to indicate all free blocks. When memory is allocated it simply pops the head of the free list. To free memory it pushes the block you no longer use onto the free list.

All the macro's I used was meant to allow the same file to be compiled under different assemblers :P

Here's what the init routine would look like without all the macros

Code: Select all

;; ==== POOL_INIT ====
;; Initializes the pool, number of elements known at runtime
;; pre:
;;  bc = number of elements to store, has to be larger then 2
;; post:
;;  Pool is initialized
#macro      POOL_INIT(base, elem)
	ld hl, base+2
	ld (base), hl   ; Initialize firstfree pointer
	ld d, h
	ld e, l
	dec bc          ; We manually initialize the last element
	dec bc
	ld a, c
	ld c, b
	ld b, a
	inc b
	inc c
_loop:
	ld a, elem
	add a, e
	ld e, a
	adc a, d
	sub e
	ld d, a
	ld (hl), e	; Write ptr to current element
	inc hl
	ld (hl), d
	ld h, d		; Advance to next element
	ld l, e
	djnz _loop
	dec c
	jr nz, lbl
	ld (hl), c	; Zero the last element to signal end of pool
	inc hl
	ld (hl), b
#endmacro
I do believe the macros make things a WHOLE lot more easier to understand.
Post Reply