Back to index

supertuxkart  0.5+dfsg1
Classes | Public Member Functions | Protected Member Functions | Private Attributes
btAlignedObjectArray< T > Class Template Reference

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 More...

#include <btAlignedObjectArray.h>

Inheritance diagram for btAlignedObjectArray< T >:
Inheritance graph
[legend]
Collaboration diagram for btAlignedObjectArray< T >:
Collaboration graph
[legend]

List of all members.

Classes

class  less

Public Member Functions

 btAlignedObjectArray ()
 ~btAlignedObjectArray ()
SIMD_FORCE_INLINE int capacity () const
SIMD_FORCE_INLINE int size () const
SIMD_FORCE_INLINE const T & operator[] (int n) const
SIMD_FORCE_INLINE T & operator[] (int n)
SIMD_FORCE_INLINE void clear ()
SIMD_FORCE_INLINE void pop_back ()
SIMD_FORCE_INLINE void resize (int newsize, const T &fillData=T())
SIMD_FORCE_INLINE T & expand (const T &fillValue=T())
SIMD_FORCE_INLINE void push_back (const T &_Val)
SIMD_FORCE_INLINE void reserve (int _Count)
template<typename L >
void quickSortInternal (L CompareFunc, int lo, int hi)
template<typename L >
void quickSort (L CompareFunc)
template<typename L >
void downHeap (T *pArr, int k, int n, L CompareFunc)
 heap sort from http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Heap/
void swap (int index0, int index1)
template<typename L >
void heapSort (L CompareFunc)
int findBinarySearch (const T &key) const
 non-recursive binary search, assumes sorted array
int findLinearSearch (const T &key) const
void remove (const T &key)
void initializeFromBuffer (void *buffer, int size, int capacity)

Protected Member Functions

SIMD_FORCE_INLINE int allocSize (int size)
SIMD_FORCE_INLINE void copy (int start, int end, T *dest)
SIMD_FORCE_INLINE void init ()
SIMD_FORCE_INLINE void destroy (int first, int last)
SIMD_FORCE_INLINE void * allocate (int size)
SIMD_FORCE_INLINE void deallocate ()

Private Attributes

btAlignedAllocator< T, 16 > m_allocator
int m_size
int m_capacity
T * m_data
bool m_ownsMemory

Detailed Description

template<typename T>
class btAlignedObjectArray< T >

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

Definition at line 46 of file btAlignedObjectArray.h.


Constructor & Destructor Documentation

template<typename T>
btAlignedObjectArray< T >::btAlignedObjectArray ( ) [inline]

Definition at line 113 of file btAlignedObjectArray.h.

              {
                     init();
              }
template<typename T>
btAlignedObjectArray< T >::~btAlignedObjectArray ( ) [inline]

Definition at line 118 of file btAlignedObjectArray.h.

              {
                     clear();
              }

Member Function Documentation

template<typename T>
SIMD_FORCE_INLINE void* btAlignedObjectArray< T >::allocate ( int  size) [inline, protected]

Definition at line 89 of file btAlignedObjectArray.h.

              {
                     if (size)
                            return m_allocator.allocate(size);
                     return 0;
              }

Here is the caller graph for this function:

template<typename T>
SIMD_FORCE_INLINE int btAlignedObjectArray< T >::allocSize ( int  size) [inline, protected]

Definition at line 57 of file btAlignedObjectArray.h.

              {
                     return (size ? size*2 : 1);
              }

Here is the caller graph for this function:

template<typename T>
SIMD_FORCE_INLINE int btAlignedObjectArray< T >::capacity ( ) const [inline]

Definition at line 123 of file btAlignedObjectArray.h.

              {      // return current length of allocated storage
                     return m_capacity;
              }

Here is the caller graph for this function:

template<typename T>
SIMD_FORCE_INLINE void btAlignedObjectArray< T >::clear ( ) [inline]

Definition at line 144 of file btAlignedObjectArray.h.

              {
                     destroy(0,size());
                     
                     deallocate();
                     
                     init();
              }

Here is the caller graph for this function:

template<typename T>
SIMD_FORCE_INLINE void btAlignedObjectArray< T >::copy ( int  start,
int  end,
T *  dest 
) [inline, protected]

