NVIDIA(R) PsFoundation Reference: E:/p4/sw/physx/PxShared/1.0/trunk/src/foundation/include/PsSortInternals.h Source File

NVIDIA PhysX

previous page next page
E:/p4/sw/physx/PxShared/1.0/trunk/src/foundation/include/PsSortInternals.h

00001 // This code contains NVIDIA Confidential Information and is disclosed to you
00002 // under a form of NVIDIA software license agreement provided separately to you.
00003 //
00004 // Notice
00005 // NVIDIA Corporation and its licensors retain all intellectual property and
00006 // proprietary rights in and to this software and related documentation and
00007 // any modifications thereto. Any use, reproduction, disclosure, or
00008 // distribution of this software and related documentation without an express
00009 // license agreement from NVIDIA Corporation is strictly prohibited.
00010 //
00011 // ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES
00012 // NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO
00013 // THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT,
00014 // MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE.
00015 //
00016 // Information and code furnished is believed to be accurate and reliable.
00017 // However, NVIDIA Corporation assumes no responsibility for the consequences of use of such
00018 // information or for any infringement of patents or other rights of third parties that may
00019 // result from its use. No license is granted by implication or otherwise under any patent
00020 // or patent rights of NVIDIA Corporation. Details are subject to change without notice.
00021 // This code supersedes and replaces all information previously supplied.
00022 // NVIDIA Corporation products are not authorized for use as critical
00023 // components in life support devices or systems without express written approval of
00024 // NVIDIA Corporation.
00025 //
00026 // Copyright (c) 2008-2014 NVIDIA Corporation. All rights reserved.
00027 // Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
00028 // Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
00029 
00030 #ifndef PSFOUNDATION_PSSORTINTERNALS_H
00031 #define PSFOUNDATION_PSSORTINTERNALS_H
00032 
00037 #include "foundation/PxAssert.h"
00038 #include "foundation/PxIntrinsics.h"
00039 #include "PsBasicTemplates.h"
00040 #include "PsUserAllocated.h"
00041 
00042 namespace physx
00043 {
00044 namespace shdfnd
00045 {
00046 namespace internal
00047 {
00048 template <class T, class Predicate>
00049 PX_INLINE void median3(T* elements, int32_t first, int32_t last, Predicate& compare)
00050 {
00051         /*
00052         This creates sentinels because we know there is an element at the start minimum(or equal)
00053         than the pivot and an element at the end greater(or equal) than the pivot. Plus the
00054         median of 3 reduces the chance of degenerate behavour.
00055         */
00056 
00057         int32_t mid = (first + last) / 2;
00058 
00059         if(compare(elements[mid], elements[first]))
00060                 swap(elements[first], elements[mid]);
00061 
00062         if(compare(elements[last], elements[first]))
00063                 swap(elements[first], elements[last]);
00064 
00065         if(compare(elements[last], elements[mid]))
00066                 swap(elements[mid], elements[last]);
00067 
00068         // keep the pivot at last-1
00069         swap(elements[mid], elements[last - 1]);
00070 }
00071 
00072 template <class T, class Predicate>
00073 PX_INLINE int32_t partition(T* elements, int32_t first, int32_t last, Predicate& compare)
00074 {
00075         median3(elements, first, last, compare);
00076 
00077         /*
00078         WARNING: using the line:
00079 
00080         T partValue = elements[last-1];
00081 
00082         and changing the scan loops to:
00083 
00084         while(comparator.greater(partValue, elements[++i]));
00085         while(comparator.greater(elements[--j], partValue);
00086 
00087         triggers a compiler optimizer bug on xenon where it stores a double to the stack for partValue
00088         then loads it as a single...:-(
00089         */
00090 
00091         int32_t i = first;    // we know first is less than pivot(but i gets pre incremented)
00092         int32_t j = last - 1; // pivot is in last-1 (but j gets pre decremented)
00093 
00094         for(;;)
00095         {
00096                 while(compare(elements[++i], elements[last - 1]))
00097                         ;
00098                 while(compare(elements[last - 1], elements[--j]))
00099                         ;
00100 
00101                 if(i >= j)
00102                         break;
00103 
00104                 PX_ASSERT(i <= last && j >= first);
00105                 swap(elements[i], elements[j]);
00106         }
00107         // put the pivot in place
00108 
00109         PX_ASSERT(i <= last && first <= (last - 1));
00110         swap(elements[i], elements[last - 1]);
00111 
00112         return i;
00113 }
00114 
00115 template <class T, class Predicate>
00116 PX_INLINE void smallSort(T* elements, int32_t first, int32_t last, Predicate& compare)
00117 {
00118         // selection sort - could reduce to fsel on 360 with floats.
00119 
00120         for(int32_t i = first; i < last; i++)
00121         {
00122                 int32_t m = i;
00123                 for(int32_t j = i + 1; j <= last; j++)
00124                         if(compare(elements[j], elements[m]))
00125                                 m = j;
00126 
00127                 if(m != i)
00128                         swap(elements[m], elements[i]);
00129         }
00130 }
00131 
00132 template <class Allocator>
00133 class Stack
00134 {
00135         Allocator mAllocator;
00136         uint32_t mSize, mCapacity;
00137         int32_t* mMemory;
00138         bool mRealloc;
00139 
00140   public:
00141         Stack(int32_t* memory, uint32_t capacity, const Allocator& inAllocator)
00142         : mAllocator(inAllocator), mSize(0), mCapacity(capacity), mMemory(memory), mRealloc(false)
00143         {
00144         }
00145         ~Stack()
00146         {
00147                 if(mRealloc)
00148                         mAllocator.deallocate(mMemory);
00149         }
00150 
00151         void grow()
00152         {
00153                 mCapacity *= 2;
00154                 int32_t* newMem = reinterpret_cast<int32_t*>(mAllocator.allocate(sizeof(int32_t) * mCapacity, __FILE__, __LINE__));
00155                 intrinsics::memCopy(newMem, mMemory, mSize * sizeof(int32_t));
00156                 if(mRealloc)
00157                         mAllocator.deallocate(mMemory);
00158                 mRealloc = true;
00159                 mMemory = newMem;
00160         }
00161 
00162         PX_INLINE void push(int32_t start, int32_t end)
00163         {
00164                 if(mSize >= mCapacity - 1)
00165                         grow();
00166                 mMemory[mSize++] = start;
00167                 mMemory[mSize++] = end;
00168         }
00169 
00170         PX_INLINE void pop(int32_t& start, int32_t& end)
00171         {
00172                 PX_ASSERT(!empty());
00173                 end = mMemory[--mSize];
00174                 start = mMemory[--mSize];
00175         }
00176 
00177         PX_INLINE bool empty()
00178         {
00179                 return mSize == 0;
00180         }
00181 };
00182 } // namespace internal
00183 
00184 } // namespace shdfnd
00185 } // namespace physx
00186 
00187 #endif // #ifndef PSFOUNDATION_PSSORTINTERNALS_H
Generated on Tue Jul 28 14:21:55 2015 for NVIDIA(R) PsFoundation Reference by
1.5.8
previous page start next page