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