Re: memory pool algorithms

On Thu, Apr 23, 2009 at 01:05:39PM +0100, [email protected] wrote:
> 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.

Could you define "retrieve by index" further?  Do you mean that if "n"
elements are allocated they must be reachable by a number with 0 and
n-1?  If yes, you obviously can't have constant-time deletion, since
you'll have a mean of n/2 references to change for every deletion.
And if you allow holes to get constant-time deletion, what properties
do you want from your index that a pointer would not have?

  OG.


------------------------------------------------------------------------------
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