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