== SoC Bullet - Bullet Upgrade to 2.76 ==
[blender.git] / extern / bullet2 / BulletCollision / Gimpact / btGenericPoolAllocator.cpp
1 /*! \file btGenericPoolAllocator.cpp
2 \author Francisco Le\7fn 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 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 }