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#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 --
42namespace 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
47template <typename T>
48//template <class T>
49class 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
59public:
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
66private:
67 SIMD_FORCE_INLINE btAlignedObjectArray<T>& operator=(const btAlignedObjectArray<T>& other);
68#endif //BT_ALLOW_ARRAY_COPY_OPERATOR
69
70protected:
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
120public:
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