Bullet Collision Detection & Physics Library
btAlignedObjectArray.h
Go to the documentation of this file.
1/*
2Bullet Continuous Collision Detection and Physics Library
3Copyright (c) 2003-2006 Erwin Coumans http://continuousphysics.com/Bullet/
4
5This software is provided 'as-is', without any express or implied warranty.
6In no event will the authors be held liable for any damages arising from the use of this software.
7Permission is granted to anyone to use this software for any purpose,
8including commercial applications, and to alter it and redistribute it freely,
9subject to the following restrictions:
10
111. 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.
122. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
133. This notice may not be removed or altered from any source distribution.
14*/
15
16
17#ifndef BT_OBJECT_ARRAY__
18#define BT_OBJECT_ARRAY__
19
20#include "btScalar.h" // has definitions like SIMD_FORCE_INLINE
21#include "btAlignedAllocator.h"
22
28
29#define BT_USE_PLACEMENT_NEW 1
30//#define BT_USE_MEMCPY 1 //disable, because it is cumbersome to find out for each platform where memcpy is defined. It can be in <memory.h> or <string.h> or otherwise...
31#define BT_ALLOW_ARRAY_COPY_OPERATOR // enabling this can accidently perform deep copies of data if you are not careful
32
33#ifdef BT_USE_MEMCPY
34#include <memory.h>
35#include <string.h>
36#endif //BT_USE_MEMCPY
37
38#ifdef BT_USE_PLACEMENT_NEW
39#include <new> //for placement new
40#endif //BT_USE_PLACEMENT_NEW
41
42// The register keyword is deprecated in C++11 so don't use it.
43#if __cplusplus > 199711L
44#define BT_REGISTER
45#else
46#define BT_REGISTER register
47#endif
48
51template <typename T>
52//template <class T>
54{
56
57 int m_size;
60 //PCK: added this line
62
63#ifdef BT_ALLOW_ARRAY_COPY_OPERATOR
64public:
66 {
67 copyFromArray(other);
68 return *this;
69 }
70#else//BT_ALLOW_ARRAY_COPY_OPERATOR
71private:
73#endif//BT_ALLOW_ARRAY_COPY_OPERATOR
74
75protected:
77 {
78 return (size ? size*2 : 1);
79 }
80 SIMD_FORCE_INLINE void copy(int start,int end, T* dest) const
81 {
82 int i;
83 for (i=start;i<end;++i)
85 new (&dest[i]) T(m_data[i]);
86#else
87 dest[i] = m_data[i];
88#endif //BT_USE_PLACEMENT_NEW
89 }
90
92 {
93 //PCK: added this line
94 m_ownsMemory = true;
95 m_data = 0;
96 m_size = 0;
97 m_capacity = 0;
98 }
99 SIMD_FORCE_INLINE void destroy(int first,int last)
100 {
101 int i;
102 for (i=first; i<last;i++)
103 {
104 m_data[i].~T();
105 }
106 }
107
109 {
110 if (size)
111 return m_allocator.allocate(size);
112 return 0;
113 }
114
116 {
117 if(m_data) {
118 //PCK: enclosed the deallocation in this block
119 if (m_ownsMemory)
120 {
121 m_allocator.deallocate(m_data);
122 }
123 m_data = 0;
124 }
125 }
126
127
128
129
130 public:
131
133 {
134 init();
135 }
136
138 {
139 clear();
140 }
141
144 {
145 init();
146
147 int otherSize = otherArray.size();
148 resize (otherSize);
149 otherArray.copy(0, otherSize, m_data);
150 }
151
152
153
156 {
157 return m_size;
158 }
159
160 SIMD_FORCE_INLINE const T& at(int n) const
161 {
162 btAssert(n>=0);
163 btAssert(n<size());
164 return m_data[n];
165 }
166
168 {
169 btAssert(n>=0);
170 btAssert(n<size());
171 return m_data[n];
172 }
173
174 SIMD_FORCE_INLINE const T& operator[](int n) const
175 {
176 btAssert(n>=0);
177 btAssert(n<size());
178 return m_data[n];
179 }
180
182 {
183 btAssert(n>=0);
184 btAssert(n<size());
185 return m_data[n];
186 }
187
188
191 {
192 destroy(0,size());
193
194 deallocate();
195
196 init();
197 }
198
200 {
201 btAssert(m_size>0);
202 m_size--;
203 m_data[m_size].~T();
204 }
205
206
210 {
211 if (newsize > size())
212 {
213 reserve(newsize);
214 }
215 m_size = newsize;
216 }
217
218 SIMD_FORCE_INLINE void resize(int newsize, const T& fillData=T())
219 {
220 const BT_REGISTER int curSize = size();
221
222 if (newsize < curSize)
223 {
224 for(int i = newsize; i < curSize; i++)
225 {
226 m_data[i].~T();
227 }
228 } else
229 {
230 if (newsize > curSize)
231 {
232 reserve(newsize);
233 }
234#ifdef BT_USE_PLACEMENT_NEW
235 for (int i=curSize;i<newsize;i++)
236 {
237 new ( &m_data[i]) T(fillData);
238 }
239#endif //BT_USE_PLACEMENT_NEW
240
241 }
242
243 m_size = newsize;
244 }
246 {
247 const BT_REGISTER int sz = size();
248 if( sz == capacity() )
249 {
250 reserve( allocSize(size()) );
251 }
252 m_size++;
253
254 return m_data[sz];
255 }
256
257
258 SIMD_FORCE_INLINE T& expand( const T& fillValue=T())
259 {
260 const BT_REGISTER int sz = size();
261 if( sz == capacity() )
262 {
263 reserve( allocSize(size()) );
264 }
265 m_size++;
266#ifdef BT_USE_PLACEMENT_NEW
267 new (&m_data[sz]) T(fillValue); //use the in-place new (not really allocating heap memory)
268#endif
269
270 return m_data[sz];
271 }
272
273
274 SIMD_FORCE_INLINE void push_back(const T& _Val)
275 {
276 const BT_REGISTER int sz = size();
277 if( sz == capacity() )
278 {
279 reserve( allocSize(size()) );
280 }
281
282#ifdef BT_USE_PLACEMENT_NEW
283 new ( &m_data[m_size] ) T(_Val);
284#else
285 m_data[size()] = _Val;
286#endif //BT_USE_PLACEMENT_NEW
287
288 m_size++;
289 }
290
291
294 {
295 return m_capacity;
296 }
297
298 SIMD_FORCE_INLINE void reserve(int _Count)
299 { // determine new minimum length of allocated storage
300 if (capacity() < _Count)
301 { // not enough room, reallocate
302 T* s = (T*)allocate(_Count);
303
304 copy(0, size(), s);
305
306 destroy(0,size());
307
308 deallocate();
309
310 //PCK: added this line
311 m_ownsMemory = true;
312
313 m_data = s;
314
315 m_capacity = _Count;
316
317 }
318 }
319
320
321 class less
322 {
323 public:
324
325 bool operator() ( const T& a, const T& b ) const
326 {
327 return ( a < b );
328 }
329 };
330
331
332 template <typename L>
333 void quickSortInternal(const L& CompareFunc,int lo, int hi)
334 {
335 // lo is the lower index, hi is the upper index
336 // of the region of array a that is to be sorted
337 int i=lo, j=hi;
338 T x=m_data[(lo+hi)/2];
339
340 // partition
341 do
342 {
343 while (CompareFunc(m_data[i],x))
344 i++;
345 while (CompareFunc(x,m_data[j]))
346 j--;
347 if (i<=j)
348 {
349 swap(i,j);
350 i++; j--;
351 }
352 } while (i<=j);
353
354 // recursion
355 if (lo<j)
356 quickSortInternal( CompareFunc, lo, j);
357 if (i<hi)
358 quickSortInternal( CompareFunc, i, hi);
359 }
360
361
362 template <typename L>
363 void quickSort(const L& CompareFunc)
364 {
365 //don't sort 0 or 1 elements
366 if (size()>1)
367 {
368 quickSortInternal(CompareFunc,0,size()-1);
369 }
370 }
371
372
374 template <typename L>
375 void downHeap(T *pArr, int k, int n, const L& CompareFunc)
376 {
377 /* PRE: a[k+1..N] is a heap */
378 /* POST: a[k..N] is a heap */
379
380 T temp = pArr[k - 1];
381 /* k has child(s) */
382 while (k <= n/2)
383 {
384 int child = 2*k;
385
386 if ((child < n) && CompareFunc(pArr[child - 1] , pArr[child]))
387 {
388 child++;
389 }
390 /* pick larger child */
391 if (CompareFunc(temp , pArr[child - 1]))
392 {
393 /* move child up */
394 pArr[k - 1] = pArr[child - 1];
395 k = child;
396 }
397 else
398 {
399 break;
400 }
401 }
402 pArr[k - 1] = temp;
403 } /*downHeap*/
404
405 void swap(int index0,int index1)
406 {
407#ifdef BT_USE_MEMCPY
408 char temp[sizeof(T)];
409 memcpy(temp,&m_data[index0],sizeof(T));
410 memcpy(&m_data[index0],&m_data[index1],sizeof(T));
411 memcpy(&m_data[index1],temp,sizeof(T));
412#else
413 T temp = m_data[index0];
414 m_data[index0] = m_data[index1];
415 m_data[index1] = temp;
416#endif //BT_USE_PLACEMENT_NEW
417
418 }
419
420 template <typename L>
421 void heapSort(const L& CompareFunc)
422 {
423 /* sort a[0..N-1], N.B. 0 to N-1 */
424 int k;
425 int n = m_size;
426 for (k = n/2; k > 0; k--)
427 {
428 downHeap(m_data, k, n, CompareFunc);
429 }
430
431 /* a[1..N] is now a heap */
432 while ( n>=1 )
433 {
434 swap(0,n-1); /* largest of a[0..n-1] */
435
436
437 n = n - 1;
438 /* restore a[1..i-1] heap */
439 downHeap(m_data, 1, n, CompareFunc);
440 }
441 }
442
444 int findBinarySearch(const T& key) const
445 {
446 int first = 0;
447 int last = size()-1;
448
449 //assume sorted array
450 while (first <= last) {
451 int mid = (first + last) / 2; // compute mid point.
452 if (key > m_data[mid])
453 first = mid + 1; // repeat search in top half.
454 else if (key < m_data[mid])
455 last = mid - 1; // repeat search in bottom half.
456 else
457 return mid; // found it. return position /////
458 }
459 return size(); // failed to find key
460 }
461
462
463 int findLinearSearch(const T& key) const
464 {
465 int index=size();
466 int i;
467
468 for (i=0;i<size();i++)
469 {
470 if (m_data[i] == key)
471 {
472 index = i;
473 break;
474 }
475 }
476 return index;
477 }
478
479 // If the key is not in the array, return -1 instead of 0,
480 // since 0 also means the first element in the array.
481 int findLinearSearch2(const T& key) const
482 {
483 int index=-1;
484 int i;
485
486 for (i=0;i<size();i++)
487 {
488 if (m_data[i] == key)
489 {
490 index = i;
491 break;
492 }
493 }
494 return index;
495 }
496
497 void removeAtIndex(int index)
498 {
499 if (index<size())
500 {
501 swap( index,size()-1);
502 pop_back();
503 }
504 }
505 void remove(const T& key)
506 {
507 int findIndex = findLinearSearch(key);
508 removeAtIndex(findIndex);
509 }
510
511 //PCK: whole function
512 void initializeFromBuffer(void *buffer, int size, int capacity)
513 {
514 clear();
515 m_ownsMemory = false;
516 m_data = (T*)buffer;
517 m_size = size;
519 }
520
521 void copyFromArray(const btAlignedObjectArray& otherArray)
522 {
523 int otherSize = otherArray.size();
524 resize (otherSize);
525 otherArray.copy(0, otherSize, m_data);
526 }
527
528};
529
530#endif //BT_OBJECT_ARRAY__
#define BT_REGISTER
#define BT_USE_PLACEMENT_NEW
If the platform doesn't support placement new, you can disable BT_USE_PLACEMENT_NEW then the btAligne...
#define SIMD_FORCE_INLINE
Definition: btScalar.h:81
#define btAssert(x)
Definition: btScalar.h:131
The btAlignedAllocator is a portable class for aligned memory allocations.
bool operator()(const T &a, const T &b) const
The btAlignedObjectArray template class uses a subset of the stl::vector interface for its methods It...
int findLinearSearch2(const T &key) const
void resizeNoInitialize(int newsize)
resize changes the number of elements in the array.
int size() const
return the number of elements in the array
void copyFromArray(const btAlignedObjectArray &otherArray)
int findLinearSearch(const T &key) const
void resize(int newsize, const T &fillData=T())
void swap(int index0, int index1)
void clear()
clear the array, deallocated memory. Generally it is better to use array.resize(0),...
btAlignedObjectArray< T > & operator=(const btAlignedObjectArray< T > &other)
void removeAtIndex(int index)
void remove(const T &key)
T & expand(const T &fillValue=T())
void destroy(int first, int last)
const T & operator[](int n) const
void quickSort(const L &CompareFunc)
void copy(int start, int end, T *dest) const
void heapSort(const L &CompareFunc)
void push_back(const T &_Val)
void initializeFromBuffer(void *buffer, int size, int capacity)
int capacity() const
return the pre-allocated (reserved) elements, this is at least as large as the total number of elemen...
btAlignedAllocator< T, 16 > m_allocator
int findBinarySearch(const T &key) const
non-recursive binary search, assumes sorted array
const T & at(int n) const
btAlignedObjectArray(const btAlignedObjectArray &otherArray)
Generally it is best to avoid using the copy constructor of an btAlignedObjectArray,...
void downHeap(T *pArr, int k, int n, const L &CompareFunc)
heap sort from http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Heap/
void quickSortInternal(const L &CompareFunc, int lo, int hi)