Bullet Collision Detection & Physics Library
btGenericPoolAllocator.cpp
Go to the documentation of this file.
1 
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 
26 
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
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 {
88 
89  m_element_size = element_size;
90  m_max_element_count = element_count;
91 
92 
93 
94 
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 
106 {
110  m_allocated_count = 0;
111  m_free_nodes_count = 0;
112 }
113 
114 
116 
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 
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
151  return true;
152 }
153 
154 
156 
157 
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
172 {
173  if(m_pool_count >= BT_DEFAULT_MAX_POOLS) return NULL;
174 
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 
205 {
206  btAlignedFree(pointer);
207  return true;
208 }
209 
210 
212 
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 
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 
248 
249 
250 #define BT_DEFAULT_POOL_SIZE 32768
251 #define BT_DEFAULT_POOL_ELEMENT_SIZE 8
252 
253 // main allocator
255 {
256 public:
258  {
259  }
260 };
261 
262 // global 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 }
#define BT_UINT_MAX
void btPoolFree(void *ptr)
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
Definition: btDbvt.cpp:52
void * btPoolRealloc(void *ptr, size_t oldsize, size_t newsize)
#define BT_DEFAULT_POOL_ELEMENT_SIZE
void * allocate(size_t size_bytes)
Allocates memory in pool.
void init_pool(size_t element_size, size_t element_count)
void * allocate(size_t size_bytes)
Allocates memory in pool.
Generic Allocator with pools.
#define BT_DEFAULT_POOL_SIZE
************** STANDARD ALLOCATOR ***************************///
size_t allocate_from_free_nodes(size_t num_elements)
*************** btGenericMemoryPool ******************///////////
virtual ~btGenericPoolAllocator()
*******************! btGenericPoolAllocator *******************!///
#define BT_DEFAULT_MAX_POOLS
size_t allocate_from_pool(size_t num_elements)
btGenericMemoryPool * push_new_pool()
Generic Pool class.
#define btAlignedFree(ptr)
GIM_STANDARD_ALLOCATOR g_main_allocator
bool failback_free(void *pointer)
void * failback_alloc(size_t size_bytes)
bool freeMemory(void *pointer)
#define btAlignedAlloc(size, alignment)
void * get_element_data(size_t element_index)
void * btPoolAlloc(size_t size)