dali-physics/third-party/bullet3/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  https://bulletphysics.org
   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 /// *************** btGenericMemoryPool ******************///////////
  24
  25 size_t btGenericMemoryPool::allocate_from_free_nodes(size_t num_elements)
  26 {
  27         size_t ptr = BT_UINT_MAX;
  28
  29         if (m_free_nodes_count == 0) return BT_UINT_MAX;
  30         // find an avaliable free node with the correct size
  31         size_t revindex = m_free_nodes_count;
  32
  33         while (revindex-- && ptr == BT_UINT_MAX)
  34         {
  35                 if (m_allocated_sizes[m_free_nodes[revindex]] >= num_elements)
  36                 {
  37                         ptr = revindex;
  38                 }
  39         }
  40         if (ptr == BT_UINT_MAX) return BT_UINT_MAX;  // not found
  41
  42         revindex = ptr;
  43         ptr = m_free_nodes[revindex];
  44         // post: ptr contains the node index, and revindex the index in m_free_nodes
  45
  46         size_t finalsize = m_allocated_sizes[ptr];
  47         finalsize -= num_elements;
  48
  49         m_allocated_sizes[ptr] = num_elements;
  50
  51         // post: finalsize>=0, m_allocated_sizes[ptr] has the requested size
  52
  53         if (finalsize > 0)  // preserve free node, there are some free memory
  54         {
  55                 m_free_nodes[revindex] = ptr + num_elements;
  56                 m_allocated_sizes[ptr + num_elements] = finalsize;
  57         }
  58         else  // delete free node
  59         {
  60                 // swap with end
  61                 m_free_nodes[revindex] = m_free_nodes[m_free_nodes_count - 1];
  62                 m_free_nodes_count--;
  63         }
  64
  65         return ptr;
  66 }
  67
  68 size_t btGenericMemoryPool::allocate_from_pool(size_t num_elements)
  69 {
  70         if (m_allocated_count + num_elements > m_max_element_count) return BT_UINT_MAX;
  71
  72         size_t ptr = m_allocated_count;
  73
  74         m_allocated_sizes[m_allocated_count] = num_elements;
  75         m_allocated_count += num_elements;
  76
  77         return ptr;
  78 }
  79
  80 void btGenericMemoryPool::init_pool(size_t element_size, size_t element_count)
  81 {
  82         m_allocated_count = 0;
  83         m_free_nodes_count = 0;
  84
  85         m_element_size = element_size;
  86         m_max_element_count = element_count;
  87
  88         m_pool = (unsigned char *)btAlignedAlloc(m_element_size * m_max_element_count, 16);
  89         m_free_nodes = (size_t *)btAlignedAlloc(sizeof(size_t) * m_max_element_count, 16);
  90         m_allocated_sizes = (size_t *)btAlignedAlloc(sizeof(size_t) * m_max_element_count, 16);
  91
  92         for (size_t i = 0; i < m_max_element_count; i++)
  93         {
  94                 m_allocated_sizes[i] = 0;
  95         }
  96 }
  97
  98 void btGenericMemoryPool::end_pool()
  99 {
 100         btAlignedFree(m_pool);
 101         btAlignedFree(m_free_nodes);
 102         btAlignedFree(m_allocated_sizes);
 103         m_allocated_count = 0;
 104         m_free_nodes_count = 0;
 105 }
 106
 107 //! Allocates memory in pool
 108 /*!
 109 \param size_bytes size in bytes of the buffer
 110 */
 111 void *btGenericMemoryPool::allocate(size_t size_bytes)
 112 {
 113         size_t module = size_bytes % m_element_size;
 114         size_t element_count = size_bytes / m_element_size;
 115         if (module > 0) element_count++;
 116
 117         size_t alloc_pos = allocate_from_free_nodes(element_count);
 118         // a free node is found
 119         if (alloc_pos != BT_UINT_MAX)
 120         {
 121                 return get_element_data(alloc_pos);
 122         }
 123         // allocate directly on pool
 124         alloc_pos = allocate_from_pool(element_count);
 125
 126         if (alloc_pos == BT_UINT_MAX) return NULL;  // not space
 127         return get_element_data(alloc_pos);
 128 }
 129
 130 bool btGenericMemoryPool::freeMemory(void *pointer)
 131 {
 132         unsigned char *pointer_pos = (unsigned char *)pointer;
 133         unsigned char *pool_pos = (unsigned char *)m_pool;
 134         // calc offset
 135         if (pointer_pos < pool_pos) return false;  //other pool
 136         size_t offset = size_t(pointer_pos - pool_pos);
 137         if (offset >= get_pool_capacity()) return false;  // far away
 138
 139         // find free position
 140         m_free_nodes[m_free_nodes_count] = offset / m_element_size;
 141         m_free_nodes_count++;
 142         return true;
 143 }
 144
 145 /// *******************! btGenericPoolAllocator *******************!///
 146
 147 btGenericPoolAllocator::~btGenericPoolAllocator()
 148 {
 149         // destroy pools
 150         size_t i;
 151         for (i = 0; i < m_pool_count; i++)
 152         {
 153                 m_pools[i]->end_pool();
 154                 btAlignedFree(m_pools[i]);
 155         }
 156 }
 157
 158 // creates a pool
 159 btGenericMemoryPool *btGenericPoolAllocator::push_new_pool()
 160 {
 161         if (m_pool_count >= BT_DEFAULT_MAX_POOLS) return NULL;
 162
 163         btGenericMemoryPool *newptr = (btGenericMemoryPool *)btAlignedAlloc(sizeof(btGenericMemoryPool), 16);
 164
 165         m_pools[m_pool_count] = newptr;
 166
 167         m_pools[m_pool_count]->init_pool(m_pool_element_size, m_pool_element_count);
 168
 169         m_pool_count++;
 170         return newptr;
 171 }
 172
 173 void *btGenericPoolAllocator::failback_alloc(size_t size_bytes)
 174 {
 175         btGenericMemoryPool *pool = NULL;
 176
 177         if (size_bytes <= get_pool_capacity())
 178         {
 179                 pool = push_new_pool();
 180         }
 181
 182         if (pool == NULL)  // failback
 183         {
 184                 return btAlignedAlloc(size_bytes, 16);
 185         }
 186
 187         return pool->allocate(size_bytes);
 188 }
 189
 190 bool btGenericPoolAllocator::failback_free(void *pointer)
 191 {
 192         btAlignedFree(pointer);
 193         return true;
 194 }
 195
 196 //! Allocates memory in pool
 197 /*!
 198 \param size_bytes size in bytes of the buffer
 199 */
 200 void *btGenericPoolAllocator::allocate(size_t size_bytes)
 201 {
 202         void *ptr = NULL;
 203
 204         size_t i = 0;
 205         while (i < m_pool_count && ptr == NULL)
 206         {
 207                 ptr = m_pools[i]->allocate(size_bytes);
 208                 ++i;
 209         }
 210
 211         if (ptr) return ptr;
 212
 213         return failback_alloc(size_bytes);
 214 }
 215
 216 bool btGenericPoolAllocator::freeMemory(void *pointer)
 217 {
 218         bool result = false;
 219
 220         size_t i = 0;
 221         while (i < m_pool_count && result == false)
 222         {
 223                 result = m_pools[i]->freeMemory(pointer);
 224                 ++i;
 225         }
 226
 227         if (result) return true;
 228
 229         return failback_free(pointer);
 230 }
 231
 232 /// ************** STANDARD ALLOCATOR ***************************///
 233
 234 #define BT_DEFAULT_POOL_SIZE 32768
 235 #define BT_DEFAULT_POOL_ELEMENT_SIZE 8
 236
 237 // main allocator
 238 class GIM_STANDARD_ALLOCATOR : public btGenericPoolAllocator
 239 {
 240 public:
 241         GIM_STANDARD_ALLOCATOR() : btGenericPoolAllocator(BT_DEFAULT_POOL_ELEMENT_SIZE, BT_DEFAULT_POOL_SIZE)
 242         {
 243         }
 244 };
 245
 246 // global allocator
 247 GIM_STANDARD_ALLOCATOR g_main_allocator;
 248
 249 void *btPoolAlloc(size_t size)
 250 {
 251         return g_main_allocator.allocate(size);
 252 }
 253
 254 void *btPoolRealloc(void *ptr, size_t oldsize, size_t newsize)
 255 {
 256         void *newptr = btPoolAlloc(newsize);
 257         size_t copysize = oldsize < newsize ? oldsize : newsize;
 258         memcpy(newptr, ptr, copysize);
 259         btPoolFree(ptr);
 260         return newptr;
 261 }
 262
 263 void btPoolFree(void *ptr)
 264 {
 265         g_main_allocator.freeMemory(ptr);
 266 }