Definition at line 61 of file btAlignedObjectArray.h.

              {
                     int 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
              }

Here is the caller graph for this function:

template<typename T>
SIMD_FORCE_INLINE void btAlignedObjectArray< T >::deallocate ( ) [inline, protected]

Definition at line 96 of file btAlignedObjectArray.h.

              {
                     if(m_data)    {
                            //PCK: enclosed the deallocation in this block
                            if (m_ownsMemory)
                            {
                                   m_allocator.deallocate(m_data);
                            }
                            m_data = 0;
                     }
              }

Here is the caller graph for this function:

template<typename T>
SIMD_FORCE_INLINE void btAlignedObjectArray< T >::destroy ( int  first,
int  last 
) [inline, protected]

Definition at line 80 of file btAlignedObjectArray.h.

              {
                     int i;
                     for (i=first; i<last;i++)
                     {
                            m_data[i].~T();
                     }
              }

Here is the caller graph for this function:

template<typename T>
template<typename L >
void btAlignedObjectArray< T >::downHeap ( T *  pArr,
int  k,
int  n,
CompareFunc 
) [inline]

heap sort from http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Heap/

Definition at line 299 of file btAlignedObjectArray.h.

              {
                     /*  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*/

Here is the caller graph for this function:

template<typename T>
SIMD_FORCE_INLINE T& btAlignedObjectArray< T >::expand ( const T &  fillValue = T()) [inline]

Definition at line 188 of file btAlignedObjectArray.h.

              {      
                     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];          
              }

Here is the caller graph for this function:

template<typename T>
int btAlignedObjectArray< T >::findBinarySearch ( const T &  key) const [inline]

non-recursive binary search, assumes sorted array

Definition at line 368 of file btAlignedObjectArray.h.

       {
              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
       }
template<typename T>
int btAlignedObjectArray< T >::findLinearSearch ( const T &  key) const [inline]

Definition at line 387 of file btAlignedObjectArray.h.

       {
              int index=size();
              int i;

              for (i=0;i<size();i++)
              {
                     if (m_data[i] == key)
                     {
                            index = i;
                            break;
                     }
              }
              return index;
       }

Here is the caller graph for this function:

template<typename T>
template<typename L >
void btAlignedObjectArray< T >::heapSort ( CompareFunc) [inline]

