source: trunk/src/bullet/LinearMath/btAlignedObjectArray.h @ 1570

Last change on this file since 1570 was 1570, checked in by sam, 9 years ago

core: add the whole BulletPhysics source code to the engine core, because
that’s precisely how they want us to use it.

  • Property svn:keywords set to Id
File size: 10.7 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#define BT_ALLOW_ARRAY_COPY_OPERATOR // enabling this can accidently perform deep copies of data if you are not careful
32
33#ifdef BT_USE_MEMCPY
34#include <memory.h>
35#include <string.h>
36#endif //BT_USE_MEMCPY
37
38#ifdef BT_USE_PLACEMENT_NEW
39#include <new> //for placement new
40#endif //BT_USE_PLACEMENT_NEW
41
42
43///The btAlignedObjectArray template class uses a subset of the stl::vector interface for its methods
44///It is developed to replace stl::vector to avoid portability issues, including STL alignment issues to add SIMD/SSE data
45template <typename T>
46//template <class T>
47class btAlignedObjectArray
48{
49        btAlignedAllocator<T , 16>      m_allocator;
50
51        int                                     m_size;
52        int                                     m_capacity;
53        T*                                      m_data;
54        //PCK: added this line
55        bool                            m_ownsMemory;
56
57#ifdef BT_ALLOW_ARRAY_COPY_OPERATOR
58public:
59        SIMD_FORCE_INLINE btAlignedObjectArray<T>& operator=(const btAlignedObjectArray<T> &other)
60        {
61                copyFromArray(other);
62                return *this;
63        }
64#else//BT_ALLOW_ARRAY_COPY_OPERATOR
65private:
66                SIMD_FORCE_INLINE btAlignedObjectArray<T>& operator=(const btAlignedObjectArray<T> &other);
67#endif//BT_ALLOW_ARRAY_COPY_OPERATOR
68
69protected:
70                SIMD_FORCE_INLINE       int     allocSize(int size)
71                {
72                        return (size ? size*2 : 1);
73                }
74                SIMD_FORCE_INLINE       void    copy(int start,int end, T* dest) const
75                {
76                        int i;
77                        for (i=start;i<end;++i)
78#ifdef BT_USE_PLACEMENT_NEW
79                                new (&dest[i]) T(m_data[i]);
80#else
81                                dest[i] = m_data[i];
82#endif //BT_USE_PLACEMENT_NEW
83                }
84
85                SIMD_FORCE_INLINE       void    init()
86                {
87                        //PCK: added this line
88                        m_ownsMemory = true;
89                        m_data = 0;
90                        m_size = 0;
91                        m_capacity = 0;
92                }
93                SIMD_FORCE_INLINE       void    destroy(int first,int last)
94                {
95                        int i;
96                        for (i=first; i<last;i++)
97                        {
98                                m_data[i].~T();
99                        }
100                }
101
102                SIMD_FORCE_INLINE       void* allocate(int size)
103                {
104                        if (size)
105                                return m_allocator.allocate(size);
106                        return 0;
107                }
108
109                SIMD_FORCE_INLINE       void    deallocate()
110                {
111                        if(m_data)      {
112                                //PCK: enclosed the deallocation in this block
113                                if (m_ownsMemory)
114                                {
115                                        m_allocator.deallocate(m_data);
116                                }
117                                m_data = 0;
118                        }
119                }
120
121       
122
123
124        public:
125               
126                btAlignedObjectArray()
127                {
128                        init();
129                }
130
131                ~btAlignedObjectArray()
132                {
133                        clear();
134                }
135
136                ///Generally it is best to avoid using the copy constructor of an btAlignedObjectArray, and use a (const) reference to the array instead.
137                btAlignedObjectArray(const btAlignedObjectArray& otherArray)
138                {
139                        init();
140
141                        int otherSize = otherArray.size();
142                        resize (otherSize);
143                        otherArray.copy(0, otherSize, m_data);
144                }
145
146               
147               
148                /// return the number of elements in the array
149                SIMD_FORCE_INLINE       int size() const
150                {       
151                        return m_size;
152                }
153               
154                SIMD_FORCE_INLINE const T& at(int n) const
155                {
156                        btAssert(n>=0);
157                        btAssert(n<size());
158                        return m_data[n];
159                }
160
161                SIMD_FORCE_INLINE T& at(int n)
162                {
163                        btAssert(n>=0);
164                        btAssert(n<size());
165                        return m_data[n];
166                }
167
168                SIMD_FORCE_INLINE const T& operator[](int n) const
169                {
170                        btAssert(n>=0);
171                        btAssert(n<size());
172                        return m_data[n];
173                }
174
175                SIMD_FORCE_INLINE T& operator[](int n)
176                {
177                        btAssert(n>=0);
178                        btAssert(n<size());
179                        return m_data[n];
180                }
181               
182
183                ///clear the array, deallocated memory. Generally it is better to use array.resize(0), to reduce performance overhead of run-time memory (de)allocations.
184                SIMD_FORCE_INLINE       void    clear()
185                {
186                        destroy(0,size());
187                       
188                        deallocate();
189                       
190                        init();
191                }
192
193                SIMD_FORCE_INLINE       void    pop_back()
194                {
195                        btAssert(m_size>0);
196                        m_size--;
197                        m_data[m_size].~T();
198                }
199
200                ///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.
201                ///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.
202                SIMD_FORCE_INLINE       void    resize(int newsize, const T& fillData=T())
203                {
204                        int curSize = size();
205
206                        if (newsize < curSize)
207                        {
208                                for(int i = newsize; i < curSize; i++)
209                                {
210                                        m_data[i].~T();
211                                }
212                        } else
213                        {
214                                if (newsize > size())
215                                {
216                                        reserve(newsize);
217                                }
218#ifdef BT_USE_PLACEMENT_NEW
219                                for (int i=curSize;i<newsize;i++)
220                                {
221                                        new ( &m_data[i]) T(fillData);
222                                }
223#endif //BT_USE_PLACEMENT_NEW
224
225                        }
226
227                        m_size = newsize;
228                }
229       
230                SIMD_FORCE_INLINE       T&  expandNonInitializing( )
231                {       
232                        int sz = size();
233                        if( sz == capacity() )
234                        {
235                                reserve( allocSize(size()) );
236                        }
237                        m_size++;
238
239                        return m_data[sz];             
240                }
241
242
243                SIMD_FORCE_INLINE       T&  expand( const T& fillValue=T())
244                {       
245                        int sz = size();
246                        if( sz == capacity() )
247                        {
248                                reserve( allocSize(size()) );
249                        }
250                        m_size++;
251#ifdef BT_USE_PLACEMENT_NEW
252                        new (&m_data[sz]) T(fillValue); //use the in-place new (not really allocating heap memory)
253#endif
254
255                        return m_data[sz];             
256                }
257
258
259                SIMD_FORCE_INLINE       void push_back(const T& _Val)
260                {       
261                        int sz = size();
262                        if( sz == capacity() )
263                        {
264                                reserve( allocSize(size()) );
265                        }
266                       
267#ifdef BT_USE_PLACEMENT_NEW
268                        new ( &m_data[m_size] ) T(_Val);
269#else
270                        m_data[size()] = _Val;                 
271#endif //BT_USE_PLACEMENT_NEW
272
273                        m_size++;
274                }
275
276       
277                /// return the pre-allocated (reserved) elements, this is at least as large as the total number of elements,see size() and reserve()
278                SIMD_FORCE_INLINE       int capacity() const
279                {       
280                        return m_capacity;
281                }
282               
283                SIMD_FORCE_INLINE       void reserve(int _Count)
284                {       // determine new minimum length of allocated storage
285                        if (capacity() < _Count)
286                        {       // not enough room, reallocate
287                                T*      s = (T*)allocate(_Count);
288
289                                copy(0, size(), s);
290
291                                destroy(0,size());
292
293                                deallocate();
294                               
295                                //PCK: added this line
296                                m_ownsMemory = true;
297
298                                m_data = s;
299                               
300                                m_capacity = _Count;
301
302                        }
303                }
304
305
306                class less
307                {
308                        public:
309
310                                bool operator() ( const T& a, const T& b )
311                                {
312                                        return ( a < b );
313                                }
314                };
315       
316
317                template <typename L>
318                void quickSortInternal(const L& CompareFunc,int lo, int hi)
319                {
320                //  lo is the lower index, hi is the upper index
321                //  of the region of array a that is to be sorted
322                        int i=lo, j=hi;
323                        T x=m_data[(lo+hi)/2];
324
325                        //  partition
326                        do
327                        {   
328                                while (CompareFunc(m_data[i],x))
329                                        i++;
330                                while (CompareFunc(x,m_data[j]))
331                                        j--;
332                                if (i<=j)
333                                {
334                                        swap(i,j);
335                                        i++; j--;
336                                }
337                        } while (i<=j);
338
339                        //  recursion
340                        if (lo<j)
341                                quickSortInternal( CompareFunc, lo, j);
342                        if (i<hi)
343                                quickSortInternal( CompareFunc, i, hi);
344                }
345
346
347                template <typename L>
348                void quickSort(const L& CompareFunc)
349                {
350                        //don't sort 0 or 1 elements
351                        if (size()>1)
352                        {
353                                quickSortInternal(CompareFunc,0,size()-1);
354                        }
355                }
356
357
358                ///heap sort from http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Heap/
359                template <typename L>
360                void downHeap(T *pArr, int k, int n, const L& CompareFunc)
361                {
362                        /*  PRE: a[k+1..N] is a heap */
363                        /* POST:  a[k..N]  is a heap */
364                       
365                        T temp = pArr[k - 1];
366                        /* k has child(s) */
367                        while (k <= n/2)
368                        {
369                                int child = 2*k;
370                               
371                                if ((child < n) && CompareFunc(pArr[child - 1] , pArr[child]))
372                                {
373                                        child++;
374                                }
375                                /* pick larger child */
376                                if (CompareFunc(temp , pArr[child - 1]))
377                                {
378                                        /* move child up */
379                                        pArr[k - 1] = pArr[child - 1];
380                                        k = child;
381                                }
382                                else
383                                {
384                                        break;
385                                }
386                        }
387                        pArr[k - 1] = temp;
388                } /*downHeap*/
389
390                void    swap(int index0,int index1)
391                {
392#ifdef BT_USE_MEMCPY
393                        char    temp[sizeof(T)];
394                        memcpy(temp,&m_data[index0],sizeof(T));
395                        memcpy(&m_data[index0],&m_data[index1],sizeof(T));
396                        memcpy(&m_data[index1],temp,sizeof(T));
397#else
398                        T temp = m_data[index0];
399                        m_data[index0] = m_data[index1];
400                        m_data[index1] = temp;
401#endif //BT_USE_PLACEMENT_NEW
402
403                }
404
405        template <typename L>
406        void heapSort(const L& CompareFunc)
407        {
408                /* sort a[0..N-1],  N.B. 0 to N-1 */
409                int k;
410                int n = m_size;
411                for (k = n/2; k > 0; k--)
412                {
413                        downHeap(m_data, k, n, CompareFunc);
414                }
415
416                /* a[1..N] is now a heap */
417                while ( n>=1 )
418                {
419                        swap(0,n-1); /* largest of a[0..n-1] */
420
421
422                        n = n - 1;
423                        /* restore a[1..i-1] heap */
424                        downHeap(m_data, 1, n, CompareFunc);
425                }
426        }
427
428        ///non-recursive binary search, assumes sorted array
429        int     findBinarySearch(const T& key) const
430        {
431                int first = 0;
432                int last = size()-1;
433
434                //assume sorted array
435                while (first <= last) {
436                        int mid = (first + last) / 2;  // compute mid point.
437                        if (key > m_data[mid])
438                                first = mid + 1;  // repeat search in top half.
439                        else if (key < m_data[mid])
440                                last = mid - 1; // repeat search in bottom half.
441                        else
442                                return mid;     // found it. return position /////
443                }
444                return size();    // failed to find key
445        }
446
447
448        int     findLinearSearch(const T& key) const
449        {
450                int index=size();
451                int i;
452
453                for (i=0;i<size();i++)
454                {
455                        if (m_data[i] == key)
456                        {
457                                index = i;
458                                break;
459                        }
460                }
461                return index;
462        }
463
464        void    remove(const T& key)
465        {
466
467                int findIndex = findLinearSearch(key);
468                if (findIndex<size())
469                {
470                        swap( findIndex,size()-1);
471                        pop_back();
472                }
473        }
474
475        //PCK: whole function
476        void initializeFromBuffer(void *buffer, int size, int capacity)
477        {
478                clear();
479                m_ownsMemory = false;
480                m_data = (T*)buffer;
481                m_size = size;
482                m_capacity = capacity;
483        }
484
485        void copyFromArray(const btAlignedObjectArray& otherArray)
486        {
487                int otherSize = otherArray.size();
488                resize (otherSize);
489                otherArray.copy(0, otherSize, m_data);
490        }
491
492};
493
494#endif //BT_OBJECT_ARRAY__
Note: See TracBrowser for help on using the repository browser.