E:/p4/sw/physx/PxShared/1.0/trunk/src/foundation/include/PsSort.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_PSSORT_H 00031 #define PSFOUNDATION_PSSORT_H 00032 00037 #include "PsSortInternals.h" 00038 #include "PsAlloca.h" 00039 00040 #define PX_SORT_PARANOIA PX_DEBUG 00041 00049 #if PX_VC 00050 #pragma warning(push) 00051 #pragma warning(disable : 4706) // disable the warning that we did an assignment within a conditional expression, as 00052 // this was intentional. 00053 #endif 00054 00055 namespace physx 00056 { 00057 namespace shdfnd 00058 { 00059 template <class T, class Predicate, class Allocator> 00060 void sort(T* elements, uint32_t count, const Predicate& compare, const Allocator& inAllocator, 00061 const uint32_t initialStackSize = 32) 00062 { 00063 static const uint32_t SMALL_SORT_CUTOFF = 5; // must be >= 3 since we need 3 for median 00064 00065 PX_ALLOCA(stackMem, int32_t, initialStackSize); 00066 internal::Stack<Allocator> stack(stackMem, initialStackSize, inAllocator); 00067 00068 int32_t first = 0, last = int32_t(count - 1); 00069 if(last > first) 00070 { 00071 for(;;) 00072 { 00073 while(last > first) 00074 { 00075 PX_ASSERT(first >= 0 && last < int32_t(count)); 00076 if(uint32_t(last - first) < SMALL_SORT_CUTOFF) 00077 { 00078 internal::smallSort(elements, first, last, compare); 00079 break; 00080 } 00081 else 00082 { 00083 const int32_t partIndex = internal::partition(elements, first, last, compare); 00084 00085 // push smaller sublist to minimize stack usage 00086 if((partIndex - first) < (last - partIndex)) 00087 { 00088 stack.push(first, partIndex - 1); 00089 first = partIndex + 1; 00090 } 00091 else 00092 { 00093 stack.push(partIndex + 1, last); 00094 last = partIndex - 1; 00095 } 00096 } 00097 } 00098 00099 if(stack.empty()) 00100 break; 00101 00102 stack.pop(first, last); 00103 } 00104 } 00105 #if PX_SORT_PARANOIA 00106 for(uint32_t i = 1; i < count; i++) 00107 PX_ASSERT(!compare(elements[i], elements[i - 1])); 00108 #endif 00109 } 00110 00111 template <class T, class Predicate> 00112 void sort(T* elements, uint32_t count, const Predicate& compare) 00113 { 00114 sort(elements, count, compare, typename shdfnd::AllocatorTraits<T>::Type()); 00115 } 00116 00117 template <class T> 00118 void sort(T* elements, uint32_t count) 00119 { 00120 sort(elements, count, shdfnd::Less<T>(), typename shdfnd::AllocatorTraits<T>::Type()); 00121 } 00122 00123 } // namespace shdfnd 00124 } // namespace physx 00125 00126 #if PX_VC 00127 #pragma warning(pop) 00128 #endif 00129 00130 #endif // #ifndef PSFOUNDATION_PSSORT_H
Generated on Tue Jul 28 14:21:55 2015 for NVIDIA(R) PsFoundation Reference by
![doxygen](doxygen.png)