from http://dblog.aldacron.net/download/freelist.d, fixed typo

Freelist.d

module freelist;
/*
    Copyright (c) 2006 Michael D. Parker
	Based upon an implementation described by Nathan Mefford in the Game Programming
	Gems 5 article, "Improving Freelists with Policy Based Design".
	
	This implementation is released into the public domain. I ask that you 
	please keep	this header intact, though of course you do not have to.
*/

/**
	A templated free list to help reduce GC collection time and increase
	access to frequently allocated/deallocated objects.
	
	Growth policies must implement two methods:
	
	uint initialCapacity()
	uint growSize()
	
	initialCapacity() should return the number of objects a free list should
	allocate space for on initialization. 
	
	growSize() should return the number of objects for which space should be 
	allocated when the free list needs to grow. If growSize returns 0, the free 
	list will not grow and will remain a fixed size.
	
	Allocation policies must somehow store the objects of the free list. The
	method of storage is implementation-dependent. Allocation policies must
	also allocate memory for new objects. The method of allocation is
	implementation-dependent. Allocation policies must implement these methods:
	
	T push()
	T pop()
	void grow(uint growSize)
	void clear()
	
	The push method should return an instance of type T. It can be a new instance
	or an existing instance. 
	
	The pop method should "return" an instance of T
	to the free list. The meaning of "return" is implementation-dependent. 
	
	The grow method should increase the amount of space available in the free list
	by growSize objects. This can mean a literal increase of memory (such as
	increasing the length of a dynamic array) or the increase of a maximum
	object counter (such as might be used with a linked list implementation).
	Either way, the allocation policy should never store more objects than the 
	total capacity "allocated" at any given time. If growSize is 0, the method 
	should be a no-op.
	
	The clear method removes all entries from the free list such that the free
	list is effectively empty. What this means exactly is implementation-dependent.
	It could mean setting a dynamic array length to 0, or removing all of the
	nodes from a linked list, or something else. Whatever the implementation,
	the state of the free list should be the same as it would be when the
	allocation policy is first instantiated.
*/
class FreeList(T, Growth, Allocation)
{
	private
	{
		// controls the growth of the free list
		Growth _growthPolicy;
		
		// controls the storage of and allocation of objects in the free list
		Allocation _allocationPolicy; 
	}
	
	/**
		Creates a new free list which uses the given growth and allocation policies.
		
		Params:
			growthPolicy		= The policy that will determine if, when and 
								  how this list grows.
			allocationPolicy	= The policy that will determine how objects are
								  stored and allocted in the free list.
	*/
	public this(Growth growthPolicy, Allocation allocationPolicy)
	{
		_growthPolicy = growthPolicy;
		_allocationPolicy = allocationPolicy;
		
		init();
	}

	/**
		Pulls an object from the free list and returns it.
		
		It is possible that a new object will be allocated. If that is the
		case, its default constructor will be called. If any objects
		require initialization after allocation, it should be handled manually.
		
		This free list's allocation policy will determine how the objects are
		allocated. The list's growth policy will determine what happens
		when the list is full. In some cases, the list may be of a fixed size,
		in which case the return value could possibly be null.

		Returns: 
			A new or recycled instance of T, or null if an new instance is not 
			free and/or could not be allocated.
	*/
	public T allocate()
	{
		T t = _allocationPolicy.pop();
		if(t is null)
		{
			uint growSize = _growthPolicy.growSize();
			if(growSize > 0)
			{
				_allocationPolicy.grow(growSize);
				t = _allocationPolicy.pop();
			}
		}
		return t;
	}
	
	/**
		Places an object bact in object to the free list.
		
		If the object has allocated any resources which need to be freed, it 
		should be done manually before calling this method.
	*/
	public void deallocate(T t)
	{
		_allocationPolicy.push(t);
	}
	
	/// Resets capacity of this free list to the initial capacity.
	public void reset()
	{
		_allocationPolicy.clear();
		init();
		
	}
	
	// Allocates the free list to the intial capacity if non-zero.
	private void init()
	{
		uint initialCapacity = _growthPolicy.initialCapacity;
		if(initialCapacity > 0)
		{
			_allocationPolicy.grow(initialCapacity);
		}
	}
}

