Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: code/branches/kicklib/src/external/bullet/LinearMath/btAlignedObjectArray.h @ 8043

Last change on this file since 8043 was 7983, checked in by rgrieder, 14 years ago

Updated Bullet Physics Engine from v2.74 to v2.77
  • Property svn:eol-style set to native
File size: 10.0 KB
Line 
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) const
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                ///Generally it is best to avoid using the copy constructor of an btAlignedObjectArray, and use a (const) reference to the array instead.
124                btAlignedObjectArray(const btAlignedObjectArray& otherArray)
125                {
126                        init();
127
128                        int otherSize = otherArray.size();
129                        resize (otherSize);
130                        otherArray.copy(0, otherSize, m_data);
131                }
132
133               
134               
135                /// return the number of elements in the array
136                SIMD_FORCE_INLINE       int size() const
137                {       
138                        return m_size;
139                }
140               
141                SIMD_FORCE_INLINE const T& at(int n) const
142                {
143                        return m_data[n];
144                }
145
146                SIMD_FORCE_INLINE T& at(int n)
147                {
148                        return m_data[n];
149                }
150
151                SIMD_FORCE_INLINE const T& operator[](int n) const
152                {
153                        return m_data[n];
154                }
155
156                SIMD_FORCE_INLINE T& operator[](int n)
157                {
158                        return m_data[n];
159                }
160               
161
162                ///clear the array, deallocated memory. Generally it is better to use array.resize(0), to reduce performance overhead of run-time memory (de)allocations.
163                SIMD_FORCE_INLINE       void    clear()
164                {
165                        destroy(0,size());
166                       
167                        deallocate();
168                       
169                        init();
170                }
171
172                SIMD_FORCE_INLINE       void    pop_back()
173                {
174                        m_size--;
175                        m_data[m_size].~T();
176                }
177
178                ///resize changes the number of elements in the array. If the new size is larger, the new elements will be constructed using the optional second argument.
179                ///when the new number of elements is smaller, the destructor will be called, but memory will not be freed, to reduce performance overhead of run-time memory (de)allocations.
180                SIMD_FORCE_INLINE       void    resize(int newsize, const T& fillData=T())
181                {
182                        int curSize = size();
183
184                        if (newsize < curSize)
185                        {
186                                for(int i = newsize; i < curSize; i++)
187                                {
188                                        m_data[i].~T();
189                                }
190                        } else
191                        {
192                                if (newsize > size())
193                                {
194                                        reserve(newsize);
195                                }
196#ifdef BT_USE_PLACEMENT_NEW
197                                for (int i=curSize;i<newsize;i++)
198                                {
199                                        new ( &m_data[i]) T(fillData);
200                                }
201#endif //BT_USE_PLACEMENT_NEW
202
203                        }
204
205                        m_size = newsize;
206                }
207       
208                SIMD_FORCE_INLINE       T&  expandNonInitializing( )
209                {       
210                        int sz = size();
211                        if( sz == capacity() )
212                        {
213                                reserve( allocSize(size()) );
214                        }
215                        m_size++;
216
217                        return m_data[sz];             
218                }
219
220
221                SIMD_FORCE_INLINE       T&  expand( const T& fillValue=T())
222                {       
223                        int sz = size();
224                        if( sz == capacity() )
225                        {
226                                reserve( allocSize(size()) );
227                        }
228                        m_size++;
229#ifdef BT_USE_PLACEMENT_NEW
230                        new (&m_data[sz]) T(fillValue); //use the in-place new (not really allocating heap memory)
231#endif
232
233                        return m_data[sz];             
234                }
235
236
237                SIMD_FORCE_INLINE       void push_back(const T& _Val)
238                {       
239                        int sz = size();
240                        if( sz == capacity() )
241                        {
242                                reserve( allocSize(size()) );
243                        }
244                       
245#ifdef BT_USE_PLACEMENT_NEW
246                        new ( &m_data[m_size] ) T(_Val);
247#else
248                        m_data[size()] = _Val;                 
249#endif //BT_USE_PLACEMENT_NEW
250
251                        m_size++;
252                }
253
254       
255                /// return the pre-allocated (reserved) elements, this is at least as large as the total number of elements,see size() and reserve()
256                SIMD_FORCE_INLINE       int capacity() const
257                {       
258                        return m_capacity;
259                }
260               
261                SIMD_FORCE_INLINE       void reserve(int _Count)
262                {       // determine new minimum length of allocated storage
263                        if (capacity() < _Count)
264                        {       // not enough room, reallocate
265                                T*      s = (T*)allocate(_Count);
266
267                                copy(0, size(), s);
268
269                                destroy(0,size());
270
271                                deallocate();
272                               
273                                //PCK: added this line
274                                m_ownsMemory = true;
275
276                                m_data = s;
277                               
278                                m_capacity = _Count;
279
280                        }
281                }
282
283
284                class less
285                {
286                        public:
287
288                                bool operator() ( const T& a, const T& b )
289                                {
290                                        return ( a < b );
291                                }
292                };
293       
294                template <typename L>
295                void quickSortInternal(L CompareFunc,int lo, int hi)
296                {
297                //  lo is the lower index, hi is the upper index
298                //  of the region of array a that is to be sorted
299                        int i=lo, j=hi;
300                        T x=m_data[(lo+hi)/2];
301
302                        //  partition
303                        do
304                        {   
305                                while (CompareFunc(m_data[i],x)) 
306                                        i++; 
307                                while (CompareFunc(x,m_data[j])) 
308                                        j--;
309                                if (i<=j)
310                                {
311                                        swap(i,j);
312                                        i++; j--;
313                                }
314                        } while (i<=j);
315
316                        //  recursion
317                        if (lo<j) 
318                                quickSortInternal( CompareFunc, lo, j);
319                        if (i<hi) 
320                                quickSortInternal( CompareFunc, i, hi);
321                }
322
323
324                template <typename L>
325                void quickSort(L CompareFunc)
326                {
327                        //don't sort 0 or 1 elements
328                        if (size()>1)
329                        {
330                                quickSortInternal(CompareFunc,0,size()-1);
331                        }
332                }
333
334
335                ///heap sort from http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Heap/
336                template <typename L>
337                void downHeap(T *pArr, int k, int n,L CompareFunc)
338                {
339                        /*  PRE: a[k+1..N] is a heap */
340                        /* POST:  a[k..N]  is a heap */
341                       
342                        T temp = pArr[k - 1];
343                        /* k has child(s) */
344                        while (k <= n/2) 
345                        {
346                                int child = 2*k;
347                               
348                                if ((child < n) && CompareFunc(pArr[child - 1] , pArr[child]))
349                                {
350                                        child++;
351                                }
352                                /* pick larger child */
353                                if (CompareFunc(temp , pArr[child - 1]))
354                                {
355                                        /* move child up */
356                                        pArr[k - 1] = pArr[child - 1];
357                                        k = child;
358                                }
359                                else
360                                {
361                                        break;
362                                }
363                        }
364                        pArr[k - 1] = temp;
365                } /*downHeap*/
366
367                void    swap(int index0,int index1)
368                {
369#ifdef BT_USE_MEMCPY
370                        char    temp[sizeof(T)];
371                        memcpy(temp,&m_data[index0],sizeof(T));
372                        memcpy(&m_data[index0],&m_data[index1],sizeof(T));
373                        memcpy(&m_data[index1],temp,sizeof(T));
374#else
375                        T temp = m_data[index0];
376                        m_data[index0] = m_data[index1];
377                        m_data[index1] = temp;
378#endif //BT_USE_PLACEMENT_NEW
379
380                }
381
382        template <typename L>
383        void heapSort(L CompareFunc)
384        {
385                /* sort a[0..N-1],  N.B. 0 to N-1 */
386                int k;
387                int n = m_size;
388                for (k = n/2; k > 0; k--) 
389                {
390                        downHeap(m_data, k, n, CompareFunc);
391                }
392
393                /* a[1..N] is now a heap */
394                while ( n>=1 ) 
395                {
396                        swap(0,n-1); /* largest of a[0..n-1] */
397
398
399                        n = n - 1;
400                        /* restore a[1..i-1] heap */
401                        downHeap(m_data, 1, n, CompareFunc);
402                } 
403        }
404
405        ///non-recursive binary search, assumes sorted array
406        int     findBinarySearch(const T& key) const
407        {
408                int first = 0;
409                int last = size();
410
411                //assume sorted array
412                while (first <= last) {
413                        int mid = (first + last) / 2;  // compute mid point.
414                        if (key > m_data[mid]) 
415                                first = mid + 1;  // repeat search in top half.
416                        else if (key < m_data[mid]) 
417                                last = mid - 1; // repeat search in bottom half.
418                        else
419                                return mid;     // found it. return position /////
420                }
421                return size();    // failed to find key
422        }
423
424
425        int     findLinearSearch(const T& key) const
426        {
427                int index=size();
428                int i;
429
430                for (i=0;i<size();i++)
431                {
432                        if (m_data[i] == key)
433                        {
434                                index = i;
435                                break;
436                        }
437                }
438                return index;
439        }
440
441        void    remove(const T& key)
442        {
443
444                int findIndex = findLinearSearch(key);
445                if (findIndex<size())
446                {
447                        swap( findIndex,size()-1);
448                        pop_back();
449                }
450        }
451
452        //PCK: whole function
453        void initializeFromBuffer(void *buffer, int size, int capacity)
454        {
455                clear();
456                m_ownsMemory = false;
457                m_data = (T*)buffer;
458                m_size = size;
459                m_capacity = capacity;
460        }
461
462        void copyFromArray(const btAlignedObjectArray& otherArray)
463        {
464                int otherSize = otherArray.size();
465                resize (otherSize);
466                otherArray.copy(0, otherSize, m_data);
467        }
468
469};
470
471#endif //BT_OBJECT_ARRAY__
Note: See TracBrowser for help on using the repository browser.