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

NVIDIA PhysX

previous page next page
E:/p4/sw/physx/PxShared/1.0/trunk/src/foundation/include/PsSort.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_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
1.5.8
previous page start next page