//==============================================================================
// Basic Growth Policies

/**
	With this policy, a free list remains a fixed size and can never allocate 
	more objects than the initial capacity.
*/
class ZeroGrowthPolicy
{
	private
	{
		uint _capacity;
	}
		
	/**
		Constructs a new policy with the given capacity.
		
		Params:
			capacity		= The fixed number of objects the free list can hold.
	*/
	public this(uint capacity)
	{
		_capacity = capacity;
	}
	
	/// Returns: Returns the initial, and in this case final, capacity of the free list.
	uint initialCapacity()
	{
		return _capacity;
	}
	
	/// Returns: This implementation always returns zero.
	uint growSize()
	{
		return 0;
	}
}

/// With this growth policy, a free list grows by a constant amount.
class ConstantGrowthPolicy
{
	private
	{
		uint _initialCapacity;
		uint _growSize;
	}
	
	/// Constructs a new policy with a default initial capacity and grow size of 16.
	public this()
	{
		this(16);
	}
		
	/**
		Constructs a new policy with the given initial capacity and a default
		growth size equal to the initial capacity.
		
		Params:
			initialCapacity		= The size by which to preallocate the free list.
	*/
	public this(uint initialCapacity)
	{
		_initialCapacity = _growSize = initialCapacity;
	}
	
	/// Returns: The initial capacity of the free list.
	uint initialCapacity()
	{
		return _initialCapacity;
	}
	
	/// Returns: The size by which the free list should grow.
	uint growSize()
	{
		return 0;
	}
}

//==============================================================================
// Basic Allocation Policies

/**
	This allocation policy treats the free list as a stack and never allocates
	a new object if no free objects are available.
	
	A dynamic array is used to store the objects. The current stack top is
	tracked via a separate integer index which is incremented and decremented
	as needed when objects are pushed on to and popped off of the stack. This
	policy makes no attempt to allocate objects when there are no free objects
	available.
	
	When this policy is paired with a NoGrowthPolicy, you are guaranteed that
	calls to pop will return null if all available objects in the free list have
	been doled out. This pairing is a good fit for objects which need to be 
	allocated in large quantities, but have short life spans. Particles
	and decals are a good example of objects which cry out for such a free
	list.
	
	Teaming this policy with a capped ConstantGrowthPolicy, the allocator will 
	continue to return instances from pop until the stack grows to a fixed 	cap, 
	at which point null will be returned when the stack is empty. You might use
	this pair for objects which are allocated infrequently, but constantly
	over the life of the application and you don't want the total going beyond
	a certain threshold. One possible use case for such a combination could be
	with buildings in a god game.
	
	Couple this policy with an uncapped ConstantGrowthPolicy and you get an
	allocator limited only by the available system resources. I think most
	of the time you would most likely be better off with one of the other
	policy combos, but it's your game!	
*/
class SimpleStackAllocationPolicy(T)
{
	protected
	{
		// the top of the stack, starting from zero.
		int _top;
		
		// the stack of free objects
		T[] _stack;
	}
	
	/// Constructs a new SimpleStackAllocationPolicy
	public this() {}
	
	/**
		Grows the capacity of the stack by the given amount.
		
		Params:
			growSize		= The amount by which to grow the stack.
	*/
	public void grow(uint growSize)
	{
		_stack.length = _stack.length + growSize;
	}
	
	/**
		Pops the next free object off the top of the stack.
		
		If no free objects are available, this implementation returns null.
		
		Returns: 
			An instance of T.
	*/
	public T pop()
	in
	{
		assert(_stack.length != 0, "Zero-length stack");
	}
	body
	{
		// if no free objects are available, return null
		if(stack.length == _top)
		{
			return onEmptyStackPop();
		}
		
		// grab the object at the top of the stack
		T t = _stack[_top];
		
		// if it's null, then this is the first access at the current index
		if(t is null)
		{
			// allocate a new object at the current stack position and assing it to t
			_stack[_top] = new T();
			t = _stack[_top];
		}
		
		// increment the stack index
		++_top;
		
		// return the object
		return t;
	}
	
