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