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