Back to index

supertuxkart  0.5+dfsg1
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 
00017 #ifndef BT_OBJECT_ARRAY__
00018 #define BT_OBJECT_ARRAY__
00019 
00020 #include "btScalar.h" // has definitions like SIMD_FORCE_INLINE
00021 #include "btAlignedAllocator.h"
00022 
00028 
00029 #define BT_USE_PLACEMENT_NEW 1
00030 //#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...
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 
00041 
00044 template <typename T> 
00045 //template <class T> 
00046 class btAlignedObjectArray
00047 {
00048        btAlignedAllocator<T , 16>  m_allocator;
00049 
00050        int                                m_size;
00051        int                                m_capacity;
00052        T*                                 m_data;
00053        //PCK: added this line
00054        bool                        m_ownsMemory;
00055 
00056        protected:
00057               SIMD_FORCE_INLINE    int    allocSize(int size)
00058               {
00059                      return (size ? size*2 : 1);
00060               }
00061               SIMD_FORCE_INLINE    void   copy(int start,int end, T* dest)
00062               {
00063                      int i;
00064                      for (i=start;i<end;++i)
00065 #ifdef BT_USE_PLACEMENT_NEW
00066                             new (&dest[i]) T(m_data[i]);
00067 #else
00068                             dest[i] = m_data[i];
00069 #endif //BT_USE_PLACEMENT_NEW
00070               }
00071 
00072               SIMD_FORCE_INLINE    void   init()
00073               {
00074                      //PCK: added this line
00075                      m_ownsMemory = true;
00076                      m_data = 0;
00077                      m_size = 0;
00078                      m_capacity = 0;
00079               }
00080               SIMD_FORCE_INLINE    void   destroy(int first,int last)
00081               {
00082                      int i;
00083                      for (i=first; i<last;i++)
00084                      {
00085                             m_data[i].~T();
00086                      }
00087               }
00088 
00089               SIMD_FORCE_INLINE    void* allocate(int size)
00090               {
00091                      if (size)
00092                             return m_allocator.allocate(size);
00093                      return 0;
00094               }
00095 
00096               SIMD_FORCE_INLINE    void   deallocate()
00097               {
00098                      if(m_data)    {
00099                             //PCK: enclosed the deallocation in this block
00100                             if (m_ownsMemory)
00101                             {
00102                                    m_allocator.deallocate(m_data);
00103                             }
00104                             m_data = 0;
00105                      }
00106               }
00107 
00108        
00109 
00110 
00111        public:
00112               
00113               btAlignedObjectArray()
00114               {
00115                      init();
00116               }
00117 
00118               ~btAlignedObjectArray()
00119               {
00120                      clear();
00121               }
00122 
00123               SIMD_FORCE_INLINE    int capacity() const
00124               {      // return current length of allocated storage
00125                      return m_capacity;
00126               }
00127               
00128               SIMD_FORCE_INLINE    int size() const
00129               {      // return length of sequence
00130                      return m_size;
00131               }
00132               
00133               SIMD_FORCE_INLINE const T& operator[](int n) const
00134               {
00135                      return m_data[n];
00136               }
00137 
00138               SIMD_FORCE_INLINE T& operator[](int n)
00139               {
00140                      return m_data[n];
00141               }
00142               
00143 
00144               SIMD_FORCE_INLINE    void   clear()
00145               {
00146                      destroy(0,size());
00147                      
00148                      deallocate();
00149                      
00150                      init();
00151               }
00152 
00153               SIMD_FORCE_INLINE    void   pop_back()
00154               {
00155                      m_size--;
00156                      m_data[m_size].~T();
00157               }
00158 
00159               SIMD_FORCE_INLINE    void   resize(int newsize, const T& fillData=T())
00160               {
00161                      int curSize = size();
00162 
00163                      if (newsize < size())
00164                      {
00165                             for(int i = curSize; i < newsize; i++)
00166                             {
00167                                    m_data[i].~T();
00168                             }
00169                      } else
00170                      {
00171                             if (newsize > size())
00172                             {
00173                                    reserve(newsize);
00174                             }
00175 #ifdef BT_USE_PLACEMENT_NEW
00176                             for (int i=curSize;i<newsize;i++)
00177                             {
00178                                    new ( &m_data[i]) T(fillData);
00179                             }
00180 #endif //BT_USE_PLACEMENT_NEW
00181 
00182                      }
00183 
00184                      m_size = newsize;
00185               }
00186        
00187 
00188               SIMD_FORCE_INLINE    T&  expand( const T& fillValue=T())
00189               {      
00190                      int sz = size();
00191                      if( sz == capacity() )
00192                      {
00193                             reserve( allocSize(size()) );
00194                      }
00195                      m_size++;
00196 #ifdef BT_USE_PLACEMENT_NEW
00197                      new (&m_data[sz]) T(fillValue); //use the in-place new (not really allocating heap memory)
00198 #endif
00199 
00200                      return m_data[sz];          
00201               }
00202 
00203 
00204               SIMD_FORCE_INLINE    void push_back(const T& _Val)
00205               {      
00206                      int sz = size();
00207                      if( sz == capacity() )
00208                      {
00209                             reserve( allocSize(size()) );
00210                      }
00211                      
00212 #ifdef BT_USE_PLACEMENT_NEW
00213                      new ( &m_data[m_size] ) T(_Val);
00214 #else
00215                      m_data[size()] = _Val;                    
00216 #endif //BT_USE_PLACEMENT_NEW
00217 
00218                      m_size++;
00219               }
00220 
00221        
00222               
00223               SIMD_FORCE_INLINE    void reserve(int _Count)
00224               {      // determine new minimum length of allocated storage
00225                      if (capacity() < _Count)
00226                      {      // not enough room, reallocate
00227                             T*     s = (T*)allocate(_Count);
00228 
00229                             copy(0, size(), s);
00230 
00231                             destroy(0,size());
00232 
00233                             deallocate();
00234                             
00235                             //PCK: added this line
00236                             m_ownsMemory = true;
00237 
00238                             m_data = s;
00239                             
00240                             m_capacity = _Count;
00241 
00242                      }
00243               }
00244 
00245 
00246               class less
00247               {
00248                      public:
00249 
00250                             bool operator() ( const T& a, const T& b )
00251                             {
00252                                    return ( a < b );
00253                             }
00254               };
00255        
00256               template <typename L>
00257               void quickSortInternal(L CompareFunc,int lo, int hi)
00258               {
00259               //  lo is the lower index, hi is the upper index
00260               //  of the region of array a that is to be sorted
00261                      int i=lo, j=hi;
00262                      T x=m_data[(lo+hi)/2];
00263 
00264                      //  partition
00265                      do
00266                      {    
00267                             while (CompareFunc(m_data[i],x)) 
00268                                    i++; 
00269                             while (CompareFunc(x,m_data[j])) 
00270                                    j--;
00271                             if (i<=j)
00272                             {
00273                                    swap(i,j);
00274                                    i++; j--;
00275                             }
00276                      } while (i<=j);
00277 
00278                      //  recursion
00279                      if (lo<j) 
00280                             quickSortInternal( CompareFunc, lo, j);
00281                      if (i<hi) 
00282                             quickSortInternal( CompareFunc, i, hi);
00283               }
00284 
00285 
00286               template <typename L>
00287               void quickSort(L CompareFunc)
00288               {
00289                      //don't sort 0 or 1 elements
00290                      if (size()>1)
00291                      {
00292                             quickSortInternal(CompareFunc,0,size()-1);
00293                      }
00294               }
00295 
00296 
00298               template <typename L>
00299               void downHeap(T *pArr, int k, int n,L CompareFunc)
00300               {
00301                      /*  PRE: a[k+1..N] is a heap */
00302                      /* POST:  a[k..N]  is a heap */
00303                      
00304                      T temp = pArr[k - 1];
00305                      /* k has child(s) */
00306                      while (k <= n/2) 
00307                      {
00308                             int child = 2*k;
00309                             
00310                             if ((child < n) && CompareFunc(pArr[child - 1] , pArr[child]))
00311                             {
00312                                    child++;
00313                             }
00314                             /* pick larger child */
00315                             if (CompareFunc(temp , pArr[child - 1]))
00316                             {
00317                                    /* move child up */
00318                                    pArr[k - 1] = pArr[child - 1];
00319                                    k = child;
00320                             }
00321                             else
00322                             {
00323                                    break;
00324                             }
00325                      }
00326                      pArr[k - 1] = temp;
00327               } /*downHeap*/
00328 
00329               void   swap(int index0,int index1)
00330               {
00331 #ifdef BT_USE_MEMCPY
00332                      char   temp[sizeof(T)];
00333                      memcpy(temp,&m_data[index0],sizeof(T));
00334                      memcpy(&m_data[index0],&m_data[index1],sizeof(T));
00335                      memcpy(&m_data[index1],temp,sizeof(T));
00336 #else
00337                      T temp = m_data[index0];
00338                      m_data[index0] = m_data[index1];
00339                      m_data[index1] = temp;
00340 #endif //BT_USE_PLACEMENT_NEW
00341 
00342               }
00343 
00344        template <typename L>
00345        void heapSort(L CompareFunc)
00346        {
00347               /* sort a[0..N-1],  N.B. 0 to N-1 */
00348               int k;
00349               int n = m_size;
00350               for (k = n/2; k > 0; k--) 
00351               {
00352                      downHeap(m_data, k, n, CompareFunc);
00353               }
00354 
00355               /* a[1..N] is now a heap */
00356               while ( n>=1 ) 
00357               {
00358                      swap(0,n-1); /* largest of a[0..n-1] */
00359 
00360 
00361                      n = n - 1;
00362                      /* restore a[1..i-1] heap */
00363                      downHeap(m_data, 1, n, CompareFunc);
00364               } 
00365        }
00366 
00368        int    findBinarySearch(const T& key) const
00369        {
00370               int first = 0;
00371               int last = size();
00372 
00373               //assume sorted array
00374               while (first <= last) {
00375                      int mid = (first + last) / 2;  // compute mid point.
00376                      if (key > m_data[mid]) 
00377                             first = mid + 1;  // repeat search in top half.
00378                      else if (key < m_data[mid]) 
00379                             last = mid - 1; // repeat search in bottom half.
00380                      else
00381                             return mid;     // found it. return position /////
00382               }
00383               return size();    // failed to find key
00384        }
00385 
00386 
00387        int    findLinearSearch(const T& key) const
00388        {
00389               int index=size();
00390               int i;
00391 
00392               for (i=0;i<size();i++)
00393               {
00394                      if (m_data[i] == key)
00395                      {
00396                             index = i;
00397                             break;
00398                      }
00399               }
00400               return index;
00401        }
00402 
00403        void   remove(const T& key)
00404        {
00405 
00406               int findIndex = findLinearSearch(key);
00407               if (findIndex<size())
00408               {
00409                      swap( findIndex,size()-1);
00410                      pop_back();
00411               }
00412        }
00413 
00414        //PCK: whole function
00415        void initializeFromBuffer(void *buffer, int size, int capacity)
00416        {
00417               clear();
00418               m_ownsMemory = false;
00419               m_data = (T*)buffer;
00420               m_size = size;
00421               m_capacity = capacity;
00422        }
00423 
00424 };
00425 
00426 #endif //BT_OBJECT_ARRAY__