← Back to branch summary

~ubuntu-branches/ubuntu/intrepid/blender/intrepid-updates

« back to all changes in this revision

Viewing changes to extern/bullet2/src/LinearMath/btAlignedObjectArray.h

  • Committer: Bazaar Package Importer
  • Author(s): Cyril Brulebois
  • Date: 2008-08-08 02:45:40 UTC
  • mfrom: (12.1.14 intrepid)
  • Revision ID: james.westby@ubuntu.com-20080808024540-kkjp7ekfivzhuw3l
Tags: 2.46+dfsg-4
http://bugs.debian.org/492280
* Fix python syntax warning in import_dxf.py, which led to nasty output
  in installation/upgrade logs during byte-compilation, using a patch
  provided by the script author (Closes: #492280):
   - debian/patches/45_fix_python_syntax_warning

Show diffs side-by-side

added added

removed removed

Lines of Context:
extern/bullet2/src/LinearMath/btAlignedObjectArray.h
 
1
/*
 
2
Bullet Continuous Collision Detection and Physics Library
 
3
Copyright (c) 2003-2006 Erwin Coumans  http://continuousphysics.com/Bullet/
 
4
 
 
5
This software is provided 'as-is', without any express or implied warranty.
 
6
In no event will the authors be held liable for any damages arising from the use of this software.
 
7
Permission is granted to anyone to use this software for any purpose, 
 
8
including commercial applications, and to alter it and redistribute it freely, 
 
9
subject to the following restrictions:
 
10
 
 
11
1. 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.
 
12
2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
 
13
3. 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
///btAlignedObjectArray uses a subset of the stl::vector interface for its methods
 
43
///It is developed to replace stl::vector to avoid STL alignment issues to add SIMD/SSE data
 
44
template <typename T> 
 
45
//template <class T> 
 
46
class btAlignedObjectArray
 
47
{
 
48
        btAlignedAllocator<T , 16>      m_allocator;
 
49
 
 
50
        int                                     m_size;
 
51
        int                                     m_capacity;
 
52
        T*                                      m_data;
 
53
 
 
54
        protected:
 
55
                SIMD_FORCE_INLINE       int     allocSize(int size)
 
56
                {
 
57
                        return (size ? size*2 : 1);
 
58
                }
 
59
                SIMD_FORCE_INLINE       void    copy(int start,int end, T* dest)
 
60
                {
 
61
                        int i;
 
62
                        for (i=start;i<end;++i)
 
63
#ifdef BT_USE_PLACEMENT_NEW
 
64
                                new (&dest[i]) T(m_data[i]);
 
65
#else
 
66
                                dest[i] = m_data[i];
 
67
#endif //BT_USE_PLACEMENT_NEW
 
68
                }
 
69
 
 
70
                SIMD_FORCE_INLINE       void    init()
 
71
                {
 
72
                        m_data = 0;
 
73
                        m_size = 0;
 
74
                        m_capacity = 0;
 
75
                }
 
76
                SIMD_FORCE_INLINE       void    destroy(int first,int last)
 
77
                {
 
78
                        int i;
 
79
                        for (i=first; i<last;i++)
 
80
                        {
 
81
                                m_data[i].~T();
 
82
                        }
 
83
                }
 
84
 
 
85
                SIMD_FORCE_INLINE       void* allocate(int size)
 
86
                {
 
87
                        if (size)
 
88
                                return m_allocator.allocate(size);
 
89
                        return 0;
 
90
                }
 
91
 
 
92
                SIMD_FORCE_INLINE       void    deallocate()
 
93
                {
 
94
                        if(m_data)      {
 
95
                                m_allocator.deallocate(m_data);
 
96
                                m_data = 0;
 
97
                        }
 
98
                }
 
99
 
 
100
        
 
101
 
 
102
 
 
103
        public:
 
104
                
 
105
                btAlignedObjectArray()
 
106
                {
 
107
                        init();
 
108
                }
 
109
 
 
110
                ~btAlignedObjectArray()
 
111
                {
 
112
                        clear();
 
113
                }
 
114
 
 
115
                SIMD_FORCE_INLINE       int capacity() const
 
116
                {       // return current length of allocated storage
 
117
                        return m_capacity;
 
118
                }
 
119
                
 
120
                SIMD_FORCE_INLINE       int size() const
 
121
                {       // return length of sequence
 
122
                        return m_size;
 
123
                }
 
124
                
 
125
                SIMD_FORCE_INLINE const T& operator[](int n) const
 
126
                {
 
127
                        return m_data[n];
 
128
                }
 
129
 
 
130
                SIMD_FORCE_INLINE T& operator[](int n)
 
131
                {
 
132
                        return m_data[n];
 
133
                }
 
134
                
 
135
 
 
136
                SIMD_FORCE_INLINE       void    clear()
 
137
                {
 
138
                        destroy(0,size());
 
139
                        
 
140
                        deallocate();
 
141
                        
 
142
                        init();
 
143
                }
 
144
 
 
145
                SIMD_FORCE_INLINE       void    pop_back()
 
146
                {
 
147
                        m_size--;
 
148
                        m_data[m_size].~T();
 
149
                }
 
150
 
 
151
                SIMD_FORCE_INLINE       void    resize(int newsize, const T& fillData=T())
 
152
                {
 
153
                        int curSize = size();
 
154
 
 
155
                        if (newsize < size())
 
156
                        {
 
157
                                for(int i = curSize; i < newsize; i++)
 
158
                                {
 
159
                                        m_data[i].~T();
 
160
                                }
 
161
                        } else
 
162
                        {
 
163
                                if (newsize > size())
 
164
                                {
 
165
                                        reserve(newsize);
 
166
                                }
 
167
#ifdef BT_USE_PLACEMENT_NEW
 
168
                                for (int i=curSize;i<newsize;i++)
 
169
                                {
 
170
                                        new ( &m_data[i]) T(fillData);
 
171
                                }
 
172
#endif //BT_USE_PLACEMENT_NEW
 
173
 
 
174
                        }
 
175
 
 
176
                        m_size = newsize;
 
177
                }
 
178
        
 
179
 
 
180
                SIMD_FORCE_INLINE       T&  expand( const T& fillValue=T())
 
181
                {       
 
182
                        int sz = size();
 
183
                        if( sz == capacity() )
 
184
                        {
 
185
                                reserve( allocSize(size()) );
 
186
                        }
 
187
                        m_size++;
 
188
#ifdef BT_USE_PLACEMENT_NEW
 
189
                        new (&m_data[sz]) T(fillValue); //use the in-place new (not really allocating heap memory)
 
190
#endif
 
191
 
 
192
                        return m_data[sz];              
 
193
                }
 
194
 
 
195
 
 
196
                SIMD_FORCE_INLINE       void push_back(const T& _Val)
 
197
                {       
 
198
                        int sz = size();
 
199
                        if( sz == capacity() )
 
200
                        {
 
201
                                reserve( allocSize(size()) );
 
202
                        }
 
203
                        
 
204
#ifdef BT_USE_PLACEMENT_NEW
 
205
                        new ( &m_data[m_size] ) T(_Val);
 
206
#else
 
207
                        m_data[size()] = _Val;                  
 
208
#endif //BT_USE_PLACEMENT_NEW
 
209
 
 
210
                        m_size++;
 
211
                }
 
212
 
 
213
        
 
214
                
 
215
                SIMD_FORCE_INLINE       void reserve(int _Count)
 
216
                {       // determine new minimum length of allocated storage
 
217
                        if (capacity() < _Count)
 
218
                        {       // not enough room, reallocate
 
219
                                T*      s = (T*)allocate(_Count);
 
220
 
 
221
                                copy(0, size(), s);
 
222
 
 
223
                                destroy(0,size());
 
224
 
 
225
                                deallocate();
 
226
 
 
227
                                m_data = s;
 
228
                                
 
229
                                m_capacity = _Count;
 
230
 
 
231
                        }
 
232
                }
 
233
 
 
234
 
 
235
                class less
 
236
                {
 
237
                        public:
 
238
 
 
239
                                bool operator() ( const T& a, const T& b )
 
240
                                {
 
241
                                        return ( a < b );
 
242
                                }
 
243
                };
 
244
        
 
245
 
 
246
                ///heap sort from http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Heap/
 
247
                template <typename L>
 
248
                void downHeap(T *pArr, int k, int n,L CompareFunc)
 
249
                {
 
250
                        /*  PRE: a[k+1..N] is a heap */
 
251
                        /* POST:  a[k..N]  is a heap */
 
252
                        
 
253
                        T temp = pArr[k - 1];
 
254
                        /* k has child(s) */
 
255
                        while (k <= n/2) 
 
256
                        {
 
257
                                int child = 2*k;
 
258
                                
 
259
                                if ((child < n) && CompareFunc(pArr[child - 1] , pArr[child]))
 
260
                                {
 
261
                                        child++;
 
262
                                }
 
263
                                /* pick larger child */
 
264
                                if (CompareFunc(temp , pArr[child - 1]))
 
265
                                {
 
266
                                        /* move child up */
 
267
                                        pArr[k - 1] = pArr[child - 1];
 
268
                                        k = child;
 
269
                                }
 
270
                                else
 
271
                                {
 
272
                                        break;
 
273
                                }
 
274
                        }
 
275
                        pArr[k - 1] = temp;
 
276
                } /*downHeap*/
 
