[1963] | 1 | /*! \file btGenericPoolAllocator.cpp |
---|
| 2 | \author Francisco Len Nßjera. 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 BT_STANDARD_ALLOCATOR: public btGenericPoolAllocator |
---|
| 255 | { |
---|
| 256 | public: |
---|
| 257 | BT_STANDARD_ALLOCATOR():btGenericPoolAllocator(BT_DEFAULT_POOL_ELEMENT_SIZE,BT_DEFAULT_POOL_SIZE) |
---|
| 258 | { |
---|
| 259 | } |
---|
| 260 | }; |
---|
| 261 | |
---|
| 262 | // global allocator |
---|
| 263 | BT_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 | } |
---|