Re: [Algorithms] memory pool algorithms

[Simon F. <sim...@po...>]

Pau...@sc... wrote:
> -----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.

Are you after *something* like "An efficient Representation for Sparse
Sets"? (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.7319)

AFFAIR it requires unique indices and I think the iteration might be in
"random" order, but maybe it can be tweaked.


Simon
-- 
___________________________________________________________________
Simon Fenney                              Principal Design Engineer
PowerVR Technologies     A Division of Imagination Technologies Ltd
Home Park Estate, Kings Langley, WD4 8LZ, UK     ph:+44 1923 260511
mailto:sim...@po...              http://www.powervr.com
___________________________________________________________________ 

"Your work is both good and original. Unfortunately the part that 
is good is not original and the part that is original is not good." 
- Samuel Johnson

"Plurality should not be assumed unnecessarily" - William of Occam,
Quodlibeta (c1324)