	/**
		Pushes an object back on to the top of the stack.		
		
		If the free list is full, this method throws an Error.
		
		Params:
			t				= An object previously retrieved via policy's  pop()
							  method.
	*/
	public void push(T t)
	in
	{
		assert(t !is null, "Returning a null object to a free list");
		assert(_stack.length != 0, "Zero-length stack");
	}
	body
	{	
		// it is an error to return an object when the list is full
		if(0 == _top)
		{
			onFullStackPush();
			return;
		}
		
		// decrement the stack index
		--_top;
		
		// put the object back in the stack
		_stack[_top] = t;
	}
	
	/// This implementation removes all elements from the internal stack.
	void clear()
	{
		_stack.length = 0;
	}
	
	/**
		Called by pop when the stack is empty.
		
		Returns: The default implementation returns null always.
	*/
	protected T onEmptyStackPop()
	{
		return null;
	}
	
	/**
		Called by push when the stack is full.
		
		The default implementation throws an error.
		
		Params:
			t				= An object which could not be pushed on to the stack
							  because the stack was full.
	*/
	protected void onFullStackPush()
	{
		throw new Error("Attempted to return an object to a full free list.");
	}	
}

/**
	This allocation policy will always allocate a new object, even when the free 
	list has no free objects available.
	
	When a free list pops an object from this policy, a new instance will always
	be returned even if the stack is empty. When objects are returned to
	the stack via the push method but the stack is full, this policy will
	either delete the object immediately or ignore it and let the GC reclaim it
	later. Either way, it does not throw an error like its super class.
	
	This policy and the NoGrowthPolicy are good partners in cases where you
	have frequent, long-lived allocations, but the peak number of active objects 
	rarely goes beyond a certain threshold. In a shmup game, you may have a
	variable number of enemies on each level. You can use the same free list
	for each level, but set it to a common-denominator. Only the levels
	that need more enemies will go beyond that capacity.
	
	With a ConstantGrowthPolicy which is capped you get essentially the
	same behavior as when you couple this with a NoGrowthPolicy. The difference
	is that you can start out with a small capacity and grow it to the maximum
	rather than starting out at maximum capacity. In some situations, this
	may be more efficient. Units in a strategy game make a perfect use case for
	this combination.
	
	Combining this policy with an uncapped ConstantGrowthPolicy results in the
	same behavior as SimpleStackAllocationPolicy with a ConstantGrowthPolicy, 
	since the list will never be empty. The only difference bewtweeen them is
	in how the push method reacts when the stack is full. In that case, it might
	be safer to use the SimpleStackAllocation in place of this so that an
	error can be thrown if any attempt is made to push an object on to a full
	stack.	
*/
class AlwaysAllocStackAllocationPolicy(T) : SimpleStackAllocationPolicy!(T)
{
	private
	{
		bool _deleteExtra;
	}
	/// Constructs a new AlwaysAllocStackAllocationPolicy which deletes extra objects
	public this() 
	{
		this(true);
	}
	
	/**
		Constructs a new AlwaysAllocStackAllocationPolicy which either deletes
		extra objects or ignores them.
		
		Params:
			deleteExtra		= If true, the onFullStackPush method will immediately
							  delete every object passed to it. When false, the
							  onFullStackPush method will ignore every object
							  passed to it.
	*/
	public this(bool deleteExtra)
	{
		_deleteExtra = deleteExtra;
	}
	
	/**
		Called by pop when the stack is empty.
		
		Returns: 
			A new instance of T.
	*/
	protected T onEmptyStackPop()
	{
		return new T();
	}
	
	/**
		Called by push when the stack is full.
		
		This implementation has two behaviors. If configured to delete extra
		objects, the given object will be deleted immediately. If not, the given
		object will be ignored and the GC will reclaim it at a later date if
		there are no other references to it out in the application. Either
		behavior could negatively impact the application if any references
		to the object are held outside of the policy.
		
		Params:
			t				= An object which could not be pushed on to the stack
							  because the stack was full.
	*/
	protected void onFullStackPush(T t)
	{
		if(_deleteExtra)
		{
			delete t;
		}
	}	
}