E:/p4/sw/physx/PxShared/1.0/trunk/src/foundation/include/PsSortInternals.h
Go to the documentation of this file.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
![doxygen](doxygen.png)