dali-physics/third-party/bullet3/src/Bullet3Common/b3AlignedObjectArray.h

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