Re: memory pool algorithms

[email protected] 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?

Something like this perhaps. Constant time allocation, deallocation, 
retrieval and cache-friendly iteration with no holes. Code sketch in ruby:

(Note: Written for clarity rather than completely optimized. In an 
optimized version the freelist would be stored in-place in the @indices 
array, for instance.)

class IDArray
	def initialize
		@objects = []
		@ids = []
		@indices = []
		@freelist = []
	end

	def insert(o)
		i = @objects.size
		if @freelist.empty?
			id = @indices.size
		else
			id = @freelist.pop
		end
		@objects.push(o)
		@ids.push(id)
		@indices[id] = i
		return id
	end
		
	def lookup(id)
		return @objects[@indices[id]]
	end
		
	def remove(id)
		i = @indices[id]
		@objects[i] = @objects.last
		@ids[i] = @ids.last
		@objects.pop
		@ids.pop
		@indices[@ids[i]] = i
		@indices[id] = nil
		@freelist.push(id)
	end
		
	def each()
		@objects.each {|o| yield o}
	end
end

// Niklas



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