Differential D8762 Diff 28333 extern/bullet2/src/BulletCollision/Gimpact/btGenericPoolAllocator.cpp

Changeset View

Standalone View

extern/bullet2/src/BulletCollision/Gimpact/btGenericPoolAllocator.cpp

	Show All 14 Lines

	1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.			1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
	2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.			2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
	3. This notice may not be removed or altered from any source distribution.			3. This notice may not be removed or altered from any source distribution.
	*/			*/

	#include "btGenericPoolAllocator.h"			#include "btGenericPoolAllocator.h"



	/// ************* btGenericMemoryPool ****************///////////			/// ************* btGenericMemoryPool ****************///////////

	size_t btGenericMemoryPool::allocate_from_free_nodes(size_t num_elements)			size_t btGenericMemoryPool::allocate_from_free_nodes(size_t num_elements)
	{			{
	size_t ptr = BT_UINT_MAX;			size_t ptr = BT_UINT_MAX;

	if(m_free_nodes_count == 0) return BT_UINT_MAX;			if (m_free_nodes_count == 0) return BT_UINT_MAX;
	// find an avaliable free node with the correct size			// find an avaliable free node with the correct size
	size_t revindex = m_free_nodes_count;			size_t revindex = m_free_nodes_count;

	while(revindex-- && ptr == BT_UINT_MAX)			while (revindex-- && ptr == BT_UINT_MAX)
	{			{
	if(m_allocated_sizes[m_free_nodes[revindex]]>=num_elements)			if (m_allocated_sizes[m_free_nodes[revindex]] >= num_elements)
	{			{
	ptr = revindex;			ptr = revindex;
	}			}
	}			}
	if(ptr == BT_UINT_MAX) return BT_UINT_MAX; // not found			if (ptr == BT_UINT_MAX) return BT_UINT_MAX; // not found


	revindex = ptr;			revindex = ptr;
	ptr = m_free_nodes[revindex];			ptr = m_free_nodes[revindex];
	// post: ptr contains the node index, and revindex the index in m_free_nodes			// post: ptr contains the node index, and revindex the index in m_free_nodes

	size_t finalsize = m_allocated_sizes[ptr];			size_t finalsize = m_allocated_sizes[ptr];
	finalsize -= num_elements;			finalsize -= num_elements;

	m_allocated_sizes[ptr] = num_elements;			m_allocated_sizes[ptr] = num_elements;

	// post: finalsize>=0, m_allocated_sizes[ptr] has the requested size			// post: finalsize>=0, m_allocated_sizes[ptr] has the requested size

	if(finalsize>0) // preserve free node, there are some free memory			if (finalsize > 0) // preserve free node, there are some free memory
	{			{
	m_free_nodes[revindex] = ptr + num_elements;			m_free_nodes[revindex] = ptr + num_elements;
	m_allocated_sizes[ptr + num_elements] = finalsize;			m_allocated_sizes[ptr + num_elements] = finalsize;
	}			}
	else // delete free node			else // delete free node
	{			{
	// swap with end			// swap with end
	m_free_nodes[revindex] = m_free_nodes[m_free_nodes_count-1];			m_free_nodes[revindex] = m_free_nodes[m_free_nodes_count - 1];
	m_free_nodes_count--;			m_free_nodes_count--;
	}			}

	return ptr;			return ptr;
	}			}

	size_t btGenericMemoryPool::allocate_from_pool(size_t num_elements)			size_t btGenericMemoryPool::allocate_from_pool(size_t num_elements)
	{			{
	if(m_allocated_count+num_elements>m_max_element_count) return BT_UINT_MAX;			if (m_allocated_count + num_elements > m_max_element_count) return BT_UINT_MAX;

	size_t ptr = m_allocated_count;			size_t ptr = m_allocated_count;

	m_allocated_sizes[m_allocated_count] = num_elements;			m_allocated_sizes[m_allocated_count] = num_elements;
	m_allocated_count+=num_elements;			m_allocated_count += num_elements;

	return ptr;			return ptr;
	}			}


	void btGenericMemoryPool::init_pool(size_t element_size, size_t element_count)			void btGenericMemoryPool::init_pool(size_t element_size, size_t element_count)
	{			{
	m_allocated_count = 0;			m_allocated_count = 0;
	m_free_nodes_count = 0;			m_free_nodes_count = 0;

	m_element_size = element_size;			m_element_size = element_size;
	m_max_element_count = element_count;			m_max_element_count = element_count;




	m_pool = (unsigned char ) btAlignedAlloc(m_element_sizem_max_element_count,16);			m_pool = (unsigned char )btAlignedAlloc(m_element_size m_max_element_count, 16);
	m_free_nodes = (size_t ) btAlignedAlloc(sizeof(size_t)m_max_element_count,16);			m_free_nodes = (size_t )btAlignedAlloc(sizeof(size_t) m_max_element_count, 16);
	m_allocated_sizes = (size_t ) btAlignedAlloc(sizeof(size_t)m_max_element_count,16);			m_allocated_sizes = (size_t )btAlignedAlloc(sizeof(size_t) m_max_element_count, 16);

	for (size_t i = 0;i< m_max_element_count;i++ )			for (size_t i = 0; i < m_max_element_count; i++)
	{			{
	m_allocated_sizes[i] = 0;			m_allocated_sizes[i] = 0;
	}			}
	}			}

	void btGenericMemoryPool::end_pool()			void btGenericMemoryPool::end_pool()
	{			{
	btAlignedFree(m_pool);			btAlignedFree(m_pool);
	btAlignedFree(m_free_nodes);			btAlignedFree(m_free_nodes);
	btAlignedFree(m_allocated_sizes);			btAlignedFree(m_allocated_sizes);
	m_allocated_count = 0;			m_allocated_count = 0;
	m_free_nodes_count = 0;			m_free_nodes_count = 0;
	}			}


	//! Allocates memory in pool			//! Allocates memory in pool
	/*!			/*!
	\param size_bytes size in bytes of the buffer			\param size_bytes size in bytes of the buffer
	*/			*/
	void * btGenericMemoryPool::allocate(size_t size_bytes)			void *btGenericMemoryPool::allocate(size_t size_bytes)
	{			{

	size_t module = size_bytes%m_element_size;			size_t module = size_bytes % m_element_size;
	size_t element_count = size_bytes/m_element_size;			size_t element_count = size_bytes / m_element_size;
	if(module>0) element_count++;			if (module > 0) element_count++;

	size_t alloc_pos = allocate_from_free_nodes(element_count);			size_t alloc_pos = allocate_from_free_nodes(element_count);
	// a free node is found			// a free node is found
	if(alloc_pos != BT_UINT_MAX)			if (alloc_pos != BT_UINT_MAX)
	{			{
	return get_element_data(alloc_pos);			return get_element_data(alloc_pos);
	}			}
	// allocate directly on pool			// allocate directly on pool
	alloc_pos = allocate_from_pool(element_count);			alloc_pos = allocate_from_pool(element_count);

	if(alloc_pos == BT_UINT_MAX) return NULL; // not space			if (alloc_pos == BT_UINT_MAX) return NULL; // not space
	return get_element_data(alloc_pos);			return get_element_data(alloc_pos);
	}			}

	bool btGenericMemoryPool::freeMemory(void * pointer)			bool btGenericMemoryPool::freeMemory(void *pointer)
	{			{
	unsigned char * pointer_pos = (unsigned char *)pointer;			unsigned char pointer_pos = (unsigned char )pointer;
	unsigned char * pool_pos = (unsigned char *)m_pool;			unsigned char pool_pos = (unsigned char )m_pool;
	// calc offset			// calc offset
	if(pointer_pos<pool_pos) return false;//other pool			if (pointer_pos < pool_pos) return false; //other pool
	size_t offset = size_t(pointer_pos - pool_pos);			size_t offset = size_t(pointer_pos - pool_pos);
	if(offset>=get_pool_capacity()) return false;// far away			if (offset >= get_pool_capacity()) return false; // far away

	// find free position			// find free position
	m_free_nodes[m_free_nodes_count] = offset/m_element_size;			m_free_nodes[m_free_nodes_count] = offset / m_element_size;
	m_free_nodes_count++;			m_free_nodes_count++;
	return true;			return true;
	}			}


	/// *****************! btGenericPoolAllocator *****************!///			/// *****************! btGenericPoolAllocator *****************!///


	btGenericPoolAllocator::~btGenericPoolAllocator()			btGenericPoolAllocator::~btGenericPoolAllocator()
	{			{
	// destroy pools			// destroy pools
	size_t i;			size_t i;
	for (i=0;i<m_pool_count;i++)			for (i = 0; i < m_pool_count; i++)
	{			{
	m_pools[i]->end_pool();			m_pools[i]->end_pool();
	btAlignedFree(m_pools[i]);			btAlignedFree(m_pools[i]);
	}			}
	}			}


	// creates a pool			// creates a pool
	btGenericMemoryPool * btGenericPoolAllocator::push_new_pool()			btGenericMemoryPool *btGenericPoolAllocator::push_new_pool()
	{			{
	if(m_pool_count >= BT_DEFAULT_MAX_POOLS) return NULL;			if (m_pool_count >= BT_DEFAULT_MAX_POOLS) return NULL;

	btGenericMemoryPool * newptr = (btGenericMemoryPool *)btAlignedAlloc(sizeof(btGenericMemoryPool),16);			btGenericMemoryPool newptr = (btGenericMemoryPool )btAlignedAlloc(sizeof(btGenericMemoryPool), 16);

	m_pools[m_pool_count] = newptr;			m_pools[m_pool_count] = newptr;

	m_pools[m_pool_count]->init_pool(m_pool_element_size,m_pool_element_count);			m_pools[m_pool_count]->init_pool(m_pool_element_size, m_pool_element_count);

	m_pool_count++;			m_pool_count++;
	return newptr;			return newptr;
	}			}

	void * btGenericPoolAllocator::failback_alloc(size_t size_bytes)			void *btGenericPoolAllocator::failback_alloc(size_t size_bytes)
	{			{

	btGenericMemoryPool * pool = NULL;			btGenericMemoryPool *pool = NULL;


	if(size_bytes<=get_pool_capacity())			if (size_bytes <= get_pool_capacity())
	{			{
	pool = push_new_pool();			pool = push_new_pool();
	}			}

	if(pool==NULL) // failback			if (pool == NULL) // failback
	{			{
	return btAlignedAlloc(size_bytes,16);			return btAlignedAlloc(size_bytes, 16);
	}			}

	return pool->allocate(size_bytes);			return pool->allocate(size_bytes);
	}			}

	bool btGenericPoolAllocator::failback_free(void * pointer)			bool btGenericPoolAllocator::failback_free(void *pointer)
	{			{
	btAlignedFree(pointer);			btAlignedFree(pointer);
	return true;			return true;
	}			}


	//! Allocates memory in pool			//! Allocates memory in pool
	/*!			/*!
	\param size_bytes size in bytes of the buffer			\param size_bytes size in bytes of the buffer
	*/			*/
	void * btGenericPoolAllocator::allocate(size_t size_bytes)			void *btGenericPoolAllocator::allocate(size_t size_bytes)
	{			{
	void * ptr = NULL;			void *ptr = NULL;

	size_t i = 0;			size_t i = 0;
	while(i<m_pool_count && ptr == NULL)			while (i < m_pool_count && ptr == NULL)
	{			{
	ptr = m_pools[i]->allocate(size_bytes);			ptr = m_pools[i]->allocate(size_bytes);
	++i;			++i;
	}			}

	if(ptr) return ptr;			if (ptr) return ptr;

	return failback_alloc(size_bytes);			return failback_alloc(size_bytes);
	}			}

	bool btGenericPoolAllocator::freeMemory(void * pointer)			bool btGenericPoolAllocator::freeMemory(void *pointer)
	{			{
	bool result = false;			bool result = false;

	size_t i = 0;			size_t i = 0;
	while(i<m_pool_count && result == false)			while (i < m_pool_count && result == false)
	{			{
	result = m_pools[i]->freeMemory(pointer);			result = m_pools[i]->freeMemory(pointer);
	++i;			++i;
	}			}

	if(result) return true;			if (result) return true;

	return failback_free(pointer);			return failback_free(pointer);
	}			}

	/// ************ STANDARD ALLOCATOR *************************///			/// ************ STANDARD ALLOCATOR *************************///


	#define BT_DEFAULT_POOL_SIZE 32768			#define BT_DEFAULT_POOL_SIZE 32768
	#define BT_DEFAULT_POOL_ELEMENT_SIZE 8			#define BT_DEFAULT_POOL_ELEMENT_SIZE 8

	// main allocator			// main allocator
	class GIM_STANDARD_ALLOCATOR: public btGenericPoolAllocator			class GIM_STANDARD_ALLOCATOR : public btGenericPoolAllocator
	{			{
	public:			public:
	GIM_STANDARD_ALLOCATOR():btGenericPoolAllocator(BT_DEFAULT_POOL_ELEMENT_SIZE,BT_DEFAULT_POOL_SIZE)			GIM_STANDARD_ALLOCATOR() : btGenericPoolAllocator(BT_DEFAULT_POOL_ELEMENT_SIZE, BT_DEFAULT_POOL_SIZE)
	{			{
	}			}
	};			};

	// global allocator			// global allocator
	GIM_STANDARD_ALLOCATOR g_main_allocator;			GIM_STANDARD_ALLOCATOR g_main_allocator;


	void * btPoolAlloc(size_t size)			void *btPoolAlloc(size_t size)
	{			{
	return g_main_allocator.allocate(size);			return g_main_allocator.allocate(size);
	}			}

	void * btPoolRealloc(void *ptr, size_t oldsize, size_t newsize)			void btPoolRealloc(void ptr, size_t oldsize, size_t newsize)
	{			{
	void * newptr = btPoolAlloc(newsize);			void *newptr = btPoolAlloc(newsize);
	size_t copysize = oldsize<newsize?oldsize:newsize;			size_t copysize = oldsize < newsize ? oldsize : newsize;
	memcpy(newptr,ptr,copysize);			memcpy(newptr, ptr, copysize);
	btPoolFree(ptr);			btPoolFree(ptr);
	return newptr;			return newptr;
	}			}

	void btPoolFree(void *ptr)			void btPoolFree(void *ptr)
	{			{
	g_main_allocator.freeMemory(ptr);			g_main_allocator.freeMemory(ptr);
	}			}