277
 
 
278
                void    swap(int index0,int index1)
 
279
                {
 
280
#ifdef BT_USE_MEMCPY
 
281
                        char    temp[sizeof(T)];
 
282
                        memcpy(temp,&m_data[index0],sizeof(T));
 
283
                        memcpy(&m_data[index0],&m_data[index1],sizeof(T));
 
284
                        memcpy(&m_data[index1],temp,sizeof(T));
 
285
#else
 
286
                        T temp = m_data[index0];
 
287
                        m_data[index0] = m_data[index1];
 
288
                        m_data[index1] = temp;
 
289
#endif //BT_USE_PLACEMENT_NEW
 
290
 
 
291
                }
 
292
 
 
293
        template <typename L>
 
294
        void heapSort(L CompareFunc)
 
295
        {
 
296
                /* sort a[0..N-1],  N.B. 0 to N-1 */
 
297
                int k;
 
298
                int n = m_size;
 
299
                for (k = n/2; k > 0; k--) 
 
300
                {
 
301
                        downHeap(m_data, k, n, CompareFunc);
 
302
                }
 
303
 
 
304
                /* a[1..N] is now a heap */
 
305
                while ( n>=1 ) 
 
306
                {
 
307
                        swap(0,n-1); /* largest of a[0..n-1] */
 
308
 
 
309
 
 
310
                        n = n - 1;
 
311
                        /* restore a[1..i-1] heap */
 
312
                        downHeap(m_data, 1, n, CompareFunc);
 
313
                } 
 
314
        }
 
