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_PSSORTINTERNALS_H
31#define PSFOUNDATION_PSSORTINTERNALS_H
32
33/** \addtogroup foundation
34@{
35*/
36
37#include "foundation/PxAssert.h"
38#include "foundation/PxIntrinsics.h"
39#include "PsBasicTemplates.h"
40#include "PsUserAllocated.h"
41
42namespace physx
43{
44namespace shdfnd
45{
46namespace internal
47{
48template <class T, class Predicate>
49PX_INLINE void median3(T* elements, int32_t first, int32_t last, Predicate& compare)
50{
51 /*
52 This creates sentinels because we know there is an element at the start minimum(or equal)
53 than the pivot and an element at the end greater(or equal) than the pivot. Plus the
54 median of 3 reduces the chance of degenerate behavour.
55 */
56
57 int32_t mid = (first + last) / 2;
58
59 if(compare(elements[mid], elements[first]))
60 swap(elements[first], elements[mid]);
61
62 if(compare(elements[last], elements[first]))
63 swap(elements[first], elements[last]);
64
65 if(compare(elements[last], elements[mid]))
66 swap(elements[mid], elements[last]);
67
68 // keep the pivot at last-1
69 swap(elements[mid], elements[last - 1]);
70}
71
72template <class T, class Predicate>
73PX_INLINE int32_t partition(T* elements, int32_t first, int32_t last, Predicate& compare)
74{
75 median3(elements, first, last, compare);
76
77 /*
78 WARNING: using the line:
79
80 T partValue = elements[last-1];
81
82 and changing the scan loops to:
83
84 while(comparator.greater(partValue, elements[++i]));
85 while(comparator.greater(elements[--j], partValue);
86
87 triggers a compiler optimizer bug on xenon where it stores a double to the stack for partValue
88 then loads it as a single...:-(
89 */
90
91 int32_t i = first; // we know first is less than pivot(but i gets pre incremented)
92 int32_t j = last - 1; // pivot is in last-1 (but j gets pre decremented)
93
94 for(;;)
95 {
96 while(compare(elements[++i], elements[last - 1]))
97 ;
98 while(compare(elements[last - 1], elements[--j]))
99 ;
100
101 if(i >= j)
102 break;
103
104 PX_ASSERT(i <= last && j >= first);
105 swap(elements[i], elements[j]);
106 }
107 // put the pivot in place
108
109 PX_ASSERT(i <= last && first <= (last - 1));
110 swap(elements[i], elements[last - 1]);
111
112 return i;
113}
114
115template <class T, class Predicate>
116PX_INLINE void smallSort(T* elements, int32_t first, int32_t last, Predicate& compare)
117{
118 // selection sort - could reduce to fsel on 360 with floats.
119
120 for(int32_t i = first; i < last; i++)
121 {
122 int32_t m = i;
123 for(int32_t j = i + 1; j <= last; j++)
124 if(compare(elements[j], elements[m]))
125 m = j;
126
127 if(m != i)
128 swap(elements[m], elements[i]);
129 }
130}
131
132template <class Allocator>
133class Stack
134{
135 Allocator mAllocator;
136 uint32_t mSize, mCapacity;
137 int32_t* mMemory;
138 bool mRealloc;
139
140 public:
141 Stack(int32_t* memory, uint32_t capacity, const Allocator& inAllocator)
142 : mAllocator(inAllocator), mSize(0), mCapacity(capacity), mMemory(memory), mRealloc(false)
143 {
144 }
145 ~Stack()
146 {
147 if(mRealloc)
148 mAllocator.deallocate(mMemory);
149 }
150
151 void grow()
152 {
153 mCapacity *= 2;
154 int32_t* newMem =
155 reinterpret_cast<int32_t*>(mAllocator.allocate(sizeof(int32_t) * mCapacity, __FILE__, __LINE__));
156 intrinsics::memCopy(dest: newMem, src: mMemory, count: mSize * sizeof(int32_t));
157 if(mRealloc)
158 mAllocator.deallocate(mMemory);
159 mRealloc = true;
160 mMemory = newMem;
161 }
162
163 PX_INLINE void push(int32_t start, int32_t end)
164 {
165 if(mSize >= mCapacity - 1)
166 grow();
167 mMemory[mSize++] = start;
168 mMemory[mSize++] = end;
169 }
170
171 PX_INLINE void pop(int32_t& start, int32_t& end)
172 {
173 PX_ASSERT(!empty());
174 end = mMemory[--mSize];
175 start = mMemory[--mSize];
176 }
177
178 PX_INLINE bool empty()
179 {
180 return mSize == 0;
181 }
182};
183} // namespace internal
184
185} // namespace shdfnd
186} // namespace physx
187
188#endif // #ifndef PSFOUNDATION_PSSORTINTERNALS_H
189

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