Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: code/trunk/src/bullet/LinearMath/btAlignedObjectArray.h @ 2835

Last change on this file since 2835 was 2662, checked in by rgrieder, 16 years ago

Merged presentation branch back to trunk.

  • Property svn:eol-style set to native
File size: 8.6 KB
RevLine 
[1963]1/*
2Bullet Continuous Collision Detection and Physics Library
3Copyright (c) 2003-2006 Erwin Coumans  http://continuousphysics.com/Bullet/
4
5This software is provided 'as-is', without any express or implied warranty.
6In no event will the authors be held liable for any damages arising from the use of this software.
7Permission is granted to anyone to use this software for any purpose,
8including commercial applications, and to alter it and redistribute it freely,
9subject to the following restrictions:
10
111. 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.
122. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
133. 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
23///If the platform doesn't support placement new, you can disable BT_USE_PLACEMENT_NEW
24///then the btAlignedObjectArray doesn't support objects with virtual methods, and non-trivial constructors/destructors
25///You can enable BT_USE_MEMCPY, then swapping elements in the array will use memcpy instead of operator=
26///see discussion here: http://continuousphysics.com/Bullet/phpBB2/viewtopic.php?t=1231 and
27///http://www.continuousphysics.com/Bullet/phpBB2/viewtopic.php?t=1240
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
32#ifdef BT_USE_MEMCPY
33#include <memory.h>
34#include <string.h>
35#endif //BT_USE_MEMCPY
36
37#ifdef BT_USE_PLACEMENT_NEW
38#include <new> //for placement new
39#endif //BT_USE_PLACEMENT_NEW
40
41
42///The btAlignedObjectArray template class uses a subset of the stl::vector interface for its methods
43///It is developed to replace stl::vector to avoid portability issues, including STL alignment issues to add SIMD/SSE data
44template <typename T> 
45//template <class T>
46class btAlignedObjectArray
47{
48        btAlignedAllocator<T , 16>      m_allocator;
49
50        int                                     m_size;
51        int                                     m_capacity;
52        T*                                      m_data;
53        //PCK: added this line
54        bool                            m_ownsMemory;
55
56        protected:
57                SIMD_FORCE_INLINE       int     allocSize(int size)
58                {
59                        return (size ? size*2 : 1);
60                }
61                SIMD_FORCE_INLINE       void    copy(int start,int end, T* dest)
62                {
63                        int i;
64                        for (i=start;i<end;++i)
65#ifdef BT_USE_PLACEMENT_NEW
66                                new (&dest[i]) T(m_data[i]);
67#else
68                                dest[i] = m_data[i];
69#endif //BT_USE_PLACEMENT_NEW
70                }
71
72                SIMD_FORCE_INLINE       void    init()
73                {
74                        //PCK: added this line
75                        m_ownsMemory = true;
76                        m_data = 0;
77                        m_size = 0;
78                        m_capacity = 0;
79                }
80                SIMD_FORCE_INLINE       void    destroy(int first,int last)
81                {
82                        int i;
83                        for (i=first; i<last;i++)
84                        {
85                                m_data[i].~T();
86                        }
87                }
88
89                SIMD_FORCE_INLINE       void* allocate(int size)
90                {
91                        if (size)
92                                return m_allocator.allocate(size);
93                        return 0;
94                }
95
96                SIMD_FORCE_INLINE       void    deallocate()
97                {
98                        if(m_data)      {
99                                //PCK: enclosed the deallocation in this block
100                                if (m_ownsMemory)
101                                {
102                                        m_allocator.deallocate(m_data);
103                                }
104                                m_data = 0;
105                        }
106                }
107
108       
109
110
111        public:
112               
113                btAlignedObjectArray()
114                {
115                        init();
116                }
117
118                ~btAlignedObjectArray()
119                {
120                        clear();
121                }
122
123                SIMD_FORCE_INLINE       int capacity() const
124                {       // return current length of allocated storage
125                        return m_capacity;
126                }
127               
128                SIMD_FORCE_INLINE       int size() const
129                {       // return length of sequence
130                        return m_size;
131                }
132               
133                SIMD_FORCE_INLINE const T& operator[](int n) const
134                {
135                        return m_data[n];
136                }
137
138                SIMD_FORCE_INLINE T& operator[](int n)
139                {
140                        return m_data[n];
141                }
142               
143
144                SIMD_FORCE_INLINE       void    clear()
145                {
146                        destroy(0,size());
147                       
148                        deallocate();
149                       
150                        init();
151                }
152
153                SIMD_FORCE_INLINE       void    pop_back()
154                {
155                        m_size--;
156                        m_data[m_size].~T();
157                }
158
159                SIMD_FORCE_INLINE       void    resize(int newsize, const T& fillData=T())
160                {
161                        int curSize = size();
162
163                        if (newsize < size())
164                        {
165                                for(int i = curSize; i < newsize; i++)
166                                {
167                                        m_data[i].~T();
168                                }
169                        } else
170                        {
171                                if (newsize > size())
172                                {
173                                        reserve(newsize);
174                                }
175#ifdef BT_USE_PLACEMENT_NEW
176                                for (int i=curSize;i<newsize;i++)
177                                {
178                                        new ( &m_data[i]) T(fillData);
179                                }
180#endif //BT_USE_PLACEMENT_NEW
181
182                        }
183
184                        m_size = newsize;
185                }
186       
187
188                SIMD_FORCE_INLINE       T&  expand( const T& fillValue=T())
189                {       
190                        int sz = size();
191                        if( sz == capacity() )
192                        {
193                                reserve( allocSize(size()) );
194                        }
195                        m_size++;
196#ifdef BT_USE_PLACEMENT_NEW
197                        new (&m_data[sz]) T(fillValue); //use the in-place new (not really allocating heap memory)
198#endif
199
200                        return m_data[sz];             
201                }
202
203
204                SIMD_FORCE_INLINE       void push_back(const T& _Val)
205                {       
206                        int sz = size();
207                        if( sz == capacity() )
208                        {
209                                reserve( allocSize(size()) );
210                        }
211                       
212#ifdef BT_USE_PLACEMENT_NEW
213                        new ( &m_data[m_size] ) T(_Val);
214#else
215                        m_data[size()] = _Val;                 
216#endif //BT_USE_PLACEMENT_NEW
217
218                        m_size++;
219                }
220
221       
222               
223                SIMD_FORCE_INLINE       void reserve(int _Count)
224                {       // determine new minimum length of allocated storage
225                        if (capacity() < _Count)
226                        {       // not enough room, reallocate
227                                T*      s = (T*)allocate(_Count);
228
229                                copy(0, size(), s);
230
231                                destroy(0,size());
232
233                                deallocate();
234                               
235                                //PCK: added this line
236                                m_ownsMemory = true;
237
238                                m_data = s;
239                               
240                                m_capacity = _Count;
241
242                        }
243                }
244
245
246                class less
247                {
248                        public:
249
250                                bool operator() ( const T& a, const T& b )
251                                {
252                                        return ( a < b );
253                                }
254                };
255       
256                template <typename L>
257                void quickSortInternal(L CompareFunc,int lo, int hi)
258                {
259                //  lo is the lower index, hi is the upper index
260                //  of the region of array a that is to be sorted
261                        int i=lo, j=hi;
262                        T x=m_data[(lo+hi)/2];
263
264                        //  partition
265                        do
266                        {   
267                                while (CompareFunc(m_data[i],x)) 
268                                        i++; 
269                                while (CompareFunc(x,m_data[j])) 
270                                        j--;
271                                if (i<=j)
272                                {
273                                        swap(i,j);
274                                        i++; j--;
275                                }
276                        } while (i<=j);
277
278                        //  recursion
279                        if (lo<j) 
280                                quickSortInternal( CompareFunc, lo, j);
281                        if (i<hi) 
282                                quickSortInternal( CompareFunc, i, hi);
283                }
284
285
286                template <typename L>
287                void quickSort(L CompareFunc)
288                {
289                        //don't sort 0 or 1 elements
290                        if (size()>1)
291                        {
292                                quickSortInternal(CompareFunc,0,size()-1);
293                        }
294                }
295
296
297                ///heap sort from http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Heap/
298                template <typename L>
299                void downHeap(T *pArr, int k, int n,L CompareFunc)
300                {
301                        /*  PRE: a[k+1..N] is a heap */
302                        /* POST:  a[k..N]  is a heap */
303                       
304                        T temp = pArr[k - 1];
305                        /* k has child(s) */
306                        while (k <= n/2) 
307                        {
308                                int child = 2*k;
309                               
310                                if ((child < n) && CompareFunc(pArr[child - 1] , pArr[child]))
311                                {
312                                        child++;
313                                }
314                                /* pick larger child */
315                                if (CompareFunc(temp , pArr[child - 1]))
316                                {
317                                        /* move child up */
318                                        pArr[k - 1] = pArr[child - 1];
319                                        k = child;
320                                }
321                                else
322                                {
323                                        break;
324                                }
325                        }
326                        pArr[k - 1] = temp;
327                } /*downHeap*/
328
329                void    swap(int index0,int index1)
330                {
331#ifdef BT_USE_MEMCPY
332                        char    temp[sizeof(T)];
333                        memcpy(temp,&m_data[index0],sizeof(T));
334                        memcpy(&m_data[index0],&m_data[index1],sizeof(T));
335                        memcpy(&m_data[index1],temp,sizeof(T));
336#else
337                        T temp = m_data[index0];
338                        m_data[index0] = m_data[index1];
339                        m_data[index1] = temp;
340#endif //BT_USE_PLACEMENT_NEW
341
342                }
343
344        template <typename L>
345        void heapSort(L CompareFunc)
346        {
347                /* sort a[0..N-1],  N.B. 0 to N-1 */
348                int k;
349                int n = m_size;
350                for (k = n/2; k > 0; k--) 
351                {
352                        downHeap(m_data, k, n, CompareFunc);
353                }
354
355                /* a[1..N] is now a heap */
356                while ( n>=1 ) 
357                {
358                        swap(0,n-1); /* largest of a[0..n-1] */
359
360
361                        n = n - 1;
362                        /* restore a[1..i-1] heap */
363                        downHeap(m_data, 1, n, CompareFunc);
364                } 
365        }
366
367        ///non-recursive binary search, assumes sorted array
368        int     findBinarySearch(const T& key) const
369        {
370                int first = 0;
371                int last = size();
372
373                //assume sorted array
374                while (first <= last) {
375                        int mid = (first + last) / 2;  // compute mid point.
376                        if (key > m_data[mid]) 
377                                first = mid + 1;  // repeat search in top half.
378                        else if (key < m_data[mid]) 
379                                last = mid - 1; // repeat search in bottom half.
380                        else
381                                return mid;     // found it. return position /////
382                }
383                return size();    // failed to find key
384        }
385
386
387        int     findLinearSearch(const T& key) const
388        {
389                int index=size();
390                int i;
391
392                for (i=0;i<size();i++)
393                {
394                        if (m_data[i] == key)
395                        {
396                                index = i;
397                                break;
398                        }
399                }
400                return index;
401        }
402
403        void    remove(const T& key)
404        {
405
406                int findIndex = findLinearSearch(key);
407                if (findIndex<size())
408                {
409                        swap( findIndex,size()-1);
410                        pop_back();
411                }
412        }
413
414        //PCK: whole function
415        void initializeFromBuffer(void *buffer, int size, int capacity)
416        {
417                clear();
418                m_ownsMemory = false;
419                m_data = (T*)buffer;
420                m_size = size;
421                m_capacity = capacity;
422        }
423
424};
425
426#endif //BT_OBJECT_ARRAY__
Note: See TracBrowser for help on using the repository browser.