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 // 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 
51 template <typename T>
52 //template <class T>
54 {
56 
57  int m_size;
59  T* m_data;
60  //PCK: added this line
62 
63 #ifdef BT_ALLOW_ARRAY_COPY_OPERATOR
64 public:
66  {
67  copyFromArray(other);
68  return *this;
69  }
70 #else//BT_ALLOW_ARRAY_COPY_OPERATOR
71 private:
73 #endif//BT_ALLOW_ARRAY_COPY_OPERATOR
74 
75 protected:
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;
518  m_capacity = capacity;
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
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:131
bool operator()(const T &a, const T &b) const
#define SIMD_FORCE_INLINE
Definition: btScalar.h:81
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.
void removeAtIndex(int index)
int size() const
return the number of elements in the array
#define BT_USE_PLACEMENT_NEW
If the platform doesn&#39;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)
void quickSort(const L &CompareFunc)
int findLinearSearch2(const T &key) const