Re: [Algorithms] memory pool algorithms

[Alen L. <ale...@cr...>]

Depends on what you call a pool, but if you use a linear part of
memory for a pool, I believe you can use a two-way mapping between
addresses (with holes) and indices (without holes) to burn some extra
memory up front and gain O(1) in return: (warning, untested code!)

- n - max size
- P[n] - pool of preallocated elements
- I2A[n] - array of index to address mappings
- A2I[n] - array of address to index mappings
- F[n] - array of free addresses
- cf - count of free indices
- c - current allocated count

initialize:
  fill F with 0..n-1 (or reverse, if you prefer)
  cf = n
  c = 0

allocate:
  a = F[--cf]
  I2A[c] = a
  A2I[a] = c++
  return a

freebyaddress(a)
  F[cf++] = a
  i = A2I[a]
  I2A[i] = I2A[--c]

// iteration...
for(i=0;i<c;i++) {
  whatever(P[I2A[i]])
}

NOTE: address of an element is constant through its lifetime (between
alloc and free), while index can change.

There are probably some errors by one above, but I hope the idea makes sense.
:)

HTH,
Alen

Paul wrote at 4/23/2009:

> -----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 pos...@sc...
> 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
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list



-- 
Alen