Definition at line 345 of file btAlignedObjectArray.h.

       {
              /* 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);
              } 
       }
template<typename T>
SIMD_FORCE_INLINE void btAlignedObjectArray< T >::init ( ) [inline, protected]

Definition at line 72 of file btAlignedObjectArray.h.

              {
                     //PCK: added this line
                     m_ownsMemory = true;
                     m_data = 0;
                     m_size = 0;
                     m_capacity = 0;
              }

Here is the caller graph for this function:

template<typename T>
void btAlignedObjectArray< T >::initializeFromBuffer ( void *  buffer,
int  size,
int  capacity 
) [inline]

Definition at line 415 of file btAlignedObjectArray.h.

       {
              clear();
              m_ownsMemory = false;
              m_data = (T*)buffer;
              m_size = size;
              m_capacity = capacity;
       }
template<typename T>
SIMD_FORCE_INLINE const T& btAlignedObjectArray< T >::operator[] ( int  n) const [inline]

Definition at line 133 of file btAlignedObjectArray.h.

              {
                     return m_data[n];
              }
template<typename T>
SIMD_FORCE_INLINE T& btAlignedObjectArray< T >::operator[] ( int  n) [inline]

Definition at line 138 of file btAlignedObjectArray.h.

              {
                     return m_data[n];
              }
template<typename T>
SIMD_FORCE_INLINE void btAlignedObjectArray< T >::pop_back ( ) [inline]

Definition at line 153 of file btAlignedObjectArray.h.

              {
                     m_size--;
                     m_data[m_size].~T();
              }

Here is the caller graph for this function:

template<typename T>
SIMD_FORCE_INLINE void btAlignedObjectArray< T >::push_back ( const T &  _Val) [inline]

Definition at line 204 of file btAlignedObjectArray.h.

              {      
                     int sz = size();
                     if( sz == capacity() )
                     {
                            reserve( allocSize(size()) );
                     }
                     
#ifdef BT_USE_PLACEMENT_NEW
                     new ( &m_data[m_size] ) T(_Val);
#else
                     m_data[size()] = _Val;                    
#endif //BT_USE_PLACEMENT_NEW

                     m_size++;
              }

Here is the caller graph for this function:

template<typename T>
template<typename L >
void btAlignedObjectArray< T >::quickSort ( CompareFunc) [inline]

Definition at line 287 of file btAlignedObjectArray.h.

              {
                     //don't sort 0 or 1 elements
                     if (size()>1)
                     {
                            quickSortInternal(CompareFunc,0,size()-1);
                     }
              }

Here is the caller graph for this function:

template<typename T>
template<typename L >
void btAlignedObjectArray< T >::quickSortInternal ( CompareFunc,
int  lo,
int  hi 
) [inline]

Definition at line 257 of file btAlignedObjectArray.h.

              {
              //  lo is the lower index, hi is the upper index
              //  of the region of array a that is to be sorted
                     int i=lo, j=hi;
                     T x=m_data[(lo+hi)/2];

                     //  partition
                     do
                     {    
                            while (CompareFunc(m_data[i],x)) 
                                   i++; 
                            while (CompareFunc(x,m_data[j])) 
                                   j--;
                            if (i<=j)
                            {
                                   swap(i,j);
                                   i++; j--;
                            }
                     } while (i<=j);

                     //  recursion
                     if (lo<j) 
                            quickSortInternal( CompareFunc, lo, j);
                     if (i<hi) 
                            quickSortInternal( CompareFunc, i, hi);
              }

Here is the caller graph for this function:

template<typename T>
void btAlignedObjectArray< T >::remove ( const T &  key) [inline]

Definition at line 403 of file btAlignedObjectArray.h.

       {

              int findIndex = findLinearSearch(key);
              if (findIndex<size())
              {
                     swap( findIndex,size()-1);
                     pop_back();
              }
       }

Here is the caller graph for this function:

template<typename T>
SIMD_FORCE_INLINE void btAlignedObjectArray< T >::reserve ( int  _Count) [inline]

Definition at line 223 of file btAlignedObjectArray.h.

              {      // determine new minimum length of allocated storage
                     if (capacity() < _Count)
                     {      // not enough room, reallocate
                            T*     s = (T*)allocate(_Count);

                            copy(0, size(), s);

                            destroy(0,size());

                            deallocate();
                            
                            //PCK: added this line
                            m_ownsMemory = true;

                            m_data = s;
                            
                            m_capacity = _Count;

                     }
              }

Here is the caller graph for this function:

template<typename T>
SIMD_FORCE_INLINE void btAlignedObjectArray< T >::resize ( int  newsize,
const T &  fillData = T() 
) [inline]

Definition at line 159 of file btAlignedObjectArray.h.

              {
                     int curSize = size();

                     if (newsize < size())
                     {
                            for(int i = curSize; i < newsize; i++)
                            {
                                   m_data[i].~T();
                            }
                     } else
                     {
                            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;
              }

Here is the caller graph for this function:

template<typename T>
SIMD_FORCE_INLINE int btAlignedObjectArray< T >::size ( ) const [inline]

Definition at line 128 of file btAlignedObjectArray.h.

              {      // return length of sequence
                     return m_size;
              }
template<typename T>
void btAlignedObjectArray< T >::swap ( int  index0,
int  index1 
) [inline]

Definition at line 329 of file btAlignedObjectArray.h.

              {
#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

              }

Here is the caller graph for this function:


Member Data Documentation

template<typename T>
btAlignedAllocator<T , 16> btAlignedObjectArray< T >::m_allocator [private]

Definition at line 48 of file btAlignedObjectArray.h.

template<typename T>
int btAlignedObjectArray< T >::m_capacity [private]

Definition at line 51 of file btAlignedObjectArray.h.

template<typename T>
T* btAlignedObjectArray< T >::m_data [private]

Definition at line 52 of file btAlignedObjectArray.h.

template<typename T>
bool btAlignedObjectArray< T >::m_ownsMemory [private]

Definition at line 54 of file btAlignedObjectArray.h.

template<typename T>
int btAlignedObjectArray< T >::m_size [private]

Definition at line 50 of file btAlignedObjectArray.h.


The documentation for this class was generated from the following file: