Re: memory pool algorithms

I think this will work:

Have a allocated/free list that is an array of indices into the memory
pool array.  The allocated/free list is divided such that the 0 through
(M - 1) elements are allocated and the M through (N - 1) elements are
free; just use an index to the start of the free elements.  The
allocated/free list is initialized with 0 through (N - 1) and the start
of the free list is index 0. When you allocate, increment the start of
the free list index, when you free an element, decrement the index and
swap the two elements.  To iterate over the allocated elements, iterate
over the 0 through (M - 1) indices, and use the index to look up the
object.  The problem with this is that you jump around memory when
iterating.  If you are concerned with thrashing the cache, it would be
better to just go through the array and skip empty elements.

-----Original Message-----
From: [email protected] [mailto:[email protected]] 
Sent: Thursday, April 23, 2009 7:06 AM
To: [email protected]
Subject: [Algorithms] memory pool algorithms

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

Hi Guys,

I was just wondering if anyone knew of an algorithm/method which 
facilitated simple memory pool allocation of a single type but with 
constant time allocation/deallocation/item retrieval by index and also 
provided a 'nice' way to iterate through the used elements?

We have a class which gives us everything but the last two together. We 
can add a linked list of used elements (giving us the iteration) but
then 
you can't retrieve by index in constant time. Or we can retrieve by
index 
in constant time but then you can't iterate cleanly because there will
be 
holes in the memory pool.

Cheers, Paul.
**********************************************************************
This email and any files transmitted with it are confidential and
intended 
solely for the use of the individual or entity to whom they are
addressed. 
If you have received this email in error please notify
[email protected]
This footnote also confirms that this email message has been checked for

all known viruses.
Sony Computer Entertainment Europe Limited
Registered Office: 10 Great Marlborough Street, London W1F 7LP, United 
Kingdom
Registered in England: 3277793
**********************************************************************
P Please consider the environment before printing this e-mail

-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 2.9.1 (Build 287)
Charset: US-ASCII

wsBVAwUBSfBYiXajGqjtoMHxAQjWewf+IQzmRj6+gox+qbzxG7tZ+AktKgCTDC+N
11Wgf8Pjo7szCdWTa3fk00T9mbNmNAtfuyFlo6tFUC310ggVETI7uItg1Enjy7/H
6unAfH1Nt14yUBI3bNZjOENXiB3ypP7EEY1wnFtSLeOTugNjUS8/xEyngv0JSiqV
KXwg85XYpvJK5UoR4IrW3obyvaDJ+rWArRNAb167xCH80KlrrXFleVDLgPrjGRmJ
vO202p2FNCNB6BsmuEK0LHWxG1n/A7sJKHlvPF32Ow5ADoMo2MxuzN7bos5hw3Yy
CVrTKImbAP6Y3wf/vIE9HYUlZW9lwWctGOVziOLXQRAMSHkPwyNxbQ==
=8a/D
-----END PGP SIGNATURE-----

------------------------------------------------------------------------
------
Stay on top of everything new and different, both inside and 
around Java (TM) technology - register by April 22, and save
$200 on the JavaOne (SM) conference, June 2-5, 2009, San Francisco.
300 plus technical and hands-on sessions. Register today. 
Use priority code J9JMT32. http://p.sf.net/sfu/p
_______________________________________________
GDAlgorithms-list mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-lis
t

------------------------------------------------------------------------------
Stay on top of everything new and different, both inside and 
around Java (TM) technology - register by April 22, and save
$200 on the JavaOne (SM) conference, June 2-5, 2009, San Francisco.
300 plus technical and hands-on sessions. Register today. 
Use priority code J9JMT32. http://p.sf.net/sfu/p
_______________________________________________
GDAlgorithms-list mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list