Revision control
Copy as Markdown
// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
// SPDX-FileCopyrightText: Copyright (c) 2008-2026 NVIDIA CORPORATION & AFFILIATES. All rights reserved.
// SPDX-License-Identifier: Apache-2.0
#ifndef PX_SORT_INTERNALS_H
#define PX_SORT_INTERNALS_H
#include "foundation/PxAssert.h"
#include "foundation/PxMathIntrinsics.h"
#include "foundation/PxBasicTemplates.h"
#include "foundation/PxUserAllocated.h"
#if !PX_DOXYGEN
namespace physx
{
#endif
template <class T, class Predicate>
PX_INLINE void PxMedian3(T* elements, int32_t first, int32_t last, Predicate& compare)
{
/*
This creates sentinels because we know there is an element at the start minimum(or equal)
than the pivot and an element at the end greater(or equal) than the pivot. Plus the
median of 3 reduces the chance of degenerate behavour.
*/
int32_t mid = (first + last) / 2;
if(compare(elements[mid], elements[first]))
PxSwap(elements[first], elements[mid]);
if(compare(elements[last], elements[first]))
PxSwap(elements[first], elements[last]);
if(compare(elements[last], elements[mid]))
PxSwap(elements[mid], elements[last]);
// keep the pivot at last-1
PxSwap(elements[mid], elements[last - 1]);
}
template <class T, class Predicate>
PX_INLINE int32_t PxPartition(T* elements, int32_t first, int32_t last, Predicate& compare)
{
PxMedian3(elements, first, last, compare);
/*
WARNING: using the line:
T partValue = elements[last-1];
and changing the scan loops to:
while(comparator.greater(partValue, elements[++i]));
while(comparator.greater(elements[--j], partValue);
triggers a compiler optimizer bug on xenon where it stores a double to the stack for partValue
then loads it as a single...:-(
*/
int32_t i = first; // we know first is less than pivot(but i gets pre incremented)
int32_t j = last - 1; // pivot is in last-1 (but j gets pre decremented)
for(;;)
{
while(compare(elements[++i], elements[last - 1]))
;
while(compare(elements[last - 1], elements[--j]))
;
if(i >= j)
break;
PX_ASSERT(i <= last && j >= first);
PxSwap(elements[i], elements[j]);
}
// put the pivot in place
PX_ASSERT(i <= last && first <= (last - 1));
PxSwap(elements[i], elements[last - 1]);
return i;
}
template <class T, class Predicate>
PX_INLINE void PxSmallSort(T* elements, int32_t first, int32_t last, Predicate& compare)
{
// selection sort - could reduce to fsel on 360 with floats.
for(int32_t i = first; i < last; i++)
{
int32_t m = i;
for(int32_t j = i + 1; j <= last; j++)
if(compare(elements[j], elements[m]))
m = j;
if(m != i)
PxSwap(elements[m], elements[i]);
}
}
template <class PxAllocator>
class PxStack
{
PxAllocator mAllocator;
uint32_t mSize, mCapacity;
int32_t* mMemory;
bool mRealloc;
public:
PxStack(int32_t* memory, uint32_t capacity, const PxAllocator& inAllocator)
: mAllocator(inAllocator), mSize(0), mCapacity(capacity), mMemory(memory), mRealloc(false)
{
}
~PxStack()
{
if(mRealloc)
mAllocator.deallocate(mMemory);
}
void grow()
{
mCapacity *= 2;
int32_t* newMem =
reinterpret_cast<int32_t*>(mAllocator.allocate(sizeof(int32_t) * mCapacity, PX_FL));
intrinsics::memCopy(newMem, mMemory, mSize * sizeof(int32_t));
if(mRealloc)
mAllocator.deallocate(mMemory);
mRealloc = true;
mMemory = newMem;
}
PX_INLINE void push(int32_t start, int32_t end)
{
if(mSize >= mCapacity - 1)
grow();
mMemory[mSize++] = start;
mMemory[mSize++] = end;
}
PX_INLINE void pop(int32_t& start, int32_t& end)
{
PX_ASSERT(!empty());
end = mMemory[--mSize];
start = mMemory[--mSize];
}
PX_INLINE bool empty()
{
return mSize == 0;
}
};
#if !PX_DOXYGEN
} // namespace physx
#endif
#endif