Main Page Class List Class Members

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