Re: [Algorithms] memory pool algorithms

[Niklas F. <ni...@gr...>]

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?

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