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

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

core: fix shitloads of compiler warnings in the Bullet source code.

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