libsst/Include/ZUtil/ZSlabAllocator.hpp

/*
	ZSlabAllocator.hpp
	Author: James Russell <jcrussell@762studios.com>
	Created: 9/12/2011

	Purpose: 

	Used to pre-allocate a large pool of objects whose size is fixed.  These objects can 
	then be allocated and deallocated as needed, which will return a pointer to an already
	allocated member.

	Will correctly handle allocation of more objects than is allocated at compile time, but
	performance will be impacted as another slab of equivalent size to the original is
	allocated.

	This is not a multithreaded access allocator.  The user of this is required to provide
	their own thread safety mechanisms.
	
	License:

	TODO
*/

#pragma once

#ifndef _ZSLABALLOCATOR_H
#define _ZSLABALLOCATOR_H

#include <ZUtil/ZUtilBuild.hpp>
#include <ZUtil/ZAlloc.hpp>
#include <ZUtil/ZAssert.hpp>
#include <ZUtil/ZLog.hpp>

/*
Slab Allocator, which holds a contiguous array of objects and leases them out for use.

The template parameter T is the type of object to hold.

The template parameter N is the size of the slab (how many objects to allocate statically).
*/
template <typename T, size_t N>
class ZSlabAllocator
{
private:
	DISABLE_COPY_AND_ASSIGN(ZSlabAllocator);

protected:

	/*
	Allocated slab of objects, that links to the next
	slab of objects.
	*/
	class Slab
	{
		private:
			T		Pool[N];			//The object pool
			T*		Handles[N];			//Handles to objects in the object pool
			size_t	HandleIndex;		//Handle index to the next available handle
			Slab*	NextPool;			//Next pool

		public:
			Slab() :
			HandleIndex(0), NextPool(NULL)
			{
				//Populate our handles pool
				for (size_t i = 0; i < N; i++)
					Handles[i] = &(Pool[i]);
			}

			//Used to verify that a handle belongs to the pool of objects
			bool IsPoolMember(T* _handle)
			{
				uintptr_t handle	= (uintptr_t) _handle;
				uintptr_t poolLower	= (uintptr_t) &Pool[0];
				uintptr_t poolUpper = (uintptr_t) &Pool[N - 1];

				if ((handle >= poolLower) && (handle <= poolUpper))	//Checks to see if handle is within the range of the pool
					if (((handle - poolLower) % sizeof(T)) == 0)	//Checks to see if handle is aligned on an object in the pool
						return true;

				return false;
			}

			T* Allocate()
			{
				T* object = NULL;

				if (HandleIndex < N)
				{
					//Grab an object from the object pool
					object = Handles[HandleIndex++];
				}
				return object;
			}

			void Deallocate(T* object)
			{
				Handles[--HandleIndex] = object;
			}
			
			Slab* GetNextPool()			{ return NextPool; }
			void SetNextPool(Slab* p)	{ NextPool = p; }

	};

	//ZSlabAllocator members
	Slab	FirstPool;
	size_t	NrAllocated;
	size_t	NrSlabs;

public:
	/*
	Default Constructor.
	*/
	ZSlabAllocator() :
	  NrAllocated(0), NrSlabs(1)
	{
	}

	/*
	Destructor.
	*/
	~ZSlabAllocator()
	{
		Slab* slab = FirstPool.GetNextPool();
		
		while(slab)
		{
			Slab* next = slab->GetNextPool();

			zdelete slab;
			slab = next;
		}
	}
	
	/*
	public ZSlabAllocator<T,N>::Allocate

	Gets a valid object of type T and returns a pointer.

	@return (T*) - a valid object pointer of type T
	*/
	T* Allocate()
	{
		T* object = NULL;

		Slab* slab = &FirstPool; //Begin with first pool

		while(object == NULL)
		{
			//Any objects left in this pool?
			object = slab->Allocate();
			if(object == NULL)
			{
				//Doh, try next pool
				Slab* next = slab->GetNextPool();

				//Unless there is no next pool...
				if(next == NULL)
				{
					//Try to allocate another one
					Slab* newPool = znew Slab;
					if(newPool == NULL)
						return NULL; //Doh, out of memory. :(
					else
						NrSlabs++;

					//Save this pool
					slab->SetNextPool(newPool);
					next = newPool;
				}

				//Try next pool
				slab = next;
			}
			else
				NrAllocated++;
		}
		
		return object;
	}

	/*
	public ZSlabAllocator<T,N>::Capacity

	Gets the size of the object pool.  Returns the total capacity of the pool.

	@return (size_t) - the capacity of the object pool
	*/
	size_t Capacity() const
	{
		return NrSlabs * N;
	}

	/*
	public ZSlabAllocator<T,N>::Count
	
	Gets the number of objects contained by the object pool.

	@return (size_t) - the number of objects contained by this pool
	*/
	size_t Available() const
	{
		return NrSlabs * N - NrAllocated;
	}

	size_t Allocated()  const
	{
		return NrAllocated;
	}

	/*
	public ZSlabAllocator<T,N>::Deallocate

	Allocates an object from the slab.

	@param _object - a valid object pointer of type T gained through 'Allocate'
	@return (void)
	*/
	void Deallocate(T *_object)
	{
		for(Slab* slab = &FirstPool; slab != NULL; slab = slab->GetNextPool())
		{
			if(slab->IsPoolMember(_object))
			{
				NrAllocated--;
				slab->Deallocate(_object);
				return;
			}
		}

		ZASSERT_RUNTIME_FAIL("ZSlabAllocator: Object deallocated that was not allocated here!");
	}

};

#endif