1//
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions
4// are met:
5// * Redistributions of source code must retain the above copyright
6// notice, this list of conditions and the following disclaimer.
7// * Redistributions in binary form must reproduce the above copyright
8// notice, this list of conditions and the following disclaimer in the
9// documentation and/or other materials provided with the distribution.
10// * Neither the name of NVIDIA CORPORATION nor the names of its
11// contributors may be used to endorse or promote products derived
12// from this software without specific prior written permission.
13//
14// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS ''AS IS'' AND ANY
15// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
18// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22// OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25//
26// Copyright (c) 2008-2021 NVIDIA Corporation. All rights reserved.
27// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
28// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
29
30#ifndef PSFOUNDATION_PSSORT_H
31#define PSFOUNDATION_PSSORT_H
32
33/** \addtogroup foundation
34@{
35*/
36
37#include "PsSortInternals.h"
38#include "PsAlloca.h"
39
40#define PX_SORT_PARANOIA PX_DEBUG
41
42/**
43\brief Sorts an array of objects in ascending order, assuming
44that the predicate implements the < operator:
45
46\see Less, Greater
47*/
48
49#if PX_VC
50#pragma warning(push)
51#pragma warning(disable : 4706) // disable the warning that we did an assignment within a conditional expression, as
52// this was intentional.
53#endif
54
55namespace physx
56{
57namespace shdfnd
58{
59template <class T, class Predicate, class Allocator>
60void sort(T* elements, uint32_t count, const Predicate& compare, const Allocator& inAllocator,
61 const uint32_t initialStackSize = 32)
62{
63 static const uint32_t SMALL_SORT_CUTOFF = 5; // must be >= 3 since we need 3 for median
64
65 PX_ALLOCA(stackMem, int32_t, initialStackSize);
66 internal::Stack<Allocator> stack(stackMem, initialStackSize, inAllocator);
67
68 int32_t first = 0, last = int32_t(count - 1);
69 if(last > first)
70 {
71 for(;;)
72 {
73 while(last > first)
74 {
75 PX_ASSERT(first >= 0 && last < int32_t(count));
76 if(uint32_t(last - first) < SMALL_SORT_CUTOFF)
77 {
78 internal::smallSort(elements, first, last, compare);
79 break;
80 }
81 else
82 {
83 const int32_t partIndex = internal::partition(elements, first, last, compare);
84
85 // push smaller sublist to minimize stack usage
86 if((partIndex - first) < (last - partIndex))
87 {
88 stack.push(first, partIndex - 1);
89 first = partIndex + 1;
90 }
91 else
92 {
93 stack.push(partIndex + 1, last);
94 last = partIndex - 1;
95 }
96 }
97 }
98
99 if(stack.empty())
100 break;
101
102 stack.pop(first, last);
103 }
104 }
105#if PX_SORT_PARANOIA
106 for(uint32_t i = 1; i < count; i++)
107 PX_ASSERT(!compare(elements[i], elements[i - 1]));
108#endif
109}
110
111template <class T, class Predicate>
112void sort(T* elements, uint32_t count, const Predicate& compare)
113{
114 sort(elements, count, compare, typename shdfnd::AllocatorTraits<T>::Type());
115}
116
117template <class T>
118void sort(T* elements, uint32_t count)
119{
120 sort(elements, count, shdfnd::Less<T>(), typename shdfnd::AllocatorTraits<T>::Type());
121}
122
123} // namespace shdfnd
124} // namespace physx
125
126#if PX_VC
127#pragma warning(pop)
128#endif
129
130#endif // #ifndef PSFOUNDATION_PSSORT_H
131

source code of qtquick3dphysics/src/3rdparty/PhysX/source/foundation/include/PsSort.h