Re: [Algorithms] memory pool algorithms

[<Pau...@sc...>]

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

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

Thanks Jeremiah, thats excellent :) No linked lists, constant time 
alloc/dealloc, element look up by index and its iterable (if there is such 
a word). I guess the only thing is the order of elements as you iterate 
through changes each time you dealloc, but thats unavoidable...

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

wsBVAwUBSfCQk3ajGqjtoMHxAQjk/QgAqBwe74v42L2XJJQeDgSNQVEb2gpiiD4C
rr/0OOE4yMnUuSWfJXfjSDMq0Q9uoqProyJKrB7oLkc8CDrQ02Qc605a53uKab2p
IbJQthcxSOvcbn7SsEgH8nu/zEyD/0TbhZRLa4ZwBM/W50tm2Q6z0zhRpLLApx59
OJ39xtu1fkuzIoz1+fRnijNN1U7c6z/1re6x4eUZAKQLI9SavKqehmt0yzZqr7s7
o8kwtF2R/VzkWjaqilgbecBwbA4GO2ZjL417Qq3Obmr51l0G5WKLOfQZG7lfFAms
QV/DL0g+wJ9t7fogopnUQhSW6cSFpCACzQSpIx8T/cyKa8qMIh+BJQ==
=AxZj
-----END PGP SIGNATURE-----