315
 
 
316
        ///non-recursive binary search, assumes sorted array
 
317
        int     findBinarySearch(const T& key) const
 
318
        {
 
319
                int first = 0;
 
320
                int last = size();
 
321
 
 
322
                //assume sorted array
 
323
                while (first <= last) {
 
324
                        int mid = (first + last) / 2;  // compute mid point.
 
325
                        if (key > m_data[mid]) 
 
326
                                first = mid + 1;  // repeat search in top half.
 
327
                        else if (key < m_data[mid]) 
 
328
                                last = mid - 1; // repeat search in bottom half.
 
329
                        else
 
330
                                return mid;     // found it. return position /////
 
331
                }
 
332
                return size();    // failed to find key
 
333
        }
 
334
 
 
335
 
 
336
        int     findLinearSearch(const T& key) const
 
337
        {
 
338
                int index=size();
 
339
                int i;
 
340
 
 
341
                for (i=0;i<size();i++)
 
342
                {
 
343
                        if (m_data[i] == key)
 
344
                        {
 
345
                                index = i;
 
346
                                break;
 
347
                        }
 
348
                }
 
349
                return index;
 
350
        }
 
351
 
 
352
        void    remove(const T& key)
 
353
        {
 
354
 
 
355
                int findIndex = findLinearSearch(key);
 
356
                if (findIndex<size())
 
357
                {
 
358
                        swap( findIndex,size()-1);
 
359
                        pop_back();
 
360
                }
 
361
        }
 
362
 
 
363
};
 
364
 
 
365
#endif //BT_OBJECT_ARRAY__
 
366
 
 
367