Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: code/branches/sound3/src/external/bullet/LinearMath/btAlignedObjectArray.h @ 6165

Last change on this file since 6165 was 5781, checked in by rgrieder, 15 years ago

Reverted trunk again. We might want to find a way to delete these revisions again (x3n's changes are still available as diff in the commit mails).

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