src/BulletCollision/Gimpact/btGenericPoolAllocator.cpp

   1 /*! \file btGenericPoolAllocator.cpp
   2 \author Francisco Leon Najera. email projectileman@yahoo.com
   3
   4 General purpose allocator class
   5 */
   6 /*
   7 Bullet Continuous Collision Detection and Physics Library
   8 Copyright (c) 2003-2006 Erwin Coumans  http://continuousphysics.com/Bullet/
   9
  10 This software is provided 'as-is', without any express or implied warranty.
  11 In no event will the authors be held liable for any damages arising from the use of this software.
  12 Permission is granted to anyone to use this software for any purpose,
  13 including commercial applications, and to alter it and redistribute it freely,
  14 subject to the following restrictions:
  15
  16 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.
  17 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
  18 3. This notice may not be removed or altered from any source distribution.
  19 */
  20
  21 #include "btGenericPoolAllocator.h"
  22
  23
  24
  25 /// *************** btGenericMemoryPool ******************///////////
  26
  27 size_t btGenericMemoryPool::allocate_from_free_nodes(size_t num_elements)
  28 {
  29         size_t ptr = BT_UINT_MAX;
  30
  31         if(m_free_nodes_count == 0) return BT_UINT_MAX;
  32         // find an avaliable free node with the correct size
  33         size_t revindex = m_free_nodes_count;
  34
  35         while(revindex-- && ptr == BT_UINT_MAX)
  36         {
  37                 if(m_allocated_sizes[m_free_nodes[revindex]]>=num_elements)
  38                 {
  39                         ptr = revindex;
  40                 }
  41         }
  42         if(ptr == BT_UINT_MAX) return BT_UINT_MAX; // not found
  43
  44
  45         revindex = ptr;
  46         ptr = m_free_nodes[revindex];
  47         // post: ptr contains the node index, and revindex the index in m_free_nodes
  48
  49         size_t  finalsize = m_allocated_sizes[ptr];
  50         finalsize -= num_elements;
  51
  52         m_allocated_sizes[ptr] = num_elements;
  53
  54         // post: finalsize>=0, m_allocated_sizes[ptr] has the requested size
  55
  56         if(finalsize>0) // preserve free node, there are some free memory
  57         {
  58                 m_free_nodes[revindex] = ptr + num_elements;
  59                 m_allocated_sizes[ptr + num_elements] = finalsize;
  60         }
  61         else // delete free node
  62         {
  63                 // swap with end
  64                 m_free_nodes[revindex] = m_free_nodes[m_free_nodes_count-1];
  65                 m_free_nodes_count--;
  66         }
  67
  68         return ptr;
  69 }
  70
  71 size_t btGenericMemoryPool::allocate_from_pool(size_t num_elements)
  72 {
  73         if(m_allocated_count+num_elements>m_max_element_count) return BT_UINT_MAX;
  74
  75         size_t ptr = m_allocated_count;
  76
  77         m_allocated_sizes[m_allocated_count] = num_elements;
  78         m_allocated_count+=num_elements;
  79
  80         return ptr;
  81 }
  82
  83
  84 void btGenericMemoryPool::init_pool(size_t element_size, size_t element_count)
  85 {
  86         m_allocated_count = 0;
  87         m_free_nodes_count = 0;
  88
  89         m_element_size = element_size;
  90         m_max_element_count = element_count;
  91
  92
  93
  94
  95         m_pool = (unsigned char *) btAlignedAlloc(m_element_size*m_max_element_count,16);
  96         m_free_nodes = (size_t *) btAlignedAlloc(sizeof(size_t)*m_max_element_count,16);
  97         m_allocated_sizes = (size_t *) btAlignedAlloc(sizeof(size_t)*m_max_element_count,16);
  98
  99         for (size_t i = 0;i< m_max_element_count;i++ )
 100         {
 101                 m_allocated_sizes[i] = 0;
 102         }
 103 }
 104
 105 void btGenericMemoryPool::end_pool()
 106 {
 107         btAlignedFree(m_pool);
 108         btAlignedFree(m_free_nodes);
 109         btAlignedFree(m_allocated_sizes);
 110         m_allocated_count = 0;
 111         m_free_nodes_count = 0;
 112 }
 113
 114
 115 //! Allocates memory in pool
 116 /*!
 117 \param size_bytes size in bytes of the buffer
 118 */
 119 void * btGenericMemoryPool::allocate(size_t size_bytes)
 120 {
 121
 122         size_t module = size_bytes%m_element_size;
 123         size_t element_count = size_bytes/m_element_size;
 124         if(module>0) element_count++;
 125
 126         size_t alloc_pos = allocate_from_free_nodes(element_count);
 127         // a free node is found
 128         if(alloc_pos != BT_UINT_MAX)
 129         {
 130                 return get_element_data(alloc_pos);
 131         }
 132         // allocate directly on pool
 133         alloc_pos = allocate_from_pool(element_count);
 134
 135         if(alloc_pos == BT_UINT_MAX) return NULL; // not space
 136         return get_element_data(alloc_pos);
 137 }
 138
 139 bool btGenericMemoryPool::freeMemory(void * pointer)
 140 {
 141         unsigned char * pointer_pos = (unsigned char *)pointer;
 142         unsigned char * pool_pos = (unsigned char *)m_pool;
 143         // calc offset
 144         if(pointer_pos<pool_pos) return false;//other pool
 145         size_t offset = size_t(pointer_pos - pool_pos);
 146         if(offset>=get_pool_capacity()) return false;// far away
 147
 148         // find free position
 149         m_free_nodes[m_free_nodes_count] = offset/m_element_size;
 150         m_free_nodes_count++;
 151         return true;
 152 }
 153
 154
 155 /// *******************! btGenericPoolAllocator *******************!///
 156
 157
 158 btGenericPoolAllocator::~btGenericPoolAllocator()
 159 {
 160         // destroy pools
 161         size_t i;
 162         for (i=0;i<m_pool_count;i++)
 163         {
 164                 m_pools[i]->end_pool();
 165                 btAlignedFree(m_pools[i]);
 166         }
 167 }
 168
 169
 170 // creates a pool
 171 btGenericMemoryPool * btGenericPoolAllocator::push_new_pool()
 172 {
 173         if(m_pool_count >= BT_DEFAULT_MAX_POOLS) return NULL;
 174
 175         btGenericMemoryPool * newptr = (btGenericMemoryPool *)btAlignedAlloc(sizeof(btGenericMemoryPool),16);
 176
 177         m_pools[m_pool_count] = newptr;
 178
 179         m_pools[m_pool_count]->init_pool(m_pool_element_size,m_pool_element_count);
 180
 181         m_pool_count++;
 182         return newptr;
 183 }
 184
 185 void * btGenericPoolAllocator::failback_alloc(size_t size_bytes)
 186 {
 187
 188         btGenericMemoryPool * pool = NULL;
 189
 190
 191         if(size_bytes<=get_pool_capacity())
 192         {
 193                 pool =  push_new_pool();
 194         }
 195
 196         if(pool==NULL) // failback
 197         {
 198                 return btAlignedAlloc(size_bytes,16);
 199         }
 200
 201         return pool->allocate(size_bytes);
 202 }
 203
 204 bool btGenericPoolAllocator::failback_free(void * pointer)
 205 {
 206         btAlignedFree(pointer);
 207         return true;
 208 }
 209
 210
 211 //! Allocates memory in pool
 212 /*!
 213 \param size_bytes size in bytes of the buffer
 214 */
 215 void * btGenericPoolAllocator::allocate(size_t size_bytes)
 216 {
 217         void * ptr = NULL;
 218
 219         size_t i = 0;
 220         while(i<m_pool_count && ptr == NULL)
 221         {
 222                 ptr = m_pools[i]->allocate(size_bytes);
 223                 ++i;
 224         }
 225
 226         if(ptr) return ptr;
 227
 228         return failback_alloc(size_bytes);
 229 }
 230
 231 bool btGenericPoolAllocator::freeMemory(void * pointer)
 232 {
 233         bool result = false;
 234
 235         size_t i = 0;
 236         while(i<m_pool_count && result == false)
 237         {
 238                 result = m_pools[i]->freeMemory(pointer);
 239                 ++i;
 240         }
 241
 242         if(result) return true;
 243
 244         return failback_free(pointer);
 245 }
 246
 247 /// ************** STANDARD ALLOCATOR ***************************///
 248
 249
 250 #define BT_DEFAULT_POOL_SIZE 32768
 251 #define BT_DEFAULT_POOL_ELEMENT_SIZE 8
 252
 253 // main allocator
 254 class GIM_STANDARD_ALLOCATOR: public btGenericPoolAllocator
 255 {
 256 public:
 257         GIM_STANDARD_ALLOCATOR():btGenericPoolAllocator(BT_DEFAULT_POOL_ELEMENT_SIZE,BT_DEFAULT_POOL_SIZE)
 258         {
 259         }
 260 };
 261
 262 // global allocator
 263 GIM_STANDARD_ALLOCATOR g_main_allocator;
 264
 265
 266 void * btPoolAlloc(size_t size)
 267 {
 268         return g_main_allocator.allocate(size);
 269 }
 270
 271 void * btPoolRealloc(void *ptr, size_t oldsize, size_t newsize)
 272 {
 273         void * newptr = btPoolAlloc(newsize);
 274     size_t copysize = oldsize<newsize?oldsize:newsize;
 275     memcpy(newptr,ptr,copysize);
 276     btPoolFree(ptr);
 277     return newptr;
 278 }
 279
 280 void btPoolFree(void *ptr)
 281 {
 282         g_main_allocator.freeMemory(ptr);
 283 }