Main Page Class List Class Members

- Main Page
- User's Guide
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

# sdk/extensions/authoring/source/VHACD/inc/btAlignedObjectArray.h

Go to the documentation of this file.

    00001 /*
    00002 Bullet Continuous Collision Detection and Physics Library
    00003 Copyright (c) 2003-2006 Erwin Coumans  http://continuousphysics.com/Bullet/
    00004
    00005 This software is provided 'as-is', without any express or implied warranty.
    00006 In no event will the authors be held liable for any damages arising from the use of this software.
    00007 Permission is granted to anyone to use this software for any purpose,
    00008 including commercial applications, and to alter it and redistribute it freely,
    00009 subject to the following restrictions:
    00010
    00011 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.
    00012 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
    00013 3. This notice may not be removed or altered from any source distribution.
    00014 */
    00015
    00016 #ifndef BT_OBJECT_ARRAY__
    00017 #define BT_OBJECT_ARRAY__
    00018
    00019 #include "btAlignedAllocator.h"
    00020 #include "btScalar.h" // has definitions like SIMD_FORCE_INLINE
    00021
    00027
    00028 #define BT_USE_PLACEMENT_NEW 1
    00029 //#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...
    00030 #define BT_ALLOW_ARRAY_COPY_OPERATOR // enabling this can accidently perform deep copies of data if you are not careful
    00031
    00032 #ifdef BT_USE_MEMCPY
    00033 #include <memory.h>
    00034 #include <string.h>
    00035 #endif //BT_USE_MEMCPY
    00036
    00037 #ifdef BT_USE_PLACEMENT_NEW
    00038 #include <new> //for placement new
    00039 #endif //BT_USE_PLACEMENT_NEW
    00040
    00043 template <typename T>
    00044 //template <class T>
    00045 class btAlignedObjectArray {
    00046     btAlignedAllocator<T, 16> m_allocator;
    00047
    00048     int32_t m_size;
    00049     int32_t m_capacity;
    00050     T* m_data;
    00051     //PCK: added this line
    00052     bool m_ownsMemory;
    00053
    00054 #ifdef BT_ALLOW_ARRAY_COPY_OPERATOR
    00055 public:
    00056     SIMD_FORCE_INLINE btAlignedObjectArray<T>& operator=(const btAlignedObjectArray<T>& other)
    00057     {
    00058         copyFromArray(other);
    00059         return *this;
    00060     }
    00061 #else //BT_ALLOW_ARRAY_COPY_OPERATOR
    00062 private:
    00063     SIMD_FORCE_INLINE btAlignedObjectArray<T>& operator=(const btAlignedObjectArray<T>& other);
    00064 #endif //BT_ALLOW_ARRAY_COPY_OPERATOR
    00065
    00066 protected:
    00067     SIMD_FORCE_INLINE int32_t allocSize(int32_t size)
    00068     {
    00069         return (size ? size * 2 : 1);
    00070     }
    00071     SIMD_FORCE_INLINE void copy(int32_t start, int32_t end, T* dest) const
    00072     {
    00073         int32_t i;
    00074         for (i = start; i < end; ++i)
    00075 #ifdef BT_USE_PLACEMENT_NEW
    00076             new (&dest[i]) T(m_data[i]);
    00077 #else
    00078             dest[i] = m_data[i];
    00079 #endif //BT_USE_PLACEMENT_NEW
    00080     }
    00081
    00082     SIMD_FORCE_INLINE void init()
    00083     {
    00084         //PCK: added this line
    00085         m_ownsMemory = true;
    00086         m_data = 0;
    00087         m_size = 0;
    00088         m_capacity = 0;
    00089     }
    00090     SIMD_FORCE_INLINE void destroy(int32_t first, int32_t last)
    00091     {
    00092         int32_t i;
    00093         for (i = first; i < last; i++) {
    00094             m_data[i].~T();
    00095         }
    00096     }
    00097
    00098     SIMD_FORCE_INLINE void* allocate(int32_t size)
    00099     {
    00100         if (size)
    00101             return m_allocator.allocate(size);
    00102         return 0;
    00103     }
    00104
    00105     SIMD_FORCE_INLINE void deallocate()
    00106     {
    00107         if (m_data) {
    00108             //PCK: enclosed the deallocation in this block
    00109             if (m_ownsMemory) {
    00110                 m_allocator.deallocate(m_data);
    00111             }
    00112             m_data = 0;
    00113         }
    00114     }
    00115
    00116 public:
    00117     btAlignedObjectArray()
    00118     {
    00119         init();
    00120     }
    00121
    00122     ~btAlignedObjectArray()
    00123     {
    00124         clear();
    00125     }
    00126
    00128     btAlignedObjectArray(const btAlignedObjectArray& otherArray)
    00129     {
    00130         init();
    00131
    00132         int32_t otherSize = otherArray.size();
    00133         resize(otherSize);
    00134         otherArray.copy(0, otherSize, m_data);
    00135     }
    00136
    00138     SIMD_FORCE_INLINE int32_t size() const
    00139     {
    00140         return m_size;
    00141     }
    00142
    00143     SIMD_FORCE_INLINE const T& at(int32_t n) const
    00144     {
    00145         btAssert(n >= 0);
    00146         btAssert(n < size());
    00147         return m_data[n];
    00148     }
    00149
    00150     SIMD_FORCE_INLINE T& at(int32_t n)
    00151     {
    00152         btAssert(n >= 0);
    00153         btAssert(n < size());
    00154         return m_data[n];
    00155     }
    00156
    00157     SIMD_FORCE_INLINE const T& operator[](int32_t n) const
    00158     {
    00159         btAssert(n >= 0);
    00160         btAssert(n < size());
    00161         return m_data[n];
    00162     }
    00163
    00164     SIMD_FORCE_INLINE T& operator[](int32_t n)
    00165     {
    00166         btAssert(n >= 0);
    00167         btAssert(n < size());
    00168         return m_data[n];
    00169     }
    00170
    00172     SIMD_FORCE_INLINE void clear()
    00173     {
    00174         destroy(0, size());
    00175
    00176         deallocate();
    00177
    00178         init();
    00179     }
    00180
    00181     SIMD_FORCE_INLINE void pop_back()
    00182     {
    00183         btAssert(m_size > 0);
    00184         m_size--;
    00185         m_data[m_size].~T();
    00186     }
    00187
    00190     SIMD_FORCE_INLINE void resize(int32_t newsize, const T& fillData = T())
    00191     {
    00192         int32_t curSize = size();
    00193
    00194         if (newsize < curSize) {
    00195             for (int32_t i = newsize; i < curSize; i++) {
    00196                 m_data[i].~T();
    00197             }
    00198         }
    00199         else {
    00200             if (newsize > size()) {
    00201                 reserve(newsize);
    00202             }
    00203 #ifdef BT_USE_PLACEMENT_NEW
    00204             for (int32_t i = curSize; i < newsize; i++) {
    00205                 new (&m_data[i]) T(fillData);
    00206             }
    00207 #endif //BT_USE_PLACEMENT_NEW
    00208         }
    00209
    00210         m_size = newsize;
    00211     }
    00212
    00213     SIMD_FORCE_INLINE T& expandNonInitializing()
    00214     {
    00215         int32_t sz = size();
    00216         if (sz == capacity()) {
    00217             reserve(allocSize(size()));
    00218         }
    00219         m_size++;
    00220
    00221         return m_data[sz];
    00222     }
    00223
    00224     SIMD_FORCE_INLINE T& expand(const T& fillValue = T())
    00225     {
    00226         int32_t sz = size();
    00227         if (sz == capacity()) {
    00228             reserve(allocSize(size()));
    00229         }
    00230         m_size++;
    00231 #ifdef BT_USE_PLACEMENT_NEW
    00232         new (&m_data[sz]) T(fillValue); //use the in-place new (not really allocating heap memory)
    00233 #endif
    00234
    00235         return m_data[sz];
    00236     }
    00237
    00238     SIMD_FORCE_INLINE void push_back(const T& _Val)
    00239     {
    00240         int32_t sz = size();
    00241         if (sz == capacity()) {
    00242             reserve(allocSize(size()));
    00243         }
    00244
    00245 #ifdef BT_USE_PLACEMENT_NEW
    00246         new (&m_data[m_size]) T(_Val);
    00247 #else
    00248         m_data[size()] = _Val;
    00249 #endif //BT_USE_PLACEMENT_NEW
    00250
    00251         m_size++;
    00252     }
    00253
    00255     SIMD_FORCE_INLINE int32_t capacity() const
    00256     {
    00257         return m_capacity;
    00258     }
    00259
    00260     SIMD_FORCE_INLINE void reserve(int32_t _Count)
    00261     { // determine new minimum length of allocated storage
    00262         if (capacity() < _Count) { // not enough room, reallocate
    00263             T* s = (T*)allocate(_Count);
    00264
    00265             copy(0, size(), s);
    00266
    00267             destroy(0, size());
    00268
    00269             deallocate();
    00270
    00271             //PCK: added this line
    00272             m_ownsMemory = true;
    00273
    00274             m_data = s;
    00275
    00276             m_capacity = _Count;
    00277         }
    00278     }
    00279
    00280     class less {
    00281     public:
    00282         bool operator()(const T& a, const T& b)
    00283         {
    00284             return (a < b);
    00285         }
    00286     };
    00287
    00288     template <typename L>
    00289     void quickSortInternal(const L& CompareFunc, int32_t lo, int32_t hi)
    00290     {
    00291         //  lo is the lower index, hi is the upper index
    00292         //  of the region of array a that is to be sorted
    00293         int32_t i = lo, j = hi;
    00294         T x = m_data[(lo + hi) / 2];
    00295
    00296         //  partition
    00297         do {
    00298             while (CompareFunc(m_data[i], x))
    00299                 i++;
    00300             while (CompareFunc(x, m_data[j]))
    00301                 j--;
    00302             if (i <= j) {
    00303                 swap(i, j);
    00304                 i++;
    00305                 j--;
    00306             }
    00307         } while (i <= j);
    00308
    00309         //  recursion
    00310         if (lo < j)
    00311             quickSortInternal(CompareFunc, lo, j);
    00312         if (i < hi)
    00313             quickSortInternal(CompareFunc, i, hi);
    00314     }
    00315
    00316     template <typename L>
    00317     void quickSort(const L& CompareFunc)
    00318     {
    00319         //don't sort 0 or 1 elements
    00320         if (size() > 1) {
    00321             quickSortInternal(CompareFunc, 0, size() - 1);
    00322         }
    00323     }
    00324
    00326     template <typename L>
    00327     void downHeap(T* pArr, int32_t k, int32_t n, const L& CompareFunc)
    00328     {
    00329         /*  PRE: a[k+1..N] is a heap */
    00330         /* POST:  a[k..N]  is a heap */
    00331
    00332         T temp = pArr[k - 1];
    00333         /* k has child(s) */
    00334         while (k <= n / 2) {
    00335             int32_t child = 2 * k;
    00336
    00337             if ((child < n) && CompareFunc(pArr[child - 1], pArr[child])) {
    00338                 child++;
    00339             }
    00340             /* pick larger child */
    00341             if (CompareFunc(temp, pArr[child - 1])) {
    00342                 /* move child up */
    00343                 pArr[k - 1] = pArr[child - 1];
    00344                 k = child;
    00345             }
    00346             else {
    00347                 break;
    00348             }
    00349         }
    00350         pArr[k - 1] = temp;
    00351     } /*downHeap*/
    00352
    00353     void swap(int32_t index0, int32_t index1)
    00354     {
    00355 #ifdef BT_USE_MEMCPY
    00356         char temp[sizeof(T)];
    00357         memcpy(temp, &m_data[index0], sizeof(T));
    00358         memcpy(&m_data[index0], &m_data[index1], sizeof(T));
    00359         memcpy(&m_data[index1], temp, sizeof(T));
    00360 #else
    00361         T temp = m_data[index0];
    00362         m_data[index0] = m_data[index1];
    00363         m_data[index1] = temp;
    00364 #endif //BT_USE_PLACEMENT_NEW
    00365     }
    00366
    00367     template <typename L>
    00368     void heapSort(const L& CompareFunc)
    00369     {
    00370         /* sort a[0..N-1],  N.B. 0 to N-1 */
    00371         int32_t k;
    00372         int32_t n = m_size;
    00373         for (k = n / 2; k > 0; k--) {
    00374             downHeap(m_data, k, n, CompareFunc);
    00375         }
    00376
    00377         /* a[1..N] is now a heap */
    00378         while (n >= 1) {
    00379             swap(0, n - 1); /* largest of a[0..n-1] */
    00380
    00381             n = n - 1;
    00382             /* restore a[1..i-1] heap */
    00383             downHeap(m_data, 1, n, CompareFunc);
    00384         }
    00385     }
    00386
    00388     int32_t findBinarySearch(const T& key) const
    00389     {
    00390         int32_t first = 0;
    00391         int32_t last = size() - 1;
    00392
    00393         //assume sorted array
    00394         while (first <= last) {
    00395             int32_t mid = (first + last) / 2; // compute mid point.
    00396             if (key > m_data[mid])
    00397                 first = mid + 1; // repeat search in top half.
    00398             else if (key < m_data[mid])
    00399                 last = mid - 1; // repeat search in bottom half.
    00400             else
    00401                 return mid; // found it. return position /////
    00402         }
    00403         return size(); // failed to find key
    00404     }
    00405
    00406     int32_t findLinearSearch(const T& key) const
    00407     {
    00408         int32_t index = size();
    00409         int32_t i;
    00410
    00411         for (i = 0; i < size(); i++) {
    00412             if (m_data[i] == key) {
    00413                 index = i;
    00414                 break;
    00415             }
    00416         }
    00417         return index;
    00418     }
    00419
    00420     void remove(const T& key)
    00421     {
    00422
    00423         int32_t findIndex = findLinearSearch(key);
    00424         if (findIndex < size()) {
    00425             swap(findIndex, size() - 1);
    00426             pop_back();
    00427         }
    00428     }
    00429
    00430     //PCK: whole function
    00431     void initializeFromBuffer(void* buffer, int32_t size, int32_t capacity)
    00432     {
    00433         clear();
    00434         m_ownsMemory = false;
    00435         m_data = (T*)buffer;
    00436         m_size = size;
    00437         m_capacity = capacity;
    00438     }
    00439
    00440     void copyFromArray(const btAlignedObjectArray& otherArray)
    00441     {
    00442         int32_t otherSize = otherArray.size();
    00443         resize(otherSize);
    00444         otherArray.copy(0, otherSize, m_data);
    00445     }
    00446 };
    00447
    00448 #endif //BT_OBJECT_ARRAY__

Copyright © 2015-2017 NVIDIA Corporation, 2701 San Tomas Expressway, Santa Clara, CA 95050 U.S.A. All rights reserved. www.nvidia.com