diff options
Diffstat (limited to 'extern/bullet2/src/LinearMath/btAlignedObjectArray.h')
| -rw-r--r-- | extern/bullet2/src/LinearMath/btAlignedObjectArray.h | 226 |
1 files changed, 208 insertions, 18 deletions
diff --git a/extern/bullet2/src/LinearMath/btAlignedObjectArray.h b/extern/bullet2/src/LinearMath/btAlignedObjectArray.h index 3bfdb36f4c7..8bef5eb5d06 100644 --- a/extern/bullet2/src/LinearMath/btAlignedObjectArray.h +++ b/extern/bullet2/src/LinearMath/btAlignedObjectArray.h @@ -20,18 +20,37 @@ subject to the following restrictions: #include "btScalar.h" // has definitions like SIMD_FORCE_INLINE #include "btAlignedAllocator.h" +///If the platform doesn't support placement new, you can disable BT_USE_PLACEMENT_NEW +///then the btAlignedObjectArray doesn't support objects with virtual methods, and non-trivial constructors/destructors +///You can enable BT_USE_MEMCPY, then swapping elements in the array will use memcpy instead of operator= +///see discussion here: http://continuousphysics.com/Bullet/phpBB2/viewtopic.php?t=1231 and +///http://www.continuousphysics.com/Bullet/phpBB2/viewtopic.php?t=1240 + +#define BT_USE_PLACEMENT_NEW 1 +//#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... + +#ifdef BT_USE_MEMCPY +#include <memory.h> +#include <string.h> +#endif //BT_USE_MEMCPY + +#ifdef BT_USE_PLACEMENT_NEW +#include <new> //for placement new +#endif //BT_USE_PLACEMENT_NEW + + ///btAlignedObjectArray uses a subset of the stl::vector interface for its methods ///It is developed to replace stl::vector to avoid STL alignment issues to add SIMD/SSE data template <typename T> //template <class T> class btAlignedObjectArray { + btAlignedAllocator<T , 16> m_allocator; + int m_size; int m_capacity; T* m_data; - btAlignedAllocator<T , 16> m_allocator; - protected: SIMD_FORCE_INLINE int allocSize(int size) { @@ -40,8 +59,12 @@ class btAlignedObjectArray SIMD_FORCE_INLINE void copy(int start,int end, T* dest) { int i; - for (i=0;i<m_size;++i) + for (i=start;i<end;++i) +#ifdef BT_USE_PLACEMENT_NEW + new (&dest[i]) T(m_data[i]); +#else dest[i] = m_data[i]; +#endif //BT_USE_PLACEMENT_NEW } SIMD_FORCE_INLINE void init() @@ -53,7 +76,7 @@ class btAlignedObjectArray SIMD_FORCE_INLINE void destroy(int first,int last) { int i; - for (i=0; i<m_size;i++) + for (i=first; i<last;i++) { m_data[i].~T(); } @@ -74,6 +97,8 @@ class btAlignedObjectArray } } + + public: @@ -123,17 +148,50 @@ class btAlignedObjectArray m_data[m_size].~T(); } - SIMD_FORCE_INLINE void resize(int newsize) + SIMD_FORCE_INLINE void resize(int newsize, const T& fillData=T()) { - if (newsize > size()) + int curSize = size(); + + if (newsize < size()) + { + for(int i = curSize; i < newsize; i++) + { + m_data[i].~T(); + } + } else { - reserve(newsize); + if (newsize > size()) + { + reserve(newsize); + } +#ifdef BT_USE_PLACEMENT_NEW + for (int i=curSize;i<newsize;i++) + { + new ( &m_data[i]) T(fillData); + } +#endif //BT_USE_PLACEMENT_NEW + } m_size = newsize; } + SIMD_FORCE_INLINE T& expand( const T& fillValue=T()) + { + int sz = size(); + if( sz == capacity() ) + { + reserve( allocSize(size()) ); + } + m_size++; +#ifdef BT_USE_PLACEMENT_NEW + new (&m_data[sz]) T(fillValue); //use the in-place new (not really allocating heap memory) +#endif + + return m_data[sz]; + } + SIMD_FORCE_INLINE void push_back(const T& _Val) { @@ -143,8 +201,12 @@ class btAlignedObjectArray reserve( allocSize(size()) ); } - m_data[size()] = _Val; - //::new ( m_data[m_size] ) T(_Val); +#ifdef BT_USE_PLACEMENT_NEW + new ( &m_data[m_size] ) T(_Val); +#else + m_data[size()] = _Val; +#endif //BT_USE_PLACEMENT_NEW + m_size++; } @@ -154,24 +216,152 @@ class btAlignedObjectArray { // determine new minimum length of allocated storage if (capacity() < _Count) { // not enough room, reallocate - if (capacity() < _Count) - { - T* s = (T*)allocate(_Count); + T* s = (T*)allocate(_Count); + + copy(0, size(), s); + + destroy(0,size()); - copy(0, size(), s); + deallocate(); + + m_data = s; + + m_capacity = _Count; + + } + } - destroy(0,size()); - deallocate(); + class less + { + public: - m_data = s; - - m_capacity = _Count; + bool operator() ( const T& a, const T& b ) + { + return ( a < b ); + } + }; + + ///heap sort from http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Heap/ + template <typename L> + void downHeap(T *pArr, int k, int n,L CompareFunc) + { + /* PRE: a[k+1..N] is a heap */ + /* POST: a[k..N] is a heap */ + + T temp = pArr[k - 1]; + /* k has child(s) */ + while (k <= n/2) + { + int child = 2*k; + + if ((child < n) && CompareFunc(pArr[child - 1] , pArr[child])) + { + child++; + } + /* pick larger child */ + if (CompareFunc(temp , pArr[child - 1])) + { + /* move child up */ + pArr[k - 1] = pArr[child - 1]; + k = child; } + else + { + break; + } + } + pArr[k - 1] = temp; + } /*downHeap*/ + + void swap(int index0,int index1) + { +#ifdef BT_USE_MEMCPY + char temp[sizeof(T)]; + memcpy(temp,&m_data[index0],sizeof(T)); + memcpy(&m_data[index0],&m_data[index1],sizeof(T)); + memcpy(&m_data[index1],temp,sizeof(T)); +#else + T temp = m_data[index0]; + m_data[index0] = m_data[index1]; + m_data[index1] = temp; +#endif //BT_USE_PLACEMENT_NEW + + } + + template <typename L> + void heapSort(L CompareFunc) + { + /* sort a[0..N-1], N.B. 0 to N-1 */ + int k; + int n = m_size; + for (k = n/2; k > 0; k--) + { + downHeap(m_data, k, n, CompareFunc); + } + + /* a[1..N] is now a heap */ + while ( n>=1 ) + { + swap(0,n-1); /* largest of a[0..n-1] */ + + + n = n - 1; + /* restore a[1..i-1] heap */ + downHeap(m_data, 1, n, CompareFunc); + } + } + + ///non-recursive binary search, assumes sorted array + int findBinarySearch(const T& key) const + { + int first = 0; + int last = size(); + + //assume sorted array + while (first <= last) { + int mid = (first + last) / 2; // compute mid point. + if (key > m_data[mid]) + first = mid + 1; // repeat search in top half. + else if (key < m_data[mid]) + last = mid - 1; // repeat search in bottom half. + else + return mid; // found it. return position ///// + } + return size(); // failed to find key + } + + + int findLinearSearch(const T& key) const + { + int index=size(); + int i; + + for (i=0;i<size();i++) + { + if (m_data[i] == key) + { + index = i; + break; } } + return index; + } + + void remove(const T& key) + { + + int findIndex = findLinearSearch(key); + if (findIndex<size()) + { + swap( findIndex,size()-1); + pop_back(); + } + } }; #endif //BT_OBJECT_ARRAY__ + + |